diff in Haskell: clarification

[Andrew J Bromage]

G'day all.

On Mon, Nov 25, 2002 at 12:19:10PM +0100, George Russell wrote:

> I have a confession to make.  Andrew Bromage's list-based code is
> much faster than my array-based code.  So I think I shall end up
> adapting Andrew Bromage's code, even though I do not understand it.

You mean you did understand the Myers algorithm? :-)

Let me know if you'd like a walk-through.  It's actually pretty
straightforward once you've got the hang of it.

For short jobs, such as finding the difference between two Haskell
identifier-sized words, O(N^2) algorithms almost always beat the
Myers O(ND) algorithm by sheer weight of constant factors.  I'd
reserve more complex approaches for more complex data if I were you.

Cheers,
Andrew Bromage