Is it possible to create a tree in F# where each Node also knows its parent?

Question

The usual tree type looks something like

type Tree<'LeafData,'INodeData> =
   | LeafNode of 'LeafData
   | InternalNode of 'INodeData * Tree<'LeafData,'INodeData> seq

Is it possible to use a tree type that could be used in a purely functional way but still gives access to the parent of each node?

Answer 1

Yes, and no.

In a purely functional setting, its best to lookup "Tree Zipper" (there are all sorts of zippers).

These purely functional data structures allow you to navigate through a data structure (here a tree) without having to embed an explicit reference to 'parent' in the data structure itself.

The tree doesnt know its parent, but the zipper knows the 'path' to a specific node, and so it knows the parent.

for an F# overview see https://tomasp.net/blog/tree-zipper-query.aspx/

(in response to your question ive included many more links and references, but the size of the response means I can't give you exactly what u want off the shelf)

There's a description of zippers in Haskell, but don't be too alarmed its quite accessible http://learnyouahaskell.com/zippers

There's paper somewhere about using differentiation to derive the data structure - though its slightly heavy going. (theres a section of this https://en.wikibooks.org/wiki/Haskell/Zippers towards the bottom that explains the mechanics)

there's this

https://hackage.haskell.org/package/rosezipper-0.2/docs/Data-Tree-Zipper.html

but my haskell is too rusty to be able to translate this very easily

There is a binary tree zipper in FSharpx.Collections.Experimental