详解函数式编程之 Monad

微信扫一扫,分享到朋友圈

详解函数式编程之 Monad

前言

最近终于搞清楚了 Monad 的本质,趁热记录下来,相信大家或多或少在编程语言中见过并用过,只不过不知道那是 Monad 罢了,也为了方便大家理解 Monad,后面我会用各种主流语言中具有代表性的 Monad 作为例子,如果对理论不感兴趣可以直接跳到后面,寻找你熟悉语言的例子进行理解后,再回头看看理论。

何为 Monad

Monad 概念最初来自于范畴论,后来引入进函数式编程语言,由函数式编程发扬光大,渐渐渗透到其他主流语言中。

FP 中具有代表性的语言是 Haskell,其特点是函数是第一公民,延迟计算、引用透明。正因为是延迟计算,所以对表达式求值时顺序是不确定的,然而在需要确定顺序的场合,比如 IO,在屏幕中打印字符串要求用户输入,然后等待用户输入,若顺序不确定,很有可能颠倒顺序,即先等待用户输入,然后打印字符串要求用户输入。而 Monad 能做到确定顺序即确定控制流,像 过程式
语言一条条语句按顺序执行那样;其次是 Monad 能屏蔽副作用,例如在 IO Monad 中,所有对 IO 操作都被屏蔽在 Monad 上下文中,从而确定了一个边界,也没违背 FP 的无副作用性质。

关于确定控制流,其实不只有 Monad 这条路,还有经典的 Continuation passing style(CPS)风格,经过 CPS 变换可以实现函数在任意点挂起,后续恢复执行,没错,这也是协程的特性,C++20 协程的 await_suspend
接口传递的就是 Continuation 供后续恢复上下文;然而 CPS 风格代码可读性过差,回调嵌套回调,层数一多智商不够用了。好在 Monad 提供了一种友好的方式,毕竟程序猿更加能接受的是符合直觉的串行代码,而不是回调嵌套代码。

Monad 定义

这部分是关于 Monad 的理论,Monad 是一个类型构造子(下面简称 M
),定义了两个操作:

  1. unit :: t -> M t
    ,将类型 T 包装
    成 Monad 类型,也被常常称为 return/pure/lift
    操作
  2. bind :: M a -> (a -> M b) -> M b
    ,bind 组合子,输入一个 M a
    和一个函数然后返回 M b
    ,输入的函数可以拿到 被包装
    的类型 a
    ,进行变换返回 M b
    。这个操作定义了二元操作符,在 haskell 里用 >>=
    操作符表示。

这两个操作可以这样理解,定义个 Monad 类型用于 包裹
另一个类型 T
,同时定义一个二元操作,左边对象是个 Monad<T>
,右边对象是个函数接受被包裹的 T
值并返回一个 Monad<U>
对象,这样就能不断通过这个二元操作串起来。

在 haskell 中定义就是:

class Monad m where
return :: a -> m a
(>>=) :: forall a b . m a -> (a -> m b) -> m b

只要满足这两个定义,就可以看做是 Monad,其有些比较有趣的性质:

  1. join :: M (M a) -> M a
    ,join 操作可以看做是去掉一层 Monad,这样性质比较重要,可以 去掉嵌套
  2. unit
    >>=
    运算的单位元

    unit t >>= f(t) ↔ f(t)
    m a >>= unit ↔ m a
    
  3. >>=
    操作满足结合律: m a >>= \x -> (f x >>= g) ↔ (m a >>= f) >>= g

主流语言的常见 Monad

Maybe

Maybe 其实是一种非常简单的 Monad,它的概念是表达一个值可有可无,当值被封装到 Maybe 的世界里,它其实有两种可能:要么拥有值即 Just,要么没有即 Nothing。根据 Monad 的性质,Maybe 应该有如下操作:

  • 将值包装成 Maybe 类型
  • 二元操作,将 Maybe 类型与操作它的函数串起来,产生新的 Maybe 类型

前者用于构造 Maybe Monad,后者用于串联一系列 Maybe 类型,避免写一堆 if/match、取值语句,况且从 Maybe 取出其不存在的值是有可能抛异常的。

既然 Maybe 可以包装一个值,那么该值可能也是 Maybe 的,即 Maybe<Maybe<T>>
,这种情况下实际取值情况有 3 种:最外层的 Just<Maybe<T>>
Nothing
,而 Just<Maybe<T>>
取值又有两种: Just<Just<T>>
Just<Nothing>
,逻辑上讲其实应该只有两种取值的: Just<T>
Nothing
。那么需要一层层判断取值么?这种情况就得写两个嵌套 if/match,若类型为 Maybe<Maybe<Maybe<T>>>
,难道需要写嵌套 3 个 if/match 么?还记得 Monad 有个有趣的性质是 join 操作么,可以通过不断 join 去除外层的 Monad,最终 flatten 成一个 Monad 即: join Maybe<Maybe<T>> -> Maybe<T>
,从而减少 if/match 嵌套判断。

很多语言都提供了这种概念,比如 Haskell 的 Maybe,Rust 的 Option,C++ 的 std::optional。

Rust

Rust 的 Option 其实做的相当完备,我们看看其定义:

enum Option<T> {
None,
Some(T),
}

和关键的 Monad 操作:

  • None/Some<T>
    提供了将值包装成 Option<T>
    的可能,即 unit
    操作
  • fn and_then<U, F>(self, f: F) -> Option<U>
    实现了二元操作,即 bind
    操作

根据例子看看这两个操作是怎么结合的:

fn sq(x: u32) -> Option<u32> { Some(x * x) }
fn nope(_: u32) -> Option<u32> { None }
assert_eq!(Some(2).and_then(sq).and_then(sq), Some(16)); // 串联操作
assert_eq!(Some(2).and_then(sq).and_then(nope), None);
assert_eq!(Some(2).and_then(nope).and_then(sq), None); // 串联操作,避免判断 None
assert_eq!(None.and_then(sq).and_then(sq), None);

可惜 Rust 不支持操作符重载,只能显式的 and_then
。顺便一提,Rust 的 Option 也提供了 join 操作,即 fn flatten(self) -> Option<T>
函数。

Haskell

Haskell 的 Maybe 定义如下:

data Maybe a = Just a | Nothing

而 Maybe 又是 Monad,定义了 unit 和 bind 操作:

instance Monad Maybe where
return  a           = Just a
(Just x) >>= f      = f x
Nothing  >>= _      = Nothing

看看例子:

sq x   = Just (x * x)
nope _ = Nothing
*Main> Just 2 >>= sq >>= sq
Just 16
*Main> Just 2 >>= sq >>= nope
Nothing
*Main> Just 2 >>= nope >>= sq
Nothing
*Main> Nothing >>= sq >>= sq
Nothing

和 Rust 那个例子一模一样,除了用 >>=
代替 and_then
。Haskell 还提供了一种语法糖 do,看起来更加直观,就和命令式语言写法差不多:

do
v1 <- Just 2
v2 <- sq v1
v3 <- sq v2
return v3 -- Just 16

C++

C++17 提供的 std::optional
其实不够完备,得自己封装一下,不适合拿出来当 Monad 讲,所以我用 C++ 实现了一个 Maybe.cpp
用于展示 Monad 的概念。

Maybe 定义如下:

template<typename T>
struct Just {
T value;
operator const T&() const { return value; }
Just(const T& value): value(value) {}
};
struct Nothing {};
template<typename T>
struct Maybe {
std::variant<Just<T>, Nothing> value;
Maybe(const T& value): value(value) {}
Maybe(const Nothing&): value(Nothing{}) {}
};

构造函数即 unit
操作,再来定义一个 bind
操作:

template<typename T>
auto just(T x) -> Maybe<T> { return x; }
struct AnyType {
template<typename T> operator T();
friend std::ostream& operator<<
(std::ostream& os, const AnyType&) { return os; };
};
auto nothing() -> Maybe<AnyType> { return Nothing{}; }
template<typename T, typename F>
auto operator>>=(const Maybe<T>& ma, F&& f) {
using R = std::invoke_result_t<F, T>;
return std::visit(overloaded {
[&](const Just<T>& v) -> R
{ return f(static_cast<T>(v)); },
[](Nothing) -> R { return Nothing{}; }
}, ma.value);
}

同样提供例子看看,可以发现和 Haskell 很相似。

show((just(3) >>=
[](int v) -> Maybe<double> {
return {v * 1.5};
}) >>= [](double v) -> Maybe<double> {
return {v * 1.5};
}); // Just 6.75
show((nothing() >>=
[](int v) -> Maybe<double> {
return {v * 1.5};
}) >>= [](double v) -> Maybe<double> {
return {v * 1.5};
}); // Nothing

IO Monad

在 FP 中一切都是纯函数,那么对于 IO 这种拥有副作用的功能,怎么融入到 FP 的世界中去呢?有了 IO Monad 包裹了对 IO 的操作动作,副作用被约束在 Monad 中,同时也提供了与外界环境交互的边界。

Haskell 提供了最基本的两个 IO 操作:

getLine :: IO String
print :: Show a => a -> IO ()

观察 getLine
发现函数返回类型是个 IO String
,也就是读到的字符串被包裹在了 IO Monad 中,用户没法直接操作 Monad 里面的值,那么若要对读到的字符串进行操作,就得通过 bind 操作,将动作隔离在 Monad 的世界里,同时该操作返回类型也必须是个 IO Monad,这样就不会将副作用带出来了。

举个例子,要求用户输入一个数,然后将该数乘以二,最后打印在屏幕上,代码这样写:

putStrLn "input a number"
>>= \_ -> getLine
>>= \str -> print $ (read str :: Int) * 2

这个表达式的类型是 IO ()
,对输入的数乘以二操作也被隔离在 IO Monad 的世界里了,普通函数没法直接拿到 IO 世界里的值,必须得将函数 lift 到这个世界里与其共舞。同样的由于 Monad 确定了控制流,保证了按代码顺序执行,先 getLine 后 print。

Writer Monad

有时候我们需要对每一步操作进行日志记录,简单起见,但是不想每次操作后进行日志拼接工作,若抽象成 Monad,可以让 bind 帮我们完成这个操作,这节我打算用 Javascript 来快速实现个原型,方便熟悉 Javascript 的同学理解。

Writer 定义为一个序对,第一个存放函数执行结果,第二个存日志: [value, string]

unit 操作定义如下:

const unit = value => [value, ""];

bind 操作对 value 执行函数 f,接着拼接日志,然后返回一个 Writer。

const bind = (writer, f) => {
const [value, log] = writer
const [result, updates] = f(value)
return [result, log + updates]
};

由于 bind 操作输入一个 Writer 最终输出的也是 Writer,那么可以考虑写个函数将一系列操作串起来:

const pipelog = (writer, ...fs) =>
fs.reduce(bind, writer);

最后看看例子:

const doubled = x => [x*2, `${x} was doubled.\n`]
const halved = x => [x/2, `${x} was halved.\n`]
pipelog(unit(2), doubled, doubled, doubled, halved)
// [8, "2 was doubled.↵4 was doubled.↵8 was doubled.↵16 was halved.↵"]

Parser Combinator

再来看看一个比较复杂的例子,Parser 也是一个 Monad,经过 bind 操作可以将各种类型的 Parser 串起来,解析字符串输出不同的结构。而 Parser 定义并不是像前面一样是个类型容器结构,而是一个函数:

Parser a :: String -> [(a, String)]

Parser 包裹了要得到的类型,通过执行 Parser 函数,解析输入一个字符串,输出所需要的类型,具体细节可以看我之前写的一篇文章: C++ 元编程之 Parser Combinator
,其中的 makeCharParser/oneOf
就是不同种类的 unit 操作,同时定义了个类似 bind 操作的 combine
和二元操作符 operator>/operator<

Promise/Future

最后一个例子,也是主流的概念,相当重要,几乎是写异步编程必须要掌握的概念,通过 Monad 操作,以同步(串行)方式写异步代码!

Promise/Future是上个世纪七十年代就提出来的概念,顾名思义,就是我给你的承诺 Promise,将来 Future 某个时间点履行承诺。通过 Promise 可以得到一个 Future,而 Future 包裹了未来的值,直到 Promise 将值设定,Future 最终可以取出值,在这之前是拿不到值的(毕竟都没有,怎么拿)。

那么 Future 做成一个 Monad 会怎么样?unit 操作就是通过 Promise 得到 Future<T>
,而 bind 二元操作就是输入一个 Future<T>
和动作,该动作可以拿到未来的值 T
,进行处理后返回一个新 Future
,这样就能将各个 Future 串起来。

既然 Future 是对未来的预期,当下可能没有值,自然拿不到值,但是我们可以通过 bind 操作将处理值的动作串起来带入 Future 的世界里,将来某个时间点执行这个动作,这也是以同步方式写异步代码!FP 的 Monad 概念完美解决了传统语言异步编程需要挂各种回调的难处。

若像 Haskell 的 do 语法糖那样引入 await 关键字,异步代码看起来就更加串行了。

Javascript

最初我是通过 Javascript 了解异步编程方式,回过头来一看,其 Promise 也是一个 Monad,然而 Future 概念也收到 Promise 里去了。

对于 unit 操作,其实是 Promise 的构造函数,传递一个动作,得到一个 Promise,表示将来会执行这个动作:

const myPromise = new Promise((resolve, reject) => {
// condition
});

而 bind 二元操作,对应于 Promise 的 then 接口,传递一个动作执行,返回一个 Promise,从而能将各个 Promise 串起来。

看一个例子感受下用 Monad 前后怎么将异步代码同步化的:

firstRequest(response =>
secondRequest(response, nextResponse =>
thirdRequest(nextResponse, finalResponse =>
console.log('Final response:' + finalResponse);
, failureCallback),
failureCallback),
failureCallback);

使用 Monad 后,大大简化回调接口:

firstRequest()
.then(response      => secondRequest(response))
.then(nextResponse  => thirdRequest(nextResponse))
.then(finalResponse => console.log('Final response:' + finalResponse))
.catch(failureCallback);

最后再引入 await 语法糖,看上去更加串行了,这也是协程的提供的手段:

try {
response      = await firstRequest();
nextResponse  = await secondRequest(response);
finalResponse = await thirdRequest(nextResponse):
console.log('Final response:' + finalResponse);
} catch (e) {
failureCallback(e);
}

尾声

终于写到最后了,其实我们用了很久的 Monad,不同的 Monad 背后高度一致性,将控制流封装起来,从而提高代码的可读性。应用多了回头理解抽象的 Monad 概念,其实也不是那么难了,之后理解这类概念就更加得心应手了,这也是抽象之美。

微信扫一扫,分享到朋友圈

详解函数式编程之 Monad

世界首款1/30实物大自由高达立像微缩模型11月将开预订 售价14990元

上一篇

《哆啦A梦》初代声优富田耕生因病去世 享年84岁

下一篇

你也可能喜欢

详解函数式编程之 Monad

长按储存图像,分享给朋友