<meta http-equiv="content-type" content="text/html; charset=utf-8"><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><div>I am a senior who used to do a lot of programming in imperative </div>
<div>languages, and now am new at learning this functional approach.</div><div>I have been experimenting with one of Simon Thompson's examples from</div><div>his book "The Craft 2e.." ; the edit-distance problem,</div>
<div>and have some questions below I would really appreciate answers to.</div><div>Here is the code from his book --</div><div><br></div><div>-- A type to represent the different sorts of Edit operations.</div><div>data Edit = Change Char |Copy |Delete |Insert Char |Kill</div>
<div> deriving (Eq,Show)</div><div>-- Transforming one string into another, optimally.</div><div>transform :: String -> String -> [Edit]</div><div>transform [ ] [ ] = []</div><div>transform xs [ ] = [Kill]</div>
<div>transform [ ] ys = map Insert ys</div><div>transform (x:xs) (y:ys)</div><div> | x==y = Copy : transform xs ys </div><div> | otherwise = best [ Delete : transform xs (y:ys) , </div><div> Insert y : transform (x:xs) ys, </div>
<div> Change y : transform xs ys ] </div><div>-- choose the sequence with the lowest cost.</div><div>best :: [ [Edit] ] -> [Edit]</div><div>best [ x ] = x</div><div>best (x:xs) </div>
<div> | cost x <= cost b = x</div><div> | otherwise = b</div><div> where </div><div> b = best xs </div><div>-- The cost is given by charging one for every operation except copy.</div>
<div>cost :: [Edit] -> Int</div><div>cost = length . filter (/=Copy)</div><div>-----------------------------------------------------</div><div><br></div><div>-- When I run the program as listed above,with the simple strings shown,</div>
<div><div>-- the 'optimal' solution is given by </div><div><br></div><div>-- transform "AZ" "5Z" == [Change '5',Copy] </div></div><div><br></div><div>-- but when I replace 'best' with 'concat' in the transform </div>
<div>-- function to see all the possibilities, some strange solutions appear.</div><div>--concat gave me one long list, which i tried to break into all the possible solutions.</div><div>- I numbered the 6 ?? possibilities below, and noticed #5 doesn't provide any</div>
<div>-- solution at all, and there are 2 'optimal' solutions. </div><div>-----------------------------------------------------------------</div><div>--transform "AZ" "5Z" (using 'concat' instead of 'best' )</div>
<div>-- 1 [Delete,Delete,Insert '5',Insert 'Z',</div><div>-- 2 Insert '5',Copy,</div><div>-- 3 Change '5',Insert 'Z',</div><div>-- 4 Insert '5',Delete,Copy,</div><div>-- 5 Insert 'Z',Kill, Change 'Z',Kill,</div>
<div>-- 6 Change '5',Copy]</div><div>---------------------------------------</div><div>- -First, I really would like to know how to print ALL the possibilities as a list of lists as they are produced</div><div>-- in order by the various function calls, not one long list as concat does. This would let me see how the </div>
<div>-- recursion steps work as well.</div><div>-- Secondly, what is happening in #5 possibility above ? The program never seems to me to check</div><div>-- anywhere that (x:xs) has actually become (y:ys). Since "AZ" is really seen as 'A' : 'Z' : [ ], then some</div>
<div>-- 'terminal' case involving [ ]'s ends the recursion each time, and that should produce a correct possible sequence?</div><div>-- It appears this can end up as an error. </div><div>-- A good explanation will go a long ways in my understanding of this small aspect of Haskell.</div>
<div>-- I can only hope one of you has the time and patience to answer this beginner. Thx.</div><div><br></div></span>