(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?