Tree definition + pointer to its subtree in ocaml

Question

How to define a tree + a pointer to its subtree in OCaml, so adding leaves to this subtree takes constant time?

Answer 1

If you want to use a purely functional representation, the zippers proposed by nlucaroni are really a good solution for presenting the cursor in depth of the data structure, which can be moved or used to update the structure.

If you want to use a solution using mutation in place, you can use mutable data through mutable record fields or links ( ref ) that are derived from it. For instance:

 type 'a tree_cell = {mutable node : 'a tree} and 'a tree = Leaf of 'a | Branch of 'a tree_cell * 'a * 'a tree_cell 

If you hold 'a tree_cell , you can mutate it (in constant time).

 let head {node = (Leaf x | Branch(_, x, _))} = x let duplicate cell = cell.node <- Branch (cell, head cell, {node = cell.node}) 

Edit: in the comments on your question, you seem to indicate your interest in a solution for n-ary trees.

The general n-ary case can be represented as

 type 'a tree_cell = {mutable node: 'a tree} and 'a tree = Branch of 'a * 'a tree_cell list 

while the zipped solution will look (untested code)

 type 'a tree = Branch of 'a * 'a forest and 'a forest = 'a tree list (* the data between the current cursor and the root of the tree *) type 'a top_context = Top | Under of 'a * 'a tree * 'a top_context (* a cursor on the 'data' element of a tree *) type 'a data_cursor = top_context * 'a tree list (* plug some data in the hole and get a tree back *) val fill_data : 'a data_cursor -> 'a -> 'a tree (* a cursor on one of the children of a tree *) type 'a list_zipper = 'a list * 'a list type 'a children_cursor = top_context * 'a * 'a tree list_zipper (* plug some subtree in the hole and get a tree back *) val fill_children : 'a children_cursor -> 'a tree -> 'a tree (* carve a data hole at the root; also return what was in the hole *) val top_data : 'a tree -> 'a data_cursor * 'a (* fill a data hole and get a cursor for the first children in return -- if it exists *) val move_down : 'a data_cursor -> 'a -> ('a children_cursor * 'a tree) option (* fill the children hole and carve out the one on the left *) val move_left : 'a data_cursor -> 'a tree -> ('a data_cursor * 'a tree) option val move_right : 'a data_cursor -> 'a tree -> ('a data_cursor * 'a tree) option (* fill the children hole and get a cursor on the data *) val move_up : 'a children_cursor -> 'a tree -> 'a data_cursor * 'a 

Answer 2

Another (simpler and more general) binary tree solution:

 type 'at = { value : 'a; mutable left : 'at option; mutable right : 'at option; } 

With this type, you can independently set the left and right subtree when they become necessary.