On Fri, Jul 30, 2010 at 04:45:02PM -0400, Andy Larocque wrote:
-- but when I replace 'best' with 'concat' in the transform -- function to see all the possibilities, some strange solutions appear.
That's because replacing 'best' with 'concat' doesn't do what you want at all. It sticks together three edit sequences into one long list, which now does not really correspond to anything -- but notice that transform makes recursive calls to itself, so now the results returned by these recursive calls will be meaningless and all bets are off. If you want to see all solutions returned, you can modify the transform function like this: transform :: String -> String -> [[Edit]] transform [ ] [ ] = [[]] transform xs [ ] = [[Kill]] transform [ ] ys = [map Insert ys] transform (x:xs) (y:ys) | x==y = map (Copy :) $ transform xs ys | otherwise = concat [ map (Delete :) $ transform xs (y:ys) , map (Insert y :) $ transform (x:xs) ys, map (Change y :) $ transform xs ys ] Note that now 'transform' returns a list of edit sequences instead of just one, and then we have to make a few more adjustments, namely wrapping the first few results in a singleton list, and adding calls to 'map', since the recursive calls will return a list of solutions and we want to (say) add 'Delete' to the beginning of each. This gives me something sensible for your example: *Main> transform "AZ" "5Z" [[Delete,Delete,Insert '5',Insert 'Z'], [Delete,Insert '5',Copy], [Delete,Change '5',Insert 'Z'], [Insert '5',Delete,Copy], [Insert '5',Insert 'Z',Kill], [Insert '5',Change 'Z',Kill], [Change '5',Copy]] -Brent