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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
