Generic Tree

generic-tree.ts

type Tree<A> = Leaf<A> | Branch<A>
type Leaf<A> = {
  kind: 'leaf';
  value: A;
}
type Branch<A> = {
  kind: 'branch';
  left: Tree<A>;
  right: Tree<A>;
}

// -- helper functions --
const leaf = <A>(value: A): Leaf<A> => ({
  kind: 'leaf',
  value,
})
const branch = <A>(left: Tree<A>, right: Tree<A>): Branch<A> => ({
  kind: 'branch',
  left,
  right,
})

// -- map function for tree --
function mapTree<A, B>(map: (val: A) => B, tree: Tree<A>): Tree<B> {
  switch (tree.kind) {
    case 'leaf':
      return leaf(map(tree.value))
    case 'branch':
      return branch(
        mapTree(map, tree.left),
        mapTree(map, tree.right)
      )
  }
}

// -- usage --
const treeA: Tree<number> = branch(
  leaf(1),
  branch(
    leaf(2),
    leaf(3)
  )
)

const treeB = map(t => t + 1, treeA)
treeB === branch(
  leaf(2),
  branch(
    leaf(3),
    leaf(4)
  )
)