[Haskell-beginners] N-ary tree search problems

Stephen Tetley stephen.tetley at gmail.com
Fri Nov 6 04:15:20 EST 2009

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

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

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

Best wishes


> 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

More information about the Beginners mailing list