Skip to content

Instantly share code, notes, and snippets.

@L8D
Created October 10, 2014 05:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save L8D/8080a9b1580d0521dc1a to your computer and use it in GitHub Desktop.
Save L8D/8080a9b1580d0521dc1a to your computer and use it in GitHub Desktop.
Basic Church-encoded data structures written in lazy-evaluable JavaScript
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