Page 1 of 2 12 LastLast
Results 1 to 10 of 13

Thread: Haskell tree search error

  1. #1
    Join Date
    Oct 2008
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Haskell tree search error

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

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

    Code:
     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:

    Code:
    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:

    Code:
    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

    Code:
    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.
    Last edited by R.B.; 11-11-2008 at 04:49 PM.

  2. #2
    Join Date
    Oct 2008
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

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

    Code:
    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!
    Last edited by R.B.; 11-07-2008 at 01:05 PM.

  3. #3
    Join Date
    Oct 2008
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

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

    Code:
    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?

  4. #4
    Join Date
    Oct 2008
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    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:

    Code:
    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.
    Last edited by R.B.; 11-11-2008 at 04:47 PM.

  5. #5
    Join Date
    May 2007
    Location
    USA
    Posts
    373
    Thanks
    2
    Thanked 4 Times in 4 Posts

    Default

    Quote Originally Posted by R.B. View Post
    Is there a better way of doing this?
    First off, you don't need Ord. All you need is Eq.

    Code:
    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)
    Code:
    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)
    Code:
    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.
    Code:
    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).
    Last edited by Trinithis; 11-07-2008 at 05:31 PM.
    Trinithis

  6. #6
    Join Date
    Jun 2005
    Location
    英国
    Posts
    11,876
    Thanks
    1
    Thanked 180 Times in 172 Posts
    Blog Entries
    2

    Default

    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).
    Twey | I understand English | 日本語が分かります | mi jimpe fi le jbobau | mi esperanton komprenas | je comprends franšais | entiendo espa˝ol | t˘i Ýt hiểu tiếng Việt | ich verstehe ein bisschen Deutsch | beware XHTML | common coding mistakes | tutorials | various stuff | argh PHP!

  7. #7
    Join Date
    Oct 2008
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    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.
    Last edited by R.B.; 11-08-2008 at 04:25 PM.

  8. #8
    Join Date
    Jun 2005
    Location
    英国
    Posts
    11,876
    Thanks
    1
    Thanked 180 Times in 172 Posts
    Blog Entries
    2

    Default

    That MonadPlus version can be written:
    Code:
    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?
    Last edited by Twey; 11-08-2008 at 04:54 PM. Reason: Unnecessary variable.
    Twey | I understand English | 日本語が分かります | mi jimpe fi le jbobau | mi esperanton komprenas | je comprends franšais | entiendo espa˝ol | t˘i Ýt hiểu tiếng Việt | ich verstehe ein bisschen Deutsch | beware XHTML | common coding mistakes | tutorials | various stuff | argh PHP!

  9. #9
    Join Date
    Oct 2008
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

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

  10. #10
    Join Date
    Oct 2008
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    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.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •