How to define a tree + a pointer to its subtree in OCaml such that adding leaves in this subtree takes constant time?
If you want to use purely functional representation, zippers -- suggested by nlucaroni -- are indeed the good solution to represent a cursor deep down a data structure, that can be moved or used to update the structure.
If you wish for a solution using in-place mutation, you can use mutable data through mutable
record fields, or the references (ref
) that are derived from it. For example:
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 an '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 of 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 zipper solution would look like (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
Another (simpler and more general) solution for a binary tree:
type 'a t = {
value : 'a;
mutable left : 'a t option;
mutable right : 'a t option;
}
With this type, you can set independently the left and right subtree as they become needed.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With