List length in scheme

Question

Hi I am trying to write a program where given a list of lists check to see if they are equal in size and return #t if they are.

So for example if i were to write (list-counter? '((1 2 3) (4 5 6) (7 8 9))) the program would return #t, and (list-counter? '((1 2 3) (4 5 6) (7 8))) would return #f.

SO far this is what I have done:

 (define list-counter?
  (lambda (x)
    (if (list? x)
        (if (list?(car x))
      (let (l (length (car x))))
        (if (equal? l (length(car x))))
        (list-counter?(cdr x))
 ) ) ) ) ) 

I think where I am going wrong is after I set the length of l to the length of the first list. Any help would be appreciated.

Solution 1

There are several ways to solve this problem. For instance, by hand and going step-by-step:

(define (all-lengths lists)
  (if (null? lists)
      '()
      (cons (length (car lists))
            (all-lengths (cdr lists)))))

(define (all-equal? head lengths)
  (if (null? lengths)
      true
      (and (= head (car lengths))
           (all-equal? head (cdr lengths)))))

(define (list-counter? lists)
  (let ((lengths (all-lengths lists)))
    (all-equal? (car lengths) (cdr lengths))))

Let me explain the above procedures. I'm dividing the problem in two steps, first create a new list with the lengths of each sublist - that's what all-lengths does. Then, compare the first element in a list with the rest of the elements, and see if they're all equal - that's what all-equal? does. Finally, list-counter? wraps it all together, calling both of the previous procedures with the right parameters.

Or even simpler (and shorter), by using list procedures (higher-order procedures):

(define (list-counter? lists)
  (apply = (map length lists)))

For understanding the second solution, observe that all-lengths and all-equal? represent special cases of more general procedures. When we need to create a new list with the result of applying a procedure to each of the elements of another list, we use map. And when we need to apply a procedure (= in this case) to all of the elements of a list at the same time, we use apply. And that's exactly what the second version of list-counter? is doing.

Solution 2

You could write an all-equal? function like so:

(define (all-equal? list)
  ;; (all-equal? '()) -> #t
  ;; (all-equal? '(35)) -> #t
  ;; (all-equal? '(2 3 2)) -> #f
  (if (or (null? list) (null? (cdr list)))
      #t
      (reduce equal? list)
  ))

then do:

(all-equal? (map length listOfLists))

---

Alternatively you can do:

(define (lists-same-size? list-of-lists)
    (if (== (length listOfLists) 0)
      #t
      (let*
        (( firstLength
             (length (car listOfLists)) )
         ( length-equal-to-first?
             (lambda (x) (== (length x) firstLength)) )
        )
        (reduce and #t (map length-equal-to-first? listOfLists))
      )
    )))

What this says is: if the list length is 0, our statement is vacuously true, otherwise we capture the first element of the list's length (in the 'else' part of the if-clause), put it in the closure defined by let's syntactic sugar (actually a lambda), and use that to define an length-equal-to-first? function.

Unfortunately reduce is not lazy. What we'd really like is to avoid calculating lengths of lists if we find that just one is not equal. Thus to be more efficient we could do:

    ...
       (let*
         ...   
         ( all-match?               ;; lazy
             (lambda (pred list)
               (if (null? list) 
                   #t 
                   (and (pred (first list)) (all-match? (cdr list)))
                      ;;^^^^^^^^^^^^^^^^^^^ stops recursion if this is false
             )) )
        )
        (all-match? length-equal-to-first? listOfLists)
      )
    )))

Note that all-match? is already effectively defined for you with MIT scheme's (list-search-positive list pred) or (for-all? list pred), or in Racket as andmap.

---

Why does it take so long to write?

You are forced to write a base-case because your reduction has no canonical element since it relies on the first element, and list manipulation in most languages is not very powerful. You'd even have the same issue in other languages like Python. In case this helps:

second method:

if len(listOfLists)==0:
    return True
else:
    firstLength = len(listOfLists[0])
    return all(len(x)==firstLength for x in listOfLists)

However the first method is much simpler to write in any language, because it skirts this issue by ignoring the base-cases.

first method:

if len(listOfLists)<2:
    return True
else:
    return reduce(lambda a,b: a==b, listOfLists)