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