Tree

Tree node is very simple tree to record parent-children relationships. You can store any type as a node. When you insert a value, the tree assigns it a unique Int ID and gives it an empty children array. You then wire up parent-child relationships by appending child IDs to a parent. This makes it easy to build trees incrementally.

You can have multiple roots. A root is simply a node that is not a child of another node.

Since everything is keyed by ID, lookups, updates, and removals are straightforward. You can walk the tree depth-first from any starting node, find a node's parent, list all descendants, or fold over every node in the tree.

type Tree node

The Tree holds all the nodes and tracks the Integer ID to node mapping.
empty : Tree node

Create an empty tree with no nodes. tree = Tree.empty Tree.nodeCount tree == 0
insert : node -> Tree node -> { id : Int, tree : Tree node }

Insert a node into the tree. Returns the auto-assigned id and the updated tree. The node starts with no children.

result = Tree.insert "root" Tree.empty
result.id == 0
Tree.nodeCount result.tree == 1

result2 = Tree.insert "child" result.tree
result2.id == 1

Another example:

let
    r1 =
        Tree.insert "root" Tree.empty

    r2 =
        Tree.insert "childA" r1.tree

    r3 =
        Tree.insert "childB" r2.tree

    tree =
        r3.tree
            |> Tree.appendChild r1.id r2.id
            |> Tree.appendChild r1.id r3.id
in
Tree.children r1.id tree
remove : Int -> Tree node -> Tree node

Remove a single node by id. Any other node that lists this id as a child will have it scrubbed from its children array. Does not remove the node's own children from the tree.

tree = Tree.empty
    |> Tree.insert "a" |> .tree
    |> Tree.insert "b" |> .tree

Tree.nodeCount tree == 2
trimmed = Tree.remove 0 tree
Tree.nodeCount trimmed == 1
Tree.member 0 trimmed == False
removeRecursive : Int -> Tree node -> Tree node

Remove a node and all of its descendants recursively. Also scrubs removed ids from any remaining children arrays.

-- Given a tree: root(0) -> child(1) -> grandchild(2)
trimmed = Tree.removeRecursive 1 tree
Tree.member 1 trimmed == False
Tree.member 2 trimmed == False
Tree.children 0 trimmed == []
get :
Int
-> Tree node
-> Maybe { value : node, children : Array Int
}

Get the full entry for a node: its value and children ids.

result = Tree.insert "hello" Tree.empty
Tree.get result.id result.tree
    == Just { value = "hello", children = [] }
Tree.get 999 Tree.empty == Nothing
getNode : Int -> Tree node -> Maybe node

Get just the value of a node, ignoring its children.

result = Tree.insert "hello" Tree.empty
Tree.getNode result.id result.tree == Just "hello"
Tree.getNode 999 Tree.empty == Nothing
children : Int -> Tree node -> Array Int

Get the children ids of a node. Returns an empty array if the node does not exist.

-- Given a tree where node 0 has children [1, 2]:
Tree.children 0 tree == [1, 2]
Tree.children 999 tree == []
childrenNodes : Int -> Tree node -> Array node

Get the values of a node's children, without ids. Returns an empty array if the node does not exist.

-- Given node 0 has children [1, 2]:
Tree.childrenNodes 0 tree == ["childA", "childB"]
childrenWithNodes : Int -> Tree node -> Array { id : Int, node : node }

Get the children of a node, with both id and value for each child. Returns an empty array if the node does not exist.

-- Given node 0 has children [1, 2]:
Tree.childrenWithNodes 0 tree
    == [ { id = 1, node = "childA" }, { id = 2, node = "childB" } ]
parent : Int -> Tree node -> Maybe Int

Find the parent id of a node. Returns Nothing if the node has no parent (i.e. it is a root or does not exist).

-- Given: root(0) -> child(1) -> grandchild(2)
Tree.parent 1 tree == Just 0
Tree.parent 2 tree == Just 1
Tree.parent 0 tree == Nothing
appendChild : Int -> Int -> Tree node -> Tree node

Append a child id to the end of a parent's children array. If the parent does not exist, the tree is returned unchanged.

r1 = Tree.insert "parent" Tree.empty
r2 = Tree.insert "child" r1.tree
tree = Tree.appendChild r1.id r2.id r2.tree
Tree.children r1.id tree == [1]
setChildren : Int -> Array Int -> Tree node -> Tree node

Replace a node's entire children array. If the node does not exist, the tree is returned unchanged.

-- Given node 0 currently has children [1, 2, 3]:
tree2 = Tree.setChildren 0 [2] tree
Tree.children 0 tree2 == [2]
updateNode : Int -> (node -> node) -> Tree node -> Tree node

Update a node's value by applying a function to it. If the node does not exist, the tree is returned unchanged.

-- Given node 0 has value "hello":
tree2 = Tree.updateNode 0 String.toUpper tree
Tree.getNode 0 tree2 == Just "HELLO"
replaceNode : Int -> node -> Tree node -> Tree node

Replace a node's value entirely, preserving its children.

-- Given node 0 has value "hello":
tree2 = Tree.replaceNode 0 "goodbye" tree
Tree.getNode 0 tree2 == Just "goodbye"
Tree.children 0 tree2 == Tree.children 0 tree
map : (node -> mappedNode) -> Tree node -> Tree mappedNode

Transform every node value in the tree. The tree structure (ids and children) is preserved.

-- Given a Tree Int with nodes 0 -> 10, 1 -> 20:
mapped = Tree.map (\n -> n * 2) tree
Tree.getNode 0 mapped == Just 20
Tree.getNode 1 mapped == Just 40
foldl :
(Int -> node -> Array Int -> acc -> acc)
-> acc
-> Tree node
-> acc

Fold over every node in the tree in Dict key order. The folding function receives the id, value, children array, and accumulator.

-- Collect all node values into an array:
values =
    Tree.foldl
        (\id value childIds acc -> Array.pushLast value acc)
        []
        tree
roots : Tree node -> Array Int

Get the ids of all root nodes. A root is any node that is not listed as a child of any other node.

-- Given: root1(0) -> child(2), root2(1)
Tree.roots tree == [0, 1]
descendants : Int -> Tree node -> Array Int

Get all descendant ids of a node, recursively. Does not include the node itself.

-- Given: root(0) -> a(1) -> b(2), root(0) -> c(3)
Tree.descendants 0 tree == [1, 2, 3]
Tree.descendants 1 tree == [2]
Tree.descendants 2 tree == []
depthFirst :
Int
-> Tree node
-> Array { id : Int, value : node , depth : Int
}

Perform a depth-first traversal starting from a given node. Visits the node first, then recurses into each child in order. Returns an array of { id, value, depth } records where depth is relative to the starting node (which has depth 0).

-- Given: root(0,"r") -> a(1,"a") -> b(2,"b")
--                    -> c(3,"c")
Tree.depthFirst 0 tree ==
    [ { id = 0, value = "r", depth = 0 }
    , { id = 1, value = "a", depth = 1 }
    , { id = 2, value = "b", depth = 2 }
    , { id = 3, value = "c", depth = 1 }
    ]
-- You can also start mid-tree:
Tree.depthFirst 1 tree ==
    [ { id = 1, value = "a", depth = 0 }
    , { id = 2, value = "b", depth = 1 }
    ]
toArray :
Tree node
-> Array { id : Int, value : node , children : Array Int
}

Flatten the entire tree into an array of records.

-- Given two nodes in the tree:
Tree.toArray tree ==
    [ { id = 0, value = "root", children = [1] }
    , { id = 1, value = "child", children = [] }
    ]
ids : Tree node -> Array Int

Get all node ids in the tree.

-- Given three nodes with ids 0, 1, 2:
Tree.ids tree == [0, 1, 2]
isMember : Int -> Tree node -> Bool

Check whether a node id exists in the tree.

result = Tree.insert "hi" Tree.empty
Tree.isMember 0 result.tree == True
Tree.isMember 5 result.tree == False
nodeCount : Tree node -> Int

Get the total number of nodes in the tree.

Tree.nodeCount Tree.empty == 0
tree = Tree.empty
    |> Tree.insert "a" |> .tree
    |> Tree.insert "b" |> .tree
Tree.nodeCount tree == 2
prettyPrint : (node -> String) -> Tree node -> String

Return a hierarchical representation of the Tree for debugging purposes. It needs a helper function to convert a node to a String.