[Haskell-cafe] diff implementation in haskell

Don Stewart dons at galois.com
Mon Dec 7 03:14:00 EST 2009

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

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

More information about the Haskell-Cafe mailing list