Hans Boehm's binary trees benchmark in F#

binarytrees.fs

[<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>]
type Tree = Empty | Node of Tree * Tree

let rec make depth =
  if depth=0 then Empty else Node(make (depth-1), make (depth-1))

let rec check = function
  | Empty -> 1
  | Node(l, r) -> 1 + check l + check r

let test maxDepth =
  let minDepth = 4
  let maxDepth = max (minDepth+2) maxDepth
  let stretchDepth = maxDepth + 1
  let stretchTree = System.Threading.Tasks.Task.Run(fun () ->
    let check = make stretchDepth |> check |> string
    "stretch tree of depth "+string stretchDepth+"\t check: "+check )

  let longLivedTree =
    let tree = make maxDepth
    let check = check tree |> string
    "long lived tree of depth "+string maxDepth+"\t check: "+check, tree
    
  let loopTrees = Array.init ((maxDepth-minDepth)/2+1) (fun d ->
    let d = minDepth+d*2
    let n = 1 <<< (maxDepth - d + minDepth)
    let c =
      let mutable c = 0
      for _ in 1..n do
        c <- c + check(make d)
      c
    string n+"\t trees of depth "+string d+"\t check: "+string c )

  stretchTree.Result |> stdout.WriteLine
  loopTrees |> Array.iter stdout.WriteLine
  fst longLivedTree |> stdout.WriteLine

do
  for maxDepth in 12..16 do
    let timer = System.Diagnostics.Stopwatch.StartNew()
    test maxDepth
    printfn "%fs" timer.Elapsed.TotalSeconds