the destination string. The convention is edit
.
edit :: Eq a => Cursor a -> Cursor a -> [Move]
- 1. If both strings have been consumed, then no moves are to be made.
edit (cdone -> True) (cdone -> True) = []
- 2. If the destination string has been fully matched while the source stringhas not, then remove characters from the source string.
edit a@(cdone -> False) b@(cdone -> True) =
(RemoveFromSrc (cix a)):edit (incr a) b
- 3. If the source string has run out of characters while the destination stringstill has characters, insert characters from the destination string.
edit a@(cdone -> True) b@(cdone -> False) =
(InsertFromDest (cix b)):edit a (incr b)
- 4. Otherwise, we have characters remaining in both strings. Try theoptions of (1) replacing a source character with a destination character (2) removing a character from the source and continuing,and (3) if the current characters match, then keep the match and tryto combine characters that come later in the string. We pick thebest out of these using the
argmin
combinator.
edit a b =
let nomatch = argmin movescost
(ReplaceSrcWithDest (cix a) (cix b):edit (incr a) (incr b))
(RemoveFromSrc (cix a):edit (incr a) b)
in case cval a == cval b of
True -> argmin movescost nomatch (edit (incr a) (incr b))
False -> nomatch
The helper used for finding minimum according to a cost model.
argmin :: (a -> Int) -> a -> a -> a
argmin f a a' = if (f a) < (f a') then a else a'