CODEWITHSUNDEEP
haskelltypes
SOAP
SOAP

Reputation: 179

Data type for Tree in Haskell

For a data type of a binary tree you can write something like this:

data Tree a = Nil | Node a (Tree a) (Tree a)

So if I do want to include trees, with Nodes having more than just two children, how could the data type possibly look like?

Upvotes: 12

Views: 14150

Answers (2)

chepner
chepner

Reputation: 532398

You can either have a fixed branching factor:

data BinaryTree a  = BTNil 
                   | BTNode a (BinaryTree a) (BinaryTree a)

data TernaryTree a = TTNil
                   | TTNode a (TernaryTree a) (TernaryTree a) (TernaryTree a)

data QuadTree a    = QTNil
                   | QTNode a (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a)

-- etc

(Note that QuadTree isn't a great name for a general tree with a branching factor of 4, since there is a specific data structure with that name.)

or you can simply use a rose tree, which stores an arbitrary list of children at each node.

data RoseTree a = RTNil | RTNode a [RoseTree a]

There is some duplication here, as RTNil is only needed to store an explicit empty tree. Leaf nodes are just RTNode a []. (Consider what difference, if any, you would assign to the values RTNode 3 [], RTNode 3 [RTNil], RTNode 3 [RTNil, RTNil], etc.)

Upvotes: 14

behzad.nouri
behzad.nouri

Reputation: 78021

A lesser known technique is Left-child right-sibling where you can use the exact same type to encode trees with more than two children per node:

left-child-right-sibiling

data Tree a
  = Nil
  | Node a (Tree a) (Tree a) -- value, left child, right sibling

The alternative [Tree a] does not have a performance advantage, since Haskell lists are linked lists.

Upvotes: 18

Related Questions