edit-dist

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

edit-dist

Andy Larocque
I am a senior who used to do a lot of programming in imperative
languages, and now am new at learning this functional approach.
I have been experimenting with one of Simon Thompson's examples from
his book "The Craft 2e.." ; the edit-distance problem,
and have some questions below I would really appreciate answers to.
Here is the code from his book --

-- A type to represent the different sorts of Edit operations.
data Edit = Change Char |Copy |Delete |Insert Char |Kill
                deriving (Eq,Show)
-- Transforming one string into another, optimally.
transform :: String -> String -> [Edit]
transform [ ] [ ] =  []
transform xs [ ] =  [Kill]
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 ]
--  choose the sequence 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.
cost :: [Edit] -> Int
cost = length . filter (/=Copy)
-----------------------------------------------------

-- When I run the program as listed above,with the simple strings shown,
-- the 'optimal' solution is given by

-- transform "AZ" "5Z"  == [Change '5',Copy]

-- but when I replace 'best' with 'concat' in the transform
-- function to see all the possibilities, some strange solutions appear.
--concat gave me one long list, which i tried to break into all the possible
solutions.
- I numbered the 6 ?? possibilities below, and noticed  #5 doesn't provide
any
-- solution at all, and there are 2 'optimal' solutions.
-----------------------------------------------------------------
--transform "AZ" "5Z"  (using 'concat' instead of 'best' )
--  1 [Delete,Delete,Insert '5',Insert 'Z',
--  2 Insert '5',Copy,
--  3 Change '5',Insert 'Z',
--  4 Insert '5',Delete,Copy,
--  5 Insert 'Z',Kill, Change 'Z',Kill,
--  6 Change '5',Copy]
---------------------------------------
- -First, I really would like to know how to print ALL the possibilities as
a list of lists as they are produced
-- in order by the various function calls, not one long list as concat does.
This would let me see how the
-- recursion steps work as well.
-- Secondly, what is happening in #5 possibility above ? The program never
seems to me to check
-- anywhere that (x:xs) has actually become (y:ys). Since "AZ" is really
seen as 'A' : 'Z' : [ ], then some
--  'terminal' case involving [ ]'s  ends the recursion each time, and that
should produce a correct possible sequence?
-- It appears this can end up as an error.
-- A good explanation will go a long ways in my understanding  of this small
aspect of Haskell.
-- I can only hope one of you has the time and patience to answer this
beginner. Thx.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100730/9c1d89e8/attachment-0001.html
Reply | Threaded
Open this post in threaded view
|

edit-dist

Brent Yorgey-2
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