Non-balanced binary tree

Question

I enjoy reading engaging book "Programming in Haskell" (Second Edition) by Graham Hutton. In Chapter "8 Declaring Types and classes", section "8.4 Recursive types", page 97 bottom I find definition of binary tree:

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

This is nice binary tree but I cannot make it with 0, 2, 4, 5, 6, 8, ... elements. I write following file bst.hs:

data Tree a = Leaf a | Node (Tree a) a (Tree a)
    deriving (Eq, Ord, Show, Read)

I start Haskell Interpreter in folder and load file.

$ ghci
GHCi, version 8.6.4: http://www.haskell.org/ghc/  :? for help
Prelude> :load bst.hs 
[1 of 1] Compiling Main             ( bst.hs, interpreted )
Ok, one module loaded.

Ok, one module loaded. But now I try show "leaf" or "tree" (as Leaf or Node) it is good.

*Main> show (Leaf 3)
"Leaf 3"
*Main> show (Node (Leaf 1) 2 (Leaf 3))
"Node (Leaf 1) 2 (Leaf 3)"

But I fail miserably to make tree with only {1, 2}. How do I write such tree? I tried:

*Main> show (Node (Leaf 1) 2 _)

<interactive>:4:23: error:
    • Found hole: _ :: Tree Integer
    • In the third argument of ‘Node’, namely ‘_’
      In the first argument of ‘show’, namely ‘(Node (Leaf 1) 2 _)’
      In the expression: show (Node (Leaf 1) 2 _)
    • Relevant bindings include
        it :: String (bound at <interactive>:4:1)
*Main> show (Node (Leaf 1) 2)

<interactive>:5:1: error:
    • No instance for (Show (Tree Integer -> Tree Integer))
        arising from a use of ‘show’
        (maybe you haven't applied a function to enough arguments?)
    • In the expression: show (Node (Leaf 1) 2)
      In an equation for ‘it’: it = show (Node (Leaf 1) 2)
*Main> show (Node (Leaf 1) 2 (Node))

<interactive>:6:24: error:
    • Couldn't match expected type ‘Tree Integer’
                  with actual type ‘Tree a0 -> a0 -> Tree a0 -> Tree a0’
    • Probable cause: ‘Node’ is applied to too few arguments
      In the third argument of ‘Node’, namely ‘(Node)’
      In the first argument of ‘show’, namely ‘(Node (Leaf 1) 2 (Node))’
      In the expression: show (Node (Leaf 1) 2 (Node))

Yes I maybe understand how it is wrong but how to make correct?

Only answer to my beginner question is maybe to declare Tree as other suggested Tree on page 99:

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

But how to make original tree with 0, 2, 4, ... elements? Or if not possible, why book not talk about it? There is always must be good reason, so what is reason?

Corwin

You can't. Your modification seems the right way to go – Prehuman

@Harald Thank you for kind help. Could you provide insight why textbook not talk about obvious deficiency? It is not obvious to learning person :-( Still there must be good reason; what is reason? – Corwin

Answer 1

That definition of a binary tree is a full binary tree, which is

"a tree in which every node has either 0 or 2 children."

It would have been clearer if the type had been named more explicitly:

data FullBinaryTree a = Leaf a | Node (FullBinaryTree a) a (FullBinaryTree a)

It's a thing, but often you see another definition of a binary tree that allows for empty nodes as well, as you suggest. The empty node is, however, typically named Empty:

data BinaryTree a = Empty | Node (BinaryTree a) a (BinaryTree a) deriving (Eq, Show)

Both are mathematically valid binary trees, but are obviously not the same. With BinaryTree you can create trees with zero, two, four, etc. values:

Prelude> Empty
Empty
Prelude> Node Empty 42 $ Node Empty 1337 Empty
Node Empty 42 (Node Empty 1337 Empty)
Prelude> Node Empty 42 $ Node (Node Empty 1337 Empty) 2112 (Node Empty 91235 Empty)
Node Empty 42 (Node (Node Empty 1337 Empty) 2112 (Node Empty 91235 Empty))

Scirrhus

Thank you for explanation and link, and for silencing doubts. Embarrassing how long time I try things out when I only need to just read more. – Corwin

Answer 2

Your original definition only allow trees wit odd numbers of elements.

You can fix it with

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

or you can store elements only in leafs

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

Azurite

Thank for attempt to answer. I write same answer in question but still answer is answer. I wait for other answers with more insight into reasons. (Stackoverflow not letting me give +1 to answer, says I am not reputable) – Corwin