 Original article
 Trees in Haskell  Dimitrios Kalemis
Glossary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

tree
An undirected graph in which any two
vertices are connected by exactly one
path, or equivalently a connected acyclic
undirected graph.
forest
An undirected graph in which any two
vertices are connected by at most one
path, or equivalently an acyclic
undirected graph, or equivalently a
disjoint union of trees.
directed acyclic graph
DAG
polytree
directed tree
oriented tree
singly connected network
[DAG]
Underlying undirected graph is a tree.
polyforest
directed forest
oriented forest
[DAG]
Underlying undirected graph is a forest.

Binary tree
Here, Tree
, Nil
and Node
are userdefined.
data Tree a = Nil
 Node a (Tree a) (Tree a)
Sum the values of a tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

module Main where
data MyTree a = MyEmptyNode
 MyFilledNode a (MyTree a) (MyTree a)
deriving (Eq,Ord,Show,Read)
main :: IO ()
main =
do
putStrLn "Begin program"
 This is where I create a new MyTree and fill in the data
let aMyTree = MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
print aMyTree
print (sumMyTree aMyTree)
let bMyTree = MyFilledNode "r" (MyFilledNode "s" MyEmptyNode MyEmptyNode) (MyFilledNode "a" MyEmptyNode MyEmptyNode)
print bMyTree
putStrLn "End program"
 This separate function allows me to sum the values of all the nodes in a tree
sumMyTree :: Num a => MyTree a > a
sumMyTree MyEmptyNode = 0
sumMyTree (MyFilledNode n t1 t2) = n + sumMyTree t1 + sumMyTree t2

Ternary tree
1
2

data MyTree a = MyEmptyNode
 MyFilledNode a (MyTree a) (MyTree a) (MyTree a)

tree (Not an nary tree)
OK, now say that we want to denote a tree that
has a variable number of subnodes for each
node.
We might decide to use a list of nodes for
that, as follows:
data MyTree a = MyEmptyNode
 MyFilledNode a [(MyTree a)]