2009/05/22

[The Little Schemer]Y Combinator(再)

WS0803 

Y Combinatorとは

 

全景

The Little Schemer」P.160 ~

;; Road to Y Combinator

(define inc
  (lambda (n)
    (+ n 1)))

 

;; normal length
(define length
  (lambda (l)
    (cond
     ((null? l) 0)
     (else (inc (length (cdr l)))))))

 

;; without "define"

 

;; empty-list-length
(lambda (l)
  (cond
   ((null? l) 0)))

 

;; execute with empty-list
((lambda (l)
   (cond
    ((null? l) 0))) '())
;; => 0

 

;; execute with non-empty-list
((lambda (l)
   (cond
    ((null? l) 0))) '(1 2 3))
;; => #<undef>

 

;; 1-element-list-length
(lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))(cdr l))))))

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))(cdr l)))))) '())
;; => 0

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))(cdr l)))))) '(a))
;; => 1

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else
    (inc ((lambda (l)
            (cond
             ((null? l) 0)))
          (cdr l))))))
  '(1 2))
;; => *** ERROR: operation + is not defined between 1 and #<undef>

 

;;2-elements-list-length
(lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))

 

;; execute 2-elements-list-length
((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'())
;; => 0

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'(a))
;; => 1

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'(a b))
;; => 2

 

((lambda (l)
  (cond
   ((null? l) 0)
   (else (inc
          ((lambda (l)
             (cond
              ((null? l) 0)
              (else (inc
                     ((lambda (l)
                        (cond
                         ((null? l) 0)))
                      (cdr l))))))
           (cdr l))))))
'(1 2 3))
;; => *** ERROR: operation + is not defined between 1 and #<undef>

 

;;((lambda (length)
;;   (lambda (l)
;;     (cond
;;      ((null? l) 0)
;;      (else (inc (length (cdr l)))))))
;; 'eternity)

 

;; eternity style empty-list-length

(((lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc (f (cdr l)))))))
'eternity) '())
;; => 0

 

;; eternity style 1-element-list-length
(((lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l)))))))
  ((lambda (f)
     (lambda (l)
       (cond
        ((null? l) 0)
        (else (inc (f (cdr l)))))))
   'eternity))
'(1))
;; => 1

 

;; eternity style 2-elements-list-length
(((lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l)))))))
  ((lambda (f)
     (lambda (l)
       (cond
        ((null? l) 0)
        (else (inc (f (cdr l)))))))
   ((lambda (f)
      (lambda (l)
        (cond
         ((null? l) 0)
         (else (inc (f (cdr l)))))))
    'eternity)))
'(1 2))
;; => 2

 

;; without repetitions
((lambda (make-length)
   (make-length 'eternity))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc (f (cdr l))))))))

 

;; execute without-repetitions-eternity-stryle-length
(((lambda (make-length)
    (make-length 'eternity))
  (lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l))))))))
'())
;; => 0

 

(((lambda (make-length)
    (make-length
     (make-length 'eternity)))
  (lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l))))))))
'(1))
;; => 1

 

(((lambda (make-length)
    (make-length
     (make-length
      (make-length 'eternity))))
  (lambda (f)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (f (cdr l))))))))
'(1 2))
;; => 2

 

;;What is recursion like?
;;It is like an infinite tower of applications of make-length to an arbitrary function.

 

;;Do we readly need an infinite tower?
;;Not really of course. Everytime we use length we only need a finite number. but we never know how many.

 

;; meke-length to make-length
((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))

 

;; execute make-length to make-length
(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'())
;; => 0

 

(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'(1))
;; => 1

 

(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'(1 2))
;; => 2

 

(((lambda (make-length)
   (make-length make-length))
(lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc ((f f) (cdr l))))))))
'(1 2 3 4 5))
;; => 5

 

;; without (f f)
(((lambda (make-length)
   (make-length make-length))
  (lambda (f)
   (lambda (l)
     (cond
      ((null? l) 0)
      (else (inc
             ((lambda (x)
                ((f f) x))
              (cdr l))))))))
'(1 2 3 4 5))
;; => 5

 

;; move out (f f)
((lambda (f)
   (f f))
  (lambda (f)
    ((lambda (g)
       (lambda (l)
         (cond
          ((null? l) 0)
          (else
           (inc (g (cdr l)))))))
     (lambda (x)
       ((f f) x)))))

 

;; execute move-out-(f f)
(((lambda (f)
    (f f))
  (lambda (f)
    ((lambda (g)
       (lambda (l)
         (cond
          ((null? l) 0)
          (else
           (inc (g (cdr l)))))))
     (lambda (x)
       ((f f) x)))))
'(1 2 3 4 5))
;; => 5

 

;; extract function's body
;;(lambda (g)
;;    (lambda (l)
;;      (cond
;;       ((null? l) 0)
;;       (else (inc (g (cdr l)))))))
(((lambda (le)
    ((lambda (f)
       (f f))
     (lambda (f)
       (le (lambda (x)
             ((f f) x))))))
  (lambda (g)
    (lambda (l)
      (cond
       ((null? l) 0)
       (else (inc (g (cdr l))))))))
'(1 2 3 4 5))
;; => 5

 

;; named y
(define y
  (lambda (le)
    ((lambda (f)
       (f f))
     (lambda (f)
       (le (lambda (x)
             ((f f) x)))))))

 

;; execute y with length
((y (lambda (g)
      (lambda (l)
        (cond
         ((null? l) 0)
         (else (inc (g (cdr l))))))))
'(1 2 3 4 5))

 

参考

 

The Little Schemer

The Little Schemer

posted with amazlet at 09.03.30

Daniel P. Friedman Matthias Felleisen
Mit Pr
売り上げランキング: 16078

おすすめ度の平均: 5.0

5 小さなScheme処理系で学ぶ数学基礎理論
5 Schemeが好きになります
5 英語であるのが苦痛にならない楽しさ
5 面白いスタイル

Amazon.co.jp で詳細を見る

0 件のコメント:

コメントを投稿