[Haskell-cafe] Strange behavior with listArray
Alex Stangl
alex at stangl.us
Wed Nov 14 15:01:17 CET 2012
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.
More information about the Haskell-Cafe
mailing list