On Wed, Nov 14, 2012 at 07:39:33AM -0000, o...@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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
