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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
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 > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners > _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Free forum by Nabble | Edit this page |