[Haskell-beginners] edit-dist

[Brent Yorgey]

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