[Haskell-cafe] diff implementation in haskell

[Chris Eidhof]

Also, there is a paper about doing a type-safe diff in Agda, http://portal.acm.org/citation.cfm?id=1596614.1596624

I heard rumors that the library will be ported to Haskell.

-chris

On 8 dec 2009, at 15:20, Bayley, Alistair wrote:

>> From: haskell-cafe-bounces at haskell.org
>> [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Ketil Malde
>>
>> Don Stewart <dons at galois.com> writes:
>>
>>
>>>    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?
>
>
> I think the space bounds are O(M+N). Section "4b. A Linear Space
> Refinement" concludes with "Unfortunately, the input sequences A and B
> must be kept in memory, implying that a total of O(M+N) space is
> needed."
>
> BTW, there is a minor improvement to this algorithm (claims to be
> faster, same space usage):
>  http://research.janelia.org/myers/Papers/np_diff.pdf
>
> found via:
>
> http://scholar.google.com/scholar?q=%22An+O(NP)+Sequence+Comparison+Algo
> rithm.%22
>
> I thought this paper was easier to understand.
>
> Alistair
> *****************************************************************
> Confidentiality Note: The information contained in this message,
> and any attachments, may contain confidential and/or privileged
> material. It is intended solely for the person(s) or entity to
> which it is addressed. Any review, retransmission, dissemination,
> or taking of any action in reliance upon this information by
> persons or entities other than the intended recipient(s) is
> prohibited. If you received this in error, please contact the
> sender and delete the material from any computer.
> *****************************************************************
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe