On Mon, Oct 12, 2009 at 11:52:30AM -0700, SimonK77 wrote:
**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 ..] !!) ... I can't see where the sharing of subexpressions happens here. Any help is highly appreciated.
This is an excellent and subtle question. The sharing behavior of the code depends on the desugaring of the syntax (map fib [0 ..] !!): is it (!!) (map fib [0 ..]) or (\x -> map fib [0 ..] !! x) I suggest, as an exercise, tracing the evaluation of memoized_fib using each of these desugarings, and then trying them out in ghci. Then you'll be able to tell which desugaring ghc is using. (It's not the one used in the Report! In principle this is a bug since we can distinguish them using seq.) Regards, Reid Barton