Little Schemer: write function that only supports lists of length ≤ 2

Question

In the book The little schemer, we find this function that only supports lists with length smaller than or equal to 1:

 (((lambda (mk-length)                                  ; A.
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l ) 0)
              (else (add1 ((mk-length  eternity ) (cdr l))))))))
 '(1))

I want to study step by step, and want to write the similar function that supports only lists of length smaller than or equal to 2.

Please, don't answer this question by offering code like:

(((lambda (mk-length)                                   ; B.
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l) 0 )
              (else (add1((mk-length mk-length) (cdr l))))))))
 '(a b c d))

because this function supports any length.

And I already know how to write function like this:

(((lambda (mk-length)                                   ; C.
      (mk-length
          (mk-length (mk-length eternity))))
  (lambda (length)
      (lambda (l)
          (cond
              ((null? l) 0)
              (else (add1 (length (cdr l))))))))
 '(1 2)) ;;

to achieve my goal. But this code is more than one step away from the first snippet.

Maybe, I should not change:

(lambda (mk-length)                                     ; D.
      (mk-length mk-length)

Penelopa

What exactly is the question? Also, you might find an answer in the answer (or linked questions) to: Little Schemer: length0 and mk-length. I won't flag as duplicate yet, because I'm not sure exactly what you're asking here. – Aristaeus

I mean do the same thing as the 3th code I paste here. But should come from the 1th code's idea. which mean don't change 4th code in the 1th code. – Penelopa

Can you provide any insight as to why you're looking for this. It's actually a non-trivial problem, because the point of this type of recursive exercise is that since the list is a recursive data structure, you need to handle just two cases: the empty list, and the non-empty list. The implementation for the <=1 case handles just the first case (the empty list). You handle the =1 case by handling the non-empty case, but that lets you handle the =2, =3, etc., cases too, since they're handled in the same way as the =1 case. – Aristaeus

2th code just change (mk-length eternity ) to (mk-length mk-length) ,can achieve the any length. It is hard to think, so I want to implement a just <=2 version. on 1th code's base – Penelopa

this is a duplicate of this question but the answer there gives length≤∞, not length≤2. – Twomey

@Penelopa great question! it is important (in maths) to go carefully, being clear about each small step in the derivation (and the next step is here). – Twomey

Answer 1

TL;DR: (mk-length A) (inside the cond form) calculates the length function that works for lists of length 0 and will use (A A) to calculate the length function that will be used to work on the tail (i.e. the result of (cdr ...)) of the argument list.

---

Your first code snippet (;A.) works for lists of length 0 and 1 only. To make it work for 2 also, replacing

                               (mk-length eternity)               ; length≤1

with

                               (mk-length   ; (2)                 ; length≤2
                                  (lambda (x) (mk-length eternity)))

works.

(NB: (mk-length eternity) itself calculates length≤0, but the overall function becomes length≤1; this is what all the further length≤i comments refer to.)

Looking closely at

     (((lambda (mk-length)
          (mk-length mk-length))            
      (lambda (mk-length)                   ; (1)
          (lambda (l)                       
              (cond
                  ((null? l ) 0)
                  (else (add1 ((mk-length   ; (2)                 ; length≤2
                                  (lambda (x) (mk-length eternity)) )
                               (cdr l))))))))
     '(1 2))

we can see that the result of (mk-length ...) at ;(2) is used to process (cdr l), while the argument to mk-length at ;(2) will replace mk-length in that call when processing the (cddr l).

If (mk-length eternity) is used (as in your first code), (cdr l) gets processed OK but ((eternity eternity) (cddr l)) naturally fails.

If (mk-length (lambda (x) (mk-length eternity))) is used, (cdr l) gets processed OK and then ((lambda (x) (mk-length eternity)) (lambda (x) (mk-length eternity))) = (mk-length eternity) is used to process (cddr l) which is also OK (so, length 2 is handled correctly), and then ((eternity eternity) (cdddr l)) naturally fails (for lengths 3 and up).

Thus to process the lists of up to three elements,

                              ((mk-length   ; (2)                 ; length≤3
                                  (lambda (x) (mk-length 
                                                (lambda (x) (mk-length eternity)))) )

can be used:

    (define (eternity x) (- 1))    ; to get an error instead of looping

    (((lambda (mk-length)
          (mk-length mk-length))
      (lambda (mk-length)
          (lambda (l)
              (cond
                  ((null? l ) 0)
                  (else (add1 ((mk-length   ; (2)                 ; length≤3
                                  (lambda (x) (mk-length
                                               (lambda (x) (mk-length eternity)))) )
                               (cdr l))))))))

      '(1 2 3))        ; => 3

    ; ...........
    ; '(1 2 3 4))      ; => **error**

As you correctly surmised, this is the interim step on the way to using

                     (mk-length (lambda (x) (mk-length x)))   ; (2)       ; length≤∞

which turns, on the processing of the next element of the list into

                     ((lambda (x) (mk-length x)) (lambda (x) (mk-length x)))
    =
                     (mk-length (lambda (x) (mk-length x)))

and thus works for every list, whatever its length is.

And by eta-conversion this is just (mk-length mk-length).

Twomey

This answer was worth looking at, for me, indeed. =) Thanks for the answer itself and for notifying me about it! – Gluttonous

@FilippW. you're welcome, and thanks for the impetus to do this (i.e. your answers and edits to this cluster of problems). Re: your edit, those weren't typos. I meant the initial l, so the call (... (cdr l)) in the second iteration, when this l is actually (cdr l) for the original l, is (.... (cddr l)). And it's (cdddr l) in the third. it's a little sloppy and confusing, but just using (cdr l) won't do either. I'll think of somehow clarifying this thing, later. thanks! – Twomey

Oh, my bad I didn't grasped it at once. Thanks for the explanation, though! – Gluttonous

Answer 2

Lists in Lisp (Scheme, Common Lisp, etc.) are built out of cons cells and a special (the empty list). That, whenever you have something that is a list, it is either:

• The empty list ()
• A cons cell (also called a pair) where the car of the pair is the first element of the list and the cdr of the pair is the rest of the list.

Because there are two types of lists, recursive algorithms on lists usually answer just two questions:

• What is the result for the empty list?
• What is the result for rest of the list and how is that turned into the result for the whole list?

For length, this means:

• The length of the empty list is 0.
• When the length of the rest of the list is n, the length of the whole list is n + 1.

The type of solution presented in The Little Schemer first develops a solution that answers the first case, which means that it works for lists of length ≤0. As soon as you have a solution that handles both cases (correctly), you have a solution that works for lists of any length. There's no real incremental solution that would extend the function to work for lists of length ≤2.

You could, I suppose, do something like:

 (((lambda (mk-length)
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l ) 0)
              (else 1)))))

That would work for lists of length 0 and lists of length 1, and it would be incorrect for all other lists, but it would return 1 for all other lists. Unless you change the structure of the recursion, I think that's really the best you can do. If you're willing to change the structure of the recursion, you could do:

 (((lambda (mk-length)
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l) 0)
              ((null? (cdr l)) 1)
              (else (add1 ((mk-length  eternity ) (cdr l))))))))

but you really shouldn't take this approach, because now you're processing lists in three different cases instead of two, which is (almost) never what you want to do.

A translation to Python

Can this thinking rewrite by python or something process language? It is still hard to image a auto created fun in recurse.

The same principle works in Python, or any language that supports higher-order functions. It's more idiomatic in Python to locally define the function and then call it, rather than calling a lambda expression directly, so this may be more readable for you:

def length(l):
    def driver(recurse):
        "Returns the result of calling `recurse` with itself."
        return recurse(recurse);
    def zeroForEmptyListOrElseOnePlusRecurse(recurse):
        """Returns a function that returns 0 if its input is the
        empty list, or else returns one plus whatever calling 
        `recurse(recurse)` with the tail of the list returns."""
        def length(l):
            """Returns 0 if l is the empty list, and one plus
            the results of `(recurse(recurse))(l)` otherwise."""
            if l == []:
                return 0;
            else:
                _, *rest = l
                return 1+(recurse(recurse))(rest)
        return length
    return (driver(zeroForEmptyListOrElseOnePlusRecurse))(l)

print(length([1,2,3])) # 3
print(length([1,2]))   # 2
print(length([1]))     # 1
print(length([]))      # 0

Aristaeus

I think you already answer my question! Can you explain more about how using your answer to get the code (mk-length mk-length) to work for any lenght of list? Substituting the mk-length to first lambda is easy to think, however it is hard to think re-substituting inside again. For me it is not nature to think about it. However it is easy for somebody else. – Penelopa

I'm not sure what you're asking. If you replace (mk-length eternity) with (mk-length mk-length) in my answer, it should work. But you'll still have a redundant clause in your cond. – Aristaeus

May be i am asking how mk-length in (add1 ((mk-lenght mk-lenght) (cdr l)) works? Can this thinking rewrite by python or something process language? It is still hard to image a auto created fun in recurse. – Penelopa

@Penelopa I've added a Python translation. – Aristaeus