Partial application versus pattern matching: why do these Haskell functions behave differently?

Question

I'm trying to understand something about Haskell functions.

First, here is a Fibonacci function defined in the typical "slow" way (i.e. recursive with no memoization, and no infinite-list tricks)

slowfib :: Int -> Integer
slowfib 0 = 0
slowfib 1 = 1
slowfib n = slowfib (n-2) + slowfib (n-1)

Next, a canonical memoizing version of the same. (Only slightly different from typical examples in tutorals/books/etc, because I prefer the prefix version of the !! operator.)

memfib = (!!) (map fib [0..])
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib(k-2) + memfib(k-1)

The above solution uses partial application of the !! operator, which makes sense: we want memfib to end up as a function that takes a parameter, and we are defining it without including a parameter in the definition.

So far so good. Now, I thought I could write an equivalent memoizing function that does include a parameter in the definition, so I did this:

memfib_wparam n = ((!!) (map fib [0..])) n
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib_wparam(k-2) + memfib_wparam(k-1)

(In Lambda calculus terms, memfib and memfib_wparams are just eta-conversions of each other. I think???)

This works, but the memoization is gone. In fact, memfib_wparam behaves even worse than showfib: Not only is it slower, but its memory usage is more than double.)

*Main> slowfib 30
832040
(1.81 secs, 921,581,768 bytes)
*Main> memfib 30
832040
(0.00 secs, 76,624 bytes)
*Main> memfib_wparam 30
832040
(2.01 secs, 2,498,274,008 bytes)

What's going on here? More importantly, what is my broader understanding of Haskell function definitions getting wrong? I was assuming the syntax I used in memfib_wparam was just syntactic sugar for what I did in memfib, but clearly it isn't.

Answer 1

The difference is in when your fib function is bound.

where-bound definitions have access to the outer function's parameters (i.e. the parameters are "in scope" within where). This means that fib should have access to n, which in turn means that fib is defined after n is passed, which means it's a different fib for every n, which means it's a different call to map fib [0..] for every n.

If you wanted to eta-expand your memfib, this would be the "right" way to do it (i.e. without unduly expanding the scope of n):

memfib = \n -> theCache !! n
    where
        theCache = map fib [0..]

        fib 0 = 0 
        fib 1 = 1 
        fib k = memfib(k-2) + memfib(k-1)

If you're comparing with lambda calculus, the key difference is that eta-reduction/expansion doesn't say anything about performance, it just guarantees that the result of the program stays the same logically. Which it does.