Re: [Haskell-cafe] diff implementation in haskell

ketil:

Don Stewart 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?

This looks like the paper, http://www.xmailserver.org/diff2.pdf Page 2, "The algorithm can be refined to use linear space", N and M appear to be the length of the sequences, D is the size of the minimum edit script. -- Don