Skip to content

Instantly share code, notes, and snippets.

@ehaliewicz
Last active December 11, 2015 23:58
Show Gist options
  • Save ehaliewicz/4680328 to your computer and use it in GitHub Desktop.
Save ehaliewicz/4680328 to your computer and use it in GitHub Desktop.
Lazy infinite fibonacci stream
(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