Last active
December 11, 2015 23:58
-
-
Save ehaliewicz/4680328 to your computer and use it in GitHub Desktop.
Lazy infinite fibonacci stream
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(define fib | |
(lambda (n) | |
(((lambda (f) | |
((lambda (x) (x x)) | |
(lambda (y) (f (lambda (a b) | |
((y y) a b)))))) | |
(lambda (f) | |
(lambda (s n) | |
(if (= n 0) | |
((lambda (c) (c (lambda (a b) a))) s) | |
(f (((lambda (c) (c (lambda (a b) b))) s)) (- n 1)))))) | |
(((lambda (f) | |
((lambda (x) (x x)) | |
(lambda (y) | |
(f (lambda (a b) | |
((y y) a b)))))) | |
(lambda (f) | |
(lambda (a b) | |
((lambda (hd tl) (lambda (x) (x hd tl))) a (lambda () (f b (+ a b))))))) 0 1) | |
n))) | |
;;; (fib 0) => 0 | |
;;; (fib 1) => 1 | |
;;; (fib 2) => 1 | |
;;; (fib 3) => 2 | |
;;; (fib 4) => 3 | |
;;; (fib 123) => 347746739180370201052517440604335969788684934927843710657352239304121649686845967975636459392453053377493026875020744760145842401792378749321113719919618588095724485583919541019961884523908359133457357334538791778480910430756107407761555218113998374287548487 | |
;;; Addendum | |
;;; I just got this to compile in my Scheme->JS compiler so I thought I'd add the code here. | |
;;; It can't hurt this gist's readability any further | |
var fib = function(n){ | |
return function(f){ | |
return function(x){ | |
return x(x) | |
}(function(y){ | |
return f(function(a, b){ return y(y)(a, b) }) }) | |
}(function(f){ | |
return function(s, n){ | |
return ((n == 0) ? | |
function(c){ | |
return c(function(a, b){ return a }) }(s) | |
: f(function(c){ | |
return c(function(a, b){ return b }) }(s)(), (n - 1))) } }) | |
(function(f){ | |
return function(x){ | |
return x(x) }(function(y){ return f(function(a, b){ return y(y)(a, b) }) }) | |
}(function(f){ | |
return function(a, b){ | |
return function(hd, tl){ | |
return function(x){ | |
return x(hd, tl) } }(a, function(){ return f(b, (a + b)) }) | |
} })(0, 1), n) }; | |
fib(1) => 1 | |
fib(2) => 1 | |
fib(3) => 2 | |
fib(12) => 144 | |
;;;; Ver 2.0 | |
;;;; Curry flavor | |
(define curried-fibs | |
(lambda (idx) | |
((((lambda (f) | |
((lambda (x) (x x)) | |
(lambda (y) (f (lambda (a) | |
(lambda (b) (((y y) a) b))))))) | |
(lambda (f) (lambda (s) | |
(lambda (idx) | |
(if (= idx 0) | |
((lambda (p) | |
(p (lambda (h) (lambda (t) h)))) s) | |
((f (((lambda (p) | |
(p (lambda (h) (lambda (t) t)))) s))) | |
(- idx 1))))))) | |
((((lambda (f) | |
((lambda (x) (x x)) | |
(lambda (y) (f (lambda (a) | |
(lambda (b) (((y y) a) b))))))) | |
(lambda (f) | |
(lambda (a) | |
(lambda (b) | |
(((lambda (h) | |
(lambda (t) (lambda (a) ((a h) t)))) a) | |
(lambda () ((f b) (+ a b)))))))) 0) 1)) | |
idx))) | |
;;; The javascript version of this one is really beautiful | |
var curried_fibs = function(idx) | |
{ | |
return function(f) | |
{ return function(x){ return x(x) | |
}(function(y) { | |
return f(function(a) { | |
return function(b){ return y(y)(a)(b) } }) })} | |
(function(f){ | |
return function(s){ | |
return function(idx){ | |
return ((idx == 0) ? | |
function(p){ | |
return p(function(h) | |
{ return function(t) | |
{ return h } }) }(s) | |
: f(function(p){ | |
return p(function(h) | |
{ return function(t) | |
{ return t } }) }(s)())((idx - 1))) } } }) | |
(function(f){ return function(x) | |
{ return x(x) }(function(y){ | |
return f(function(a) | |
{ return function(b) { return y(y)(a)(b) } }) }) } | |
(function(f){ return function(a) | |
{ return function(b) | |
{ return function(h) | |
{ return function(t) | |
{ return function(a) | |
{ return a(h)(t) } } }(a)(function(){ return f(b)((a + b)) }) } } })(0)(1)) | |
(idx) } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment