Am Montag 12 Oktober 2009 21:09:38 schrieb minh thu:

2009/10/12 SimonK77 <simonkaltenbacher@googlemail.com>:

...

**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!

Hi,

Instead of repeating as-is map fib [0..] consider it as a single list that is always reused. Since the list maps the input of the fib function to the result of the function and that list is always reused, the recursive calls have immediately the answer (i.e. at the cost of the lookup).

Yes, since memoized_fib is bound by a simple pattern binding and not a function binding, the list is shared among different invocations of memoized_fib, same as if it was given an explicit name. You can see it by adding tracing output: import Debug.Trace tfib :: Int -> Integer tfib = let fib 0 = 0 fib 1 = 1 fib n = trace ("eval fib " ++ show n) $ tfib (n-2) + tfib (n-1) in (map fib [0 .. ] !!) *MFib> tfib 6 eval fib 6 eval fib 4 eval fib 2 eval fib 3 eval fib 5 8 (0.00 secs, 538564 bytes) *MFib> tfib 10 eval fib 10 eval fib 8 eval fib 7 eval fib 9 55 (0.00 secs, 0 bytes)

So your fragment

(0 : 1 : (map fib [0..] !! 0 + map fib [0..] !! 1) ...

should look like

lst = (0 : 1 : (lst !! 0 + lst !! 1) ...

which is similar to the zipWith (+) version.

Except it's much slower.

Cheers, Thu

Am Mittwoch 14 Oktober 2009 23:30:05 schrieb SimonK77:

Hallo Daniel,

can you explain the difference between a "pattern binding" and a "function binding"? I haven't heard about these two terms so far.

The formal specification is at http://haskell.org/onlinereport/decls.html#sect4.4.3 A function binding is a binding where the function name and at least one parameter (pattern) appear to the left of '=', while in a pattern binding only bound patterns appear on the left. -- function bindings fun x = expression -- binds fun x \/ y = expr' -- binds (\/) -- pattern bindings func = \x -> expression -- binds func var = expr -- binds var (v1,v2) = express -- binds v1 and v2 (a0:a1:tl) -- binds a0, a1 and tl | even v1 = exp1 | otherwise = exp2 The first three are *simple* pattern bindings.

And furthermore: Why does the memoization only happen with pattern binding?

I don't know all the details either, but the point is that names bound by a (simple) pattern binding are "constant applicative forms" (http://www.haskell.org/haskellwiki/CAF) which can be shared by all uses (if they have a monomorphic type, cf. also http://www.haskell.org/haskellwiki/Monomorphism_Restriction and http://haskell.org/onlinereport/decls.html#sect4.5.5), while names bound by a function binding aren't shared across computations (I think it is generally undecidable how much could be shared and anyway it would be too complicated for the compiler to investigate that - too little gain for too much effort). So with function-bound fbfib :: Int -> Integer fbfib k = let fib 0 = 0 fib 1 = 1 fib n = fbfib (n-2) + fbfib (n-1) in (map fib [0 ..] !! k) fb2fib :: Int -> Integer fb2fib k = let fib 0 = 0 fib 1 = 1 fib n = fb2fib (n-2) + fb2fib (n-1) flst = map fib [0 .. ] in (flst !! k) nothing is shared, each (recursive) call to fb(2)fib creates a new list of Fibonacci values (in principle, different arguments could require very different code-paths, so we don't even bother to let the compiler look for the few cases where it could determine sharing would be beneficial). With pattern-bound functions, it's harder to know when sharing will happen. It depends on the form of the RHS and where things that might be shared are bound. In 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 ..] !!) the list of Fibonacci numbers is shared, even though it hasn't been given a name (In general, give entities you want to be shared a name of their own to increase the chance of them being really shared). If you define the function with a simple pattern binding which has a lambda-expression on the right hand side, it depends on whether things are bound within the lambda-scope or outside. In plfib :: Int -> Integer plfib = \k -> let fib 0 = 0 fib 1 = 1 fib n = plfib (n-2) + plfib (n-1) in (map fib [0 ..] !! k) the things which could be shared are bound inside the lambda-expression, therefore they aren't shared (they could potentially depend on the lambda-bound variable[s], here k). Lifting the binding of fib outside the lambda pblfib :: Int -> Integer pblfib = let fib 0 = 0 fib 1 = 1 fib n = pblfib (n-2) + pblfib (n-1) in \k -> (map fib [0 ..] !! k) doesn't help - of course, the list in which we index is still inside the lambda. Give it a name and hoist it outside the lambda: peblfib :: Int -> Integer peblfib = let fib 0 = 0 fib 1 = 1 fib n = peblfib (n-2) + peblfib (n-1) flst = map fib [0 .. ] in \k -> (flst !! k) Now flst is a CAF which can be shared, and indeed it is: *MFib> peblfib 40 102334155 (0.00 secs, 0 bytes)

Best regards,

Simon

Hope this gets you started, Daniel