Ability to remind Haskell default behavior

Question

I saw all the other memorial tricks and methods in Haskell, but what I'm looking for is a simple compiler / interpreter level implementation 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 need some kind of compiler for ghc (or any other Haskell compiler) that executes the code above using memoization by default. For example, to calculate "fib 10", you must first calculate "fib 8" and "fib 9". In addition, the calculation of "fib 9" depends on the first calculation of "fib 8". Therefore, when calculating "fib 10", I want the compiler / interpreter to understand this and calculate "fib 8" only once.

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

thanks

Answer 1

Compilers usually do not provide the "memoize" parameter, because it is difficult to know where and how the programmer wants to perform the memonization. Memorization is mainly related to the needs of time and space.

Now, if you want to write a function a little differently, then there is a way to separate the definition of the function and the memoization method 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 the Luke Palmer data-memocombinators package , as well as my own toy package, runmemo . Note that his meat is the same as what you wrote, except that he calls recurse for recursive calls. Although it can be baked in the compiler, I see no reason, since Haskell is expressive enough to handle this without requiring the compiler to know what we are doing.