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 right

This 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.