# Implementation notes

All done! The new procedures intended for public are tree-find,
tree-find-equal?, tree-atoms-any?, tree-atoms-every? and tree-remove.

For my own use that are not meant as part of the interface are spair?,
display2 and find-shared-tail. Even though find-shared-tail might seem
generally useful, it doesn't error-check enough for suitability
outside of this specific context.

List-replace, on the other hand, could be useful. I've started using
this library already, and when writing my own tree operators building
on these I did end up using list-replace in them also.

## Suggested change to spec

Oh and remember to add to the spec that it is an error for move-tree
when newparent is a subtree of newparent. That is not handled. The
reverse is handled (albeit in an expensive way) because it is
occasionally useful.

## tree-move

The big savings with the 25 line version of tree-move (the composite
version was 2 lines) is when the shared parentage is really big. I.e.
when there is a loooong shared tree-path for the two operations.

I.o.w when the moving around part is very deep into the tree.

Calling it 25 lines is selling it short because find-share-tail is 6
lines and only used by it. The 9 line
tree-replace-on-path-with-values is also only used by it. So 40
overall.

It got really hairy.
I'm not even sure you save anything.

All of the tree rewriting operators work by finding tree-path and then
zipping up the path with recursive calls to list-replace. What the
long version of tree-move does is that instead of doing this twice,
consecutively, it finds the two paths, merges them into sort of a Y
structure. Works through the sub-paths separately until they meet and
then goes through the shared-tail all the way up to the root.

Composite-tree-move originally was two lines (one signature, one body)
but is now six lines because it, like the full tree-move, handles when
subtree is a subtree of newparent. That special case is dealt with the
same in both versions: expensively. But, hopefully not too expensively
since the change is going to be local and therefore hopefully small.

The theory is that composite-tree-move is more expensive because of
two reasons.

1. It re-inverts the tree, unlike the full version which only uses the
   supplied inversion. (Both do also additionally call invert-tree for
   the special case.)
2. It zips all the way through the root twice, unlike the full version
   which "joins forces" so to speak, for the shared part of the
   tree-path is shared.

It's OK that full version is long & hairy because it has a lot of, uh,
"bespoke" code wheras the composite can just reuse. But, what might
make the full version more expensive is the call to shared-tail (which
I have tried to implement cheaply) and three calls to length. All of
that is on the tree-path, which is a flat linked list of links, not on
the tree itself. So it is my belief that the full tree-move is faster
but only profiling will tell.

### Long let*

Another thing that may make the long version expensive is the nine
(9!!!) variable let*. That's a lot of lambda wrapping depending on the
implementation. For optimization, it could be factored out into a long
series of wrapped non-starred let so that some but not all of the
variable assignments are parallel. This decision is left up to the
specific Scheme implementors out there. One compiler could implement a
long let* more efficiently and another might prefer the series of
non-starred lets.

## Display2

If there is a more idiomatic thing to handle optional port arguments
than my display2 hack, then that's a welcome suggestion &
contribution. My solution there doesn't look particularly elegant.