Length
June 29, 2018
Here is the length
function the beginning programmer wrote:
(define (len xs) (if (null? xs) 0 (+ 1 (len (cdr xs))))) > (len '(a b c d e f g)) 7
That works fine, but is non-tail-recursive, so it can blow out the stack if the list is too long. Here is a tail-recursive version of the function that requires only constant space to operate:
(define (len-aux xs n) (if (null? xs) n (len-aux (cdr xs) (+ n 1)))) (define (len xs) (len-aux xs 0)) > (len '(a b c d e f g)) 7
We can abbreviate that function using a named-let
:
(define (len xs) (let loop ((xs xs) (n 0)) (if (null? xs) n (loop (cdr xs) (+ n 1))))) > (len '(a b c d e f g)) 7
The beginning programmer was correct that it is not necessary to compute the length of both lists to determine which is shorter. Instead, it is possible for the function to stop as soon as the shorter list is identified. Here is our version of that function:
(define (shorter? xs ys) (cond ((null? ys) #f) ((null? xs) #t) (else (shorter? (cdr xs) (cdr ys))))) > (shorter? '(a b c d e f g) '(h i j k l m n o p)) #t
The first cond
clause returns #f
if the second list is null while the first is not, the second cond
clause returns #t
if the first list is null whle the second is not, and the else
clause returns the recursive result of calling the function when both input lists are shortened by one item.
You can run the program at https://ideone.com/axcmH3.
language like python tracks the length of list, so the get the length of list is constant time.
Here is a solution is standard Scheme that is easy to read as a
logical expression.
Here’s a solution in racket. The output is:
0 ==> The 1st list is shortest
1 ==> The 2nd list is shortest
2 ==> Both lists are of equal length
(define (shortest-list ls1 ls2)
(let check ((x ls1) (y ls2) (len 0))
(cond
((and (empty? x) (empty? y)) 2)
((empty? x) 0)
((empty? y) 1)
(else (check (cdr x) (cdr y) (add1 len))))))
@echo, lists in Python are arrays, not linked-lists.
https://docs.python.org/3/faq/design.html#how-are-lists-implemented
Here’s a solution in Common Lisp. The shortest function returns 0 if both lists are the same size, 1 if the first list is shortest, and 2 if the second list is shortest.
Example:
Here’s a solution in Haskell.
Example:
Klong version
shorter([]; [])
“Equal”
shorter([]; [1])
“1st”
shorter([1]; [])
“2nd”
shorter([1 2]; [3])
“2nd”
shorter([1 2]; [1 2 3])
“1st”
shorter([1]; [1])
“Equal”
Klong version (corrected)
ln::{ln2::{:[x~[]; y; .f(1_x; y+1)]}; ln2(x; 0)}
:monad
shorter::{:[0=ln(x)+ln(y); "Equal" :|ln(y)=0; "2nd" :| ln(x)=0; "First"; shorter(1_x; 1_y)]}
:dyad
Example:
Another Haskell solution, which is similar to Daniel’s. The main difference is that I’ve golfed it slightly to eliminate one case (at the expense of some symmetry in the arguments).
A good return type for the Haskell solutions re: length comparison is
Ordering
, which allows you to return LT, GT, or EQ values.A solution in Racket.
An answer in C#
@TomParish, it looks like your solution is simulating a linked list with an array.
Here’s a C# solution that uses a linked list directly. Unlike my earlier solutions, there is no attempt to make the length function tail recursive since this won’t be optimized in C#.
Output: