Today I had this strange experience regarding eta-reduction and Haskell’s laziness.

I was trying out some memoization examples from http://www.haskell.org/haskellwiki/Memoization, so I spent some time specifically on:

memoized_fib :: Int -> Integer

memoized_fib = (map fib [0 ..] !!)

where fib 0 = 0

fib 1 = 1

fib n = memoized_fib (n-2) + memoized_fib (n-1)

So I ran this example in Haskell and everything worked fine!

In order to understand what this function does, I started to explore it around and eventually I rewrote the second line as:

memoized_fib x = (map fib [0 ..] !!) x

However, be careful when you are doing something like this! By removing the eta-reduction on this kind of functions, Haskell evaluates x on every iteration!

So the memoized_fib worked as slow as slow_fib.

As strange and as non-intuitive as this may sound, eta-reduction *can* change the overall behaviour of a function.

Advertisements