Naive Fibonacci, tail recursive, and memoized mutual recursive variants in Reason

fibonacci.re

module Performance {
  external now: unit => float = "performance.now"
}

module BigInt {
  type t
  type op = (t, t) => t

  ;[@mel.send] external toString: t => string = "toString"

  let zero: t = [%mel.raw "0n"]
  let one: t = [%mel.raw "1n"]
  let (+): op = [%mel.raw "(x, y) => x + y"]
}

open BigInt

// stack overflow when n is big
let rec naiveFib = fun
  | 0 => zero
  | 1 => one
  | n when n < 0 => "negative not allowed" |> invalid_arg
  | n => naiveFib(n - 1) + naiveFib(n - 2)

let rec tailFib(~prev=zero, ~result=one) = fun
  | 0 => prev
  | 1 => result
  | n when n < 0 => "negative not allowed" |> invalid_arg
  | n => tailFib(~prev=result, ~result=result + prev, n - 1)

let lazyFib(maxN) = {
  let (^) = Lazy.force
  let rec cacheFib(n) = cache^[n]^
  and cache = lazy {
    fib |> Array.init(maxN)
  } 
  and fib(n) = lazy {
    switch (n) {
      | 0 => zero
      | 1 => one
      | _ => cacheFib(n - 1) + cacheFib(n - 2)
    }
  }
  cacheFib
}

let memoFib = lazyFib(3000)

let test(~name="test", ~until, impl) =
  impl
  |> Array.init(until)
  |> Array.map(toString)
  |> Js.Array.joinWith(", ")
  |> String.cat(name ++ " = ")
  |> Js.log

let profile(~name="test", ~until, ~times, impl) = {
  let start = Performance.now()
  for (_ in 1 to times) (for (i in 1 to until) {
    impl(i - 1) |> ignore
  })
  let seconds = (Performance.now() -. start) /. 1000.
  let operations = times * until |> float_of_int
  let opsPerSec = operations /. seconds |> int_of_float
  Js.log({j|$name until $until in $opsPerSec ops/sec|j})
}

naiveFib |> test(~name="naiveFib until 10", ~until=10)
tailFib |> test(~name="tailFib until 10", ~until=10)
memoFib |> test(~name="memoFib until 10", ~until=10)

let by10(impl, n) = impl(n * 10)
tailFib |> by10 |> test(~name="tailFib by 10", ~until=10)
memoFib |> by10 |> test(~name="memoFib by 10", ~until=10)

naiveFib |> profile(~name="naiveFib", ~until=30, ~times=10)
tailFib |> profile(~name="tailFib", ~until=300, ~times=100)
memoFib |> profile(~name="memoFib", ~until=3000, ~times=1000)