function newfibs()
fibtable = {[0]=0, 1}
function fibs (n)
if fibtable[n] then
return fibtable[n]
else
fibtable[n] = fibs(n -1) + fibs(n - 2)
return fibtable[n]
end
end
return fibs
end
I wrote this in like 30 seconds. A C equivalent that memoized previously calculated values in the Fibonacci sequence would have taken me several minutes to write. How did I ever get by without closures and tables?
Yeap, they sure are. But here, have some more generality.
-- f: (type_of(f), k) -> v
function memoizer(f)
local tb = {}
local mt = {
__call = function(self,k)
local memo_v = self[k]
if memo_v ~= nil then
return memo_v
else
local v = f(self, k)
self[k] = v
return v
end
end
}
setmetatable(tb, mt)
return tb
end
function fibs(f, n)
if n == 1 or n == 2 then
return 1
else
return f(n - 1) + f(n - 2)
end
end
slow_fibs = function(n) return fibs(slow_fibs, n) end
still not general enough, i cannot simply make an existing function memoized by adding a single line of code (i'd need to rename the base function, add the memoized function, and change the tests). needs more function decorators.
Name:
Anonymous2012-11-17 11:32
end end end end end end
Terrible!
Name:
Anonymous2012-11-17 11:48
Not really.
Dynamic scope > static scope
Name:
Anonymous2012-11-17 12:00
>implying these are better than javascript's closures
A C equivalent that memoized previously calculated values in the Fibonacci sequence would have taken me several minutes to write.
Why would you tell us that you are a bad programmer?
Name:
Anonymous2012-11-17 15:30
(%-.-*:)t.
Recursive fibs is wasteful.
Name:
Anonymous2012-11-17 16:41
static int fib_r (int p, int h, int i) {
switch (i) {
case 0: return p;
case 1: return h;
case 2: return p + h;
default: return fib_r(h, p+h, i-1);
}
}
>>18
It returns the element at the given index, so ['a','b','c'] !! 1 = 'b'. Also, (fibs !!) is a partial application - it's a function that given x, returns fibs !! x.
Name:
Anonymous2012-11-17 23:57
Thank you!
Name:
Anonymous2012-11-18 6:00
>>19
I love function composition but writing it always feels like I'm about to do something incredibly inefficient.
>>22
I imported it for (<$>). Yeah, I realize now that all I needed was Data.Functor, but I've gotten in the habit of importing Applicative whenever I'm using functors.
Name:
Anonymous2012-11-18 12:23
Writing this efficiently without specialized language support is CS101 - Algorithms and Programming I.