21

详解函数式编程之 Monad

 3 years ago
source link: https://netcan.github.io/2020/09/30/详解函数式编程之Monad/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

前言

最近终于搞清楚了 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 概念，其实也不是那么难了，之后理解这类概念就更加得心应手了，这也是抽象之美。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK