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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
