zipper/rose_tree

A functional zipper for rose trees (multi-way trees).

This module provides tools to navigate and modify rose tree structures efficiently. The zipper makes it easy to move up, down, and sideways in a tree and to perform local modifications without traversing the entire tree.

Most navigation and local modification operations are $O(1)$ . Going up the tree is $O(k)$ , where $k$ is the number of left siblings of the current node. Operations that convert from or to a full tree structure are $O(n)$ , where $n$ is the number of nodes in the tree.

It supports both a standard RoseTree type and can be adapted to work with any user-defined rose tree structure via an Adapter.

Unlike binary trees, rose trees do not have a separate concept of a leaf node; a node with an empty list of children is considered a leaf. This distinction leads to some differences in the API compared to the zipper/tree module. For example, get_value always succeeds because every location in a rose tree zipper has a value.

Usage

import zipper/rose_tree

let my_tree =
  rose_tree.RoseTree(1, [
    rose_tree.RoseTree(2, []),
    rose_tree.RoseTree(3, []),
  ])

let zipper = rose_tree.from_standard_tree(my_tree)

// Navigate and modify the tree
let assert Ok(zipper) = rose_tree.go_down(zipper)
let zipper = rose_tree.set_value(zipper, 4)
let assert Ok(zipper) = rose_tree.go_up(zipper)

rose_tree.to_standard_tree(zipper)
// => RoseTree(1, [RoseTree(4, []), RoseTree(3, [])])

Types

Adapter

</>

Adapter for converting between a user-defined tree type and the standard rose tree type.

The adapter provides functions to convert between a user-defined tree structure and the standard rose tree representation used by the zipper.

get_value: Extracts the node value from a user tree node.
get_children: Returns a list of standard RoseTree children. Note that the implementer of this function is responsible for converting the user-defined child nodes into the standard RoseTree format.
build_node: Constructs a user tree node from a value and a list of standard RoseTree children.

pub type Adapter(a, user_rose_tree) {
  Adapter(
    get_value: fn(user_rose_tree) -> a,
    get_children: fn(user_rose_tree) -> List(RoseTree(a)),
    build_node: fn(a, List(RoseTree(a))) -> user_rose_tree,
  )
}

Constructors

Adapter(
  get_value: fn(user_rose_tree) -> a,
  get_children: fn(user_rose_tree) -> List(RoseTree(a)),
  build_node: fn(a, List(RoseTree(a))) -> user_rose_tree,
)

RoseTree

</>

A rose tree (multi-way tree) node data structure.

value – the payload stored in this node
children – list of subtrees (nodes with empty list represent leaves)

pub type RoseTree(a) {
  RoseTree(value: a, children: List(RoseTree(a)))
}

Constructors

RoseTree(value: a, children: List(RoseTree(a)))

Zipper

opaque </>

A zipper for navigating and manipulating rose trees.

Conceptually, a Zipper represents a specific location within a rose tree, effectively partitioning it into the current focused subtree and its surrounding context (the path back to the root, including siblings).

All functions are pure and do not modify the input Zipper. They return a new Zipper instance representing the modified state.

pub opaque type Zipper(a)

Values

delete

</>

pub fn delete(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Deletes the current focus node.

The focus moves to the right sibling if it exists, otherwise to the left sibling, otherwise to the parent.

Returns Ok(zipper) with the focus moved to the new location. Returns Error(Nil) if the focus is the root node.

Examples

let tree = RoseTree(0, [RoseTree(1, []), RoseTree(2, []), RoseTree(3, [])])
let zipper = from_standard_tree(tree)
let assert Ok(zipper) = go_down(zipper) // focus on 1
let assert Ok(zipper) = go_right(zipper) // focus on 2

let assert Ok(zipper) = delete(zipper)
get_value(zipper) // focus moved to the right sibling
// => 3

to_standard_tree(zipper)
// => RoseTree(0, [RoseTree(1, []), RoseTree(3, [])])

from_standard_tree

</>

pub fn from_standard_tree(tree: RoseTree(a)) -> Zipper(a)

Creates a zipper from a standard rose tree.

The initial focus of the zipper is the root of the tree.

Examples

let tree = RoseTree(1, [])
let zipper = from_standard_tree(tree)
get_value(zipper)
// => 1

from_tree

</>

pub fn from_tree(
  users_tree: user_tree,
  adapter: Adapter(a, user_tree),
) -> Zipper(a)

Creates a zipper from a user-defined tree using an adapter.

Examples

// Given a user-defined tree `my_tree` and a corresponding `adapter`:
let zipper = from_tree(my_tree, adapter)

// The zipper can now be navigated and modified.
get_value(zipper)
// => root_value

get_standard_tree

</>

pub fn get_standard_tree(zipper: Zipper(a)) -> RoseTree(a)

Gets the current focus subtree as a standard rose tree.

Examples

let child_tree = RoseTree(2, [])
let zipper = from_standard_tree(RoseTree(1, [child_tree]))
let assert Ok(zipper) = go_down(zipper)

get_standard_tree(zipper)
// => RoseTree(2, [])

get_tree

</>

pub fn get_tree(
  zipper: Zipper(a),
  adapter: Adapter(a, user_tree),
) -> user_tree

Gets the current focus subtree as a user-defined tree using an adapter.

Examples

// Given a `zipper` and a corresponding `adapter` for a custom tree type:
let focused_subtree = get_tree(zipper, adapter)

// `focused_subtree` is an instance of the custom tree type.

get_value

</>

pub fn get_value(zipper: Zipper(a)) -> a

Gets the value of the current focus node.

Examples

let zipper = from_standard_tree(RoseTree(42, []))
get_value(zipper)
// => 42

go_down

</>

pub fn go_down(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Moves the focus to the first child of the current node.

Returns Ok(zipper) focused on the first child if it exists. Returns Error(Nil) if the current node is a leaf (has no children).

Examples

let tree = RoseTree(1, [RoseTree(2, [])])
let zipper = from_standard_tree(tree)

let assert Ok(zipper) = go_down(zipper)
get_value(zipper)
// => 2

go_left

</>

pub fn go_left(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Moves the focus to the left sibling of the current node.

Returns Ok(zipper) focused on the left sibling if it exists, or Error(Nil) if there is no left sibling (current node is leftmost).

Examples

let tree = RoseTree(1, [RoseTree(2, []), RoseTree(3, [])])
let zipper = from_standard_tree(tree)
let assert Ok(zipper) = go_down(zipper)
let assert Ok(zipper) = go_right(zipper)
get_value(zipper)
// => 3

let assert Ok(zipper) = go_left(zipper)
get_value(zipper)
// => 2

go_right

</>

pub fn go_right(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Moves the focus to the right sibling of the current node.

Returns Ok(zipper) focused on the right sibling if it exists, or Error(Nil) if there is no right sibling (current node is rightmost).

Examples

let tree = RoseTree(1, [RoseTree(2, []), RoseTree(3, [])])
let zipper = from_standard_tree(tree)
let assert Ok(zipper) = go_down(zipper)
let assert Ok(zipper) = go_right(zipper)
get_value(zipper)
// => 3

go_up

</>

pub fn go_up(zipper: Zipper(a)) -> Result(Zipper(a), Nil)

Moves the focus to the parent node.

Returns Ok(zipper) focused on the parent node if not at the root. Returns Error(Nil) if already at the root.

This function takes $O(k)$ time, where $k$ is the number of left siblings of the current node.

Examples

let tree = RoseTree(1, [RoseTree(2, [])])
let zipper = from_standard_tree(tree)
let assert Ok(zipper) = go_down(zipper)
get_value(zipper)
// => 2

let assert Ok(zipper) = go_up(zipper)
get_value(zipper)
// => 1

insert_child

</>

pub fn insert_child(
  zipper: Zipper(a),
  tree: RoseTree(a),
) -> Zipper(a)

Inserts a new tree as the first child of the current node.

Examples

let zipper = from_standard_tree(RoseTree(1, [RoseTree(3, [])]))
let zipper = insert_child(zipper, RoseTree(2, []))

to_standard_tree(zipper)
// => RoseTree(1, [RoseTree(2, []), RoseTree(3, [])])

insert_child_back

</>

pub fn insert_child_back(
  zipper: Zipper(a),
  tree: RoseTree(a),
) -> Zipper(a)

Inserts a new tree as the last child of the current node.

Examples

let zipper = from_standard_tree(RoseTree(1, [RoseTree(2, [])]))
let zipper = insert_child_back(zipper, RoseTree(3, []))

to_standard_tree(zipper)
// => RoseTree(1, [RoseTree(2, []), RoseTree(3, [])])

insert_left

</>

pub fn insert_left(
  zipper: Zipper(a),
  tree: RoseTree(a),
) -> Result(Zipper(a), Nil)

Inserts a new tree as the immediate left sibling of the current node.

Returns Ok(zipper) with the new sibling inserted. Returns Error(Nil) if the current node is the root.

Examples

let tree = RoseTree(0, [RoseTree(2, [])])
let zipper = from_standard_tree(tree) |> go_down // focus on 2

let new_sibling = RoseTree(1, [])
let assert Ok(zipper) = insert_left(zipper, new_sibling)

to_standard_tree(zipper)
// => RoseTree(0, [RoseTree(1, []), RoseTree(2, [])])

insert_right

</>

pub fn insert_right(
  zipper: Zipper(a),
  tree: RoseTree(a),
) -> Result(Zipper(a), Nil)

Inserts a new tree as the immediate right sibling of the current node.

Returns Ok(zipper) with the new sibling inserted. Returns Error(Nil) if the current node is the root.

Examples

let tree = RoseTree(0, [RoseTree(1, [])])
let zipper = from_standard_tree(tree) |> go_down // focus on 1

let new_sibling = RoseTree(2, [])
let assert Ok(zipper) = insert_right(zipper, new_sibling)

to_standard_tree(zipper)
// => RoseTree(0, [RoseTree(1, []), RoseTree(2, [])])

is_leaf

</>

pub fn is_leaf(zipper: Zipper(a)) -> Bool

Checks if the current focus node is a leaf (has no children).

Examples

let leaf_zipper = from_standard_tree(RoseTree(1, []))
is_leaf(leaf_zipper)
// => True

let node_zipper = from_standard_tree(RoseTree(1, [RoseTree(2, [])]))
is_leaf(node_zipper)
// => False

is_leftmost

</>

pub fn is_leftmost(zipper: Zipper(a)) -> Bool

Checks if the current focus node is the leftmost among its siblings.

Returns True if the node is the root or has no left siblings.

Examples

let tree = RoseTree(0, [RoseTree(1, []), RoseTree(2, [])])
let zipper = from_standard_tree(tree)
let assert Ok(zipper) = go_down(zipper) // focus on 1

is_leftmost(zipper)
// => True

is_rightmost

</>

pub fn is_rightmost(zipper: Zipper(a)) -> Bool

Checks if the current focus node is the rightmost among its siblings.

Returns True if the node is the root or has no right siblings.

Examples

let tree = RoseTree(0, [RoseTree(1, []), RoseTree(2, [])])
let zipper = from_standard_tree(tree)
let assert Ok(zipper) = go_down(zipper)
let assert Ok(zipper) = go_right(zipper) // focus on 2

is_rightmost(zipper)
// => True

is_root

</>

pub fn is_root(zipper: Zipper(a)) -> Bool

Checks if the current focus is the root of the tree.

Examples

let zipper = from_standard_tree(RoseTree(1, [RoseTree(2, [])]))
is_root(zipper)
// => True

let assert Ok(child_zipper) = go_down(zipper)
is_root(child_zipper)
// => False

set_standard_tree

</>

pub fn set_standard_tree(
  zipper: Zipper(a),
  tree: RoseTree(a),
) -> Zipper(a)

Sets the current focus subtree to a new standard rose tree.

This replaces the entire focused subtree with the provided tree.

Examples

let zipper = from_standard_tree(RoseTree(1, [RoseTree(2, [])]))
let new_subtree = RoseTree(99, [])
let zipper = set_standard_tree(zipper, new_subtree)

to_standard_tree(zipper)
// => RoseTree(99, [])

set_tree

</>

pub fn set_tree(
  zipper: Zipper(a),
  tree: user_tree,
  adapter: Adapter(a, user_tree),
) -> Zipper(a)

Sets the current focus subtree to a user-defined tree using an adapter.

Examples

// Given a `zipper`, a `my_subtree` of a user-defined type,
// and a corresponding `adapter`:
let updated_zipper = set_tree(zipper, my_subtree, adapter)

// The focus of `updated_zipper` is now `my_subtree`.

set_value

</>

pub fn set_value(zipper: Zipper(a), value: a) -> Zipper(a)

Sets the value of the current focus node.

Examples

let zipper = from_standard_tree(RoseTree(1, []))
let zipper = set_value(zipper, 42)
get_value(zipper)
// => 42

to_standard_tree

</>

pub fn to_standard_tree(zipper: Zipper(a)) -> RoseTree(a)

Converts a zipper back to a standard rose tree.

This function reconstructs the entire tree by navigating to the root from the current focus and rebuilding the structure along the way.

Examples

let tree = RoseTree(1, [RoseTree(2, [])])
let zipper = from_standard_tree(tree)
let assert Ok(zipper) = go_down(zipper)

to_standard_tree(zipper)
// => RoseTree(1, [RoseTree(2, [])])

to_tree

</>

pub fn to_tree(
  zipper: Zipper(a),
  adapter: Adapter(a, user_tree),
) -> user_tree

Converts a zipper back to a user-defined tree using an adapter.

Examples

// Given a `zipper` and a corresponding `adapter` for a custom tree type:
let my_tree = to_tree(zipper, adapter)

// `my_tree` is now an instance of the custom tree type.

update

</>

pub fn update(
  zipper: Zipper(a),
  updater: fn(a) -> a,
) -> Zipper(a)

Updates the value of the current focus node using a transformation function.

Examples

let zipper = from_standard_tree(RoseTree(10, []))
let zipper = update(zipper, fn(x) { x * 2 })
get_value(zipper)
// => 20