Created
October 10, 2014 05:39
-
-
Save L8D/8080a9b1580d0521dc1a to your computer and use it in GitHub Desktop.
Basic Church-encoded data structures written in lazy-evaluable JavaScript
This file contains 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
function compose(f) { | |
return function(g) { | |
return function(x) { | |
return f(g(x)); | |
}; | |
}; | |
} | |
// allTheNumbersFrom(Zero) -> 0, 1, 2, 3... | |
function allTheNumbersFrom(number) { | |
return function(iterator) { | |
return function(empty) { | |
return iterator(number)(allTheNumbersFrom(Succ(number))); | |
}; | |
}; | |
} | |
/*--- BOOLEANS ---*/ | |
function True(yes) { | |
return function(no) { | |
return yes; | |
}; | |
} | |
function False(yes) { | |
return function(no) { | |
return no; | |
}; | |
} | |
function toBool(bool) { | |
return bool(true)(false); | |
} | |
function fromBool(value) { | |
return value ? True : False; | |
} | |
/*--- NUMERALS ---*/ | |
function Succ(number) { | |
return function(succ) { | |
return function(zero) { | |
return succ(number); | |
}; | |
}; | |
} | |
function Zero(succ) { | |
return function(zero) { | |
return zero; | |
}; | |
} | |
function fromNumber(int) { | |
return int <= 0 ? Zero : Succ(fromNumber(int - 1)); | |
} | |
function toNumber(number) { | |
return number(function(predicate) { | |
return 1 + toNumber(predicate); | |
})(0); | |
} | |
/*--- SEQUENCES ---*/ | |
function Cons(head) { | |
return function(tail) { | |
return function(func) { | |
return function(empty) { | |
return func(head)(tail); | |
}; | |
}; | |
}; | |
} | |
function Empty(func) { | |
return function(empty) { | |
return empty; | |
}; | |
} | |
function map(iterator) { | |
return function(list) { | |
return list(function(head) { | |
return compose(Cons(iterator(head)))(map(iterator)); | |
})(Empty); | |
}; | |
} | |
function filter(iterator) { | |
return function(list) { | |
return list(function(head) { | |
return compose(iterator(head)(Cons(head))(function(list) { | |
return list; | |
}))(filter(iterator)); | |
})(Empty); | |
}; | |
} | |
function reduce(iterator) { | |
return function(value) { | |
return function(list) { | |
return list(function(head) { | |
return reduce(iterator)(iterator(value)(head)); | |
})(value); | |
}; | |
}; | |
} | |
function scan(iterator) { | |
return function(value) { | |
return function(list) { | |
return Cons(value)(list(function(head) { | |
return scan(iterator)(iterator(value)(head)); | |
})(Empty)); | |
}; | |
}; | |
} | |
function take(number) { | |
return function(list) { | |
return number(function(predicate) { | |
return list(function(head) { | |
return compose(Cons(head))(take(predicate)); | |
})(Empty); | |
})(Empty); | |
}; | |
} | |
function drop(number) { | |
return function(list) { | |
return number(function(predicate) { | |
return list(function(head) { | |
return drop(predicate); | |
})(Empty); | |
})(list); | |
}; | |
} | |
function fromArray(array) { | |
var list = Empty; | |
var index = array.length; | |
while (index--) { | |
list = Cons(array[index])(list); | |
} | |
return list; | |
} | |
function toArray(list) { | |
return reduce(function(array) { | |
return function(element) { | |
return array.concat([element]); | |
}; | |
})([])(list); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment