haskell - 为什么使用 `Eq a` 的解决方案需要 `elem` 约束？

Question

我正在解决 Haskell Book 中的以下练习:

-- >>> flipMaybe [Just 1, Just 2, Just 3]
-- Just [1, 2, 3]
-- >>> flipMaybe [Just 1, Nothing, Just 3]
-- Nothing

flipMaybe :: [Maybe a] -> Maybe [a]
flipMaybe = undefined

首先我尝试使用 elem ,

flipMaybeWithElem :: [Maybe a] -> Maybe [a]
flipMaybeWithElem ms
  | Nothing `elem` ms = Nothing
  | otherwise         = Just (catMaybes ms)

但我收到错误消息:

misc.hs:86:5: error:
    • No instance for (Eq a) arising from a use of ‘elem’
      Possible fix:
        add (Eq a) to the context of
          the type signature for:
            flipMaybe2 :: forall a. [Maybe a] -> Maybe [a]
    • In the expression: Nothing `elem` ms
      In a stmt of a pattern guard for
                     an equation for ‘flipMaybe2’:
        Nothing `elem` ms
      In an equation for ‘flipMaybe2’:
          flipMaybe2 ms
            | Nothing `elem` ms = Nothing
            | otherwise = Just (catMaybes ms)
   |
86 |   | Nothing `elem` ms = Nothing
   |     ^^^^^^^^^^^^^^^^^

我知道我应该只添加 Eq a =>对函数签名的约束，但我试图忠实于提供的函数 stub 。所以我重用了以前的功能，它确实有效:

flipMaybe :: [Maybe a] -> Maybe [a]
flipMaybe ms =
  case (filter isNothing ms) of
    [] -> Just (catMaybes ms)
    _  -> Nothing

使用的辅助函数:

isNothing :: Maybe a -> Bool
isNothing Nothing = True
isNothing _       = False

mayybee :: b -> (a -> b) -> Maybe a -> b
mayybee b _ Nothing = b
mayybee b f (Just a) = f a

fromMaybe :: a -> Maybe a -> a
fromMaybe a maybe = mayybee a id maybe

catMaybes :: [Maybe a] -> [a]
catMaybes xs = map (fromMaybe undefined) (filter isJust xs)

所以 为什么第一个解决方案没有 elem在没有类型约束的情况下工作？

难道仅仅是因为 filter和 isNothing对类型变量和 elem 没有限制有？ (同样对于 isNothing，类型变量甚至从未发挥作用，因为它被忽略了。)

> :t filter               
filter :: (a -> Bool) -> [a] -> [a]

> :t isNothing                              
isNothing :: Maybe a -> Bool                               

> :t elem
elem :: (Eq a, Foldable t) => a -> t a -> Bool 

Maybe有一个 Eq例如，但我猜编译器对 a 一无所知， 正确的？

Answer 1

Is it simply because filter and isNothing have no constraints on the type variables and elem has? (Also with isNothing the type variable never even comes into play because it is ignored.)

你在这里一针见血。 elem ，一般来说，只有在 Eq a 时才有效很满意。您正在尝试在 [Maybe a] 上使用它, 和 Maybe a有以下 Eq实例。

instance Eq a => Eq (Maybe a) where
    ...

所以 elem看着你的 Maybe a并说“我需要这个是 Eq”。它看到上面的实例并说“对于 Maybe a 要满足 Eq ， a 必须满足 Eq ，我不知道 Eq a ”。现在，在您的特定情况下，您只比较 Nothing ，所以 Eq a instance 从未实际使用过。但是编译器没有足够的信息来知道这一点；它只知道 elem需要 Eq a ，并且您没有为它提供该约束。

为了让这个功能在没有 Eq 的情况下工作，你需要按照你已经做过的方式来做，要么使用显式递归，要么使用 filter和 isNothing .总之，我想你已经找到答案了，我只是重申一下你已经说过的话。