[Haskell-beginners] How memorize intermediate computation value[my brain is so hurt]?

[Chaddaï Fouché]

On Sat, Feb 4, 2012 at 11:36 AM, anyzhen <jiangzhen3s at qq.com> wrote:
> there have a lot of situation we need memorize intermediate computation
> value.
> and use in further.
> like this, compute nth fib question.
> So,how memorize it?
>
> i have an ugly solution.it used HashTable for memorization.
>
> fib n table
>  | n==1 =1
>  | n==2 =1
>  | otherwise =
>   case lookup table of
>     Just v   ->(v,table)
>     Nothing ->let (v,table') = fib (n-1) table in
>                    let ( v',table'')= v + fib(n-2) table' in
>                    (v',table'')
>
> i am an beginner come from imperative programming language.
> so fib memorize version program hurt my brain ... particular in Nothing
> branches.
> so do you have some good idea

Do you really want to memoize the function from one call to the next
or only in one invocation of the function ?
If the second, you can just use a local function which keep track of
only the necessary results :

> fib n = go n 1 1
>   where
>     go 0 a b = a
>     go n a b = go (n-1) b $! (a+b)

(the $! is just so that a+b is evaluated immediately (strictly), in
order to not accumulate a big thunk of addition to perform later)
Note that writing fib example is almost an industry in FP land, so you
can find plenty of other versions, some more mind bending like :

> fib n = fibs !! n
> fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

If it's the second, refer to the excellent answers of my colleagues.

-- 
Jedaï