Binary Tree type constructor in Haskell

Question

I'm trying binary tree type constructor which is:

data Tree a = Leaf a | Branch a (Tree a) (Tree a)

How we prove that not all kinds of binary tree can be represented by this constructor? How we improve this definition to cover all types of binary tree? And how it works?

This Tree does not allow empty Tree, therefore, you cannot generate a Tree that is a list in disguise, aka Branch 1 Leaf (Branch 2 Leaf (Branch 3 Leaf)). That being said, I'm not really sure what you're asking about. — Zeta
– Zeta, Commented Apr 28, 2017 at 12:24
@Zeta you meant Branch 1 Leaf (Branch 2 Leaf (Branch 3 Leaf Leaf)). this is not to nitpick, of course, but for the benefit of a casual reader. — Will Ness
– Will Ness, Commented Apr 28, 2017 at 13:51
I rolled back to your first version. It is against the rules of SO to make drastic changes to the question, that invalidate existing answers. — Will Ness
– Will Ness, Commented Apr 28, 2017 at 20:48

Benjamin Hodgson · Accepted Answer · 2017-04-28 12:25:11Z

2

Your Tree a has labels of type a at every Branch and every Leaf constructor. So, for example, Branch 'u' (Branch 'n' (Leaf 'i') (Leaf 'p')) (Leaf 'z') looks like this:

    +-'u'-+
    |     |
 +-'n'-+ 'z'
 |     |
'i'   'p'

That excludes, say, trees with different labels at the nodes and leaves, or trees that are labelled only internally or only externally. For example, this tree has numbers at the leaves and characters at the nodes.

    +-'o'-+
    |     |
 +-'h'-+  9
 |     |
 7     2

(You can use Tree (Either n l) but that doesn't encode the invariant that only ns appear internally and only ls appear externally.)

Since this appears to be a homework assignment I won't tell you what a more general type of tree might look like, but I'm sure you can figure it out.

answered Apr 28, 2017 at 12:25

Benjamin Hodgson

44.9k18 gold badges115 silver badges168 bronze badges

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

Comments

Will Ness · Accepted Answer · 2017-06-11 21:26:55Z

Ask yourself, how many a values can your tree hold? They appear either in leaves or nodes,

data Tree a = Leaf a | Branch a    (Tree a)    (Tree a)

so

num_values  =      1 | (      1 + num_values + num_values  )

It doesn't make much sense in this form, so let's write it as

numvals     =      1 : [      1 +            s          | s <- diagonalize
                                 [ [   n     +     m    | m <- numvals ] 
                                                        | n <- numvals   ] ]

diagonalize :: [[a]] -> [a]
diagonalize ((n:ns):t) = n:go [ns] t
   where
   go as (b:bs) = map head as ++ go (b:map tail as) bs

so that we get

~> take 100 numvals
[1,3,5,5,7,7,7,7,7,9,9,9,9,9,11,9,9,9,11,11,11,11,9,9,11,13,11,13,11,9,9,11,13,1 3,13,13,11,9,9,11,13,13,15,13,13,11,11,11,11,13,13,15,15,13,13,11,11,11,13,13,13 ,15,15,15,13,13,13,11,11,13,15,13,15,15,15,15,13,15,13,11,11,13,15,15,15,15,15,1 5,15,15,15,13,11,11,13,15,15,17,15,15]

but you want 0, 2, 4, ... to appear there as well.

edit: It is easy to fix this, with

data Tree a = Leaf | Branch a (Tree a) (Tree a)

Now

numvals2    =    0 : [      1 +       s          | s <- diagonalize
                          [ [     n   +   m      | m <- numvals2 ] 
                                                 | n <- numvals2   ] ]

and

~> take 100 numvals2
[0,1,2,2,3,3,3,3,3,4,4,4,4,4,5,4,4,4,5,5,5,5,4,4,5,6,5,6,5,4,4,5,6,6,6,6,5,4,4,5 ,6,6,7,6,6,5,5,5,5,6,6,7,7,6,6,5,5,5,6,6,6,7,7,7,6,6,6,5,5,6,7,6,7,7,7,7,6,7,6,5 ,5,6,7,7,7,7,7,7,7,7,7,6,5,5,6,7,7,8,7,7]

Collectives™ on Stack Overflow

Binary Tree type constructor in Haskell

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related