[Haskell-cafe] Implementing Mathematica

[oleg at pobox.com]

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.