Translating imperative memoization code to Haskell

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.

Answers


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)


Need Your Help

Dynamically retrieve values of index properties in C#

c# reflection properties

I am trying to create a SortedList of property names and values for any object. The two methods below iterate an object's properties storing its respective values in a sorted list (if there is a be...

How to hyperlink to deep Doxygen content?

doxygen permalinks

As implied by Are URLs to doxygen pages permanent, URL in doxygen are not permanent.