I recently purchased [Inferring Phylogenies](https://rads.stackoverflow.com/amzn/click/com/0878931775) by Joseph Felsenstein, which is a great book about mathematical and computational methods for inferring phylogenetic trees, and have been playing around with implementing some of the algorithms it describes.

Specifically I'm interested in doing so using in a functional setting with persistent data structures, as a lot of the methods involve walking through a space of possible trees and it would be nice to cheaply remember the history of where we've been via structural sharing (a lá what aphyr does with "worlds" in [this blog post](https://aphyr.com/posts/314-computational-techniques-in-knossos)), easily cache previously computed values for subtrees, etc.

The problem with this is that a lot of the methods involve "rerooting" trees, which I cannot figure out how to do cheaply in a purely functional way. Basically I need some way of capturing the idea that each of the following (using clojure notation, representing trees as vectors):

```
[:a [:b [:c :d]]] 
[:b [:a [:c :d]]]
[:a [:b [:d :c]]]
[:b [:a [:d :c]]]
[[:a :b] [:c :d]] 
[[:c :d] [:a :b]]
[:c [:d [:a :b]]]
[:d [:c [:a :b]]]
[:c [:d [:b :a]]]
[:d [:c [:b :a]]]

```

represent the same data and only differ in where the root is placed; they each represent the unrooted tree:

```
a   b
 \ /
  |
 / \
c   d

```

I'd like to be able to navigate into one of these trees with a zipper and then call a function `reroot`, which will return a new tree that's zipped up in such a way that the root is at the current `loc`.

In the book Felsenstein describes a data structure for a cheaply rerootable tree, which looks something like the following hastily made diagram

![terrible diagram](https://i.stack.imgur.com/KNFFl.jpg)

in which the circles are structs and the arrows are pointers. The rings of structs are internal nodes on the tree, and once we have a reference to one, we can move the root there by doing some pointer swapping. Unfortunately this is a mutating operation and requires mutual references, both of which are impossible in a purely functional setting.

I feel like there should be a way to do what I want using zippers, but I've been playing around with `clojure.core/zip` for a while and getting nowhere.

Does anyone know of an implementation of something like this or have suggestions for things I should read / papers I should look at / ideas for how to do this?

Thanks!