Length function in " The Seasoned Schemer"

Question

I have been reading The Seasoned Schemer and i came across this definition of the length function

(define length
  (let ((h (lambda (l) 0)))
    (set! h (L (lambda (arg) (h arg))))
    h))

Later they say :

What is the value of (L (lambda (arg) (h arg)))? It is the function

(lambda (l)
  (cond ((null? l) 0)
     (else (add1 ((lambda (arg) (h arg)) (cdr l))))))

I don't think I comprehend this fully. I guess we are supposed to define L ourselves as an excercise. I wrote a definition of L within the definition of length using letrec. Here is what I wrote:

(define length
  (let ((h (lambda (l) 0)))
    (letrec ((L
              (lambda (f)
                (letrec ((LR
                          (lambda (l)
                            (cond ((null? l) 0)
                                  (else
                                   (+ 1 (LR (cdr l))))))))
                  LR))))                  
    (set! h (L (lambda (arg) (h arg))))
    h)))

So, L takes a function as its argument and returns as value another function that takes a list as its argument and performs a recursion on a list. Am i correct or hopelessly wrong in my interpretation? Anyway the definition works

 (length (list 1 2 3 4))  => 4

Óscar López · Accepted Answer · 2012-06-15T01:26:11.933

In "The Seasoned Schemer" length is initially defined like this:

(define length
  (let ((h (lambda (l) 0)))
    (set! h (lambda (l)
              (if (null? l)
                  0
                  (add1 (h (cdr l))))))
    h))

Later on in the book, the previous result is generalized and length is redefined in terms of Y! (the applicative-order, imperative Y combinator) like this:

(define Y!
  (lambda (L)
    (let ((h (lambda (l) 0)))
      (set! h (L (lambda (arg) (h arg))))
      h)))

(define L
  (lambda (length)
    (lambda (l)
      (if (null? l)
          0
          (add1 (length (cdr l)))))))

(define length (Y! L))

The first definition of length shown in the question is just an intermediate step - with the L procedure exactly as defined above, you're not supposed to redefine it. The aim of this part of the chapter is to reach the second definition shown in my answer.

Length function in " The Seasoned Schemer"

1 Answers1