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
)