Algebraic data type in Javascript with Flow

tree-no_classes.js

/* @flow */

type Tree<T> =
  | { type: "Node", value: T, left: Tree<T>, right: Tree<T> }
  | { type: "EmptyTree" }

function find<T>(p: (v: T) => boolean, t: Tree<T>): T | void {
  var l, v

  if (t.type === "Node") {
    l = find(p, t.left), v = t.value
    if (typeof l !== 'undefined') {
      return l
    }
    else if (p(v)) {
      return v
    }
    else {
      return find(p, t.right)
    }
  }

  else if (t.type === "EmptyTree") {
    // We would get an error here if we tried to reference `t.value`, `t.left`,
    // or `t.right`, because the "EmptyTree" shape does not have those things.
    return undefined
  }
}

tree.js

type Tree<T> = Node<T> | EmptyTree

class Node<T> {
  value: T;
  left:  Tree<T>;
  right: Tree<T>;
  constructor(value, left, right) {
    this.value = value
    this.left  = left
    this.right = right
  };
}
class EmptyTree {}

function find<T>(p: (v: T) => boolean, t: Tree<T>): T | void {
  var l, v;

  if (t instanceof Node) {
    l = find(p, t.left), v = t.value
    if (typeof l !== 'undefined') {
      return l
    }
    else if (p(v)) {
      return v
    }
    else {
      return find(p, t.right)
    }
  }

  else if (t instanceof EmptyTree) {
    return undefined;
  }
}