lib.bend checks

raw source on the hub · import 0x19fe2a68aca335d0b2f345065652553f/lib.bend as Lib

Tree — foundational binary tree for Bend. Publish entry for this package. Depends only on Base.

Encoding: Leaf{} (empty) | Node{left, value, right}. Values live at nodes. Quantity: Tree<a, A> is Kind(a), same convention as List/Maybe. Map uses parallel fork on subtrees (Array.map style) when both sides recurse.

1 import

import Base

Types

type Tree source · line 9 · raw

@-a:Quant -> @-A:Kind(a) -> Kind(a)

Leaf
```
@-a:Quant -> @-A:Kind(a) -> Tree<a, A>
```

Node

@-a:Quant -> @-A:Kind(a) -> @left:Tree<a, A> -> @value:A -> @right:Tree<a, A> -> Tree<a, A>

Definitions

def Tree.empty source · line 13 · raw

@-a:Quant -> @-A:Kind(a) -> Tree<a, A>

def Tree.leaf source · line 17 · raw

@-a:Quant -> @-A:Kind(a) -> Tree<a, A>

Alias for the empty leaf constructor (values live on Node).

def Tree.singleton source · line 20 · raw

@-a:Quant -> @-A:Kind(a) -> @x:A -> Tree<a, A>

def Tree.is_empty source · line 23 · raw

@-a:Quant -> @-A:Kind(a) -> @t:Tree<a, A> -> Bool

def Tree.size source · line 30 · raw

@-a:Quant -> @-A:Kind(a) -> @t:Tree<a, A> -> Nat

def Tree.to_list source · line 72 · raw

@-a:Quant -> @-A:Kind(a) -> @t:Tree<a, A> -> List<a, A>

In-order flattening.

Templates

template Tree.map source · line 39 · raw

@-A:Type -> @-B:Type -> @-f:(@_:A -> B) -> @t:Tree<&1, A> -> Tree<&1, B>

Template map, same shape as List.map (affine Tree<A> = Tree<&1, A>). Subtrees mapped in parallel via nl nr = ... ....

template Tree.fold source · line 48 · raw

@-a:Quant -> @-A:Kind(a) -> @-B:Type -> @-leaf:B -> @-node:(@_:B -> @_:A -> @_:B -> B) -> @t:Tree<a, A> -> B

Catamorphism: ~leaf/~node so both branches can reuse them (tree fan-out).

template Tree.reduce.node source · line 62 · raw

@-A:Type -> @-f:(@_:A -> @_:A -> A) -> @lv:A -> @x:A -> @rv:A -> A

Combiner for reduce: (left ⊕ value) ⊕ right.

template Tree.reduce source · line 66 · raw

@-a:Quant -> @-A:Kind(a) -> @-f:(@_:A -> @_:A -> A) -> @-z:A -> @t:Tree<a, A> -> A

Monoid-style reduce with zero (~z duplicated across branches).