Memoization of interdependent haskell functions

Question

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?

Answer 1

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.