Haskell data structures oddity

Question

I've been attempting to write a small file to try out a bag-like data structure. So far my code is as follows:

data Fruit = Apple | Banana | Pear deriving (Eq, Show)
data Bag a = EmptyBag | Contents [(a, Integer)]

emptyBag :: Bag a
emptyBag = EmptyBag

unwrap :: [a] -> a
unwrap [x] = x

isObject theObject (obj, inte) = theObject == obj

count :: Bag a -> a -> Integer
count (Contents [xs]) theObject = snd (unwrap (filter (isObject theObject) [xs]))
count EmptyBag _ = 0

But when I try and run it I get the error Could not deduce (Eq a) from the context () arising from a use of 'isObject' at ....

Whereas when I take the count function out and call snd(unwrap(filter (isObject Banana) [(Apple,1),(Banana,2)])) it happily returns 2.

Any clues on why this is, or advice on writing this kind of data structure would be much appreciated.

There's no need for an EmptyBag constructor; use Contents [] instead. — augustss
– augustss, Commented May 25, 2011 at 19:51
count will also crash when you try to do something like count (Contents [(Banana,2),(Apple,3)]) Apple as [xs] only matches on lists with one element! — yatima2975
– yatima2975, Commented May 25, 2011 at 20:22

geekosaur · Accepted Answer · 2011-05-25 15:46:37Z

6

(==) can only be used in a context that includes Eq, but when you declared count you didn't include that context. If I'm reading correctly, that would be

count :: Eq a => Bag a -> a -> Integer

If you declare count without including the type, you can ask ghci for the inferred type; or just ask for the inferred type of snd (unwrap (filter (isObject Banana) [(Apple,1),(Banana,2)]))

answered May 25, 2011 at 15:46

geekosaur

61.8k13 gold badges127 silver badges115 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Owen Over a year ago

Your solution is correct, but I don't entirely see why; I presumed since the function isObject works for comparisons, it wouldn't stop working in this context - what exactly does adding Eq a => change in the program?

dvitek Over a year ago

Eq a tells your compiler that theObject is a member of the Eq typeclass - namely, that you can test if it's equal to something else of the same type. There are certain data types (functions are the best example) that are not members of the Eq typeclass. (For example, (+1) and ((+2).(-1)) cannot be tested for equality, although in almost all cases they will return the same result.)

geekosaur Over a year ago

Secretly, a typeclass function such as (==) is looked up in a table containing the information about the type; the Eq a => declares the type of this table, which is passed as an additional argument behind the scenes. (If you look at the GHC Core output you will see the actual tables being passed around.) With isObject you let GHC work out the type itself, and it did so, including the Eq a constraint; but when you specify the type of count yourself, you don't get to leave things like that out (not without some fairly hairy Oleg-isms, at least). It's all or nothing.

Dan Burton Over a year ago

Removing the explicit type signature on count also fixes the problem. Then you could use ghci to see what type is inferred.

Collectives™ on Stack Overflow

Haskell data structures oddity

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related