Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Alternative ways define trees (trent shipley)
2. Alternative ways define trees (C Maeder)
----------------------------------------------------------------------
Message: 1
Date: Wed, 5 Sep 2018 02:53:25 -0700
From: trent shipley <[email protected]>
To: Haskell Beginners <[email protected]>
Subject: [Haskell-beginners] Alternative ways define trees
Message-ID:
<caeflyb+wreu-rodpbl2vh+apcggw8w0oco4wf-mvfrzb8zv...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20180905/4ae57049/attachment-0001.html>
------------------------------
Message: 2
Date: Wed, 5 Sep 2018 13:07:36 +0200
From: C Maeder <[email protected]>
To: trent shipley <[email protected]>
Cc: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Alternative ways define trees
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
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
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 123, Issue 3
*****************************************
