How memorize intermediate computation value[my brain is so hurt]?
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
This might help :)
http://www.kennknowles.com/blog/2008/05/10/debugging-with-open-recursion-mix...
On 4 February 2012 10:36, 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
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
There are quite a few packages on hackage that do memoization. Many
of them actually have fibonacci sequences as examples. These vary in
terms of complexity.
http://hackage.haskell.org/package/data-memocombinators
http://hackage.haskell.org/package/monad-memo
http://hackage.haskell.org/package/memoize
On Sat, Feb 4, 2012 at 5: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
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
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ï
participants (4)
-
anyzhen -
Benjamin Edwards -
Chaddaï Fouché -
David McBride