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.

Answer 1

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)