<div dir="ltr"><div>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?</div><div><br></div><div>Regards,</div><div><br></div><div>Trent Shipley</div><div><br></div><div>{--</div><div><br></div><div>3. Consider the following type of binary trees:</div><div><br></div><div><font face="monospace">data Tree a = Leaf a | Node (Tree a) (Tree a)</font></div><div><br></div><div>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</div><div><br></div><div><font face="monospace">balanced :: Tree a -> Bool</font></div><div><br></div><div>that decides if a binary tree is balanced or not.</div><div><br></div><div>Hint: first define a function that returns the number of leaves in a tree.</div><div><br></div><div>Hutton, Graham. Programming in Haskell (Kindle Locations 3355-3361). Cambridge University Press. Kindle Edition.</div><div><br></div><div>--}</div><div><br></div><div><font face="monospace">data Tree a   = Leaf a   | Node   (Tree a)   (Tree a)</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">-- From Hutton.  </font></div><div><font face="monospace">-- 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.</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">data Tree' a  = Leaf' a  | Node'  (Tree' a)  Maybe (Tree' a) -- First failed experiment.</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">-- 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".</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">{-------------------------</font></div><div><font face="monospace">ex8_3experiments.hs:20:46: error:</font></div><div><font face="monospace">    • Expecting one more argument to ‘Maybe’</font></div><div><font face="monospace">      Expected a type, but ‘Maybe’ has kind ‘* -> *’</font></div><div><font face="monospace">    • In the type ‘Maybe’</font></div><div><font face="monospace">      In the definition of data constructor ‘Node'’</font></div><div><font face="monospace">      In the data declaration for ‘Tree'’</font></div><div><font face="monospace">Failed, modules loaded: none.</font></div><div><font face="monospace">---------------------------}</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">data Tree'' a = Leaf'' a | Node'' (Tree'' a) (Tree'' a) | Node'' (Tree'' a) -- second failed experiment.</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">-- This is an inferior option for this, since your tree walking functions have to worry about a non-existent right path.</font></div><div><font face="monospace">-- How would I create this?</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">{--------------------------</font></div><div><font face="monospace">ex8_3experiments.hs:21:59: error:</font></div><div><font face="monospace">    Multiple declarations of ‘Node''’</font></div><div><font face="monospace">    Declared at: ex8_3experiments.hs:21:28</font></div><div><font face="monospace">                 ex8_3experiments.hs:21:59</font></div><div><font face="monospace">Failed, modules loaded: none.</font></div><div><font face="monospace">---------------------------}</font></div><div><font face="monospace"><br></font></div><div><font face="monospace"><br></font></div><div><font face="monospace">tEven :: Tree Int</font></div><div><font face="monospace">tEven = Node (Node (Leaf 1) (Leaf 2))</font></div><div><font face="monospace">             (Node (Leaf 3) (Leaf 4))</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">-- Test :: Tree Int</font></div><div><font face="monospace">-- tTest = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3))</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">{---------------</font></div><div><font face="monospace">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.</font></div><div><font face="monospace"><br></font></div><div><font face="monospace"><br></font></div><div><font face="monospace">      n</font></div><div><font face="monospace">     / \</font></div><div><font face="monospace">    /   \</font></div><div><font face="monospace">   n     n</font></div><div><font face="monospace">  / \   / \</font></div><div><font face="monospace"> 1  2  3   n</font></div><div><font face="monospace">          / \</font></div><div><font face="monospace">         4   5</font></div><div><font face="monospace">----------------}</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">tOdd :: Tree Int</font></div><div><font face="monospace">tOdd = Node (Node (Leaf 1) (Leaf 2))</font></div><div><font face="monospace">             (Node (Leaf 3) (Node (Leaf 4) (Leaf 5)))</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">tUnbal :: Tree Int</font></div><div><font face="monospace">tUnbal = Node (Node (Leaf 1)</font></div><div><font face="monospace">               (Node (Leaf 2)</font></div><div><font face="monospace">                (Node (Leaf 3)</font></div><div><font face="monospace">                 (Leaf 4))))</font></div><div><font face="monospace">               (Node (Leaf 5) (Leaf 6))</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">leaves :: Tree a -> Int</font></div><div><font face="monospace">leaves (Leaf _) = 1</font></div><div><font face="monospace">leaves (Node l r) = leaves l + leaves r</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">-- From Hutton's solutions.</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">balanced :: Tree a -> Bool</font></div><div><font face="monospace">balanced (Leaf _) = True</font></div><div><font face="monospace">balanced (Node l r) = abs(leaves l - leaves r) <= 1</font></div><div><font face="monospace">                      && balanced l</font></div><div><font face="monospace">                      && balanced r</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">-- From Hutton's solutions.</font></div></div>