Jon Harrop wrote:
However, I can't think how you might return physically identical results when possible in Haskell.
Perhaps you might be interested then in the following function that non-destructively updates a subterm in a large term, preserving sharing. The function can be used to do a substitution in a term. The function is described in http://okmij.org/ftp/Haskell/Zipper2.lhs beginning with the phrase ``We start therefore with an improved term enumerator that maximally preserves sharing. If no updates were done, the result of the traversal is the original term itself -- rather than its copy. Furthermore, this property holds for each subterm. The new traversal function lets us operate on subterms in pre-order, in-order, or post-order. More importantly, it lets us effectively span a `canonical' spanning tree on a term, so each node can be unambiguously identified. We do not require equality on (sub)terms.'' That was the second article in a series; please see http://okmij.org/ftp/Computation/Continuations.html#zipper for the full series.