难道是 (Alternative f, Foldable f) => Monad f？

Question

以下类型检查：

instance (Applicative f, Alternative f, Foldable f) => Monad f where 
  (>>=) = flip $ \f -> foldr (<|>) empty . fmap f
  -- Or equivalently
  a >>= b = getAlt . foldMap Alt . fmap b $ a

这实际上是一个有效的 Monad 实例吗？如果是，为什么不使用它？如果不是，它是否违反任何法律或类似法律？我没有证明定律成立，但我也找不到反例。

Answer 1

这应该是右恒等元律的反例。

下面，我们利用 GHC.Generics 中的仿函数积 Maybe :*: Maybe，但如果需要，它可以被内联。这也是一个适用的、替代的、可折叠的和 monad。我相信这些实例上的图书馆是守法的。

然后我们将建议的 instance Monad（问题中的那个）与标准库中的那个进行比较。我们发现建议的实例不满足正确的身份法则，而它似乎在库实例中成立（至少在我非常有限的测试中）。

{-# LANGUAGE FlexibleInstances, GeneralizedNewtypeDeriving, TypeOperators #-}
{-# OPTIONS -Wall #-}

module NotAMonad where

import Control.Applicative
import GHC.Generics ((:*:)(..))

-- A basic wrapper to avoid overlapping instances, and to be able to
-- define a custom monad instance.
newtype Wrap m a = Wrap { unWrap :: m a }
    deriving (Functor, Applicative, Alternative, Foldable, Show)

-- The proposed instance
instance (Applicative f, Alternative f, Foldable f) => Monad (Wrap f) where 
  (>>=) = flip $ \f -> foldr (<|>) empty . fmap f

-- This is Applicative, Alternative, and Foldable
type T = Maybe :*: Maybe

-- A basic test
test :: Wrap T Int
test = Wrap (Just 3 :*: Just 4) >>= return
-- result:
-- Wrap {unWrap = Just 3 :*: Just 3}

4 现在被 3 取代。不过，我没有试图解释原因。我猜这是由 Just 3 <|> Just 4 = Just 3.

引起的

使用库 monad 实例，一切看起来都很好：

> (Just 3 :*: Just 4) >>= return
Just 3 :*: Just 4

Answer 2

Alternative 有点怪怪的。它本质上是 monoid 构造函数 的 class：类型构造函数 T 这样对于任何包含的类型 X，T X 是一个 monoid。这与仿函数……单子并没有太大关系，而且在数学上的深度要低得多。（所以，只是为了数学上的优雅，在 Alternative 下设置 Monad 会有点糟糕。）

为了清楚起见，让我们根据 Monoid 编写该实例（这实际上不会编译）：

instance (Foldable f, (∀ x . Monoid (f x))) => Monad f where
  (>>=) = flip $ \f -> foldr mappend empty . fmap f
        ≡ flip $ \f -> fold . fmap f
        ≡ flip foldMap

或者确实

  (=<<) = foldMap

所以，这绝对不是什么未知数。

要检查定律，我们最好看一下 Kleisli 公式：

  (f <=< g) x = f =<< g x
              ≡ foldMap f $ g x

即

  f <=< g = foldMap f . g

那么单子定律是

留下身份
```
f <=< pure ≡ foldMap f . pure =! f
```
正确身份
```
pure <=< f ≡ foldMap pure . f =! f
```

关联性

(f <=< g) <=< h ≡ foldMap (foldMap f . g) . h
                =! foldMap f . foldMap g . h
                ≡ foldMap f . (foldMap g . h) ≡ f <=< (g <=< h)

简而言之，我们需要

foldMap f . pure =! f =! foldMap pure . f∀f
foldMap (foldMap f . g) =! foldMap f . foldMap g∀f,g

这看起来当然不无道理，但我看不出你可以从哪里严格地得出任意 Foldable+Alternative 个实例的结论。

真的，我看到这个实例的最大问题是它不够通用。大多数 monad 既不是 Foldable 也不是 Alternative。如果有像您建议的那样的覆盖所有定义，则需要 OverlappingInstances 定义您自己的任何实例，并且这些通常被认为是没有充分理由不应使用的东西。

不过我想知道绑定方法的以下默认定义是否会有任何问题：

{-# LANGUAGE DefaultSignatures #-}
class Applicative f => Monad f where
  return :: a -> m a
  return = pure
  (>>=) :: m a -> (a -> m b) -> m b
  default (>>=) :: (Foldable m, Monoid m b)
          => m a -> (a -> m b) -> m b
  (>>=) = flip foldMap

那至少可以定义例如列表实例简单为

instance Monad []

根本不需要写出方法，因为果然如此，foldMap ≡ concatMap ≡ (=<<)。

难道是 (Alternative f, Foldable f) => Monad f？

Could it be that (Alternative f, Foldable f) => Monad f?

haskell

monads

typeclass

alternative-functor

foldable