Functions
For example, the traditional Fibonacci function:
is hopelessly inefficient, but
But Lua, uniquely I suspect, lets us trade in the other direction, delaying the filling of a table:
The function
f(x)
use a fixed amount of space and who knows how much time, whereas tables t[x]
use a fixed amount of time and who knows how much space. The traditional speed-up, trading space for time, is called memoization:
Lua:
memoize = function (f)
local t = { }
return function (x)
local a = t[x]
if not a then
a = f(x)
t[x] = a
end -- if
return a
end -- function
end -- function
Lua:
fib = function (n)
if n < 2 then return n end -- if
return f(n-1) + f(n-2)
end -- function
memoize (fib)
is much better.But Lua, uniquely I suspect, lets us trade in the other direction, delaying the filling of a table:
Lua:
local t = setmetatable ( { 0, 1}, {
__index = function (f,x)
local a = f[x-1] + f[x-2]
f[x] = a
return a
end -- function
})
newfib = function (x) return t[x] end -- function
newfib
is better still. Are there other languages that make this space/time duality so explicit?