如何用类型类定义bind运算符？Haskell集合Monad报错排查

我想实现一个无顺序概念、类列表的Monad（替代List monad的顺序特性），用基于列表的Set实现（避免Data.Set需要Ord实例的限制），但编写的代码出现编译错误，核心问题是无法在Monad的>>=中添加必要的Eq约束。

原始代码 #

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

编译错误 #

• 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)

已尝试的方案 #

我尝试修改>>=的类型签名，添加Eq约束：

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)

但引发新的编译错误：

• 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)

解决方案 #

问题根源在于两点：一是原始Set的约束写法错误，二是标准Monad不允许>>=带额外约束。我们可以通过GADT扩展封装Eq约束，同时修正Set的定义和工具函数逻辑。

完整修正代码 #

{-# LANGUAGE GADTs #-}

-- 修正Set定义，移除构造器上的Eq约束，改为在需要的地方声明约束
data Set a = Set [a]

-- 用GADT定义SetMonad，确保每个SetMonad实例都隐含对应类型的Eq约束
data SetMonad a where
  SetMonad :: Eq a => Set a -> SetMonad a

-- 实现Functor：利用GADT自动推导的Eq约束，确保映射后的类型满足去重要求
instance Functor SetMonad where
  fmap f (SetMonad (Set xs)) = SetMonad $ fromList $ map f xs

-- 实现Applicative
instance Applicative SetMonad where
  pure x = SetMonad $ Set [x]
  (<*>) (SetMonad (Set fs)) (SetMonad (Set xs)) = SetMonad $ fromList $ [f x | f <- fs, x <- xs]

-- 实现Monad：从SetMonad实例中自动获取Eq约束，满足fromList的要求
instance Monad SetMonad where
  return = pure
  (SetMonad (Set xs)) >>= f =
    let -- 对每个元素应用绑定函数，得到SetMonad列表
        mapped = map f xs
        -- 提取每个SetMonad中的Set数据
        extractSet (SetMonad s) = s
        sets = map extractSet mapped
        -- 合并所有集合的元素
        allElems = concatMap elems sets
        -- 去重得到最终集合
        finalSet = fromList allElems
    in SetMonad finalSet

-- 获取Set中的元素列表
elems :: Set a -> [a]
elems (Set xs) = xs

-- 修正fromList的去重逻辑，正确移除重复元素
fromList :: Eq a => [a] -> Set a
fromList = Set . go []
  where
    go _ [] = []
    go seen (x:xs)
      | x `elem` seen = go seen xs
      | otherwise = x : go (x:seen) xs

关键说明 #

1. GADT的作用：通过GADT定义的SetMonad会自动为每个实例携带Eq a约束，编译器会在需要的地方（比如调用fromList时）自动推导该约束，无需在>>=的类型签名中额外添加，符合标准Monad的要求。
2. 修正Set定义：移除数据构造器上的Eq约束是Haskell的最佳实践，约束应该放在函数或类型类实例上，而非数据类型本身。
3. 修复去重逻辑：原始fromList的逻辑错误，会保留重复元素，修正后的版本会正确过滤掉已出现的元素。

内容的提问来源于stack exchange，提问作者Yugumo