3 ms·
I thought this was going to be about booleans from nothing at all: true = function(x,y){ return x; } false = function(x,y){ return y; } ifelse = fu
by jules 16y ago
I thought this was going to be about booleans from nothing at all:
true = function(x,y){ return x; }
false = function(x,y){ return y; }
ifelse = function(x,a,b){ x(a,b)(); }
not = function(x){ return x(false,true); }
and = function(x,y){ return x(y,false); }
or = function(x,y){ return x(true,y); }
bool = and(not(true),or(true,false))
ifelse(bool,
function(){ alert("true!") },
function(){ alert("false!") }
)
Amazing, isn't it?
It gets better.
Pairs:
pair = function(x,y){ return function(f){ return f(x,y); } }
fst = function(p){ return p(function(x,y){ return x; }); }
snd = function(p){ return p(function(x,y){ return y; }); }
Unions:
left = function(x){ return function(f,g){ return f(x); } }
right = function(x){ return function(f,g){ return g(x); } }
Pairs combined with unions make lists:
cons = function(x,y){ return left(pair(x,y)); }
head = function(l){ return l(function(p){ return fst(p); }, function(n){ alert("Can't take head of nil"); }) }
tail = function(l){ return l(function(p){ return snd(p); }, function(n){ alert("Can't take tail of nil"); }) }
nil = right(false)
isnil = function(l){ return l(function(p){ return false; }, function(n){ return true; }) }
map = function(f,l){
return ifelse(isnil(l),
function(){ return nil; },
function(){ return cons(f(head(l)),map(f,tail(l))); })
}
filter = function(f,l){
return ifelse(isnil(l),
function(){ return nil; },
function(){
return ifelse(f(head(l)),
function(){ return cons(head(l),filter(f,tail(l))); },
function(){ return filter(f,tail(l)); })
});
}
Isn't it neat how you can build everything, including conditionals, booleans, pairs and lists from functions?
Note that this code was not tested in any way, so it likely contains bugs.
- freyrs3 16y agoYou really can build everything out of anonymous functions, including all of arithmetic: zero = function(x,y){ return y; } succ = function (f) { return function (x) {return f(n(f(x)));};} one = succ(zero); two = succ(one); Look up lambda calculus if anyone is interested.
- jules 16y agoThe only problem then is, how do you do pred the inverse of succ? ;)
- mathgladiator 16y agoThe same way you build the integers. Built it out of pairs. a --> (a,0) -a --> (0,a) succ((a,0)) = (a+1,0) pred((a,0)) = (a,0+1)
- mathgladiator 16y agovia something like: http://news.ycombinator.com/item?id=2030649 http://news.ycombinator.com/item?id=2030649
- freyrs3 16y agoYou need to construct integers with a tuple type, in lambda calculus its: pair = λ x. λ y. λ z. x. y. z Or if you are willing to let pred(0) = 0 then you can use: pred = λ x. λy. λ z. x . (λ i. λ j. j. i. y (λ k. z) (λ k. k)
- mathgladiator 16y agoI recommend the Numbers Book ( http://www.amazon.com/Numbers-Graduate-Texts-Mathematics-Readings/dp/0387974970 http://www.amazon.com/Numbers-Graduate-Texts-Mathematics-Rea... ): I just did a construction of the integers assuming either sets or arrays. I could equally have used your list definition. http://pastie.org/1397123 http://pastie.org/1397123 and http://news.ycombinator.com/item?id=2030649 http://news.ycombinator.com/item?id=2030649 I've very tempted to combine your work with this and then go on to define rationals and then the reals. The reals would be very interesting since it would be a sequence that takes an epsilon and gets a rational number that is close enough. It's kind of crazy to think that all these real numbers are infinite cauchy sequences. If I define a real as function(eps) { return some_rational; } then I could define it piece_wise and say function mult_real(a,b) { return function(eps) { return a(eps/2) * b(eps/2); } }
- jules 16y agoBuilding the reals out of lambda calculus would be cool. I don't think however that your definition of mult_real is correct. For example if a=b=10 and eps=2, then a(eps/2) x b(eps/2) could be anything between 9x9=81 and 11x11=121, whereas you'd want it to be between 99 and 101? How to fix this?