Memoization performance

Learn
#1

Hello, I’d like help with a beginner question, please. I am following this example Memoization - HaskellWiki.

First, it is amazing that memoization is ‘induced’ by using the fixed point combinator, but perhaps that isn’t surprising to a computer scientist.

My question is to do the ‘memoization function’:

memo :: (Int -> a) -> (Int -> a)
memo f = (map f [0..] !!)

The example works fine until I modify it as follows:

memo :: (Int -> a) -> (Int -> a)
memo f = (\x -> (map f [0..] !!) x)

I would have expected this to be a no-op, but it unexpectedly destroys performance.

Thank you!

#2

Yes this is a bit tricky.

I guess you have to get an intuition to where the scope for the internal list (that is created with map f [0..]) is and if/where it is (re)created.

In the first version memo the list (or the thunk for that list) is referenced once in the resulting function and the whole memoization-trick here is that this list is reused whenever you use the resulting function.

In your changed version it’s behind the \x -> ... lambda - so you’ll recreate it for each call of said lambda.

I guess a more similar example (for the no-op) would be

memo :: (Int -> a) -> (Int -> a)
memo f = let values = map f [0..] in (\x -> values !! x)
#3

Thank you! I need to think about this. I guess you are saying the list is local to the scope of the lambda, and is thus recreated whenever the lambda is invoked. And, loosely, it seems the entire goal of this endeavor is to put all function calls in the same scope (s.t. the thunks are recognized as identical).

#4

Yes the goal is to reuse the (lazy) list.
This way you get the memoization-effect by using the laziness build into the language.

2 Likes