## Length

### June 29, 2018

Recently, at a beginning programmer’s forum, I saw a user asking about the function `length` that finds the length of a list. He gave a simple version of `length`, then used it find the lengths of two lists and determine which was shorter. He correctly realized that calculating the full lengths of both lists is inefficient if one list is much longer than the other, and he asked if there was a way to run through the lists simultaneously, stopping as soon as it is known which list is shorter.

Your task is to write `length` and a function to determine which of two lists is shorter; your solution must use recursion. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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

```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)}
shorter::{[l2]; l2::y; :[ln(x)=0; :[ln(y)=0; "Equal"; "1st"]; :[ln(y)=0; "2nd"; ls(1_x; 1_y)]]}
```

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

7. Klong version (corrected)

ln::{ln2::{:[x~[]; y; .f(1_x; y+1)]}; ln2(x; 0)}
shorter::{:[0=ln(x)+ln(y); "Equal" :|ln(y)=0; "2nd" :| ln(x)=0; "First"; shorter(1_x; 1_y)]}

Example:

```        shorter([]; [])
"Equal"
shorter([]; )
"First"
shorter(; [])
"2nd"
shorter(; [2 3])
"First"
shorter([2 3]; )
"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

```void Main()
{
var empty = new int;
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)
{
{
}

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