A tree node carrying some data. Can have children nodes.

Create a node like:

type alias MyData = { .. }


Node { data = MyData .., children = [ .. ] }

Calculates the height of a tree, which is the number of steps of the longest path to a leaf node. Since a tree consists of at least one node, the height of a tree is always at least 1.

Calculates the height of a forest (list of trees), which is the height of the tallest tree in the forest. The calculated height value is 0 if the forest is empty of trees, otherwise always at least 1.

Joins the text representation of all nodes of a tree into a single string, separated by given separator, in the traversal order. Will never be an empty string.

Joins the text representation of all nodes of a forest into a single string, separated by given separator, in left->right order. Can be an empty string in case the forest is empty of trees.

A node annotated with

• zero-based index of the node, in the traversal order
• zero-based level of the node (level is less then the height of the tree the node is in)
• the node itself.

Lists the nodes of a tree, annotated, in the traversal order. Will never be an empty list. See AnnotatedNode for what a node is annotated with.

Lists the nodes of a forest, annotated, in left-right order. Can be an empty list in case the forest is empty of trees. See AnnotatedNode for what a node is annotated with.

Retrieves the list of children of a node.

Retrieves the data stored within a node.

Lists the nodes of a tree, in the traversal order. Will never be an empty list.

Lists the nodes of a forest, in left-right order. Can be an empty list in case the forest is empty of trees.

Fold options to use with foldTree or foldForest.

Think of the first argument to a List.foldl invocation ((a -> b -> b)), which is a function to fold the value of a list item with some previously obtained value.

In the case of folding an entire tree, more aggregator fold functions are needed.

Implement these aggregator functions as if they had the following declarations:

preFoldingThunk

preFoldingThunk : foldState -> Node d -> foldState
preFoldingThunk foldStateFromParent node =
    ...

Function FoldOptions.preFoldingThunk is used just before visiting the children of a node, and its first argument will be either

• the fold state handed down from the parent node
• or the initial fold fold state given to a root foldTree invocation.

postFoldingThunk

postFoldingThunk : foldState -> Node d -> foldState -> foldState
postFoldingThunk foldStateFromParent node previousFoldState =
    ...

Function FoldOptions.postFoldingThunk is used after visiting all children of a node, just before leaving the node.

Its first argument will be the same value given to FoldOptions.preFoldingThunk earlier (as a convenience).

The second argument will be the node we are about to leave.

The third argument will be either

• the fold state calculated by FoldOptions.preFoldingThunk if there are no child nodes of this node,
• or the fold state obtained by processing the last child node.

childrenFoldingThunk

childrenFoldingThunk : foldState -> Node d -> foldState -> foldState
childrenFoldingThunk previousFoldState node nodeFoldState =
    ...

Function FoldOptions.childrenFoldingThunk is used during visiting the children nodes of a node, or when folding a list of nodes by invoking foldForest.

Its first argument will be

• the fold state calculated by FoldOptions.preFoldingThunk if this is the first child node of a parent node,
• or the initial fold state given to the root foldForest invocation if the first node in the list of nodes,
• or the fold state obtained by processing the previous sibling node (= the result of FoldOptions.postFoldingThunk produced by the foldTree invocation on the previous sibling node).

The second argument will be the node that just has been visited.

The third argument will be the fold value obtained from visiting that node.

Fold states example

For a simple tree with root node a,

a
|
+- b
+- c

the following fold states will be calculated for an invocation of foldTree myFoldOptions initialFoldState a:

• fS1 = preFoldingThunk initialFoldState a
• fS2 = preFoldingThunk fS1 b
• fS3 = postFoldingThunk fS1 b fS2
• fS4 = childrenFoldingThunk fS1 b fS3
• fS5 = preFoldingThunk fS4 c
• fS6 = postFoldingThunk fS4 c fS5
• fS7 = childrenFoldingThunk fS4 c fS6
• fS8 = postFoldingThunk initialFoldState a fS7

and return eventually with fold state value fS8.

Default fold options. On the off chance the default implementation of some fold state functions suits you, you may re-use them specifying only what you need:

myFoldOptions =
  { defaultFoldOptions
  | preFoldingThunk = \foldStateFromParent node -> ..
  }

The default fold state function implementations are:

• preFoldingThunk = \foldStateFromParent node -> foldStateFromParent
• postFoldingThunk = \foldStateFromParent node previousFoldState -> previousFoldState
• childrenFoldingThunk = \previousFoldState node nodeFoldState -> nodeFoldState

essentially, the initial fold state value will be handed over, from calculation to calculation, and returned as the final fold state, without change.

Folds a tree, similar to List.foldl. Children of a node are visited from left to right. Specifics of folding / aggregating are controlled by fold options, see FoldOptions and defaultFoldOptions.

Folds a forest (list of trees), visiting trees from left to right of the list.