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.