Haskell tree search error

[R.B.]

Hi, I wonder if someone could provide a little insight...

I'm trying to figure out trees, I have the following tree defined:


data Tree a b = Empty | Leaf a b | Node b (Tree a b) (Tree a b)

where a and b will typically be chars and floats, respectively.

I'm trying to search for chars in the tree using:


search :: Ord a => a ->(Tree a b) -> Bool
search _ Empty = False
search y (Leaf x _) = (x==y)
search y (Node x left_sub_tree right_sub_tree)
| x==y = True
| x>y = search y left_sub_tree
| otherwise = search y right_sub_tree

Which gives me the error:



ERROR file:.\trees.hs:24 - Inferred type is not general enough
*** Expression : search
*** Expected type : Ord a => a -> Tree a b -> Bool
*** Inferred type : Ord a => a -> Tree a a -> Bool

I can see the issue is the "Tree a a" bit... I'm just not able to fix it!

An example of a tree I'm using is


t1 :: Tree Char Float
t1 = Node 0(Node 0 (Leaf 'a' 0) (Leaf 'b' 0) ) (Node 0 (Leaf 'c' 0) (Leaf 'd' 0) )

Thanks for your time.

[R.B.]

Heh.... just as I posted I realised what was wrong with this:


search y (Node x left_sub_tree right_sub_tree)

That's completely stupid as x here is not that same as in the previous line, and is not even the thing I'm looking at since the chars can only be on a leaf. Apologies for my ineptitude. Still not sure how to make the thing work though!

[R.B.]

Hm, I seem to have something that works... although it looks kinda stupid.



search :: Ord a => a->(Tree a b) -> Bool
search _ Empty = False
search y (Leaf x _) = (x==y)
search y (Node _ left_sub_tree right_sub_tree)
| search y left_sub_tree == True = True
| otherwise = search y right_sub_tree

Is there a better way of doing this?

[R.B.]

Well I'm trying to have a return type of something other than Bool now, more specifically, the Float in Leaf I had made an anonymous type before, so when a Char is found the Float at that Leaf is returned...

Unfortunately, I can't figure out how to make it work with a return type other than Bool. Since the Chars I'm comparing are only stored in Leafs I can't do something like:


search y (Node _ left_sub_tree right_sub_tree)
| (x<y) = search y left_sub_tree
| (x>y) = search y right_sub_tree

If anyone has a suggestion I'd appreciate it... I realise this is a bit of a one man show so far, ah well... if nothing else it's helping me work through it myself.

[Trinithis]

Is there a better way of doing this?

First off, you don't need Ord. All you need is Eq.



search :: Eq a => a -> (Tree a b) -> Bool
search y = search'
where
search' Empty = False
search' (Leaf x _) = x == y
search' (Node _ left right) = search' left || search' right


One issue with your desired second version of search comes in the case where the value is found nowhere in the tree. For example, a tree with only Empty nodes at its end, or simply a tree filled with values not that value. What you probably need to do is use Maybe (or rather any MonadPlus instance).

Maybe version (less general)


search :: Eq a => a -> (Tree a b) -> Maybe b
search a = search'
where
search' Empty = Nothing
search' (Leaf a' b) = if a == a'
then Just b
else Nothing
search' (Node _ left right) = case search' left of -- NOTE: can be done using mplus
Nothing -> seach' right
Just b -> Just b


MonadPlus version (more general)


search :: (MonadPlus m, Eq a) => a -> (Tree a b) -> m b
search a = search'
where
search' Empty = mzero
search' (Leaf a' b) = if a == a'
then return b
else mzero
search' (Node _ left right) = search' left `mplus` search' right


Note you can define the Bool version of the function using this new search function.


import Data.Maybe (isJust)

dot = (.).(.)

searchBool :: Eq a => a -> (Tree a b) -> Bool
searchBool = isJust `dot` seach


As a side note, people camelCase (CamelCase) in Haskell. They dont_use_underscores (DONT_USE_UNDERSCORES).

[Twey]

It's missing the point of a binary search tree a little to not require Ord. The performance drops quite drastically (O(n) becomes the worst case for any tree, rather than just an unbalanced tree).

[R.B.]

Thank you Trinithis, you've introduced me to a couple of things I had not been aware of, namely monads and the "case...of" statement. Very interesting. Also I love the practise of making the function and its input a local variable ( i.e. search' ).

Twey, it had occured to me that this might possibly as well be a list of lists rather than a tree for all the difference it makes... but I need to figure them out so it doesn't matter for the time being.

[Twey]

That MonadPlus version can be written:
search :: (MonadPlus m, Eq a) => a -> (Tree a b) -> m b
search a Empty = mzero
search a (Leaf a' b) | a == a' = return b
| otherwise = mzero
search a (Node _ left right) = search left `mplus` search rightThis structure seems a little odd to me, though. If a Node's value is equal, it doesn't matter and the search continues until an appropriate Leaf is found?

[R.B.]

Yes, in this particular search the value in the node doesn't matter. I suppose it's more of a traversal of the leaves than a search...

[R.B.]

Hm, I've just been reading about map and I'm wondering if it's possible to use it to apply this function to each Char in a String, since String = [Char]. Had a quick go but not quite got a hold on it yet.

[Trinithis]

Sure you can. For example toLower from Data.Char is a funtion with the type Char -> Char

Fire up ghci and try this out:


Prelude> map Data.Char.toLower "He yelled 'HELLO!!!'"
"he yelled 'hello!!!'"

[R.B.]

That's cool. Handy.

Would it work for search as above? ... gonna have a quick go.

... few mins later...

Well, couldn't make map work with that, is it possible to work map with a function that takes more inputs than just a list? Had a go of doing it recursively as well:


stringSearch :: String->(Tree Char Float) -> Maybe [Char]
stringSearch _ Empty = Nothing
stringSearch "" _ = Nothing
stringSearch (h:t) tree = search h tree

Heh... this works for the first char in a string, so I suppose this means it could work for the rest of it. But it's late here, and I'm fairly poor at this at the best of times, so I can't figure out the recursion step right now.

Anyway, off to bed. Thanks again for helping me figure this stuff out, really useful.

[Twey]

Yes, of course:
import Data.Char (toUpper)

strUp :: String -> String
strUp = map toUpper