所以这个 Monads 到底是什么啊之让我学学

简单的说单子(Monad)就是自函子范畴上的一个幺半群 👀 你说这个谁懂啊

从很久以前就听说了 Monads 这个概念，但是一直都不懂，今天终于花了几个小时去理解（然后还是似懂非懂）

Option, one of the most simple Monad ¶

monad 可以理解成包了一些其他控制结构/副作用, 用来提供数据的管线

让我们看看 Haskell 和 Lean 4 里分别对 Monad 的定义

class Monad m where
  return :: a -> m a           -- 也可以叫 pure
  (>>=)  :: m a -> (a -> m b) -> m b

class Monad (m : Type u → Type v) where
  pure : {α : Type u} → α → m α
  bind : {α β : Type u} → m α → (α → m β) → m β

之后我们 focus on 最经典的 Monads 之一 也就是 Option 或者说 Maybe

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

-- 真实代码不长这样

inductive Option (α : Type u) where
  /-- No value. -/
  | none : Option α
  /-- Some value of type `α`. -/
  | some (val : α) : Option α

instance : Monad Option where
  pure x := some x
  bind opt next :=
    match opt with
    | none => none
    | some x => next x

可以大概地看出一件事：一个 Monad （在这里）是一个类型类，得到一种将它们串起来的方法

什么事类型类呢？类型类可以理解为一个接口 / trait 之类的东西，实现了这个接口以后就有这个接口的特征

也就是说，我们给 Option 实现了 Monad 以后，就能用 Monad 来串联 Option 了

#eval bind (some 2) λ x => pure $ x + 3
#eval (some 2) >>= λ x => pure $ x + 3
-- some 5

也就是说，我们可以这样直观地去理解一个 Monad：它是一个管子，pure 用来往管子里放东西，bind 用来定义管子里的东西怎么流动。

为了方便非函数式背景的人比如我进一步理解 Monad，我们可以用 C++ 模拟一个半残的 Monad Option：

#include <functional>
#include <iostream>
#include <optional>
template <class T, class M> class Monads {
public:
  static auto pure(T) -> M;
  static auto bind(M, std::function<M(T)>) -> M;
  auto operator>>(std::function<M(T)> fun) -> M { return bind(*this, fun); }
};

template <class T> class Option : public Monads<T, Option<T>> {
  std::optional<T> v;
  Option(std::optional<T> v) : v(std::move(v)) {}

public:
  static auto pure(T val) -> Option<T> { return Option(std::optional<T>(val)); }
  static auto bind(Option opt, std::function<Option(T)> fun) -> Option {
    if (opt.v.has_value()) {
      return fun(opt.v.value());
    } else {
      return Option(std::nullopt);
    }
  }
  auto operator>>(std::function<Option(T)> fun) -> Option {
    return bind(*this, fun);
  }
  auto get_v() -> std::optional<T> { return this->v; }
};

int main() {
  auto opt = Option<int>::pure(3);
  auto p2 = opt >> [](int v) { return Option<int>::pure(v + 2); };
  std::cout << p2.get_v().value(); // 5
}

有了 Monad 定义的这根管子，任何继承了 Monad （或者说实现了 Monad 接口）的类都将会有一个 >> 符号，把自己“流”到一个函数里面，流出来一个新的 Monad。这就是 Monad 的作用。

Why Monads ¶

如果没有 monads，我们可能不得不写出这样的代码

def get1357 (xs : List α) : Option (α × α × α × α) :=
  match xs[0]? with
  | none => none
  | some first =>
    match xs[2]? with
    | none => none
    | some third =>
      match xs[4]? with
      | none => none
      | some fifth =>
        match xs[6]? with
        | none => none
        | some seventh =>
          some (first, third, fifth, seventh)

比如说许多的非函数式语言，就不得不这样写

func foo() {
  _, err = task1();
  if err != nil {
    return nil, err
  }
  _, err = task2();
  if err != nil {
    return nil, err
  }
  _, err = task3();
  if err != nil {
    return nil, err
  }
  _, err = task4();
  if err != nil {
    return nil, err
  }
  _, err = task5();
  if err != nil {
    return nil, err
  }
}

人们已经注意到这样的链式行为非常多，以至于在 C#, Kotlin, Javascript 等语言中，有一个 ?. 运算符，专门用于链式地在可能为 null 的值上查找属性或调用方法的。如果 ?. 前的值为 null，则整个表达式为 null。否则，该非 null 值会被用于使用。像这样链接 null 检查比编写和维护深层嵌套的 if 方便得多。

State Monad ¶

在接触纯函数式语言的时候，我们最先知道的也是最先深受其害大为震撼的，应该是它的不可变。我们不再能方便地使用状态。但是有时候，必须要用到一些状态。

比如，让我们用函数式语言写一个斐波那契数列的计算。

fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n - 2)

main :: IO ()
main = print $ fib 10
-- 55

它很好，但是效率致命的低下，具有指数级的时间复杂度。有很多更加函数式风格的改善，不过让我们考虑 C/C++ 的代码

int fib(int n) {
    int a = 1, b = 1;
    for (int i = 1; i <= n; i++) {
        int c = a;
        a = b;
        b = a + c;
    }
    return a;
}

a 和 b 是状态，维护了 fib (n - 1) 和 fib (n - 2)

如果是函数式语言的话，容易想出一种解决方案：把状态当成参数传入（和传出）。给定状态 $S$, 返回 $(R, S')$ 其中 $R$ 是本来的返回值，$S'$ 是修改后的新状态。

fibHelper :: Int -> (Int, Int) -> Int
fibHelper 0 (a, b) = a
fibHelper n (a, b) = fibHelper (n - 1) (b, a + b)

fib :: Int -> Int
fib n = fibHelper n (0, 1)

main :: IO ()
main = print $ fib 10
-- 55

这样很好地解决了这个问题。

注意到，因为有了状态，之前理论上可能可以交换的执行顺序变得固定了。在之前，fib (n - 1) 和 fib (n - 2) 完全是独立的，理论上先算哪个都没关系。现在后面的状态总是依赖于前面的状态被计算出。这种关系形成了一个链条，于是有了我们 Monads 的用武之地。

State Monads 通常被实现为一个

structure State (σ α : Type) where
  run : σ → (α × σ)

容易看出这就是一个对 state -> (val, state) 的包装，

instance : Monad (State σ) where
  pure x := ⟨fun s => (x, s)⟩  -- 直接返回 x，不改变状态
  bind sa f := ⟨fun s =>
    let (a, s') := sa.run s  -- 取出当前状态，计算 a
    (f a).run s'⟩  -- 用新状态执行 f

然后在上面经常会实现有 get 和 put 两个很方便的函数

def get : State σ σ :=
  ⟨fun s => (s, s)⟩  -- 直接返回当前状态 s

def put (s' : σ) : State σ Unit :=
  ⟨fun _ => ((), s')⟩  -- 不关心旧状态，直接设置新状态

比如之前那个斐波那契数列，可以这样写：

import Std

def fibStep : StateM (Nat × Nat) Nat := do
  let (a, b) ← get    -- 读取 (a, b)
  set (b, a + b)     -- 更新状态为 (b, a+b)
  return b

def fib (n: Nat) := (do
  for _ in [0:n] do
    _ <- fibStep
  return <- fibStep).run' (0, 1)

#eval [1,2,3,4,5,6].map fib
-- [1, 2, 3, 5, 8, 13]

我们把它 desugar，基本上相当于

def fibStep' : StateM (Nat × Nat) Nat :=
  get >>= fun (a, b) =>           -- 读取 (a, b)
  set (b, a + b) >>= fun _ =>     -- 更新状态为 (b, a+b)
  pure b                          -- 返回 b

def fibrecu (step : Nat) : StateM (Nat × Nat) Nat :=
  fibStep >>= fun r => match step with
  | .zero => pure r
  | .succ step' => fibrecu step'

def fib' (n : Nat) : Nat := (fibrecu n).run' (0, 1)

#eval [1,2,3,4,5,6].map fib'
-- [1, 2, 3, 5, 8, 13]

也就是说，在 State Monad 这个神奇的管道下，只需要传入初始状态，则 get 和 set 就能一路把状态在管道内传递，而无需我们手动维护。有了 State Monads 我们就在 “不可变” 的语言里产生了 “可变”

当然，我们这样费力 Desugar 反而有点适得其反了，其实我们本身就是为了能写 do 记号而引入的 Monads。

Promise Monad ¶

什么？这不是 Promise，这是一个异步 Monad 。我们这个异步 Monad 体积小方便携带，拆开一包，放 then 里就变出值，怎么 then 都有值，用来解决回调地狱，做异步都是很好用的。你看打开以后像 Monads 一样的结构，放在事件循环里，你看它遇 resolved 变大变高，可用性很强的。打开以后，是一条加大加厚的 value，你看它怎么玩都玩不坏，不掉毛不掉絮，then 个七八次都没问题，异步函数带上它非常方便，你用它跑个 XMLHTTPRequest，跑个 fs.readFile，干净又卫生。什么？在哪里用？点击键盘 F12，开 Console，敲一行，看一行，还有结果。

当我们写 JavaScript 的时候，应该感谢 Monads 的伟力。显然 Promise （删掉 catch）本质上是一个 Monad：

const monad_promise = {
  pure: Promise.resolve as <T>(t: T) => Promise<T>,
  bind: Promise.prototype.then as <T, U>(
    this: Promise<T>,
    fn: (t: T) => Promise<U>
  ) => Promise<U>,
};

有了 Promise Monad，之前的回调地狱就这样变成了

Promise.resolve(3)
  .then((x) => x + 4)
  .then((x) => x * 2)
  .then((x) => some_api(x));

同样的，Javascript 也提供了像 do notation 那样消除显式的 then 的工具，也就是 async

async function () {
  let x = await Promise.resolve(3);
  x = await add4(x);
  x = await somefunc(x);
  x = await some_api(x);
  return x
}

起到了将异步函数打成看上去像同步一样的效果。

总结 ¶

所以并非只有函数式语言，我们其实已经应用了许多的 Monads 到实践中。Monads 将链式的控制流封装起来，提供统一的表达方式，从而提高代码的可读性。