Hi Trent Shipley, the most general trees are given in http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Tree.html A short version is: data Tree a = Tree a [Tree a] Such a tree can have arbitrarily many sub-trees. A leaf could be defined as: leaf a = Tree a [] Note that any node has a value (in contrast to binary trees). Your failed experiment below could be corrected with additional parentheses: data Tree' a = Leaf' a | Node' (Tree' a) (Maybe (Tree' a)) For all this tree versions there is no notion of something like an empty tree. Adding an extra constructor (like "Empty | ...") has the effect that subtrees may also be empty, which may be not desirable if subtrees should be simply omitted if empty. HTH Christian Am 05.09.2018 um 11:53 schrieb 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.

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners