小而无类型的Monads (2024)

# 微型无类型单子 来源：https://text.marvinborner.de/2024-11-18-00.html - 标签联合 ([Tagged Unions](https://text.marvinborner.de/2024-11-18-00.html#tagged-unions)) - Maybe ([Maybe](https://text.marvinborner.de/2024-11-18-00.html#maybe)) - Either ([Either](https://text.marvinborner.de/2024-11-18-00.html#either)) - 语法 ([Syntax](https://text.marvinborner.de/2024-11-18-00.html#syntax)) - 状态 ([State](https://text.marvinborner.de/2024-11-18-00.html#state)) - 输入输出 ([IO](https://text.marvinborner.de/2024-11-18-00.html#io)) - 解析器 ([Parser](https://text.marvinborner.de/2024-11-18-00.html#parser)) 单子是常用于抽象化显式上下文传递的结构，能使程序更清晰、更易理解。然而，其底层实现常被描述得过于复杂，或隐藏在混乱的类型与实例化代码中。若深入单子的根源，你会发现其机制出奇地简单。我自己在 inbruijn（https://bruijn.marvinborner.de/）——一种无类型、纯函数式语言——中实验单子后，在纯粹函数式但无类型的实现中发现了一种美感，希望与各位分享[1](https://text.marvinborner.de/2024-11-18-00.html#fn1)。作为“副作用”，这些单子变得极其精简，大多数定义仅需几个字符！由于收到一些关于文章晦涩的建设性批评，这里我改用常见的 JavaScript 语法（而非 bruijn）并尝试更好地解释。你可以在[此仓库](https://github.com/marvinborner/picomonad/)中找到所有函数的实现。（另外，这些内容仅用于学习和娱乐，请勿用于生产环境） ## 标签联合 首先介绍一种函数式数据结构基础——我们要在不使用对象或数组等结构的情况下编码状态！同时，我们不关心任何潜在的类型检查。一个数据结构可以（至少）做两件事：**存储**数据和**提取**数据。对于存储，必须确保数据本身（若被解释为函数）永远不会被调用，否则数据可能无法恢复（或直接抛出错误）。对于提取，我们将使用我称为“选择器”的参数。这些选择器用于将存储的数据应用到相应选择器上，从而使数据易于提取。例如，假设我们需要一个能容纳两种不同“类型”（或标签！）——“人”和“动物”——的数据结构。我们希望该结构能告知当前存储的是哪种类型的条目，并提供提取特定类型条目的方法。我们需要两个不同的选择器（每种类型一个），它们本质上就是作为参数传递的函数，我们将用存储的值来调用它们。 要将值存储为“人”或“动物”类型，我们使用两个不同的构造函数，它们接受一个参数 `value`： ``` // Person 构造函数 Person = value => person => animal => person(value) // Animal 构造函数 Animal = value => person => animal => animal(value) // 示例 examplePerson = Person("Lars") // 结果：person => animal => person("Lars") exampleAnimal = Animal("Duck") // 结果：person => animal => animal("Duck") ``` 要判断构造的数据是“人”还是“动物”，可以使用选择器函数。由于选择器函数会被应用于结构内的值，我们忽略参数并返回布尔值： ``` // Person 检查 isPerson = personOrAnimal => personOrAnimal(_ => true)(_ => false) // Animal 检查 isAnimal = personOrAnimal => personOrAnimal(_ => false)(_ => true) console.log(isPerson(examplePerson)) // true console.log(isPerson(exampleAnimal)) // false ``` 从结构中提取数据的方式类似： ``` // Person 提取 getPerson = person => person(value => value)(_ => _) // ---------^^^^^^---------- // 此参数被忽略！ // Animal 提取 getAnimal = animal => animal(_ => _)(value => value) console.log(getPerson(examplePerson)) // "Lars" console.log(getAnimal(exampleAnimal)) // "Duck" ``` 这当然是一个可任意扩展的极简示例。例如，假设一个人有多个属性（如姓名和年龄）。我们也可以扩展 Animal 构造函数以保持对称性，或保持原样并修改函数： ``` // Person 构造函数 Person = name => age => person => animal => person(name)(age) // Person 检查 isPerson = personOrAnimal => personOrAnimal(_ => _ => true)(_ => false) // --^- -^- -----^------ // 姓名 年龄 动物值 // Person 提取 getPersonName = person => person(name => age => name)(_ => _) getPersonAge = person => person(name => age => age)(_ => _) // 类似地，调整被忽略参数的数量： Animal = value => person => animal => animal(value) isAnimal = personOrAnimal => personOrAnimal(_ => _ => false)(_ => true) getAnimal = animal => animal(_ => _ => _)(value => value) ``` 希望你能看出这种编码的优雅与强大之处。事实上，许多对纯 lambda 演算（本质上即上述匿名函数集合）的形式化研究，最终都归结为使用多个参数和选择器函数的同一原则！例如： ``` // Church 对构造函数 // 单标签：选择器 (s) ChurchPair = a => b => s => s(a)(b) // ^----^ -^----^- // 值 选择器 // Church 数 // 两标签：后继 (s) 和 零 (z) // 存储的值在 z 中，通过选择器的组合 churchThree = s => z => s(s(s(z))) // -^----^- // 选择器 // Scott 数 // 两标签：后继 (s) 和 零 (z) // 存储的值是另一个 Scott 数！ scottThree = s1 => z1 => s1(s2 => z2 => s2(s3 => z3 => s3(s4 => z4 => z4))) // -^----^- // 选择器 ``` ## Maybe Maybe 单子非常常见，在大多数现代语言中以某种形式出现，有时名为 `Option`。它可以存储一个或零个元素，并支持检查是否存储了条目。例如，如果两个数的除法通常返回另一个数，你可以将其返回类型修改为 `Maybe`，使其包含除以零的特殊情况（此时函数不应返回任何东西）。这两种状态通常称为“Just”和“Nothing”，或“Some”和“None”： ``` // 返回 Maybe：Either "Nothing" 或 "Just()" function divide(a, b) { if (b === 0) return Nothing return Just(a / b) } ``` 我们可以用标签联合来编码此结构： ``` Nothing = nothing => just => nothing Just = v => nothing => just => just(v) // --^-- --^^^^-- // 值 选择器 isNothing = maybe => maybe(true)(_ => false) isJust = maybe => maybe(false)(_ => true) // ------^------ // 被忽略的值 getValue = just => just()(v => v) // 或更友好地： prettyMaybe = maybe => maybe("Nothing")(v => "Just " + v) console.log(prettyMaybe(Nothing)) // "Nothing" console.log(prettyMaybe(Just(42))) // "Just 42" ``` 我们现在就可以使用上述除法函数： ``` result = divide(42, 0) if (isNothing(result)) console.error("糟糕！") else console.log(getValue(result)) ``` 以这种方式使用单子时，你需要许多（可能嵌套的）if 语句。然而，这正是单子魔力通常展现的地方！正是这种丑陋、显式的状态跟踪（此处为“是否为空”）是单子试图消除的。如果 JavaScript 原生支持单子，连续操作的语法可能如下： ``` input = +prompt("请输入一个数字！") do { a <- divide(42, input) b <- divide(42, a) c <- divide(b, a) return(c) } // 结果是 Nothing 或 Just(c) ``` 在 `do` 内，操作被链接并存储到变量中。然而，尽管 `divide` 返回 Maybe 单子，各变量实际上是数字！数字会自动从 `Just` 中提取并放入下一个语句。如果任何除法返回 `Nothing`，整个链将中断并返回 `Nothing`。这种在 `divide` 等操作之间的行为由 `bind` 操作定义。最终的 `return`（此后称为 `unit`，以避免名称冲突）再次将值包装到单子中（此处通过 `Just`）[2](https://text.marvinborner.de/2024-11-18-00.html#fn2)。 具体来说，`bind` 函数做两件事：提取单子的值（如果存在），并将其应用于给定函数。在有类型语言中，该函数必须再次返回单子，以确保 `bind` 的最终结果始终是单子。 ``` unit = Just // maybe 是 Maybe 单子，f 是函数 bind = maybe => f => { if (isNothing(maybe)) return Nothing else return f(getValue(maybe)) } ``` 这还不够函数式！试着理解为什么以下定义是等价的： ``` bind = maybe => f => maybe(maybe)(f) ``` 先前的 `do {}` 块现在可以用多个 `bind` 翻译（这基本上也是具有此类语法的函数式编程语言脱糖后的形式）： ``` input = +prompt("请输入一个数字！") bind(divide(42, input))(a => bind(divide(42, a))(b => bind(divide(b, a))(c => unit(c)))) ``` ## Either Either 单子与 Maybe 单子非常相似。它不是存储“无值”或“一个值”，而是存储两个不同值（带有“Left”或“Right”标签）。例如，延续上面的例子，假设我们的 `divide` 函数在除以零的情况下实际上应返回错误消息，而非返回“无”： ``` // 返回 Either：Either "Left()" 或 "Right()" function divide(a, b) { if (b === 0) return Left("错误：除以零") return Right(a / b) } ``` 所需函数现在应相当明显： ``` Left = v => left => right => left(v) Right = v => left => right => right(v) // --^-- -^^^^^-- // 值 选择器 isLeft = either => either(_ => true)(_ => false) isRight = either => either(_ => false)(_ => true) // ^-----------^ // 被忽略的值 getLeft = left => left(v => v)() getRight = right => right()(v => v) // 或更友好地： prettyEither = either => either(v => "Left " + v)(v => "Right " + v) console.log(prettyEither(Left("错误"))) // "Left 错误" console.log(prettyEither(Right(42))) // "Right 42" ``` 以单子方式链接 Either 应仅传递标记为“Right”的值，而“Left”情况立即返回： ``` // 返回值应标记为 "Right" unit = Right // either 是 Either 单子，f 是函数 bind = either => f => { if (isLeft(either)) return either else return f(getRight(either)) } // 或简化为： bind = either => f => either(Left)(f) ``` 嵌套的 bind 现在按预期工作： ``` input = +prompt("请输入一个数字！") bind(divide(42, input))(a => bind(divide(42, a))(b => bind(divide(b, a))(c => unit(c)))) // input=42 => Right(42) // input=0 => Left("错误：除以零") ``` ## 语法 在继续讨论更复杂的单子之前，我想介绍一种更简洁的语法。你可能已注意到，反复编写 `bind` 会变得烦人且难以阅读。这就是为什么大多数支持单子的语言都有如上所示的 `do` 记法。受 [Magnus Tovslid 的工作](https://medium.com/@magnusjt/the-io-monad-in-javascript-how-does-it-compare-to其他技术-124ef8a35b63) 启发，我用 JavaScript 生成器实现了类似的东西： ``` DO = (unit, bind) => f => { const gen = f() const next = acc => { const {done, value} = gen.next(acc) return done ? unit(value) : bind(value)(next) } return next() } // Either 的特定 DO 实例： doEither = DO(unit, bind) ``` 这样，我们可以使用一种稍显怪异但更可读的 `do` 记法： ``` input = 42 result = doEither(function* () { a = yield divide(42, input) b = yield divide(42, a), c = yield divide(b, a), return c; }) console.log(prettyEither(result)) // "Right 42" ``` ## 状态 接下来是更复杂的单子！状态单子在不想使用可变状态但仍希望以优雅方式为函数附加状态时很有用。假设你有一个带种子的随机数生成器，想生成三个连续的随机数。使用可变状态，可以这样解决： ``` rng = max => seed => (1103515245 * seed + 12345) % max seed = 161 rand = () => (seed = rng(1000)(seed), seed) console.log([rand(), rand(), rand()]) // [790, 895, 620] ``` 相反，我们构建一个 `bind`，通过“自动修改”状态来连接 `rand` 调用。状态包含两个值：当前状态（当然），以及另一个可用于累加数据等操作的额外变量——否则，链接的操作只能传递（即使修改过的）状态。我们将这两个值存储在 Church 对中，它本质上是一个带有两个值的标签（选择器）。 ``` State = v => st => s => s(st)(v) // --^-- -^^-- -^----^- // 值 状态 选择器 ``` 在 `bind` 中，第一个参数的函数（例如像 `rand` 这样的状态转换器）应用于当前状态，产生一个新状态和一个值。该值和新状态随后传递给绑定链中的下一个函数（`bind` 的第二个参数）。 ``` /* * 伪代码： * bind = run => f => s0 => { * (s1, v) = run(s0) * return f(v)(s1) * } */ bind = run => f => s0 => run(s0)(s1 => v => f(v)(s1)) // --^^^^^^^^^^-- // 反柯里化 Church 对 unit = State // State 的特定 DO 实例： doState = DO(unit, bind) ``` 现在我们可以将上一个示例转换为使用单子状态： ``` // 用包含两个初始数字的 State 元组初始化 rand rand = seed => (g => State(g)(g))(rng(1000)(seed)) threeNumbers = bind(rand)(a => bind(rand)(b => bind(rand)(c => unit([a, b, c])))) // 或更简单地： threeNumbers = doState(function* () { const a = yield rand const b = yield rand const c = yield rand return [a, b, c] }) console.log(threeNumbers(161)(st => v => v)) // [790, 895, 620] // -^^^ ^^^^^^^^^^^^ // 种子 选择器 ``` 然而，状态单子不仅可用于生成随机数。例如，很容易推导出一种“写入者”单子，在处理其他数据的同时累积日志： ``` log = (a, str) => st => s => s(st + str)(a) deepthought = doState(function* () { const answer = yield log(42, "寻找答案... ") const correct = yield log(answer == 42, "验证答案... ") if (correct) yield log(null, "正确！") else yield log(null, "错误！") return answer }) console.log(deepthought("")(log => answer => ({answer, log}))) // { answer: 42, log: '寻找答案... 验证答案... 正确！' } ``` 你可以在 [GitHub](https://github.com/marvinborner/picomonad/) 上找到使用 `get`、`put`、`modify`、`ap` 和 `fmap` 的更多高级示例。 ## 输入输出 纯语言常使用单子处理输入输出，因为纯粹地跟踪输入和输出会导致极其混乱的代码。然而，典型实现的内部也被描述为“深奥而神奇”[3](https://text.marvinborner.de/2024-11-18-00.html#fn3)，因此我展示一个略微简化的版本。IO 单子在像 JavaScript 这样的语言中通常没有意义，因为 `prompt`、`alert` 或 `console.log` 等副作用可以从任何地方触发。然而，将所有非纯代码（`IO` 魔术）集中在一个地方，可以让我们通过微小的更改改变副作用的整个*本质*，例如支持多种类型的 IO。 假设我们的 IO 基于读写单个字符的能力。我们可以将该单子建模为状态单子的扩展： ``` doIO = doState // 这里还可以添加文件打开、读取、写入等 read = st => s => s(st)(st.read()) write = ch => st => s => s(st)(st.write(ch)) // ----^^--^^---- // 效果对象 ``` 这里的*状态*是一个可用 IO 效果的对象。在 bind 中传递的值是调用其中一个效果的结果。使用此状态有许多不同的解决方案。例如，我们可以纯粹地跟踪所有 IO 调用，然后在最后一次性惰性地评估它们。