[Haskell-cafe] Adding Ord constraint to instance Monad Set?

[Simon Peyton-Jones]

Alex

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

	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!

Simon