(note I'm putting the question here because it's about the conceptual mechanics of it, rather than a coding problem)
I was working on a small program, that was using a sequence of fibonacci numbers in its equasion, but I noticed that if I got over a certain number it got painfully slow, googling around a bit I stumbled upon a technique in Haskell known as Memoization
, they showed code working like this:
-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)
-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
where fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
So my question to you guys is, how or rather why does this work?
Is it because it somehow manages to run through most of the list before the calculation catches up? But if haskell is lazy, there isn't really any calculation that needs to catch up... So how does it work?
the calculation catches up
?. BTW, memoization is not specific to haskell: en.wikipedia.org/wiki/Memoization