On Sun, Oct 06, 2002 at 12:16:50PM +0100, Jon Fairbairn wrote: > > > I have already isolated my bug within one function, but > > that function has somewhat funky recursion, and uses an > > array (which I'm none too familiar with in haskell), and > > there aren't any smaller parts that I can see to test. :( > > More seriously: It seems to me likely that this function is > too complicated for your current level of understanding > (which probably means it's simply too complicated, full stop).
Indeed it was (and still is, to an extent). The difficulty was that I was trying to implement the Hunt-Szymanski LCS algorithm without really understanding how it works, just by implementing the algorithm as original 1977 paper. > Often, a better approach than trying to debug a function is > to break the function into smaller parts using higher levels > of abstraction. For example, you say that it involves > "funky" recursion: perhaps it can be rewritten in terms of a > fold or similar? Actually, after looking at it again, I realized that the only funky recursion was that I was implementing the equivalent of two nested iterative loops with one recursive fuction. When I broke this into two functions (one of which was a one-liner, and the other almost an identical copy of the code from the original non-working function), everything started working. I think this advice, together with a day of rest, was just what I needed! It took a while to work out a few other bugs (mostly related to the fact that Hunt and Szymanski assumed two strings of equal length for simplicity), but I now have a working and reasonably fast LCS functions. :) My "diff" command (written to use as a speed test) seems just about 10 to 15 times slower than GNU diff for a particular pair of files, which isn't bad considering that I have done nothing to optimise for speed! btw, thank you also to everyone else who gave me advice! -- David Roundy http://civet.berkeley.edu/droundy/ _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe