Here’s a simple Haskell program declaring
Tree data type with
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
Tree with higher order functions. The trick used here is to pass
p as arguments to data constructors. Only one of these 3 arguments is used by each data constructor:
bis a value for
lis a function taking an integer
nas an argument and returns a value for
pis a function taking left and right trees as arguments and returns a value for
(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
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
Tree respectively. If
Bud, it returns 0. If
w is a
Leaf node, it returns
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);