Geek asks and answers

Length function in "The Seasoned Schemer"

I read The Seasoned Schemer and I came across this definition of a length function

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

They later say:

What is the meaning of (L (lambda (arg) (h arg)))? This is a function.

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

I do not think I fully understand this. I think we should define L ourselves as an exercise. I wrote a definition of L in 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 another function as the value, which takes the list as its argument and performs recursion on the list. Am I right or hopelessly mistaken in my interpretation? In any case, the definition works

 (length (list 1 2 3 4))  => 4
+5
source share
1

"The Seasoned Schemer" length :

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

length Y! ( , Y combinator) :

(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))

length, , - L , , . - , .

+3

More articles:


All Articles