Empty or Tree?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Empty or Tree?

bahadýr altan
Hello everyone. I'm trying to write a code which works on binary trees. When I write code like this ?with a tree with empty nodes :

data Tree ?= ?Empty | Node ?Integer Tree Tree

function Node a (Node b Empty Empty)??(Node c Empty Empty)

it works fine.?
But when I try to create a more generic code like this ?which could ?work with trees who don't have empty nodes in grandchild level :?

function Node a (Node b Tree Tree)??(Node c Tree Tree )?


I get this error :?Undefined data constructor "Tree"

Can you help me with creating more generic code please?
Thanks
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120310/aa5a121d/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Empty or Tree?

Aditya Manthramurthy
I think this is because "Tree" is a data type and not a data constructor.
According to your definition of Tree, Empty and Node are the constructors.

Node a (Node b (Node c Empty Empty) (Node d Empty Empty)) (Node e (Node f
Empty Empty) (Node g Empty Empty))

is a valid tree if a, b, c, d, e, f, g are integers.

Hope this helps.

--
Aditya.

On 10 March 2012 15:58, bahad?r altan <doaltan at yahoo.co.uk> wrote:

> Hello everyone. I'm trying to write a code which works on binary trees.
> When I write code like this  with a tree with empty nodes :
>
> data Tree  =  Empty | Node  Integer Tree Tree
>
> function Node a (Node b Empty Empty)  (Node c Empty Empty)
>
> it works fine.
> But when I try to create a more generic code like this  which could  work
> with trees who don't have empty nodes in grandchild level :
>
> function Node a (Node b Tree Tree)  (Node c Tree Tree )
>
> I get this error : Undefined data constructor "Tree"
>
> Can you help me with creating more generic code please?
> Thanks
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120310/9588e1d2/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

Empty or Tree?

Adrien Haxaire-2
In reply to this post by bahadýr altan
On Sat, Mar 10, 2012 at 10:28:43AM +0000, bahad?r altan wrote:

> Hello everyone. I'm trying to write a code which works on binary trees. When I write code like this ?with a tree with empty nodes :
>
> data Tree ?= ?Empty | Node ?Integer Tree Tree
>
> function Node a (Node b Empty Empty)??(Node c Empty Empty)
>
> it works fine.?
> But when I try to create a more generic code like this ?which could ?work with trees who don't have empty nodes in grandchild level :?
>
> function Node a (Node b Tree Tree)??(Node c Tree Tree )?
>
>
> I get this error :?Undefined data constructor "Tree"
>
> Can you help me with creating more generic code please?
> Thanks

Hello,

You defined a Tree as an Empty or a Node. So to build it, you can use only Empty or Node, which is what you do in your first function. In the second one however, you use Tree, which is the type, not the constructor.

If you use them it will look like :

function Node a (Node b t1 t2) (Node c t3 t4)
  where
    t1 = Empty
    t2 = Node d Empty Empty
    ...

Adding the function signature before your function implementatio help sort things out for the parameters you need: t1, to t4, to a to c, etc

Hope that helps.
Adrien

--
Adrien Haxaire
www.adrienhaxaire.org | @adrienhaxaire


Reply | Threaded
Open this post in threaded view
|

Empty or Tree?

Michael Schober
In reply to this post by bahadýr altan
> But when I try to create a more generic code like this which could work
> with trees who don't have empty nodes in grandchild level :
>
> function Node a (Node b Tree Tree) (Node c Tree Tree )

The problem is that 'Tree' is a type, not a constructor. Someone correct
me, if I'm mistaken (this is my first post to the mailing-list, yieah
:-)), but what seems to cause the problem is that the pattern matcher
needs constructors, so it can determine, whether a pattern can produce
an input data.

There are several solutions. If you don't need the further subtrees,
leave them fully unspecified via the underscore:

function (Node a (Node b _ _) (Node c _ _)) = ...

or you could give them variable names like this:

function (Node a (Node b bl br) (Node c cl cr)) = ...

where bl, br, cl, and cr are variables of the type Tree. However, what
you might want to accomplish is a recursive function over the recursive
type to get a fully generic code. This usually looks something like this:

-- a generic recursive function
cFunction :: Tree -> a
cFunction Empty = ...
cFunction (Node i l r) = f i (cFunction l) (cFunction r)
   where
     f :: Integer -> a -> a -> a
     f int recLeft recRight = ...

Hope that helped.


Reply | Threaded
Open this post in threaded view
|

Empty or Tree?

Angelos Sphyris-2

 
>Someone correct
> me, if I'm mistaken
> but what seems to cause the problem is that the pattern matcher
> needs constructors, so it can determine, whether a pattern can produce
> an input data.
Yes, I would agree with you on that. It seems correct to me.
 
Angelos


 

> Date: Sat, 10 Mar 2012 12:45:07 +0100
> From: Micha-Schober at web.de
> To: beginners at haskell.org
> Subject: Re: [Haskell-beginners] Empty or Tree?
>
> > But when I try to create a more generic code like this which could work
> > with trees who don't have empty nodes in grandchild level :
> >
> > function Node a (Node b Tree Tree) (Node c Tree Tree )
>
> The problem is that 'Tree' is a type, not a constructor. Someone correct
> me, if I'm mistaken (this is my first post to the mailing-list, yieah
> :-)), but what seems to cause the problem is that the pattern matcher
> needs constructors, so it can determine, whether a pattern can produce
> an input data.
>
> There are several solutions. If you don't need the further subtrees,
> leave them fully unspecified via the underscore:
>
> function (Node a (Node b _ _) (Node c _ _)) = ...
>
> or you could give them variable names like this:
>
> function (Node a (Node b bl br) (Node c cl cr)) = ...
>
> where bl, br, cl, and cr are variables of the type Tree. However, what
> you might want to accomplish is a recursive function over the recursive
> type to get a fully generic code. This usually looks something like this:
>
> -- a generic recursive function
> cFunction :: Tree -> a
> cFunction Empty = ...
> cFunction (Node i l r) = f i (cFunction l) (cFunction r)
> where
> f :: Integer -> a -> a -> a
> f int recLeft recRight = ...
>
> Hope that helped.
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
     
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120322/9981b84a/attachment.htm>