Created
May 20, 2012 07:46
-
-
Save osa1/2757232 to your computer and use it in GitHub Desktop.
Lisp-style lazy-lists in Lua
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 makeThunk(f, args) | |
return { tag = "thunk", f = f, args = args } | |
end | |
function evalThunk(t) | |
return t.f(unpack(t.args)) | |
end | |
function cons(first, rest) | |
return { first = first, | |
rest = rest } | |
end | |
function range(b, e, s) | |
b = b or 0 | |
s = s or 1 | |
if e == nil or b <= e then | |
return cons(b, makeThunk(range, {b+s, e, s})) | |
end | |
end | |
function evalPart(t, p) | |
if t == nil then | |
return nil | |
elseif type(t[p]) == "table" and t[p].tag == "thunk" then | |
t[p] = evalThunk(t[p]) | |
end | |
return t[p] | |
end | |
function first(t) | |
return evalPart(t, "first") | |
end | |
function rest(t) | |
return evalPart(t, "rest") | |
end | |
function nth(t, n) | |
if n == 0 then | |
return first(t) | |
end | |
return nth(rest(t), n-1) | |
end | |
function map(f, l) | |
return cons(f(first(l)), makeThunk(map, {f, rest(l)})) | |
end | |
function filter(f, l) | |
while not f(first(l)) do | |
l = rest(l) | |
end | |
return cons(first(l), makeThunk(filter, {f, rest(l)})) | |
end | |
-- Examples -------------------------------------------------------------------- | |
function fact(n, f) | |
n = n or 1 | |
f = f or 1 | |
return cons(n, makeThunk(fact, {n*f, f+1})) | |
end | |
-- > a = fact() | |
-- > print(nth(a, 5)) | |
-- 120 | |
-- > print(nth(a, 250)) | |
-- inf | |
function fib(a, b) | |
a = a or 0 | |
b = b or 1 | |
return cons(a, makeThunk(fib, {b, a+b})) | |
end | |
-- > a = fib() | |
-- > print(nth(a, 0)) | |
-- 0 | |
-- > print(nth(a, 1)) | |
-- 1 | |
-- > print(nth(a, 2)) | |
-- 1 | |
-- > print(nth(a, 3)) | |
-- 2 | |
-- > print(nth(a, 13)) | |
-- 233 | |
-- Continuations --------------------------------------------------------------- | |
function sum(n, cont) | |
if n <= 1 then | |
return makeThunk(cont, {1}) | |
end | |
local function newCont(v) | |
return makeThunk(cont, {v+n}) | |
end | |
return makeThunk(sum, {n-1, newCont}) | |
end | |
function trampoline(thunk) | |
while true do | |
if type(thunk) ~= "table" then | |
return thunk | |
elseif thunk.tag == "thunk" then | |
thunk = evalThunk(thunk) | |
end | |
end | |
end | |
-- > a = sum(123, function(n) print("result: ", n) end) | |
-- > trampoline(a) | |
-- result: 7626 | |
-- Lazy list version | |
function sumList(sum, cur) | |
sum = sum or 0 | |
cur = cur or 1 | |
return cons(sum, makeThunk(sumList, {sum+cur, cur+1})) | |
end | |
-- > a = sumList() | |
-- > print(nth(a, 10)) | |
-- 55 | |
-- > print(nth(a, 11)) | |
-- 66 | |
-- > print(nth(a, 123)) | |
-- 7626 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment