N-ary tree search problems

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

N-ary tree search problems

Ryan Temple
I'm making a general purpose N-ary tree and im coming up with "unexpected
'=' on line 17" as an error.  I have spent a fair while trying to work out
why this isn't accepting the case that an Empty gtree returns false for any
member search.  i realise this is probably a very trivial error but any help
would be appreciated:

module GTrees where

data Gtree = Empty |
             Leaf String |
             Node String [Gtree]
             deriving (Show)

--Tests if a given string is a member of the tree

gtreeMember :: (Ord a) => a -> Gtree a -> Bool
  gtreeMember y Empty = False  -- line 17
  gtreeMember y (Leaf x) = (x==y)
  gtreeMember y (Node x tree)
      |x==y = True
      |otherwise gtreeMember tree

This is the code up to the point of the error with the error line
highlighted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20091104/18de551b/attachment.html
Reply | Threaded
Open this post in threaded view
|

N-ary tree search problems

iæfai
Try to make sure things are lined up properly, like the Empty and  
Left, and why are some gtreeMember indented?

On 2009-11-04, at 7:04 AM, Ryan Temple wrote:

> I'm making a general purpose N-ary tree and im coming up with  
> "unexpected
> '=' on line 17" as an error.  I have spent a fair while trying to  
> work out
> why this isn't accepting the case that an Empty gtree returns false  
> for any
> member search.  i realise this is probably a very trivial error but  
> any help
> would be appreciated:
>
> module GTrees where
>
> data Gtree = Empty |
>             Leaf String |
>             Node String [Gtree]
>             deriving (Show)
>
> --Tests if a given string is a member of the tree
>
> gtreeMember :: (Ord a) => a -> Gtree a -> Bool
>  gtreeMember y Empty = False  -- line 17
>  gtreeMember y (Leaf x) = (x==y)
>  gtreeMember y (Node x tree)
>      |x==y = True
>      |otherwise gtreeMember tree
>
> This is the code up to the point of the error with the error line
> highlighted
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners

Reply | Threaded
Open this post in threaded view
|

N-ary tree search problems

Stephen Tetley-2
Hello Ryan

As iaefai said, consistent indentation is the key.

But you also have a problem with the type signature of gtreeMember

gtreeMember :: (Ord a) => a -> Gtree a -> Bool

The part ** Gtree a ** insists that you Gtree has a parametric type -
think of list - [a] where a is type parameter, then concretely a list
can hold any type e.g. [Int] a list of Int, [Bool] a list of Bool, and
so on...

However your Gtree type is not parametric - elements can only be
**String**. So you need to change the signature of gtreeMember so that
it explicitly uses Strings and correct Gtree so it doesn't have a type
parameter:

gtreeMember :: String -> Gtree -> Bool

As there is no longer a type variable you no longer need the type
constraint - Ord a.

That gets things to work, but as you want a general purpose tree this
specialization to Strings for the element isn't really what you need.
Following on you would want to change the Gtree data type to be
polymorphic on element, whence it will have a parametric type
signature:


data Gtree a = Empty
             | Leaf a
             | Node a [Gtree a]
  deriving (Show)

(Trivia - I've changed the style to be have the line for each
alternative constructor start with | which is more conventional, your
tastes may vary. Ideally the pipes should line up with the equals, but
as I'm typing with a variable width font I can't be sure).

Note the ** Gtree a ** in the initial part of the data declaration,
also note the ** Gtree a** in the recursive part of the Node
constructor.


Best wishes

Stephen




> On 2009-11-04, at 7:04 AM, Ryan Temple wrote:

>>
>> data Gtree = Empty |
>> ? ? ? ? ? ?Leaf String |
>> ? ? ? ? ? ?Node String [Gtree]
>> ? ? ? ? ? ?deriving (Show)
>>
>> --Tests if a given string is a member of the tree
>>
>> gtreeMember :: (Ord a) => a -> Gtree a -> Bool
>> ?gtreeMember y Empty = False ?-- line 17
>> ?gtreeMember y (Leaf x) = (x==y)
>> ?gtreeMember y (Node x tree)
>> ? ? |x==y = True
>> ? ? |otherwise gtreeMember tree
Reply | Threaded
Open this post in threaded view
|

Re: N-ary tree search problems

Christian Maeder-2
In reply to this post by Ryan Temple
Ryan Temple schrieb:

> I'm making a general purpose N-ary tree and im coming up with
> "unexpected '=' on line 17" as an error.  I have spent a fair while
> trying to work out why this isn't accepting the case that an Empty gtree
> returns false for any member search.  i realise this is probably a very
> trivial error but any help would be appreciated:
>
> module GTrees where
>
> data Gtree = Empty |
>              Leaf String |
>              Node String [Gtree]
>              deriving (Show)

You may want to consider a node with a singleton list as "Leaf" and a
node with an empty list as "Empty" (if the additional "String" for
"Node" does not harm for an empty tree).

> --Tests if a given string is a member of the tree
>
> gtreeMember :: (Ord a) => a -> Gtree a -> Bool
>   gtreeMember y Empty = False  -- line 17
>   gtreeMember y (Leaf x) = (x==y)
>   gtreeMember y (Node x tree)
>       |x==y = True
>       |otherwise gtreeMember tree

After proper indentation and deciding if Gtree is polymorphic or not in
the signature and data type, this last line will not work:
1. there must be a "=" following "otherwise"
2. gtreeMember expects two arguments
3. the variable "tree" is a list of Gtrees
   whereas gtreeMember only works for a single Gtree.

HTH Christian