[Haskell-cafe] Strange behavior with listArray

[Alex Stangl]

On Tue, Nov 13, 2012 at 08:06:59AM -0000, oleg at okmij.org wrote:
> Alex Stangl posed a problem of trying to efficiently memoize a
> function without causing divergence:
> ...
> 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

Hi Oleg,

That works well for the trivial toy test case that I reduced it down to,
however it's not clear that it works well for the general case in which
significant state is carried across the generation of the successive
list elements. To make this concrete, here is the real solve function,
which computes a border array (Knuth-Morris-Pratt failure function) for
a specified string, before the broken memoization modification is made:

solve :: String -> String
solve w = let h = length w - 1
              wa = listArray (0, h) w
              pI = 0 : solveR (tail w) 0
              solveR :: String -> Int -> [Int]
              solveR [] _ = []
              solveR cl@(c:cs) k = if k > 0 && wa!k /= c
                                     then solveR cl (pI!!(k-1))
                                     else let k' = if wa!k == c
                                                     then k + 1
                                                     else k
                                          in k' : solveR cs k'
          in (intercalate " " . map show) pI

Here solveR corresponds to f in the toy program and pI is the list
I would like to memoize since references to earlier elements could
get expensive for high values of k. It is not obvious to me how to
apply your index transformation to this, such that what you end up
with isn't worse than what we started with.

Thanks,

Alex