Y Combinatorで再帰

The Little SchemerでY Combinatorの部分を読んだので、忘れないうちに復習。階乗とか作ってみた。

The Little SchemerのY Combinator は引数が1つの手続きしか作れないから、applyを使って任意個の引数を取る手続きを生成できるように、ちょっと拡張した。

調子にのって、初めての人のためのLispに出てきた完全なコピーのappendを Y Combinator で書いてみた。Y Combinatorを知らない人にとっては謎の多いコードかもしれない。

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda xs (apply (f f) xs)))))))

(define fact
  (Y (lambda (f)
       (lambda (n)
	 (cond
	  ((>= 1 n) 1)
	  (else (* n (f (- n 1)))))))))

(define copy
  (Y (lambda (f-copy)
       (lambda (ls)
	 (cond 
	  ((null? ls) '())
	  (else
	   (cons (car ls) (f-copy (cdr ls)))))))))

(define append
  (lambda (ls1 ls2)
    ((Y (lambda (f-append)
	  (lambda (ls1 ls2)
	    (cond ((null? ls1) ls2)
		  (else 
		   (cons (car ls1) (f-append (cdr ls1) ls2)))))))
     ls1 (copy ls2))))