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 user-defined.

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 n-ary 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)]