[Haskell-cafe] diff implementation in haskell

[Ketil Malde]

Don Stewart <dons at galois.com> writes:

>> Are there pure haskell implementations of diff and diff3 algorithms?

>     http://hackage.haskell.org/package/Diff

Wherein we can read:

| This is an implementation of the O(ND) diff algorithm [...]. It is O(mn)
| in space. 

At first I thought 'N' and 'M' would be the lengths of the lists, and
'D' is the number of differences, but then the space bound doesn't make
sense.  I tried to find the reference, but Citeseer is down
(again. sigh).

Anybody know what the bounds really are?

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants