Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

btree

btree is a type that represents a binary tree. Every btree is either a Node that contains a value and two children (Node or Nil), or it is Nil and contans no values.

<span class='hljs-keyword'>type</span> t = <span class='hljs-keyword'>fn</span> <span class='hljs-type'>I</span> <span class='hljs-keyword'>=&gt;</span> <span class='hljs-punctuation'>(</span><span class='hljs-type'>Node</span> <span class='hljs-type'>of</span> <span class='hljs-type'>I</span><span class='hljs-punctuation'>,</span> <span class='hljs-punctuation'>(</span><span class='hljs-type'>t</span> <span class='hljs-type'>I</span><span class='hljs-punctuation'>)</span><span class='hljs-punctuation'>,</span> <span class='hljs-punctuation'>(</span><span class='hljs-type'>t</span> <span class='hljs-type'>I</span><span class='hljs-punctuation'>)</span><span class='hljs-punctuation'>)</span> | <span class='hljs-type'>Nil</span>

Functions

Nil: unit -> (btree '0)

The constructor for a Nil btree. This is used to represent an empty child.

Example

# <span class='hljs-keyword'>module</span> demo = 
  <span class='hljs-keyword'>let</span> my_empty_tree = <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span><span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span>
# <span class='hljs-keyword'>end</span>

Node: '0 * btree '0 * btree '0 -> btree '0

The constructor for a Node btree.

Example

# <span class='hljs-keyword'>module</span> demo = 
  <span class='hljs-keyword'>let</span> my_tree = <span class='hljs-title function_'>btree</span><span class='hljs-punctuation'>:</span>Node <span class='hljs-punctuation'>(</span><span class='hljs-variable constant_'>1</span><span class='hljs-punctuation'>,</span> <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span><span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span><span class='hljs-punctuation'>,</span> <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span><span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span><span class='hljs-punctuation'>)</span>
  <span class='hljs-comment'>(* my_tree ==  1
   *            / \
   *          nil nil
   *)</span>
# <span class='hljs-keyword'>end</span>

insert: '0 -> ('0 -> '0 -> boolean) -> (btree '0) -> (btree '0)

Returns a copy of the passed tree with the passed value inserted according to the passed operation.

Notes

insert checks if the function is true with the passed value and the current tree value, if it is, it will attempt to insert the passed value as the left child. Otherwise, it will attempt to insert the passed value as the right child. This process is repeateded recursively until a Node has a Nil child in the appropriate position.

Example

# <span class='hljs-keyword'>module</span> demo = 
  <span class='hljs-keyword'>let</span> my_tree = <span class='hljs-title function_'>btree</span><span class='hljs-punctuation'>:</span>Node <span class='hljs-punctuation'>(</span><span class='hljs-variable constant_'>5</span><span class='hljs-punctuation'>,</span> <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span><span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span><span class='hljs-punctuation'>,</span> <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span><span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span><span class='hljs-punctuation'>)</span>
  <span class='hljs-keyword'>let</span> my_new_tree = <span class='hljs-title function_'>btree</span><span class='hljs-punctuation'>:</span>insert <span class='hljs-variable constant_'>2</span> <span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-params'>b</span> <span class='hljs-keyword'>=&gt;</span> a <span class='hljs-operator'>&lt;</span> b<span class='hljs-punctuation'>)</span> my_tree
  <span class='hljs-comment'>(* my_new_tree == 5
  *                / \
  *               2  
  *)</span>
  <span class='hljs-keyword'>let</span> my_newer_tree = <span class='hljs-title function_'>btree</span><span class='hljs-punctuation'>:</span>insert <span class='hljs-variable constant_'>7</span> <span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-params'>b</span> <span class='hljs-keyword'>=&gt;</span> a <span class='hljs-operator'>&lt;</span> b<span class='hljs-punctuation'>)</span> my_new_tree
  <span class='hljs-comment'>(* my_newer_tree == 5
  *                  / \
  *                 2   7 
  *                / \ / \ 
  *)</span>
  <span class='hljs-keyword'>let</span> my_newest_tree = <span class='hljs-title function_'>btree</span><span class='hljs-punctuation'>:</span>insert <span class='hljs-variable constant_'>9</span> <span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-params'>b</span> <span class='hljs-keyword'>=&gt;</span> a <span class='hljs-operator'>&lt;</span> b<span class='hljs-punctuation'>)</span> my_newer_tree
  <span class='hljs-comment'>(* my_newest_tree == 5
  *                   / \
  *                  2   7 
  *                 / \ / \
  *                        9
  *)</span>
# <span class='hljs-keyword'>end</span>

iterate_tree_df: ('0 -> unit) -> (btree '0) -> unit

Runs the passed function on each element in the tree depth-first, then returns unit.

Example

# <span class='hljs-keyword'>module</span> demo = 
  <span class='hljs-keyword'>let</span> lt = <span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-params'>b</span> <span class='hljs-keyword'>=&gt;</span> a <span class='hljs-operator'>&lt;</span> b  
  <span class='hljs-keyword'>let</span> my_tree = <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span> <span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span> <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>5</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>2</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>7</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>8</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>3</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>1</span> lt
  <span class='hljs-keyword'>let</span> <span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span> = <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>iterate_tree_df</span> <span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-keyword'>=&gt;</span> string<span class='hljs-punctuation'>:</span>from_int <span class='hljs-operator'>|&gt;</span> <span class='hljs-title function_'>std</span><span class='hljs-punctuation'>:</span>print_string<span class='hljs-punctuation'>)</span> my_tree
  <span class='hljs-comment'>(* my_tree == 5
  *            / \
  *           2   7 
  *          / \ / \
  *         1  3    8 
  *)</span>
  <span class='hljs-comment'>(* prints 123578 *)</span>
# <span class='hljs-keyword'>end</span>

iterate_tree_bf: ('0 -> unit) -> (btree '0) -> unit

Runs the passed function on each element in the tree breadth-first, then returns unit.

Example

# <span class='hljs-keyword'>module</span> demo = 
  <span class='hljs-keyword'>let</span> lt = <span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-params'>b</span> <span class='hljs-keyword'>=&gt;</span> a <span class='hljs-operator'>&lt;</span> b  
  <span class='hljs-keyword'>let</span> my_tree = <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span> <span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span> <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>5</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>2</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>7</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>8</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>3</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>1</span> lt
  <span class='hljs-keyword'>let</span> <span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span> = <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>iterate_tree_bf</span> <span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-keyword'>=&gt;</span> <span class='hljs-title class_'>string</span><span class='hljs-punctuation'>::</span>from_int <span class='hljs-operator'>|&gt;</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>print_string</span><span class='hljs-punctuation'>)</span> my_tree
  <span class='hljs-comment'>(* my_tree == 5
  *            / \
  *           2   7 
  *          / \ / \
  *         1  3    8 
  *)</span>
  <span class='hljs-comment'>(* prints 521378 *)</span>
# <span class='hljs-keyword'>end</span>

map_tree: ('0 -> '1) -> (btree '0) -> (btree '1)

Returns a copy of the passed tree with the passed function applied to each element.

Examples

# <span class='hljs-keyword'>module</span> demo = 
  <span class='hljs-keyword'>let</span> lt = <span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-params'>b</span> <span class='hljs-keyword'>=&gt;</span> a <span class='hljs-operator'>&lt;</span> b  
  <span class='hljs-keyword'>let</span> my_tree = <span class='hljs-title class_'>btree</span><span class='hljs-punctuation'>::</span><span class='hljs-title function_'>Nil</span> <span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span> <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>5</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>2</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>7</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>8</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>3</span> lt <span class='hljs-operator'>|&gt;</span> <span class='hljs-variable constant_'>1</span> lt
  <span class='hljs-comment'>(* my_tree == 5
  *            / \
  *           2   7 
  *         / \ / \
  *        1  3    8 
  *)</span>
  <span class='hljs-keyword'>let</span> my_mapped_tree = <span class='hljs-title function_'>btree</span><span class='hljs-punctuation'>:</span>map_tree <span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> <span class='hljs-params'>a</span> <span class='hljs-keyword'>=&gt;</span> a <span class='hljs-operator'>*</span> <span class='hljs-variable constant_'>2</span><span class='hljs-punctuation'>)</span> my_tree
  <span class='hljs-comment'>(* my_mapped_tree == 10
  *                    / \
  *                   4   14 
  *                  / \ / \
  *                 2  6    16 
  *)</span>
# <span class='hljs-keyword'>end</span>