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

[Benjamin Franksen]

On Wednesday 31 March 2004 00:11, S. Alexander Jacobson wrote:
> 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
>     Probable fix:
>         Add (Ord b) to the class or instance method `>>='

I am not quite sure what that means either. I used to understand it as meaning 
"Add (Ord b) either to the type of method '>>=' (in the class) or to the 
class itself or to the instance in which method '>>=' is defined". Now, the 
last is actually impossible in this case, since the instance declaration 
nowhere mentions a type variable to which the context could be added.

>     In the definition of `>>=': >>= m k = concatSets (mapSet k m)
>     In the definition for method `>>='
>     In the instance declaration for `Monad Set'
>
> Since I obviously can't modify the class
> declaration for Monad, the question arises:
>
>    How does one add (Orb b) to the instance method '>>='?

One can't (in this case, otherwise see above remarks).

> PS I assume the reason that Set is not declared as
> a Monad in Data.Set is oversight rather than
> incompatibility....

I fear your assumption is wrong. I really can't see how to restrict the 
'element' types in instances of class Monad. BTW, even multi-parameter 
classes don't help here.

Now, as i think a little more about it, i believe what you want to do makes no 
sense. The monad operation '>>=' works on monads over *different* 'element' 
(i.e. argument) types (look at the type of '>>='). Your implementation only 
works if argument types are the same. I can't see how this can be generalized 
to different argument types even if both are instances of class Ord.

Maybe sets simply aren't (i.e. can't be made) monads in any natural way.

Ben