8

以下类型检查：

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实例吗？如果是，为什么不使用它？如果不是，它是否违反了任何法律或其他法律？我没有证明这个规律成立，但我也找不到反例。

4

2 回答 2

7

这应该是正确身份单子法则的反例。

下面，我们利用 中的函子乘积Maybe :*: Maybe，GHC.Generics但如果愿意，它可以被内联。这也是一个 applicative、alternative、foldable 和 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
于 2017-05-24T11:35:49.693 回答
6

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

IE

  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实例的结论。

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

但是，我确实想知道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 ≡ (=<<).

于 2017-05-24T12:51:32.340 回答