2010/04/01

TSS length, Y!, Y-bang

The Seasoned Shcemer P.119からまたもやlengthを使ったY Combinatorが出てきます。The Little Schemerで出てきたY Combinatorと違うのは、どうやら副作用を使うところのようです。名前にも「!(bangと読むらしい)」がついています。

ここ、ちょっとよくわかりませんでした。再読が必要かもしれません。取り合えずコードは書いてみました。
;; length
(define add1
(lambda (n)
(+ n 1)))
(define length
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(define length
(lambda (l)
0))
(set! length
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(define length
(let ((h (lambda (l) 0)))
(set! h
(lambda (l)
(cond
((null? l) 0)
(else (add1 (h (cdr l)))))))
h))
(length '(1 2 3))
; -> 3
; ?
(define length
(let ((h #f))
(set! h (lambda (l)
(if (null? l)
0
(add1 (h (cdr l))))))))
(length '(1 2 3 4 5))
; -> 5
(define L
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l))))))))
(define length
(let ((h (lambda (l)
0)))
(set! h
(L (lambda (arg)
(h arg))))))
;; Y!
(define Y!
(lambda (L)
(let ((h (lambda (l)
(quote ()))))
(set! h
(L (lambda (arg)
(h arg))))
h)))
(define Y-bang
(lambda (f)
(letrec
((h (f (lambda (arg)
(h arg)))))
h)))
((Y! L) '(1 2 3))
; -> 3


The Seasoned Schemer

0 件のコメント:

コメントを投稿