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

Answer 1

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.