[Haskell-cafe] Adding Ord constraint to instance Monad Set?
simonpj at microsoft.com
Wed Mar 31 09:08:54 EST 2004
| Following the declaration of "instance Monad "
| in the prelude, and puzzling over the absence of
| its equivalent from Data.Set, I naively typed:
| instance Monad Set where
| m >>= k = concatSets (mapSet k m)
| return x = unitSet x
| fail s = emptySet
| concatSets sets = foldl union emptySet (setToList sets)
| instance (Eq b,Ord b) => Ord (Set b) where
| compare set1 set2 = compare (setToList set1) (setToList set2)
| and got the following error:
| Could not deduce (Ord b) from the context (Monad Set)
| arising from use of `concatSets' at dbMeta3.hs:242
I'm sorry to say that you just can't make Set an instance of Monad.
To make an instance of Monad for a type constructor T you must have a
bindT :: forall a b. T a -> (a -> T b) -> T b
And there just *is* no such function for Set, because of the need for
ordering. There's a less polymorphic function
bindSet :: forall a b. (Ord a, Ord b)
=> T a -> (a -> T b) -> T b
To see why this is no good, consider
sequence :: Monad m => [m a] -> m [a]
The code for sequence calls (>>=) a lot. You can't supply bindSet as
the function to call because bindSet takes two Ord parameters at
run-time, whereas ordinary bind does not. It's not just a quirk of the
type system -- there is a real problem!
More information about the Haskell-Cafe