Eta-reduction and laziness

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s