Skip to content

Latest commit

 

History

History
193 lines (156 loc) · 5.14 KB

Monad.md

File metadata and controls

193 lines (156 loc) · 5.14 KB
Raw

十分钟魔法练习：单子

By 「玩火」 改写 「光量子」

前置技能：Rust 基础，HKT

use crate::HKT::HKT;
use compile_fail::compile_fail;

注意：

本节依赖的 HKT 使用了不稳定语言特性实现，详见 高阶类型 一节。

单子

单子(Monad)是指一种有一个类型参数的数据结构，拥有pure（也叫unit或者return）和fmap（也叫bind或者>>=）两种操作：

pub trait Monad<'a, A>: HKT {
    fn pure(v: A) -> Self;
    fn fmap<F: 'a, B>(self, f: F) -> Self::Higher<B>
    where
        F: Fn(A) -> Self::Higher<B>;
}

其中pure要求返回一个包含参数类型内容的数据结构，fmap要求把值经过f以后再串起来。

举个最经典的例子：

List Monad

impl<A> Monad<'_, A> for Vec<A> {
    fn pure(v: A) -> Self {
        vec![v]
    }
    fn fmap<F, B>(self, f: F) -> Self::Higher<B>
    where
        F: Fn(A) -> Self::Higher<B>,
    {
        // let mut new_vec: Self::Higher<B> = vec![];
        // self.into_iter()
        //     .for_each(|item| f(item).into_iter().for_each(|i| new_vec.push(i)));
        // new_vec
        self.into_iter().flat_map(f).collect()
    }
}

于是我们可以得到如下平凡的结论：

#[test]
fn test_monad_vec() {
    assert_eq!(Vec::<i64>::pure(3), vec![3]);
    assert_eq!(
        vec![1, 2, 3].fmap(|v| vec![v + 1, v + 2]),
        vec![2, 3, 3, 4, 4, 5]
    )
}

Option Monad

Rust 是一个空安全的语言，想表达很多语言中null这一概念，我们需要使用 Option 类型。对于初学者来说，面对一串可能出现空值的逻辑来说，判空常常是件麻烦事：

fn add_i(ma: Option<i64>, mb: Option<i64>) -> Option<i64> {
    // 提示：请不要在实际场景下写出这样的代码
    if let None = ma {
        return None;
    }
    if let None = mb {
        return None;
    }
    Some(ma.unwrap() + mb.unwrap())
}

现在，我们将Option扩展成HKT：

impl<A> HKT for Option<A> {
    type Higher<T> = Option<T>;
}

可以像这样定义Option Monad：

impl<A> Monad<'_, A> for Option<A> {
    fn pure(v: A) -> Self {
        Some(v)
    }
    fn fmap<F, B>(self, f: F) -> Self::Higher<B>
    where
        F: Fn(A) -> Self::Higher<B>,
    {
        if let None = self {
            None
        } else {
            f(self.unwrap())
        }
    }
}

上面add_i的代码就可以改成：

fn add_m(ma: Option<i64>, mb: Option<i64>) -> Option<i64> {
    type m = Option<i64>;
    ma.fmap(|a| {
        // a <- ma
        mb.fmap(|b| {
            // b <- mb
            m::pure(a + b) // pure (a + b)
        })
    });

    // 也可以写成如下形式
    m::fmap(ma, |a| {
        // a <- ma
        m::fmap(mb, |b| {
            // b <- mb
            m::pure(a + b) // pure (a + b)
        })
    })
}

这样看上去比连续if-return优雅很多。在一些有语法糖的语言(Haskell)里面Monad的逻辑甚至可以像上面右边的注释一样简单明了。

注：

让我们试着在 Rust 里糊一下这个语法糖（do notation）

macro_rules! mdo {
    ($monad:ty, pure $e:expr) => (<$monad>::pure($e));

    ($monad:ty, _ <- $e:expr ; $($rest:tt)*) => (<$monad>::fmap($e, move |_| mdo!($monad, $($rest)*)));
    ($monad:ty, _ <- pure $e:expr ; $($rest:tt)*) => (<$monad>::fmap($monad::pure($e), move |_| mdo!($monad, $($rest)*)));

    ($monad:ty, $v:ident <- $e:expr ; $($rest:tt)*) => (<$monad>::fmap($e, move |$v| mdo!($monad, $($rest)*)));
    ($monad:ty, $v:ident <- pure $e:expr ; $($rest:tt)*) => (<$monad>::fmap($monad::pure($e), move |$v| mdo!($monad, $($rest)*)));

    ($monad:ty, ($($vs:pat),*) <- $e:expr ; $($rest:tt)*) => (<$monad>::fmap($e, move |($($vs),*)| mdo!($monad, $($rest)*)));
    ($monad:ty, ($($vs:pat),*) <- pure $e:expr ; $($rest:tt)*) => (<$monad>::fmap($monad::pure($e), move |($($vs),*)| mdo!($monad, $($rest)*)));

    ($monad:ty, $e:expr ; $($rest:tt)*) => (<$monad>::fmap($e, move |_| mdo!($monad, $($rest)*)));
    ($monad:ty, $e:expr) => ($e)
}

fn add_m_with_do(ma: Option<i64>, mb: Option<i64>) -> Option<i64> {
    type m = Option<i64>;
    mdo!(m,
        a <- ma;
        b <- mb;
        pure (a + b)
    )
}

敏锐的读者在阅读上述add_i的实现时，可能已经发现，在 Rust 中这一函数有更自然的内置写法：

fn add_i_alt(ma: Option<i64>, mb: Option<i64>) -> Option<i64> {
    ma.and_then(|a| mb.and_then(|b| Some(a + b)))
}

如果你曾阅读过 Option 相关的文档或源码，你可能会看到如下注释：

/// Returns [`None`] if the option is [`None`], otherwise calls `f` with the
/// wrapped value and returns the result.
///
/// Some languages call this operation flatmap.
#[compile_fail]
pub fn and_then<U, F: FnOnce(T) -> Option<U>>(self, f: F) -> Option<U> {}

让我们抄下来并改写一下 fmap 的签名：

#[compile_fail]
fn fmap<U, F: Fn(A) -> Self::Higher<U>>(&self, f: F) -> Self::Higher<U> {}

所以，如果你已经写过一段时间的 Rust，你很有可能已经在不知不觉中大量使用了 Option Monad 和 flatmap 了。