fib, tail-call-fib, lazy-fib

一般的な fib, 末尾再帰 fib, 遅延評価 fib ということで。（なんか途中に nlet が紛れ込んでますが）

• Gauche ユーザリファレンス: 11.53 util.stream - ストリームライブラリ
• ストリーム - karetta.jp

遅延評価については、Gauche には util.stream というのがあるようです。馴染みがないです。

	;; fib
	(define (fib n)
	(cond ((zero? n) 0)
	((= 1 n) 1)
	(else (+ (fib (- n 1))
	(fib (- n 2))))))
	(fib 10)
	;; 55
	(use srfi-1)
	(map fib (iota 10))
	;; (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377)
	;; tail call fib
	(define (fib n)
	(let loop ((cur 0)(next 1)(n n))
	(if (zero? n)
	cur
	(loop next (+ cur next)(- n 1)))))
	(fib 10)
	;; 55
	(map fib (iota 15))
	;; (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377)
	(define-syntax nlet
	(syntax-rules ()
	((_ tag ((var val) ...) body ...)
	(letrec ((tag (lambda (var ...)
	body ...)))
	(tag val ...)))))
	(define (fib n)
	(macroexpand '(nlet loop ((cur 0)(next 1)(n n))
	(if (zero? n)
	cur
	(loop next (+ cur next)(- n 1))))))
	(fib 10)
	;; (#<identifier user#letrec>
	;; ((loop
	;; (#<identifier user#lambda> (cur next n)
	;; (if (zero? n)
	;; cur
	;; (loop next (+ cur next) (- n 1))))))
	;; (loop 0 1 n))
	;; lazy fib
	;; ストリーム - karetta.jp http://karetta.jp/book-node/gauche-hacks/014529
	;; Gauche ユーザリファレンス: 11.53 util.stream - ストリームライブラリ http://practical-scheme.net/gauche/man/gauche-refj_170.html
	(use util.stream)
	(define fib (stream-cons 0 (stream-cons 1 (stream-map + fib (stream-cdr fib)))))
	(stream->list (stream-take fib 10))
	;; (0 1 1 2 3 5 8 13 21 34)
	(stream-ref fib 10000)
	;; 336447648764317832666216120...
	(stream->list (stream-take-while (pa$ > 1000) fib))
	;; (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987)
	(define (fib)
	(letrec ((recur (lambda (a b)
	(let ((n (+ a b)))
	(stream-delay
	(stream-cons n (recur b n)))))))
	(stream-cons 0 (stream-cons 1 (recur 0 1)))))
	(stream->list (stream-take (fib) 10))
	;; (0 1 1 2 3 5 8 13 21 34)
	(stream-ref (fib) 10)
	;; 55
	(stream-ref (fib) 1000)
	;; 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
	(stream->list (stream-take (stream-filter odd? (fib)) 15))
	;; (1 1 3 5 13 21 55 89 233 377 987 1597 4181 6765 17711)

view raw fib.scm hosted with ❤ by GitHub