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.

You're going to need to make a new data type. If you want an arbitrary number, that means you want 0 or more. What common data structure contains 0 or more elements? — bheklilr
– bheklilr, Commented Feb 24, 2014 at 22:10
data BinTree = L | N BinTree BinTree has 2 branches. data BinTree = L | N BinTree BinTree BinTree has 3 branches. But what if you wanted a tree that can have a mixed number of branches? What stays the same between these two definitions and what changes? — bheklilr
– bheklilr, Commented Feb 24, 2014 at 22:26

user1861759 · Accepted Answer · 2014-02-25 01:08:05Z

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

answered Feb 25, 2014 at 1:08

user1861759

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Haskell Non-Binary Tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related