Functional datatypes in javascript

One of the ways I have seen is to create a constructor function for each case of the algebraic data type and use instanceof tests to implement the branching. For example, this is how the Roy language implements pattern matching and tagged unions.

var Node = function(a, b){
    //protect against people forgetting to use "new" to call the constructor:
    if(!(this instanceof Node)){ return new Node(a, b) }

    //optionaly do extra type checking, if that is your thing:
    if(!(a instanceof Leaf)){ /*...*/ }
    if(!(b instanceof Leaf)){ /*...*/ }

    //save properties
    this.node1 = a;
    this.node2 = b;
};

var Leaf = function(value){
    /*...*/
    this.value = value;
};

This way, the tag the the internal "__proto__" property, and the payload are the usual instance proeprties in the object.

A reason I like this approach is that it is very "type safe". The internal prototype property is not editable and using a constructor or object (instead of a symbol or string) makes it less subject to name clashes, either with different types or with properties of your object.

Another good point is that, unlike depending on duck typing, this approach also seamlessly works with enums and other situations where the different cases have the same set of properties.

A bad thing about Javascript is that, as in the LISP case, it does not have built in support for destructuring so you might want to make a custom matching function like the following one.

var match_tree = function(x, cases){
    //just a helper function to make things pretty
    if(x instanceof Node){
        return cases.node.call(this, x.node1, x.node2);
    }else if(x instanceof Leaf){
        return cases.leaf.call(this, x.value);
    }else{
        throw new TypeError("pattern match failed");
    }
};

var sum_leaves = function(tree){
    return match_tree(tree, {
        node: function(val){ return val },
        leaf: function(left, right){
           return sum_leaves(left) + sum_leaves(right);
        }
    });
 };

I'm the creator of a language called Roy. Roy is a language with static types, algebraic data types and pattern matching. It also compiles to JavaScript.

Your example would look something like this:

data Tree = Node Tree Tree | Leaf Number

Number is a built-in JavaScript type.

Now we can pattern match on the ADT:

let isNode n = match n
  case (Node a b) = true
  case (Leaf l) = false

let isLeaf l = match l
  case (Leaf l) = true
  case (Node a b) = false

Here's the JavaScript output:

var Node = function(Tree_0, Tree_1) {
    if(!(this instanceof Node)) {
        return new Node(Tree_0, Tree_1);
    }
    this._0 = Tree_0;
    this._1 = Tree_1;
};
var Leaf = function(Number_0) {
    if(!(this instanceof Leaf)) {
        return new Leaf(Number_0);
    }
    this._0 = Number_0;
};
var isNode = function(n) {
    return (function() {
        if(n instanceof Node) {
            var a = n._0;
            var b = n._1;
            return true;
        } else if(n instanceof Leaf) {
            var l = n._0;
            return false;
        }
    })();
};
var isLeaf = function(l) {
    return (function() {
        if(l instanceof Leaf) {
            var l = l._0;
            return true;
        } else if(l instanceof Node) {
            var a = l._0;
            var b = l._1;
            return false;
        }
    })();
};