[Haskell-cafe] Strange behavior with listArray

[oleg at okmij.org]

Alex Stangl posed a problem of trying to efficiently memoize a
function without causing divergence:
> solve = let a :: Array Int Int
>             a = listArray (0, 3) (0 : f 0)
>             f k = if k > 0
>                     then f (a!0)
>                     else 0 : f 1
>         in (intercalate " " . map show . elems) a

Daniel Fischer explained the reason for divergence:
> The problem, Alex, is that
>
> f k = if k > 0
>         then f (a!0)
>         else 0 : f 1
>
> is strict, it needs to know the value of (a!0) to decide which branch to take.
> But the construction of the array a needs to know how long the list (0 : f 0)
> is (well, if it's at least four elements long) before it can return the array.
> So there the cat eats its own tail, f needs to know (a part of) a before it
> can proceed, but a needs to know more of f to return than it does.

But the problem can be fixed: after all, f k is a list of integers. A
list is an indexable collection. Let us introduce the explicit index:

> import Data.Array((!),Array,elems,listArray)
> import Data.List(intercalate)
>
> solve = (intercalate " " . map show . elems) a
>  where
>  a :: Array Int Int
>  a = listArray (0, 3) (0 : [f 0 i | i <- [0..]])
>
>  f 0 0 = 0
>  f 0 i = f 1 (i-1)
>  f k i = f (a!0) i

This converges. Here is a bit related problem:
	http://okmij.org/ftp/Haskell/AlgorithmsH.html#controlled-memoization