Implement basic addition for binary digits

Binary.re

// This is a useless waste of time. I'm not sure why several years ago
// I thought it would be fun to define digits e.g. type t = Zero | One | Two | etc
// and then implement Semiring (or at least addition) for that type.
//
// But it didn't take long before I ran into the need to "carry the one"
// and I wasn't sure how to proceed.
//
// So here, several years later, I've distilled the problem down to base 2,
// which constantly requires "carrying the one" when adding. To solve this
// I just pattern-match on all of the relevant cases.
//
// Obviously this is is slow and inefficient and I'm not sure why I spent time
// on it, but I guess it was kind of fun?
let rec pow = a =>
  fun
  | 0 => 1
  | 1 => a
  | n => {
    let b = pow(a, n / 2);
    b * b * ((n mod 2 == 0) ? 1 : a);
  };

module Binary = {
  type digit = Zero | One;
  type t = list(digit)

  let to_int = xs => {
    let rec go = (acc, pos) =>
      fun
      | [] => acc
      | [Zero, ...xs] => go(acc, pos + 1, xs)
      | [One, ...xs] => go(acc + (pow(2, pos)), pos + 1, xs);

    go(0, 0, List.rev(xs))
  };

  let add = (a, b) => {
    let rec go = (~carry=false, acc) =>
      fun

      // both sides complete
      | ([], []) => carry ? [One, ...acc] : acc

      // one side complete, other side has zero digit
      | ([], [Zero, ...xs])
      | ([Zero, ...xs], []) => go([carry ? One : Zero, ...acc], ([], xs))

      // one side complete, other side has one digit
      | ([], [One, ...xs])
      | ([One, ...xs], []) => go(~carry, [carry ? Zero : One, ...acc], ([], xs))

      // both sides have values and we need to carry the one
      | ([One, ...xs], [One, ...ys]) => go(~carry=true, [carry ? One : Zero, ...acc], (xs, ys))

      // both sides have values and one of them is a one
      | ([One, ...xs], [Zero, ...ys])
      | ([Zero, ...xs], [One, ...ys]) => go(~carry, [carry ? Zero : One, ...acc], (xs, ys))

      // both sides have values and both are zero
      | ([Zero, ...xs], [Zero, ...ys]) => go([carry ? One : Zero, ...acc], (xs, ys));
      

    go([], (List.rev(a), List.rev(b)))
  };
};

let log_add = (a, b) => {
  open Binary;
  let to_string_int = x => x |> to_int |> string_of_int;

  Js.log2(
    to_string_int(a) ++ " + " ++ to_string_int(b) ++ " =", 
    to_int(add(a, b))
  );
};

log_add([], [Zero]);
log_add([One], []);
log_add([One], [One]);
log_add([One, Zero], [One]);
log_add([One, One, One, One, One], [One, One]);
log_add([One, One, Zero], [One, Zero, One, Zero]);