diff in Haskell: clarification

[George Russell]

Andrew J Bromage wrote:
> 
> 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.
What I find really *annoying* is that there doesn't seem to be a worst
case subquadratic method when you are given a linear ordering as well.
I mean there really ought to be one, but I don't see how you can do it
even if all the two strings are allowed to contain is 0s and 1s.  Perhaps
I'm being really stupid somewhere.

I think more than a walk-through I would appreciate it if your code had some
kind of fall-through to avoid it taking forever when someone throws it two
completely different 10000 element lists.