[Haskell-cafe] Strange behavior with listArray

[Alex Stangl]

On Wed, Nov 14, 2012 at 07:39:33AM -0000, oleg at okmij.org wrote:
> dimensional memo table. Luckily, our case is much less general. We do
> have a very nice dynamic programming problem. The key is the
> observation
> 	k' : solveR (i+1) k'
> After a new element, k', is produced, it is used as an argument to the
> solveR to produce the next element. This leads to a significant
> simplification:
> 
> > solve2 :: String -> Array Int Int
> > solve2 w = pI
> >  where
> >  h = length w - 1
> >  wa = listArray (0, h) w
> >  pI = listArray (0,h) $ 0 : [ solveR i (pI!(i-1)) | i <- [1..] ]
> >  solveR :: Int -> Int -> Int
> >  solveR i k = 
> >    let c = wa!i in 
> >    if k > 0 && wa!k /= c
> >       then solveR i (pI!(k-1))
> >       else let k' = if wa!k == c
> >                        then k + 1
> >                        else k
> >            in k'
> >
> > t2s1 = solve2 "the rain in spain"
> > t2s2 = solve2 "aaaaaaaaaaaa"
> > t2s3 = solve2 "abbaabba"

My hat's off to you, sir. This is kind of interesting -- I would
normally consider this indexing transformation as an approach for
defeating memoization, yet in this case it serves as the key that
makes the broader memoization possible, lifting it up a level.

Thanks!

Alex

P.S. A side benefit of this approach is that it's easy to switch
from listArray to array, since we already have the index handy.