[Haskell-beginners] Alternative ways define trees

[C Maeder]

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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>