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.