[Haskell-cafe] diff implementation in haskell
ketil at malde.org
Mon Dec 7 03:07:47 EST 2009
Don Stewart <dons at galois.com> writes:
>> Are there pure haskell implementations of diff and diff3 algorithms?
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
Anybody know what the bounds really are?
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe