Alex Stangl wrote: > 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. Ok, let's apply a few program transformations. First we notice that the list pI must have the same length as the string w. Since we have already converted the string w to an array, wa, we could index into that array. We obtain the following version. > solve1 :: String -> String > solve1 w = (intercalate " " . map show) pI > where > h = length w - 1 > wa = listArray (0, h) w > pI = 0 : solveR 1 0 > solveR :: Int -> Int -> [Int] > solveR i k | i > h = [] > 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' : solveR (i+1) k' > > t1s1 = solve1 "the rain in spain" > t1s2 = solve1 "aaaaaaaaaaaa" > t1s3 = solve1 "abbaabba" We don't need to invent an index: it is already in the problem. The unit tests confirm the semantics is preserved. The _general_ next step is to use the pair of indices (i,k) as the key to the two 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" The unit tests pass. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe