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