RE: [Haskell-cafe] Adding Ord constraint to instance Monad Set?
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
On Wed, 31 Mar 2004, Simon Peyton-Jones wrote:
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 translate the question from my problem to this one: What would be if Set would be declared within Ord context, i.e. data (Ord a) => Set a = ... ? Now it would be safe to use Set as Monad because Sets could only constructed from Ord types. But GHC doesn't accept this and an answer to my surprise was (see http://www.haskell.org//pipermail/haskell-cafe/2004-March/005985.html) "Constraints on datatype declarations are a misfeature of Haskell, and have no useful effect." Is this the final conclusion?
Am Mittwoch, 31. März 2004 10:28 schrieb Henning Thielemann:
On Wed, 31 Mar 2004, Simon Peyton-Jones wrote:
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 translate the question from my problem to this one: What would be if Set would be declared within Ord context, i.e. data (Ord a) => Set a = ... ? Now it would be safe to use Set as Monad because Sets could only constructed from Ord types. But GHC doesn't accept this and an answer to my surprise was (see http://www.haskell.org//pipermail/haskell-cafe/2004-March/005985.html)
"Constraints on datatype declarations are a misfeature of Haskell, and have no useful effect."
This answer is, of course, not very descriptive. The problem is that the context (Ord a) in the data declaration only says that the the data constructor(s) is/are restricted by this context. So if you have a declaration data (Ord a) => Set a = MkSet ..., it means that MkSet has type (Ord a) => ... -> Set a instead of just ... -> Set a. There still exist types Set element where element is not an instance of Ord. You just cannot construct any value of such types except bottom (undefined).
[...]
Wolfgang
participants (3)
-
Henning Thielemann -
Simon Peyton-Jones -
Wolfgang Jeltsch