JavaScript lacks algebraic data type, but we can emulate it because JavaScript has first-class functions.

Here’s a simple Haskell program declaring `Tree`

data type with `Bud`

, `Leaf`

and `Tree`

data constructors. `treeSum`

calculates the sum of leaf nodes by iterating all nodes in the given tree.

data Tree = Bud | Leaf Int | Tree Tree Tree deriving Show treeSum :: Tree -> Int treeSum Bud = 0 treeSum (Leaf n) = n treeSum (Tree t1 t2) = treeSum t1 + treeSum t2 main = do let t0 = treeSum Bud putStrLn $ show t0 let t1 = treeSum (Leaf 2) putStrLn $ show t1 let t2 = treeSum (Tree (Leaf 3) (Tree (Leaf 5) Bud)) putStrLn $ show t2

In JavaScript, we can emulate the data constructors of `Tree`

with higher order functions. The trick used here is to pass `b`

, `l`

and `p`

as arguments to data constructors. Only one of these 3 arguments is used by each data constructor:

`b`

is a value for`Bud`

.`l`

is a function taking an integer`n`

as an argument and returns a value for`Leaf`

.`p`

is a function taking left and right trees as arguments and returns a value for`Tree`

.

(ES6 let and arrow are used for conciseness.)

let Bud = b => l => p => b; let Leaf = n => b => l => p => l(n); let Tree = t1 => t2 => b => l => p => p(t1(b)(l)(p))(t2(b)(l)(p))

You can think of `Bud`

as a value by itself. For `Leaf`

and `Tree`

, you can create each node by partially applying arguments.

var t0 = Bud; var t1 = Leaf(2); var t2 = Tree(Leaf(2), Bud);

With this encoding scheme, defining `treeSum`

is trivial. You just need to pass 3 functions to handle `Bud`

, `Leaf`

and `Tree`

respectively. If `w`

is `Bud`

, it returns 0. If `w`

is a `Leaf`

node, it returns `n`

. If `w`

is a `Tree`

node, it returns the sum of left and right trees.

let treeSum = w => w(0)(n => n)(x => y => x + y);

The client code looks almost the same to Haskell.

var v0 = treeSum(Bud); console.log(v0); var v1 = treeSum(Leaf(2)); console.log(v1); var v2 = treeSum(Tree(Leaf(3))(Tree(Leaf(5))(Bud))); console.log(v2);