How to define bind operator using type class?

Question

How to define bind operator using type class?

I want to define monad instance to a type. Below is the source code I wrote.

data Set a = Eq a => Set [a]

newtype SetMonad a = SetMonad {unMonad :: Set a}

instance Functor SetMonad

instance Applicative SetMonad

-- Implemention of Monad instance for "SetMonad"
instance Monad SetMonad where
  (>>=) :: SetMonad a -> (a -> SetMonad b) -> SetMonad b
  (SetMonad v) >>= f = SetMonad $ fromList $ concat $ elems $ unMonad $ mapM f (elems v)

-- utils for "Set a"

elems :: Set a -> [a]
elems (Set a) = a

fromList :: Eq a => [a] -> Set a
fromList [] = Set []
fromList (x : xs) = fromList' [] (x : xs)
  where
    fromList' [] (x : xs) = fromList' [x] xs
    fromList' ys (x : xs) = if x `elem` ys then fromList' (x : ys) xs else fromList' ys xs
    fromList' ys [] = Set ys

Actually, this code has a compile error.

• No instance for (Eq b) arising from a use of ‘fromList’
  Possible fix:
    add (Eq b) to the context of
      the type signature for:
        (>>=) :: forall a b. SetMonad a -> (a -> SetMonad b) -> SetMonad b
• In the second argument of ‘($)’, namely ‘fromList d’
  In the expression: SetMonad $ fromList d
  In the expression:
    let d = concat $ elems $ unMonad $ mapM f (elems v)
    in SetMonad $ fromList dtypecheck(-Wdeferred-type-errors)

bind operator's type is defined in the other package (Control.Monad) and I cannot override this (compile error occurs.) but I need to use (==) operator in the implemention of (>>=). how should I fix it?

What I tried

• Tried to change the type defination of bind operator.

instance Monad SetMonad where
  (>>=) :: Eq a => SetMonad a -> (a -> SetMonad b) -> SetMonad b
  (SetMonad v) >>= f = SetMonad $ fromList $ concat $ elems $ unMonad $ mapM f (elems v)

and caused compile errors:

• No instance for (Eq a)
    arising from the check that an instance signature is more general
    than the type of the method (instantiated for this instance)
    instance signature:
      >>= :: forall a b.
             Eq a =>
             SetMonad a -> (a -> SetMonad b) -> SetMonad b
    instantiated method type:
      forall a b. SetMonad a -> (a -> SetMonad b) -> SetMonad b
  Possible fix:
    add (Eq a) to the context of
      the type signature for:
        (>>=) :: forall a b. SetMonad a -> (a -> SetMonad b) -> SetMonad b
• When checking that instance signature for ‘>>=’
    is more general than its signature in the class
    Instance sig: forall a b.
                  Eq a =>
                  SetMonad a -> (a -> SetMonad b) -> SetMonad b
       Class sig: forall a b.
                  SetMonad a -> (a -> SetMonad b) -> SetMonad b
  In the instance declaration for ‘Monad SetMonad’

• Could not deduce (Eq b) arising from a use of ‘fromList’
  from the context: Eq a
    bound by the type signature for:
               (>>=) :: forall a b.
                        Eq a =>
                        SetMonad a -> (a -> SetMonad b) -> SetMonad b
    at /home/txjp/dev/drive2/src/Sandbox2.hs:127:12-64
  Possible fix:
    add (Eq b) to the context of
      the type signature for:
        (>>=) :: forall a b.
                 Eq a =>
                 SetMonad a -> (a -> SetMonad b) -> SetMonad b
• In the first argument of ‘($)’, namely ‘fromList’
  In the second argument of ‘($)’, namely
    ‘fromList $ concat $ elems $ unMonad $ mapM f (elems v)’
  In the expression:
    SetMonad $ fromList $ concat $ elems $ unMonad $ mapM f (elems v)

Background

List monad is usiful for nondeterministic computation. but sometimes unfavorable because it has the idea of order when I interested only in combinations. So, I wanted to implement list-like monad which have no concept of order.

Normally, I should use Data.Set package, but it need to be Ord instance to use. so, I used a list-based implemention to make things easier.

Please give me some help. Thank you.

Answer 1

This is a known conumdrum. There are hacks to get this working, but IMO the issue is ultimately that sets just don't make sense as monads in the Hask category.

They do make sense as monads in the subcategory of types with an Eq instance. This is the kind of thing that I wrote the constrained-category package for. _{(There are many alternatives: data-category, constrained-monads, constrained, subhask...)}. The idea is to restrict all mapping so you always stay within the class of allowed types. You don't really need to include the Eq constraint in the type then, this mostly just complicates things.

import qualified Prelude as Hask

import Control.Category.Constrained
import Control.Category.Constrained.Prelude

import Data.List (nub)

newtype Set a = Set { setElems :: [a] }

instance Eq a => Eq (Set a) where
  (==) = ... -- beware that order should not matter

fromList :: Eq a => [a] -> Set a
fromList = Set . nub

instance Functor Set (Eq ⊢ (->)) (Eq ⊢ (->)) where
  fmap (ConstrainedMorphism f) = ConstrainedMorphism
           $ \(Set s) -> fromList $ map f s

instance Monoidal Set (Eq⊢(->)) (Eq⊢(->)) where
  pureUnit = ConstrainedMorphism pure
  fzipWith (ConstrainedMorphism f)
    = ConstrainedMorphism $ \(Set xs, Set ys)
        -> Set . fromList $ fzipWith f (xs,ys)
instance Applicative Set (Eq ⊢ (->)) (Eq ⊢ (->)) where
  pure = ConstrainedMorphism pure

instance Monad Set (Eq ⊢ (->)) where
  join (Set s) = fromList $ s >>= setElems