可能性存在吗？(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实例是否有效？如果是，为什么没有被使用？如果不是，它是否违反了任何法律或规定？我没有证明这些规律成立，但也找不到反例。

- user1747134

---

并不是因为它没有违反任何法律，就意味着它是理想的。我认为通常情况下人们不希望自动派生Monad，因为可以选择另一种方式来实现Monad。 - Willem Van Onsem

例如，如果您有一个支持关联数组（字典）的类型类，您可以将其定义为某种状态单子。但也许您希望某种关联数组根本不作为状态单子工作，而是作为（模拟的）处理器。 - Willem Van Onsem

Answer 1

这应该是一个反例来证明正确的身份单子律。

下面，我们利用GHC.Generics中的函子乘积Maybe :*: Maybe，但如果需要，它可以被内联。 这也是一个应用、替代、可折叠和单子。 我相信这些实例的库都遵守法律。

然后我们将提议的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。

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

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

- chi

Answer 2

Alternative有些不太正规。它本质上是单子构造器的类：类型构造器T，使得对于任何包含类型X，T X是一个单子。这与函子、单子无关，数学上也没有那么深奥。（因此，仅出于数学优雅性考虑，将Monad设置在Alternative下面可能有点糟糕。）

让我们以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

然后单子定律如下：

• Left identity

  f <=< pure ≡ foldMap f . pure =! f
  

• Right identity

  pure <=< f ≡ foldMap pure . f =! f
  

• Associativity

  (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

这看起来似乎不令人过分担心，但我并不认为你可以严格地推导出任意+实例的结果。

实际上，我认为这个实例的最大问题在于它远远没有足够的普适性。大多数monad既不是也不是。如果有一个像你所提议的那样的万能定义，它将需要使用才能定义自己的任何实例，而通常认为不应该没有充分理由就使用这些实例。

然而，我确实想知道下面的默认定义bind方法是否存在任何问题：

{-# 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 ≡ (=<<)。

（注：该句话是关于it技术的内容，涉及函数式编程中的方法调用。）

- leftaroundabout

---

我想知道可折叠幺半群是否本质上等同于列表，直到同构。我无法在默认定义中看到问题，但也许它只适用于[]和其他很少的情况(?)。 - chi

@chi，这还不太够。考虑一下自由幺半群的定义。foldMap 可以得到一个部分，但你还需要 singleton，并且 foldMap f (singleton x) = f x。当然，你还需要 foldMap f (x <> y) = foldMap f x <> foldMap f y。当然，在这个点上，你肯定应该加入 Traversable，因为你可以在自由幺半群中这样做。 - dfeuer

姓和名。 - Alexey Romanov