(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 30slow_fib :: Int -> Integerslow_fib 0 = 0slow_fib 1 = 1slow_fib n = slow_fib (n-2) + slow_fib (n-1)-- Memorized variant is near instant even after 10000memoized_fib :: Int -> Integermemoized_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?
Can someone explain the concept behind Haskell's memoization?
haskell;recursion
Just to explain the mechanics behind the actual memoization,memo_fib = (map fib [1..] !!)produces a list of thunks, unevaluated computations. Think of these like unopened presents, as long as we don't touch them, they won't run.Now once we evaluate a thunk, we never evaluate it again. This is actually the only form of mutation in normal haskell, thunks mutate once evaluated to become concrete values.So back to your code, you've got a list of thunks, and you still do this tree recursion, but you recurse using the list, and once an element in the list is evaluated, it never gets computed again. Thus, we avoid the tree recursion in the naive fib function.As an tangentially interesting note, this is especially fast over a series of fibonnaci numbers are computed since that list is only evaluated once, meaning that if you calculate memo_fib 10000 twice, the second time should be instantaneous. This is because Haskell only evaluated arguments to functions once and you're using partial application instead of a lambda.TLDR: By storing calculations in a list, each element of the list is evaluated once, therefore, each fibonnacci number is calculated exactly once throughout the entire program.Visualization: [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5] -- Evaluating THUNK_5 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4] [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4] [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4] [1, 1, 2, THUNK_4, 2 + THUNK4] [1, 1, 2, 1 + 2, 2 + THUNK_4] [1, 1, 2, 3, 2 + 3] [1, 1, 2, 3, 5]So you can see how for evaluating THUNK_4 is much faster since it's subexpressions are already evaluated.