Created
April 6, 2013 07:40
-
-
Save akbiggs/5325304 to your computer and use it in GitHub Desktop.
Following through Steve Losh's post on representing lists as lambdas.
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
/* LISTS */ | |
var empty_list = function(selector) { | |
return selector(undefined, undefined, true); | |
}; | |
var prepend = function(el, list) { | |
return function(selector) { | |
return selector(el, list, false); | |
}; | |
}; | |
var head = function(list) { | |
return list(function(h, t, e) { | |
return h; | |
}); | |
}; | |
var tail = function(list) { | |
return list(function(h, t, e) { | |
return t; | |
}); | |
}; | |
var is_empty = function(list) { | |
return list(function(h, t, e) { | |
return e; | |
}); | |
}; | |
var map = function(fn, l) { | |
if (is_empty(l)) { | |
return empty_list; | |
} else { | |
return prepend(fn(head(l)), map(fn, tail(l))) | |
} | |
}; | |
var filter = function(fn, l) { | |
if (is_empty(l)) { | |
return empty_list; | |
} else if (fn(head(l))) { | |
return prepend(head(l), filter(fn, tail(l))) | |
} else { | |
return filter(fn, tail(l)) | |
} | |
} | |
/* BOOLEANS */ | |
var not = function(x) { | |
return x === false; | |
}; | |
var and = function(x, y) { | |
if (not(x)) { | |
return false; | |
} else { | |
return y; | |
} | |
}; | |
var or = function(x, y) { | |
if (x) { | |
return true; | |
} else { | |
return y; | |
} | |
}; | |
/* NUMBERS */ | |
var zero = empty_list; | |
var one = prepend(empty_list, empty_list) | |
var two = prepend(empty_list, prepend(empty_list, empty_list)) | |
var inc = function(n) { | |
return prepend(empty_list, n); | |
}; | |
var dec = function(n) { | |
return tail(n); | |
}; | |
var is_zero = function(n) { | |
return is_empty(n); | |
}; | |
var add = function(x, y) { | |
if (is_zero(y)) { | |
return x; | |
} | |
return add(inc(x), dec(y)); | |
}; | |
var sub = function(x, y) { | |
if (is_zero(y)) { | |
return y; | |
} else { | |
return sub(dec(x), dec(y)); | |
} | |
}; | |
var mul = function(x, y) { | |
if (is_zero(y)) { | |
return zero; | |
} else { | |
return add(x, mul(x, dec(y))); | |
} | |
}; | |
var pow = function(x, y) { | |
if (is_zero(y)) { | |
return one; | |
} else { | |
return mul(x, pow(x, dec(y))); | |
} | |
}; | |
var is_equal = function(x, y) { | |
return is_zero(sub(x, y)); | |
}; | |
var less_than = function(x, y) { | |
if (and(is_zero(x), is_zero(y))) { | |
return false; | |
} else if (is_zero(x)) { | |
return true; | |
} else if (is_zero(y)) { | |
return false; | |
} else { | |
return less_than(dec(x), dec(y)); | |
} | |
}; | |
var greater_than = function(x, y) { | |
return less_than(y, x); | |
}; | |
var div = function(x, y) { | |
if (less_than(x, y)) { | |
return zero; | |
} else { | |
return inc(div(sub(x, y), y)); | |
} | |
}; | |
var rem = function(x, y) { | |
if (less_than(x, y)) { | |
return x; | |
} else { | |
return rem(sub(x, y), y); | |
} | |
}; | |
/* MORE LISTS */ | |
var nth = function(l, n) { | |
if (is_zero(n)) { | |
return head(l); | |
} else { | |
return nth(tail(l), dec(n)); | |
} | |
}; | |
var drop = function(l, n) { | |
if (is_zero(n)) { | |
return l; | |
} else { | |
return drop(tail(l), dec(n)); | |
} | |
}; | |
var take = function(l, n) { | |
if (is_zero(n)) { | |
return empty_list; | |
} else { | |
return prepend(head(l), take(tail(l), dec(n))); | |
} | |
}; | |
var slice = function(l, start, end) { | |
return take(drop(l, start), sub(end, start)); | |
}; | |
var length = function(l) { | |
if (is_empty(l)) { | |
return 0; | |
} else { | |
return inc(length(tail(l))); | |
} | |
}; | |
/* TESTS */ | |
head(prepend(5, empty_list)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment