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.