An option to make memoization the default behaviour of Haskell

Question

I have seen all the other memoization tricks and techniques in Haskell but what I am looking for is a straightforward implementation in the level of compiler/interpreter that takes care of memoization for me.

For example, consider the following code for the Fibonacci function:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

I want some kind of compiler option for ghc (or any other Haskell compiler) that executes the code above using memoization by default. For example, to compute "fib 10", one needs "fib 8" and "fib 9" to be computed first. Also, computing "fib 9" depends on first computing "fib 8". So, when computing "fib 10" I want the compiler/interpreter to understand that and compute "fib 8" only once.

Please note that I don't want to write a new Fibonacci function that takes care of memoization (as is the case with all other memoization questions in Haskell). What I want is to keep the function as above and still have memoization. I don't know if any Haskell compiler has that capability and that's part of my question. Do you know a Haskell compiler that can give me this?

Thanks

A typical technique to get "function" values memoized is to use a list instead via lazy evaluations. This would be a different implementation though. haskell.org/haskellwiki/… — Benjamin Bannier
Currently, no compiler I know of has such a feature. It is imaginable to have a {-# MEMOISE #-} pragma, but for polymorphic functions, you'd probably need to give a list of types at which it should be memoised. However, I doubt that would be implemented, since hand-made memoisation is much more flexible and easy enough to do. — Daniel Fischer
This sounds like a great recipe for using a great deal of memory in a great hurry. — C. A. McCann
The closest you are likely to get is Delta ML created by Guy Blelloch, Umut Acar and others. There are quite a few papers about it and an implementation exists though it addresses a related, but slightly different domain to memoization. Otherwise, memoization is unlikely to be part of a "mainstream" compiler. — stephen tetley

Dan Burton Dan Burton · Accepted Answer · 2012-10-25T01:00:00

Compilers typically won't provide a "memoize" option, because it is difficult to know where and how the programmer wants memoization to be performed. Memoization is essentially trading time & space requirements.

Now, if you're willing to write the function in a slightly different way, then there is a way to decouple the definition of the function and the memoization technique used.

import Data.RunMemo (Memoizable, runMemo, noMemo)
import Data.MemoCombinators as Memo (integral)

fibMemoizable :: Memoizable (Integer -> Integer)
fibMemoizable recurse = go where
  go 0 = 1
  go 1 = 1
  go n = recurse (n - 1) + recurse (n - 2)

fastFib :: Integer -> Integer
fastFib = runMemo Memo.integral fibMemoizable

slowFib :: Integer -> Integer
slowFib = runMemo noMemo fibMemoizable

This uses Luke Palmer's data-memocombinators package, as well as my own toy package, runmemo. Notice that the meat of it is the same as what you wrote, except that it invokes recurse for recursive calls. While this could be baked into a compiler, I see no reason, since Haskell is expressive enough to deal with this without requiring that the compiler be aware of what we're doing.

An option to make memoization the default behaviour of Haskell

1 Answers