Haskell Non-Binary Tree

Question

For a school assignment, I made a binary tree implementation in Haskell as such:

data BinTree = L | N BinTree BinTree deriving (Eq, Show)

-- this function creates the full binary tree of size 2^(n+1) -1
makeBinTree 0 = L
makeBinTree n = N (makeBinTree (n-1)) (makeBinTree (n-1))

Which creates a binary tree in which each parent node has two children. So, makeBinTree 3 has the following output: N (N (N L L) (N L L)) (N (N L L) (N L L))

For my own understanding, I was hoping to make a tree such that each parent node has an arbitrary number of children. I've been stuck for a while on how to proceed.

So the input would be:

makeBinTree 2 3

and the output would be:

N (N L L L) (N L L L) (N L L L)

Any hints of how to do it would be greatly appreciated.

Answer 1

You can do it like in the code below, where you have to specify the tree in reverse Polish notation, and where the numbers are the parity of the trees you're creating.

The program crashes if a tree tries to adopt a number of trees greater than the number of trees in the tree list.

The program produces multiple trees if the last tree created doesn't adopt all trees in the tree list.

data Tree = Branch [Tree] deriving Show

make :: [Int] -> [Tree] -> [Tree]
make [] l2 = l2
make (i1 : l1) l2 = make l1 (Branch (take i1 l2) : drop i1 l2)

Example:

make [0, 0, 2, 0, 2] [] = [Branch [Branch [], Branch [Branch [], Branch []]]]