vallog: pluggable Y Combinator

2010/05/14

pluggable と付いてますが、メモ化された Y Combinator と違って、ただの素の Y Combinator です。

どちらかというと、メモ化関数を Y Combinator に対応させるということで良いと思います。コードはこちら。

	;; pluggable Y Combinator

	(define Y
	(lambda (c)
	((lambda (f)
	(f f))
	(lambda (g)
	(c (lambda x
	(apply (g g) x)))))))

	(define (make-memoize)
	(let ((cache (make-hash-table 'equal?)))
	(lambda (f)
	(lambda args
	(let ((val (hash-table-get cache args #f)))
	(or val
	(let ((ret (apply f args)))
	(hash-table-put! cache args ret)
	ret)))))))

	(time ((Y (compose (make-memoize) fib)) 35))
	;(time ((Y (compose (make-memoize) fib)) 35))
	; real 0.000
	; user 0.000
	; sys 0.000
	14930352

	(time ((Y (compose (make-memoize) fib)) 2000))
	;(time ((Y (compose (make-memoize) fib)) 2000))
	; real 0.250
	; user 0.219
	; sys 0.000
	6835702259575806647045396549170580107055408029365524565407553367798082454408054014954534318953113802726603726769523447478238192192714526677939943338306101405105414819705664090901813637296453767095528104868264704914433529355579148731044685634135487735897954629842516947101494253575869699893400976539545740214819819151952085089538422954565146720383752121972115725761141759114990448978941370030912401573418221496592822626

view raw pluggable-y.scm hosted with ❤ by GitHub

参考にしたのは、昨日に引き続きこちら。これすごくおもしろいです。やばいです。

wrap は compose で良いですね。

gauche のコンビネータ。

vallog