The Edit Distance Problem
Adapted from the solution by Simon Thompson.
This is a literate Haskell program (.lhs) that can be loaded
like an ordinary Haskell program (.hs) but also supports
the generation of nice documentation. For more details see
http://www.haskell.org/haskellwiki/Literate_programming
A type to represent the different Edit operations.
> data Edit = Change Char |
> Copy |
> Delete |
> Insert Char
> deriving (Eq,Show)
Transforming one string into another, optimally,
> transform :: String -> String -> [Edit]
> transform [] [] = []
> transform xs [] = replicate (length xs) Delete
> transform [] ys = map Insert ys
> transform (x:xs) (y:ys)
> | x==y = Copy : transform xs ys
> | otherwise = best [ Delete : transform xs (y:ys) ,
> Insert y : transform (x:xs) ys ,
> Change y : transform xs ys ]
How do we choose the best sequence? We choose the one with the lowest
cost.
> best :: [[Edit]] -> [Edit]
> best [x] = x
> best (x:xs)
> | cost x <= cost b = x
> | otherwise = b
> where
> b = best xs
The cost is given by charging one for every operation except copy,
which is equivalent to `leave unchanged'.
> cost :: [Edit] -> Int
> cost = length . filter (/=Copy)