# Alternative ways define trees Classic List Threaded 2 messages Reply | Threaded
Open this post in threaded view
|

## Alternative ways define trees

 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 functionbalanced :: Tree a -> Boolthat 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:59Failed, modules loaded: none.---------------------------}tEven :: Tree InttEven = 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 InttOdd = Node (Node (Leaf 1) (Leaf 2))             (Node (Leaf 3) (Node (Leaf 4) (Leaf 5)))tUnbal :: Tree InttUnbal = Node (Node (Leaf 1)               (Node (Leaf 2)                (Node (Leaf 3)                 (Leaf 4))))               (Node (Leaf 5) (Leaf 6))leaves :: Tree a -> Intleaves (Leaf _) = 1leaves (Node l r) = leaves l + leaves r-- From Hutton's solutions.balanced :: Tree a -> Boolbalanced (Leaf _) = Truebalanced (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
Reply | Threaded
Open this post in threaded view
|

## Alternative ways define trees

 Hi Trent Shipley, the most general trees are given in http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Tree.htmlA 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