[Haskell-beginners] 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