notes of chapter 9 of "The little schemer"

lambda.ss

#lang scheme
;; notes about Y combinator and related.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; function never stop
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define eternity
  (lambda (x)
    (eternity x)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; when we have the 'define' keyword
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define length
  (lambda (x)
    (cond 
      ((null? x) 0)
      (else (+ 1 (length (cdr x)))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; what if we didn't have 'define'?
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; this is a function can determine the length of 
;; empty list, call it length_0
(lambda (l)
  (cond 
    ((null? l) 0)
    (else (+ 1 (eternity (cdr l))))))

;; example
;; ==> 0
((lambda (l)
  (cond 
    ((null? l) 0)
    (else (+ 1 (eternity (cdr l))))))
 (quote ()))

;; then we can make length_1, length_2, ... length_n

;; but we need to write an infinite function, right?

;; TBD , how we move to mk-length?

;; warm-up, mk-length to make length_0
((lambda (mk-length)
  (mk-length eternity))
 (lambda (length)
   (lambda (l)
   (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l))))))))

;; example
;; ==> 0
(((lambda (mk-length)
  (mk-length eternity))
 (lambda (length)
   (lambda (l)
   (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l))))))))
 (quote ()))

;; try length_1?
((lambda (mk-length)
   (mk-length
    (mk-length eternity)))
 (lambda (length)
   (lambda (l)
   (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l))))))))

;; example
;; ==> 0
(((lambda (mk-length)
   (mk-length
    (mk-length eternity)))
 (lambda (length)
   (lambda (l)
   (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l))))))))
 (quote ()))

;; another example
;; ==> 1
(((lambda (mk-length)
   (mk-length
    (mk-length eternity)))
 (lambda (length)
   (lambda (l)
   (cond
     ((null? l) 0)
     (else (+ 1 (length (cdr l))))))))
 (list 1))

;; well, it seems that we still need to write 
;; infinite patterns. 

;; can we do a little better?
;; notice this will apply mk-length once more.
;; issues: contraction violation
(((lambda (mk-length)
   (mk-length
    (mk-length mk-length)))
 (lambda (mk-length)
   (lambda (l)
   (cond
     ((null? l) 0)
     (else (+ 
            1 
            ((mk-length eternity) (cdr l))))))))
 (list 1))