Defining a rose tree (multiway tree) data type

A rose tree relaxes the limitation of at most two children per node. It can have an arbitrary number of elements. Rose trees are common when parsing HTML to represent the Document Object Model (DOM).

Getting ready

We will be representing the following tree in this recipe. The root node has three children:

How to do it...

We will not need any imports for this recipe:

1. The rose tree data type is similar to that of the binary tree, except that instead of left and right children, it will store an arbitrary list of children:

   data Tree a = Node { value  :: a
                      , children  :: [Tree a] } 
                      deriving Show

2. Construct the tree from the preceding diagram and print it out:

   main = do
     let n1 = Node { value = 1, children = [] }
     let n2 = Node { value = 2, children = [] }
     let n3 = Node { value = 3, children = [] }
     let n4 = Node { value = 6, children = [n1, n2, n3] }
     print n4

3. The printed output will be as follows:

   $ runhaskell...