def build

bend-lawful-stdlib@0.1.0.0 · src/tree.bend:40

import Base

40# a balanced tree with 2^d leaves f(lo), f(lo+1), ..., so both halves of
41# each parallel call do the same amount of work
42def build(~A: Data, ~f: Nat -> A, +d: Nat, +lo: Nat) -> Tree<A>:
43  match d:
44    case 0n:
45      Tip{f(lo)}
46    case 1n+p:
47      l r = build(~A, ~f, p, lo) build(~A, ~f, p, Nat.add(lo, Nat.pow(2n, p)))
48      Fork{l, r}