benchmarks_game/binary_trees.fz

# https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html#binarytrees
# based on the c program by Jeremy Zerfas
binary_trees is

  node(left node|unit, right node|unit) ref is

  createTree(depth i32) node is
    if(depth > 0) then
      node createTree(depth - 1) createTree( depth - 1)
    else
      node node(unit, unit) unit

  checksum(n node) i32 is
    match n.left
      unit   => 1
      l node =>
        match n.right
          unit   => 1
          r node => (checksum(l) + checksum(r) + 1)

  min_depth := 4
  max_depth := 21
  stretch_tree := createTree(max_depth+1)
  checksum := checksum(stretch_tree)
  say "stretch tree of depth {max_depth+1}\t check: $checksum"

  long_lived_tree := createTree(max_depth)

  for depth in (min_depth..max_depth).filter(x -> x % 2 == 0) do
    iterations := (u64 1) << (max_depth - depth + min_depth).as_u64
    total_trees_checksum := mut 0

    for _ in ((u64 1)..iterations) do
      tree := createTree(depth)
      total_trees_checksum <- total_trees_checksum.get + checksum(tree)

    say "$iterations\t trees of depth {depth}\t check: {total_trees_checksum.get}"

  say "long lived tree of depth $max_depth\t check: {checksum(long_lived_tree)}"