On Sat, Feb 4, 2012 at 11:36 AM, anyzhen
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ï