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.

Advertisements

Pages: 1 2

13 Responses to “Length”

  1. echo said

    language like python tracks the length of list, so the get the length of list is constant time.

  2. chaw said

    Here is a solution is standard Scheme that is easy to read as a
    logical expression.

    (import (scheme base)
            (scheme write))
    
    (define (shorter? lst1 lst2)
      (and (pair? lst2)
           (or (null? lst1)
               (shorter? (cdr lst1)
                         (cdr lst2)))))
    
    (display (map shorter?
                  '(() ()  (1) (1)   (1 2) (1 2))
                  '(() (1) ()  (1 2) (1)   (1 2))))
    (newline)
    
    (#f #t #f #t #f #f)
    

  3. Kevin said

    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))))))

  4. Daniel said

    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.

    (defun len (lst)
      (labels ((aux (lst n)
                 (if (null lst)
                     n
                     (aux (cdr lst) (1+ n)))))
        (aux lst 0)))
    
    (defun shortest (lst1 lst2)
      (cond ((and (null lst1) (null lst2)) 0)
            ((null lst1) 1)
            ((null lst2) 2)
            (t (shortest (cdr lst1) (cdr lst2)))))
    

    Example:

    CL-USER> (len '(a b c d e f g))
    7
    CL-USER> (shortest '(a b c d e f g) '(h i j k l m n o p))
    1
    CL-USER>
    
  5. Daniel said

    Here’s a solution in Haskell.

    len lst = aux lst 0 where
      aux [] n = n
      aux (x:xs) n = aux xs (n + 1)
    
    shortest [] [] = 0
    shortest [] (y:ys) = 1
    shortest (x:xs) [] = 2
    shortest (x:xs) (y:ys) = shortest xs ys
    

    Example:

    *Main> len ['a','b','c','d','e','f','g']
    7
    *Main> shortest "abcdefg" "hijklmnop"
    1
    *Main> shortest [1,2,3] []
    2
    
  6. Steve said

    Klong version

            ln::{ln2::{:[x~[]; y; .f(1_x; y+1)]}; ln2(x; 0)}
    :monad
            shorter::{[l2]; l2::y; :[ln(x)=0; :[ln(y)=0; "Equal"; "1st"]; :[ln(y)=0; "2nd"; ls(1_x; 1_y)]]}
    :dyad
    

    shorter([]; [])
    “Equal”
    shorter([]; [1])
    “1st”
    shorter([1]; [])
    “2nd”
    shorter([1 2]; [3])
    “2nd”
    shorter([1 2]; [1 2 3])
    “1st”
    shorter([1]; [1])
    “Equal”

  7. 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:

            shorter([]; [])
    "Equal"
            shorter([]; [1])
    "First"
            shorter([1]; [])
    "2nd"
            shorter([1]; [2 3])
    "First"
            shorter([2 3]; [1])
    "2nd"
            shorter([2 3]; [1 2])
    "Equal"
    
  8. Globules said

    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).

    -- Return true if and only if the first list is strictly shorter than the second
    -- list.  The result is undefined if both lists are infinite.
    shorterThan  :: [a] -> [a] -> Bool
    shorterThan []     (_:_)  = True
    shorterThan _      []     = False
    shorterThan (_:xs) (_:ys) = xs `shorterThan` ys
    
    main :: IO ()
    main = do
      print $ []      `shorterThan` []
      print $ [1..5]  `shorterThan` [1..5]
      print $ [1..5]  `shorterThan` [1..10]
      print $ [1..10] `shorterThan` [1..5]
      print $ [1..10] `shorterThan` [1..]
      print $ [1..]   `shorterThan` [1..5]
    
    $ ./shorter
    False
    False
    True
    False
    True
    False
    
  9. Jared said

    A good return type for the Haskell solutions re: length comparison is Ordering, which allows you to return LT, GT, or EQ values.

  10. r. clayton said

    A solution in Racket.

  11. Tom Parrish said

    An answer in C#

    void Main()
    {
    	var empty = new int[0];
    	var five = new[] { 1, 2, 3, 4, 5 };
    	var four = new[] { 1, 2, 3, 4 };
    	
    	IsShorterThan(five,four).Dump();
    	IsShorterThan(four, five).Dump();
    	IsShorterThan(four, four).Dump();
    	IsShorterThan(empty, four).Dump();
    	IsShorterThan(four, empty).Dump();
    }
    
    bool IsShorterThan(IEnumerable self, IEnumerable other)
    {
    	var selfHead = self.Cast<object>().FirstOrDefault();
    	var otherHead = other.Cast<object>().FirstOrDefault();
    	if(selfHead == null || otherHead == null)
    	{
    		return selfHead == null && otherHead != null;
    	}
    	
    	return IsShorterThan(self.Cast<object>().Skip(1),other.Cast<object>().Skip(1));
    }
    
  12. Daniel said

    @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#.

    using System;
    using System.Text;
    
    namespace cs {
        class Node<T> {
            public T value;
            public Node<T> next;
            
            override public string ToString() {
                StringBuilder sb = new StringBuilder();
                sb.Append("[");
                Node<T> node = this;
                while (node != null) {
                    sb.Append(node.value);
                    node = node.next;
                    if (node != null) sb.Append(", ");
                }
                sb.Append("]");
                return sb.ToString();
            }
        }
    
        class Program {
            static int Length<T>(Node<T> list) {
                if (list == null) {
                    return 0;
                } else {
                    return 1 + Length(list.next);
                }
            }
    
            // Returns -1 if list1 shorter than list2,
            //          0 if list1 and list2 are the same length,
            //      or  1 if list1 longer than list2.
            static int Compare<T>(
                    Node<T> list1, Node<T> list2) {
                if (list1 == null && list2 == null) {
                    return 0;
                } else if (list1 == null) {
                    return -1;
                } else if (list2 == null) {
                    return 1;
                } else {
                    return Compare(list1.next, list2.next);
                }
            }
    
            static void Main(string[] args) {
                Node<int> list1 = null;
                for (int i = 7; i > 0; --i) {
                    Node<int> next = list1;
                    list1 = new Node<int>();
                    list1.value = i;
                    list1.next = next;
                }
                Node<int> list2 = null;
                for (int i = 9; i > 0; --i) {
                    Node<int> next = list2;
                    list2 = new Node<int>();
                    list2.value = i;
                    list2.next = next;
                }
                Console.WriteLine("list1: " + list1);
                Console.WriteLine("list2: " + list2);
                Console.WriteLine("Length(list1): " + Length(list1));
                Console.WriteLine("Length(list2): " + Length(list2));
                Console.WriteLine("Compare(list1,list2): " + Compare(list1, list2));
            }
        }
    }
    

    Output:

    list1: [1, 2, 3, 4, 5, 6, 7]
    list2: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    Length(list1): 7
    Length(list2): 9
    Compare(list1,list2): -1
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: