[Haskell-beginners] Alternative ways define trees

[trent shipley]

In which I try a couple of ways to declare alternative trees that can have
one or two sub-trees per node, but my attempts don't work.  How do I get
them to work?  Is it preferable to require two trees per node?

Regards,

Trent Shipley

{--

3. Consider the following type of binary trees:

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

Let us say that such a tree is balanced if the number of leaves in the left
and right subtree of every node differs by at most one, with leaves
themselves being trivially balanced. Define a function

balanced :: Tree a -> Bool

that decides if a binary tree is balanced or not.

Hint: first define a function that returns the number of leaves in a tree.

Hutton, Graham. Programming in Haskell (Kindle Locations 3355-3361).
Cambridge University Press. Kindle Edition.

--}

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

-- From Hutton.
-- You can't have an empty tree of a node with no branches.  A degenerate
tree consists of one leaf, when my intuition says a leaf should be required
to have a node.  A node must have two sub-trees, it can't have one
sub-tree.  I have mixed feelings about not being able to have a node with
one sub-tree.

data Tree' a  = Leaf' a  | Node'  (Tree' a)  Maybe (Tree' a) -- First
failed experiment.

-- can this be made with the "data" word, if not what are the options?
This is my preferred constructor.  A node that can contain two trees, or
one tree and "Nothing".

{-------------------------
ex8_3experiments.hs:20:46: error:
    • Expecting one more argument to ‘Maybe’
      Expected a type, but ‘Maybe’ has kind ‘* -> *’
    • In the type ‘Maybe’
      In the definition of data constructor ‘Node'’
      In the data declaration for ‘Tree'’
Failed, modules loaded: none.
---------------------------}

data Tree'' a = Leaf'' a | Node'' (Tree'' a) (Tree'' a) | Node'' (Tree'' a)
-- second failed experiment.

-- This is an inferior option for this, since your tree walking functions
have to worry about a non-existent right path.
-- How would I create this?

{--------------------------
ex8_3experiments.hs:21:59: error:
    Multiple declarations of ‘Node''’
    Declared at: ex8_3experiments.hs:21:28
                 ex8_3experiments.hs:21:59
Failed, modules loaded: none.
---------------------------}


tEven :: Tree Int
tEven = Node (Node (Leaf 1) (Leaf 2))
             (Node (Leaf 3) (Leaf 4))

-- Test :: Tree Int
-- tTest = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3))

{---------------
To make a "canonical" balanced odd tree you have an odd number of two leaf
sub-trees, and one three leaf sub-tree at the end.


      n
     / \
    /   \
   n     n
  / \   / \
 1  2  3   n
          / \
         4   5
----------------}

tOdd :: Tree Int
tOdd = Node (Node (Leaf 1) (Leaf 2))
             (Node (Leaf 3) (Node (Leaf 4) (Leaf 5)))

tUnbal :: Tree Int
tUnbal = Node (Node (Leaf 1)
               (Node (Leaf 2)
                (Node (Leaf 3)
                 (Leaf 4))))
               (Node (Leaf 5) (Leaf 6))

leaves :: Tree a -> Int
leaves (Leaf _) = 1
leaves (Node l r) = leaves l + leaves r

-- From Hutton's solutions.

balanced :: Tree a -> Bool
balanced (Leaf _) = True
balanced (Node l r) = abs(leaves l - leaves r) <= 1
                      && balanced l
                      && balanced r

-- From Hutton's solutions.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20180905/4ae57049/attachment.html>