可能是那个(替代f,可折叠f)=> Monad f？

Question

以下typechecks:

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

这应该是正确的身份单一法律的反例.

下面,我们Maybe :*: Maybe从中获取functor产品GHC.Generics,但如果愿意,可以内联.这也是一个应用,替代,可折叠和monad.我相信这些实例上的图书馆是守法的.

然后,我们将建议instance Monad(问题中的那个)与标准库1进行比较.我们发现正确的身份法不满足所提出的实例,而它似乎在图书馆实例中(至少在我非常有限的测试中).

{-# 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是一个hacky野兽.它本质上是monoid构造函数的类:类型构造函数T,对于任何包含的类型X,T X都是monoid.这与functor ... monad并没有多大关系,并且数学上的深度要小得多.(所以,只有数学上的优雅,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

然后是monad法则

• 左派身份

  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定义你自己的任何实例,而这些通常被认为是你没有充分理由不应该使用的东西.

但我确实想知道以下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 ? (=<<).