tree.comp

/**
Binary search tree
Operations for a minimal binary tree with shape-dispatched
insertion, lookup, and in-order traversal.

Highlights

- Immutable trees share unchanged nodes across generations, inserting a value only rebuilds the path from root to insertion point
- `@flat` wrapper on `tree-values` concatenates multiple expressions into a single sequence, the in-order traversal reads as three lines: left, self, right
- `~nil` vs `~tree` overloads replace null checks, the base case and recursive case are separate function definitions, not branches in one function
- `@update` on `tree-insert ~tree` means the body only returns the one child field that changed, the other child and value pass through

*/

!shape tree ~{value~num left~branch right~branch}
!shape branch ~(tree | nil) = nil


!main console [
	{5 3 8 1 7 9}
	| reduce initial=nil tree-insert
	| tree-values
	| output
]


/// Add new value into tree, dispatched on nil vs tree
!pure empty.tree-insert ~nil [
	!param value ~num

	{value} | tree
]

!pure tree-insert ~tree @update(
	!param value ~num

	!on value <> $.value
	~less {left = [$.left | tree-insert value]}
	~any {right = [$.right | tree-insert value]}
)


/// Check if tree contains value
!pure empty.tree-contains ~nil (
	!param value ~num
	false
)

!pure tree-contains ~tree (
	!param value ~num

	!on value <> $.value
	~less [$.left | tree-contains value]
	~greater [$.right | tree-contains value]
	~equal true
)


/// Iterate values from tree in order
!pure empty.tree-values ~nil {
}

!pure tree-values ~tree @flat {
	[$.left | tree-values]
	{$.value}
	[$.right | tree-values]
}