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-boun...@haskell.org
[mailto:haskell-cafe-boun...@haskell.org] On Behalf Of Ketil Malde
Don Stewart <d...@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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
