[Haskell-cafe] Strange behavior with listArray

Alex Stangl alex at stangl.us
Wed Nov 14 03:21:00 CET 2012


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



More information about the Haskell-Cafe mailing list