[Haskellcafe] Adding Ord constraint to instance Monad Set?
Simon PeytonJones
simonpj at microsoft.com
Wed Mar 31 09:08:54 EST 2004
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
runtime, whereas ordinary bind does not. It's not just a quirk of the
type system  there is a real problem!
Simon
More information about the HaskellCafe
mailing list