[Haskell-cafe] Sharing Subexpressions: Memoization of Fibonacci
sequence
SimonK77
simonkaltenbacher at googlemail.com
Mon Oct 12 14:52:30 EDT 2009
**Edit: formatting was bad**
Hallo everyone,
the last few weeks I was trying to get used to memoization in haskell. As I
found out in a previous post, memoization in haskell is, due to the graph
reduction strategy used in haskell, almost always implemented by sharing
subexpressions in an expression.
In examples as the following this is quite easy to see.
fibs = 0:1:zipWith (+) fibs (tail fibs)
But as I browsed through the search results from google for this topic, I
encountered the following implementation:
memoized_fib :: Int -> Integer
memoized_fib =
let fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
in (map fib [0 ..] !!)
You'll find it at Haskell.org. Here's the
http://www.haskell.org/haskellwiki/Memoization link
Let's assume we have the following implementation of the
higher-order-function map:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
The reduction sequence of memoized_fib 5 would start as follows:
//Reduction of memoized_fib 5
memoized_fib 5 = (map fib [0..] !!) 5
= (fib 0 : map fib [1..] !!) 5
= (0 : fib 1 : map fib [2..] !!) 5
= (0 : 1 : fib 2 : map fib [3..] !!) 5
= (0 : 1 : (memoized_fib 0 + memoized_fib 1) : fib 3 : map fib [4..]
!!) 5
= (0 : 1 : (map fib [0..] !! 0 + map fib [0..] !! 1) : (memoized_fib 1
+ memoized_fib 2) : map fib [4..] !!) 5
.
.
.
.
and so on!
I can't see where the sharing of subexpressions happens here. Any help is
highly appreciated.
Best regards
Simon
--
View this message in context: http://www.nabble.com/Sharing-Subexpressions%3A-Memoization-of-Fibonacci-sequence-tp25861134p25861177.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
More information about the Haskell-Cafe
mailing list