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/