[Haskell-cafe] diff implementation in haskell

[Don Stewart]

ketil:
> 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