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