# Memoization of interdependent haskell functions

I have three functions which act on a matrix and kind of find a minimum sum path (Note `dim` = 80, See https://projecteuler.net/problem=82):

``````-- f is the minimum cost from x, y by taking only up and right (up and down doesn't make sense)
f :: [[Int]] -> Int -> Int -> Int
f arr x y
| y == dim-1 = arr !! x !! y
| otherwise = arr !! x !! y + if x > 0 then min (h arr x (y+1)) (f arr (x-1) y) else h arr x (y+1)

-- g is the minimum cost from x, y by taking only down and right (up and down doesn't make sense)
g :: [[Int]] -> Int -> Int -> Int
g arr x y
| y == dim-1 = arr !! x !! y
| otherwise = arr !! x !! y + if x + 1 < dim then min (h arr x (y+1)) (g arr (x+1) y) else h arr x (y+1)

-- h is the minimum cost from x, y by taking both up, down and right
h :: [[Int]] -> Int -> Int -> Int
h arr x y
| y == dim-1 = arr !! x !! y
| otherwise = min (g arr x y) (f arr x y)
``````

I tried using `Data.Function.Memoize` but that also wasn't quite working (I strongly believe that I am doing something wrong), i.e. I was making `memoF = memoize f` and so on and replacing calls to `f`, `g` and `h` with `memoF` and so on.

I finally need to find `minimum [h arr x 0 | x <- [0..dim-1]]`.

What should I be doing?

## 1 Answer

Quoting from the documentation of the memoization package you're using:

Note that most memoization in this style relies on assumptions about the implementation of non-strictness (as laziness) that are not guaranteed by the semantics.

This library relies on a trick that depends in the precise way the Haskell compiler tracks which terms have been evaluated and which haven't in order to trick the compiler into effectively memoizing your function for you. Like many such language implementation hacks, it's not reliable.

The idea behind all these hacks is to pretend that you have a compete table of all possible results, and let lazy evaluation expand only the parts that are necessary. But lazy evaluation isn't intended to work like this, and there no guarantee that you don't end up reevaluating parts multiple times. If it works, that's great. But when it doesn't:

https://github.com/TerrorJack/memo-hashtables implements memoization using a mutable hashtable. It uses `unsafePerformIO` to perform the mutation, but that's OK because it's provable that referential integrity isn't affected. This is much more reliable and I suspect more efficient than the other techniques.