Translating imperative memoization code to Haskell

Question

Memoization is a useful thing and since it's heavily related to functions, I'd assume Haskell has the right machinery to implement it in an at least fairly straightforward manner.

var memo = function (f) {
    var cache = {};
    return function (x) {
        if (cache[x]) return cache[x];
        else return cache[x] = f(x);
    }
}

//Usage:
var fib = memo(function (x) {
    if (x == 0) return 1;
    if (x == 1) return 1;
    return fib(x - 1) + fib(x - 2);
});

fib(100);

This is the code I wrote in JavaScript that does what I want. What would be a good translation to Haskell that can offer similar practicality AND performance?

To reduce ambiguity of the question, I'm not interested in replicating the generality of the JS solution because Haskell is strongly typed. Something with a type signature of

memo :: (Int -> b) -> (Int -> b)

that can be manually extended for multiple parameters and maybe even various types would be fine.

leftaroundabout · Accepted Answer · 2014-04-01 16:13:49Z

9

The main important thing the JavaScript solution hinges on is a fast-access mutable container; those languages generally implement them as hashmaps and make them a central language component (mainly because more sophisticated, specialised data structures can't be expressed in the feeble type system).

But not in Haskell. There are hash-maps in libraries allright, but there's also containers specifically designed for memoisation: memo-tries. Why not use those?

You can of course also hack your way without efficient container structures. The simplest way to memoise an Int -> function would be to store an infinite list of all results:

memoInt :: (Int -> b) -> Int -> b
memoInt f = look
 where positives = [ f x | x <- [0..] ]
       negatives = [ f x | x <- [-1, -2 ..] ]
       look x | x<0        = negatives !! (1-x)
              | otherwise  = positives !! x

Obviously, the list-lookups become very expensive for large |x|.

For a somewhat weird, but very easy way to make this reasonably fast, namely O (√n) instead of O (n):

memoInt' :: (Int -> b) -> Int -> b
memoInt' f = look
 where table = [ [ f (sqrtX^2 + dx) | dx <- [0..]    ]
                                    | sqrtX <- [0..] ]
       look x | x<0        = negDomain x
              | otherwise  = let sqrtX = floor . sqrt $ fromIntegral x
                             in table !! sqrtX !! (max 0 $ x - sqrtX)
       negDomain = memoInt' (f . negate)

(This might break for large numbers because of floating-point trouble, it's not really safe use of sqrt)

edited Apr 1, 2014 at 16:13

answered Apr 1, 2014 at 15:40

leftaroundabout

121k6 gold badges185 silver badges337 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Luka Horvat Over a year ago

I can't complain about this answer since it is a correct one, but I'm not really happy with what it is. I have a choice of using a very expensive implementation that I can understand or use a fast one that someone else implemented for me and that I couldn't understand myself. Leaves a bad feeling.

Luka Horvat Over a year ago

Wouldn't it be great if I could just swap out the infinite list for an infinite lazy map?

Cirdec Over a year ago

+1 for memo-tries. I was going to invent what turns out to be the HasTrie instance for Integer to answer this.

leftaroundabout Over a year ago

@LukaHorvat Data.Map isn't intended for infinite collections. Again, memo tries are intended for this, so do use them! I can't really see why you shouldn't understand that yourself, just browse through the library code. It's definitely easier than understanding JavaScripts hash maps, which you'd need to fully understand your original code.

Cirdec Over a year ago

@Luke, the "infinite lazy map" needs to know what the structure of the map is ahead of time, since it can't be changed by side effect as the code is evaluated. That means the structure of the map must depend solely on the structure of the datatype that is the key, and not on which values of the key have been populated.

|

Collectives™ on Stack Overflow

Translating imperative memoization code to Haskell

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related