[Haskell-cafe] Sharing Subexpressions: Memoization of Fibonacci sequence

[Daniel Fischer]

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