N-ary tree search problems
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
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 Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
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
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
participants (4)
-
Christian Maeder -
iæfai -
Ryan Temple -
Stephen Tetley