如何检测Monad？

Question

我们中的许多人没有函数式编程的背景知识,更不用说类别理论代数了.所以我们假设我们需要并因此创建一个类似的泛型类型

data MySomething t = ....... 

然后我们继续编程,并使用MySomething.什么证据应提醒我们,MySomething是一个单子,那我们必须通过写能使之instance Monad MySomething ...和定义return,并>>=为它？

谢谢.

编辑:另见这个问题:链接操作是monad类解决的唯一问题吗？,这个答案monad是一个带辅助操作的函数数组

Answer 1

我对Monads的理解向前迈出了一大步,就是Monads是Tree with Grafting.如果你的类型看起来像一棵树,并且t值出现在树叶上,那么你手上可能有一个monad.

简单的例子

一些数据类型显然是树,例如Maybe类型

data Maybe a = Nothing | Just a

其中包含空叶或具有单个值的叶.该列表是另一种明显的树类型

data List a = Nil | Cons a (List a)

它可以是空叶,也可以是具有单个值和另一个列表的叶.更明显的树是二叉树

data Tree a = Leaf a | Bin (Tree a) (Tree a)

在叶子上的值.

更难的例子

但是,有些类型乍一看看起来不像树木.例如,'reader'monad(aka function monad或environment monad)看起来像

data Reader r a = Reader { runReader :: r -> a }

此刻看起来不像一棵树.但是,让我们专注于一个具体类型r,例如Bool-

data ReaderBool a = ReaderBool (Bool -> a)

来自Boolto 的函数a等效于一对(a,a),其中该对的左元素是函数的值,True右参数是 - 上的值False-

data ReaderBool a = ReaderBool a a

看起来更像是只有一种叶子的树 - 事实上,你可以把它变成一个单子

instance Monad ReaderBool where
    return a = ReaderBool a a
    ReaderBool a b >>= f = ReaderBool a' b'
      where
        ReaderBool a' _ = f a
        ReaderBool _ b' = f b

道德是一个函数r -> a可以被视为一个包含许多类型值的大元组a,每个可能的输入一个 - 并且元组可以被视为一个特别简单的树的叶子.

州monad是这种类型的另一个例子

data State s a = State { runState :: s -> (a, s) }

您可以在其中查看s -> (a, s)类型值的大元组(a, s)- 一个可能的类型输入s.

还有一个例子 - 简化的IO动作monad

data Action a = Put String (Action a)
              | Get (String -> Action a)
              | Return a

这是一棵树有三种类型的叶子 - Put叶子只携带另一个动作,Get叶子,可以看作是一个无限的动作元组(每个可能的String输入一个)和一个Return只带有单个值的简单叶子类型a.所以看起来它可能是一个monad,事实确实如此

instance Monad Action where
  return = Return

  Put s a  >>= f = Put s (a >>= f)
  Get g    >>= f = Get (\s -> g s >>= f)
  Return a >>= f = f a

希望这给你一点点直觉.

将monad想象为树,将return操作作为获取具有一个值的简单树的方法,以及将>>=操作作为用新树替换树叶处的元素的方式,可以是看待monad的强大统一方式.

Answer 2

值得一提的是,没有直接的方法可以注意到Monad的某些东西 - 而是当你怀疑某些东西可能是Monad来证明你的怀疑是正确的时候.

也就是说,有一些方法可以提高你对Monads的敏感度.

了解依赖关系

对于任何类型T,遵纪守法instance Monad T意味着遵纪守法instance Applicative T,守法instance Functor T.通常Functor比检测(或反驳)更容易Monad.Applicative在看到它们也是a之前,它们的结构可以很容易地检测到一些计算Monad.

具体来说,这就是你如何证明任何Monad一个Functor和一个Applicative

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype Wrapped m a = W { unW :: m a } -- newtype lets us write new instances
  deriving ( Monad )

instance Monad m => Functor (Wrapped m) where
  fmap f (W ma) = W (ma >>= return . f)

instance Monad m => Applicative (Wrapped m) where
  pure = W . return
  W mf <*> W mx = W $ do
    f <- mf
    x <- mx
    return (f x)

通常,可用于理解此类型层次结构的最佳资源是Typeclassopedia.我不能建议阅读它.

了解您的标准单子和变压器

有一套非常标准的简单monad,任何中级Haskell程序员都应该立即熟悉它们.这是Writer,Reader,State,Identity,Maybe,和Either,Cont和[].通常,您会发现您的类型只是对这些标准monad之一的一个小修改,因此可以以类似于标准的方式制作monad本身.

此外,一些Monad称为变换器的 s "堆叠"以形成其他Monads.这具体意味着你可以将Readermonad和Writermonad的修改形式结合起来形成ReaderWritermonad.这些修改过的表单在transformers和mtl包中公开,通常用附加的方式划分T.具体而言,您可以定义ReaderWriter使用标准的变压器从transformers这样的

import Control.Monad.Trans.Reader
import Control.Monad.Writer

newtype ReaderWriter r w a = RW { unRW :: ReaderT r (Writer w) a }
  deriving Monad

-- Control.Monad.Trans.Reader defines ReaderT as follows
--
--     newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }
--
-- the `m` is the "next" monad on the transformer stack

一旦你学习了变换器,你会发现更多的标准类型只是基本monad的堆栈,因此从转换器的monad实例继承它们的monad实例.这是构建和检测monad 的非常强大的方法.

要了解这些,最好只研究transformers和mtl包中的模块.

注意排序

通常引入Monad以提供动作的明确排序.如果你正在编写一个需要具体表示一系列动作的类型,你可能手上有一个monad - 但你也可能只有一个Monoid.

请参阅我之前的这个答案,深入讨论如何将某个序列写成Monad......但这样做没有任何好处..有时序列只是一个列表.

了解扩展

有时你会有一个显然不是monad的数据类型,但显然它依赖于monad实例.一个常见的例子是解析可能显而易见的是你需要进行一个跟随许多选择的搜索,但是不能立即明确你可以从中形成一个monad.

但是如果你熟悉Applicative或者Monad你知道有Alternative和MonadPlus类

instance Monad m => MonadPlus m where ...
instance Applicative f => Alternative f where ...

这对于采用替代方案的结构计算很有用.这表明可能有找到你的类型monad结构的方法!

了解自由结构

有一个关于仿函数的免费 monad 的概念.这个术语非常类别理论,但它实际上是一个非常有用的概念,因为任何monad都可以被认为是解释相关的自由monad.此外,自由monad是相对简单的结构,因此更容易获得它们的直觉.请注意,这些内容相当抽象,但需要花费一些精力才能消化.

免费monad定义如下

data Free f a = Pure a
              | Fix (f (Fix f a))

这只是我们的函子的f一个固定点,它与一个Pure值相邻.如果你研究类型固定点(参见recursion-schemes包或Bartosz Milewski的理解F代数了解更多),你会发现该Fix位只定义了任何递归data类型,并且该Pure位允许我们将"空洞"注入到由as 填充的常规类型中.

在(>>=)一个Free Monad只是拿其中的一个aS和填补其与新的孔Free f a.

(>>=) :: Free f a -> (a -> Free f a) -> Free f a
Pure a >>= g = g a
Fix fx >>= g = Fix (fmap (>>= g) fx) -- push the bind down the type

这个概念与Chris Taylor的答案非常相似--- Monads只是树状的类型,在那里(>>=)移植了新的树状部分.或者,正如我上面所描述的那样,Monads只是带有Pure孔的常规类型,可以在以后填充.

免费monad在抽象方面有更多的深度,所以我建议Gabriel Gonzalez 用免费的monads文章清除你的代码,它向你展示如何使用免费monad模拟复杂的计算.

了解规范分解

我将要提出的最后一个技巧结合了自由monad的概念和排序的概念,并且是新的通用monad包的基础extensible-effects.

想到monad的一种方法是按顺序执行一组指令.例如,Statemonad可能是指令

Get :: State s s
Put :: s -> State s ()

我们可以用稍微不直观的方式具体地表示为Functor

data StateF s x = Get (s -> x) | Put s x deriving Functor

我们引入该x参数的原因是因为我们将StateF通过形成定点来对序列进行排序StateF.直觉上,这就好像我们自己替换它x,StateF以便我们可以编写类似的类型

modify f = Get (\s -> Put (f s) (...))

其中(...)是序列中的下一个动作.我们使用上面monad中的Pure构造函数,而不是永远地继续它free.为此,我们还必须标记非Pure位Fix

-- real Haskell now
modify f = Fix (Get $ \s -> Fix (Put (f s) (Pure ()))

这种思维模式还有很多,我将再次引导你看Gabriel的文章.

但是你现在可以带走的是,有时候你有一种表明一系列事件的类型.这可以解释为某种典型的表示方式,Monad您可以使用free从规范表示中构建有问题的Monad.我经常使用这种方法在我的应用程序中构建"语义"monad,如"database access monad"或"logging"monad.

Answer 3

根据我的经验,找出并同时为monad建立直觉的最简单方法是尝试实现return并(>>=)为您的类型并验证它们是否满足monad定律.