Haskell 笔记:Monad 引论

动机

pure functions 看似完美,但却不能模拟现实世界中的诸多任务。这是由于 pure functions 是良定的映射,对于特定的输入值会返回唯一的输出。这种模式在面对如下任务时会显得苍白无力:

  • 有可能失败的任务。如大多数的 IO。
  • 依赖外部状态的任务。如(伪)随机数生成器。
  • 非确定性任务,即对于确定的输入可能有多个输出。这种在 IP 中较为少见。
  • 对外界会造成影响的任务。如大多数的写入过程。

这些问题可以用数学中的域扩充技巧来解决。

域扩充

在数学中,当定义问题的范畴不足以容纳问题的解时,我们通常会对相关的范畴进行扩充。类似的技巧同样也可以应用在这里。

假设一个不良定的函数 f: A -> B

  • 如果 f 有可能失败,我们可以将 B 扩充为 Err(B) ∪ { reasons of failures },其中 reasons of failures 可能是对异常的描述,也可以是空值一类的东西。则 f': A -> Err(B) 是良定的映射,且与 f 行为一致。事实上,这就是 Maybe Monad 和 Either Monad。
  • 如果 f 依赖于外部状态,我们定义 Pref(B)从外部状态空间到 B 的映射的全体,则 f': A -> Pref(B) 为良定的映射,且行为和 f 一致。换言之,对于特定的输入 af'(a) 返回一个函数,其中蕴含了已知 a 时如何从各种不同状态得到结果的逻辑。事实上,这就是 State Monad。
  • 如果 f 具有非确定性,我们将 B 扩充为 Power(B),即 B 的幂集。则 f': A -> Power(B) 为良定的映射,且行为与 f 一致。事实上,这就是 List Monad。
  • 如果 f 依赖于真实世界,我们将 B 扩充为 IO(B),其中的元素为一些值域为 B伪函数,可能对真实世界有影响。这些伪函数已经脱离了 pure functions 的范畴,但将它们看成元素是没有问题的。如此一来 f': A -> IO(B) 为良定的映射,且行为与 f 一致。事实上,这就是 IO Monad。

以上操作都有一个共同点,即对一个不良定函数的值域做了扩充,使之变成良定函数。如果用 Haskell 语言描述,它们都有相似的型:f :: a -> m b,其中 m 为扩充规则。

一个问题随之而来:这样的新函数该怎么结合?为此我们要对相关逻辑进行抽象。这就是 Monad。

Monad

这里我们尝试从实际需求出发,导出一个 Type Constructor 成为 Monad 的必要条件。

约定两个名称:

  • a -> m b 型函数为 monadic function
  • a -> b 型函数为 non-monadic function

首先需要解决的是 monadic functions 如何结合的问题。这个问题具有重要的现实意义。monadic function 常常代表某种计算任务,它们之间的结合相当于把若干计算任务串行化,而后者是非常常见的需求。

我们希望有一种运算符有如下的类型 (b -> m c) -> (a -> m b) -> (a -> m c),在此记为 >=> (因其形状,常被叫做 fish operator)。一个自然的想法是,Monad m 需要某种平凡的拆箱操作 extract' :: m a -> a。所谓“平凡”,即 extract' 不应该丢失参数的任何信息。但这往往不能实现,因为 m a 通常会比 a 包含更多的信息,导致 extract' 无法构成良定的映射。例如 Maybe a 中的值 Nothing 就无法在 a 中找到对应的值。

而事实上,我们不需要条件这么强的拆箱操作。在 m 已是 Functor 的情况下,拆箱操作可以弱化为 join :: m (m a) -> m a。我们尝试用 fmapjoin 合成 >=>

f :: b -> m c
g :: a -> m b

fmap f :: m b -> m (m c)
(fmap f) . g :: a -> m (m c)
join . (fmap f) . g :: a -> m c

-- i.e.

f >=> g = join . (fmap f) . g

Functor 的假设是容易成立的。当然我们可以定义多个不同的 fmap,如此产生的 Monad 会有不同的语义。join 的假设也是容易成立的,m (m a) 通常和 m a 包含相同多的信息。故此做法是实际可行的。

我们再考虑 monadic function 和 non-monadic function 结合的问题。期望有如此一个运算:>.> :: (b -> c) -> (a -> m b) -> (a -> m c)。注意,此处返回值是 a -> m c 而不是 a -> c,因为我们不希望 a -> m b 产生的额外信息有所丢失。自然地,我们希望有一个平凡的装箱操作,return :: a -> m a。如此一来便可结合 >=> 完成上面的运算:

f :: b -> c
g :: a -> m b

return . f :: b -> m c
(return . f) >=> g :: a -> m c

-- i.e.

f >.> g :: (return . f) >=> g

non-monadic function 和 monadic function 另一个方向的结合是平凡的。

综上我们可以得到成为 Monad 的基本条件:

  • 是 Functor,存在 fmap :: (a -> b) -> m a -> m b
  • 有一个平凡的拆箱操作 join :: m (m a) -> m a
  • 有一个平凡的装箱操作 return :: a -> m a

为了描述平凡,我们要求三个函数必须满足如下公理(下面的 f 为 non-monadic function):

  1. return . f == (fmap f) . returnreturn 的平凡性)
  2. join . fmap (fmap f) == (fmap f) . joinjoin 的平凡性)

事实上在 Category Theory 中,还有另外两条公理:

  • join . (fmap join) == join . join
  • join . fmap return == join . return == id

以上四条公理描述了 Id(恒等 Functor)、mm^2m^3 之间的泛性质,并使图交换。

Monad Typeclass

以下为 Prelude 中的定义:

class Functor m => m a where

return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b

此处没有出现 join,也没有 fish operator,而是使用了一个更常用的算符 >>= (通常称为 bind operator)。这是因为在实际中我们不直接将函数结合,而是使用 non-pointfree 的写法。

此外,还有 >> :: m a -> m b -> m b 运算符。return>>=>> 三者是构成 do-notation 的基础。此处不再赘述。

References


作者:hsfzxjy
链接:
许可:CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途,非商业转载请注明出处。

«Haskell 笔记:State Monad

OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.