schemeseasoned-schemer

Length function in " The Seasoned Schemer"


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

Solution

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