Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场

Monad

作者头像
lambeta
发布于 2018-08-17 03:40:50
发布于 2018-08-17 03:40:50
1.5K00
代码可运行
举报
文章被收录于专栏:编舟记编舟记
运行总次数:0
代码可运行

Monad不就是个自函子范畴上的幺半群,这有什么难理解的(A monad is just a monoid in the category of endofunctors) —— Phillip Wadler

自函子(Endofunctor)

什么是函数(Function)? 函数表达的映射关系在类型上体现在特定类型(proper type)之间的映射。

什么是自函数(Endofunction)?

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
identity :: Number -> Number

自函数就是把类型映射到自身类型。函数identity是一个自函数的特例,它接收什么参数就返回什么参数,所以入参和返回值不仅类型一致,而且值也相同。

接下来,回答什么是自函子(Endofunctor)之前,我们先弄清什么是函子(Functor)?

函子有别于函数,函数描述的是特定类型(proper type)之间的映射,而函子描述的是范畴(category)之间的映射。

那什么是范畴(category)?

我们把范畴看做一组类型及其关系态射(morphism)的集合。包括特定类型及其态射,比如Int、String、Int -> String;高阶类型及其态射,比如List[Int]、List[String]、List[Int] -> List[String]

接下来看看函子是如何映射两个范畴的,见下图:

范畴

图中范畴C1和范畴C2之间有映射关系,C1中Int映射到C2中的List[Int],C1中String映射到C2中的List[String]。除此之外,C1中的关系态射Int -> String也映射到C2中的关系List[Int] -> List[String]态射上。

换句话说,如果一个范畴内部的所有元素可以映射为另一个范畴的元素,且元素间的关系也可以映射为另一个范畴元素间关系,则认为这两个范畴之间存在映射。所谓函子就是表示两个范畴的映射。

澄清了函子的含义,那么如何在程序中表达它?

在Haskell中,函子是在其上可以map over的东西。稍微有一点函数式编程经验,一定会想到数组(Array)或者列表(List),确实如此。不过,在我们的例子中,List并不是一个具体的类型,而是一个类型构造子。举个例子,构造List[Int],也就是把Int提升到List[Int],记作Int -> List[Int]。这表达了一个范畴的元素可以映射为另一个范畴的元素。

List具有map方法,不妨看看map的定义:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
f :: A -> B
map :: f -> List[A] -> List[B]

具体到我们的例子当中,就有:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
f :: Int -> String
map :: f -> List[Int] -> List[String]

展开来看:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
map :: Int -> String -> List[Int] -> List[String]

map的定义清晰地告诉我们:Int -> String这种关系可以映射为List[Int] -> List[String]这种关系。这就表达了元素间的关系也可以映射为另一个范畴元素间关系。

所以类型构造器List[T]就是一个函子。

理解了函子的概念,接着继续探究什么是自函子。我们已经知道自函数就是把类型映射到自身类型,那么自函子就是把范畴映射到自身范畴。

自函子是如何映射范畴的,见下图:

Identity自函子范畴

图中表示的是一个将范畴映射到自身的自函子,而且还是一个特殊的Identity自函子。为什么这么说?从函子的定义出发,我们考察这个自函子,始终有List[Int] -> List[Int]以及List[Int] -> List[String] -> List[Int] -> List[String]这两种映射。 我们表述成:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
类型List[Int]映射到自己
态射f :: List[Int] -> List[String]映射到自己

我们记作:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
F(List[Int]) = List[Int]
F(f) = f
其中,F是Functor.

除了Identity的自函子,还有其它的自函子,见下图:

自函子范畴

图中的省略号代表这些范畴可以无限地延伸下去。我们在这个大范畴所做的所有映射操作都是同一范畴内的映射,自然这样的范畴就是一个自函子的范畴。

我们记作:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
List[Int] -> List[List[Int]]
List[Int] -> List[String] -> List[List[Int]] -> List[List[String]]
...

所以List[Int]、List[List[Int]]、...、List[List[List[...]]]及其之间的态射是一个自函子的范畴。


幺半群

[幺半群][1]是一个带有二元运算 : M × M → M 的集合 M ,其符合下列公理: 结合律:对任何在 M 内的a、b、c, (ab)c = a(bc) 。 单位元:存在一在 M 内的元素e,使得任一于 M 内的 a 都会符合 ae = e*a = a 。

接着我们看看在自函子的范畴上,怎么结合幺半群的定义得出Monad的。

假设我们有个cube函数,它的功能就是计算每个数的3次方,函数签名如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
cube :: Number -> Number

现在我们想在其返回值上添加一些调试信息,所以返回一个元组(Tuple),第二个元素代表调试信息。函数签名如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
f :: Number -> (Number,String)

入参和出参不一致,这会产生什么影响?我们看看幺半群的定义中规定的结合律。对于函数而言,结合律就是将函数以各种结合方式嵌套起来调用。我们将常用的compose函数看作此处的二元运算。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
var compose = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};

compose(f, f)

从函数签名可以很容易看出,右边的f运算的结果是元组,而左侧的f却是接收一个Number类型的函数,它们是彼此不兼容的。

有什么好办法能消除这种不兼容性?结合前面所讲,cube是一个自函数Number -> Number,而元组(Number,String)在Hask范畴是一个自函子,理由如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
F Number = (Number,String) 
F Number -> Number = (Number,String) -> (Number,String)

假如输入和输出都是元组,结果会如何呢?

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
fn :: (Number,String) -> (Number,String)

compose(fn, fn)  

这样是可行的!在验证满足结合律之前,我们引入一个bind函数来辅助将f提升成fn.

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
f :: Number -> (Number,String) => fn :: (Number,String) -> (Number,String)
: 在Haskell中称为 liftM
var bind = function(f) {
  return function F(tuple) {
    var x  = tuple[0],
        s  = tuple[1],
        fx = f(x),
        y  = fx[0],
        t  = fx[1];

    return [y, s + t];
  };
};

我们来实现元组自函子范畴上的结合律:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
var cube = function(x) {
  return [x * x * x, 'cube was called.'];
};

var sine = function(x) {
  return [Math.sin(x), 'sine was called.'];
};

var f = compose(compose(bind(sine), bind(cube)), bind(cube));
f([3, ''])

var f1 = compose(bind(sine), compose(bind(cube), bind(cube)));
f1([3,''])
>>>
[0.956, 'cube was called.cube was called.sine was called.']
[0.956, 'cube was called.cube was called.sine was called.']

这里f和f1代表的调用顺序产生同样的结果,说明元组自函子范畴满足结合律。

那如何找到这样一个e,使得a*e=e*a=a,此处的*compose运算

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// unit :: Number -> (Number,String)
var unit = function(x) { return [x, ''] };

var f = compose(bind(sine), bind(cube));

compose(f, bind(unit)) = compose(bind(unit), f) = f

这里的bind(unit)就是e了。

到这里,思路逐步清晰了。在Haskell这类的强类型语言中,我们甚至可以组装自己的Tuple Monad。如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
type Tuple(Number,String)
flatmap :: Tuple -> Number -> Tuple -> Tuple
unit :: Number -> Tuple
map :: Tuple >>= unit
    :: Tuple -> Number -> Number -> Tuple

//compose
// flatmap 即 bind,中缀表达式一般是 >>=
Tuple >>= (Number -> Tuple) >>= (Number -> Tuple)

Monads for functional programming一书中介绍说monad是一个三元组(M, unit, *),对应此处就是(Tuple, unit, bind).

参考链接:

  1. Translation from Haskell to JavaScript of selected portions of the best introduction to monads I've ever read
  2. 我所理解的monad
  3. Monads for functional programming
  4. Functor, Applicative, Monad
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016.07.16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
什么是 Monad (Functional Programming)?函子到底是什么?ApplicativeMonad
函数式编程的精髓就在于,我们可以用好多好多小小函数,搭搭搭,组成一个个大函数,最终写出整个程序来。比如我们想写一个函数
一个会写诗的程序员
2018/12/12
4.7K0
一些范畴论上的概念
函子与函数不同,函数描述的是类型之间的映射,而函子描述的是 范畴(category) 之间的映射
Orlion
2024/09/02
2580
一些范畴论上的概念
✨从代码复用讲起,专栏阶段性作结,聊聊?
本文为稀土掘金技术社区首发签约文章,14天内禁止转载,14天后未获授权禁止转载,侵权必究!
掘金安东尼
2022/11/16
6820
✨从代码复用讲起,专栏阶段性作结,聊聊?
学习函数式编程 Monad
上一篇《轻松玩转函数式编程》中,我们讨论了常用的函数式编程案例,一些同学反馈没有讲到底层概念,想了解一下什么是 Monad?基于这个问题,我们来探究一下。
疯狂的技术宅
2020/11/30
8320
深入理解函数式编程(下)
函数式编程是一种历史悠久的编程范式。作为演算法,它的历史可以追溯到现代计算机诞生之前的λ演算,本文希望带大家快速了解函数式编程的历史、基础技术、重要特性和实践法则。
美团技术团队
2022/12/16
1.1K0
深入理解函数式编程(下)
编程语言:类型系统的本质
我一直对编写更好的代码有浓厚的兴趣。如果你能真正理解什么是抽象,什么是具象,就能理解为什么现代编程语言中,接口和函数类型为什么那么普遍存在了。在使用函数式语言进行编程后,就能够很清晰地理解为什么随着时间的推移,更主流的语言开始采用函数式语言中的一些被认为理所当然的特性。
一个会写诗的程序员
2022/09/01
2.9K0
编程语言:类型系统的本质
Monad_Haskell笔记10
从类型来看,Functor到Applicative再到Monad是从一般到特殊的递进过程(Monad是特殊的Applicative,Applicative是特殊的Functor)
ayqy贾杰
2019/06/12
9120
【单子】说白了不过就是【自函子范畴】上的一个【幺半群】而已?请说人话!!
起初本瓜看到【单子】说白了不过就是【自函子范畴】上的一个【幺半群】而已?这句话的时候,还以为自己在看量子力学的量子纠缠相关内容,单子、函子、粒子、玻色子、费米子、绝绝子。。。
掘金安东尼
2022/09/19
1.2K0
【单子】说白了不过就是【自函子范畴】上的一个【幺半群】而已?请说人话!!
15 分钟了解 Monad
看到函数式编程相关的资料的时候, 总是看到 Monad 这个词, 一直想了解一下, 然而查资料对 Monad 的定义往往是上来一大堆数学概念:
爬虫技术学习
2023/02/10
4100
15 分钟了解 Monad
用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:
"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda calculus)。λ演算可以接受函数当作输入(参数)和输出(返回值)。
一个会写诗的程序员
2018/08/17
1.3K0
用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:
《Kotin 极简教程》第8章 函数式编程(FP)(1)第8章 函数式编程(FP)《Kotlin极简教程》正式上架:
"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda calculus)。λ演算可以接受函数当作输入(参数)和输出(返回值)。
一个会写诗的程序员
2018/08/17
1.6K0
Js-函数式编程 前言什么是函数式编程为什么Js支持FP纯函数柯里化组合 compose范畴学functorMonadApplicative FunctorFunctor\Monad\Applic
JavaScript是一门多范式语言,即可使用OOP(面向对象),也可以使用FP(函数式),由于笔者最近在学习React相关的技术栈,想进一步深入了解其思想,所以学习了一些FP相关的知识点,本文纯属个人的读书笔记,如果有错误,望轻喷且提点。
菜的黑人牙膏
2019/04/09
1.9K0
Js-函数式编程
		前言什么是函数式编程为什么Js支持FP纯函数柯里化组合 compose范畴学functorMonadApplicative FunctorFunctor\Monad\Applic
Java示例演示Functor 和monad
This article was initially an appendix in our Reactive Programming with RxJavabook. However introduction to monads, albeit very much related to reactive programming, didn't suit very well. So I decided to take it out and publish separately as a blog post.
Dylan Liu
2019/07/01
7030
函子定律
前段时间学了下 Haskell,看完了《Haskell 趣学指南》,刷了一些题,《Real World Haskell》正在看。因为早先看过《SICP》,有点 FP 的基础,平常写 Swift 也喜欢用些 FP 的技巧,所以暂时没有什么特别颠覆性的感觉。最大的感受是,以前对 Functor、Applicative 和 Monad 的理解太片面了。
Sheepy
2018/09/10
1K0
Monad 定律
monad 是支持>>=操作的 applicative 函子,>>=读作绑定,它的类型是:
Sheepy
2018/09/10
5460
函数式编程入门教程
你可能听说过函数式编程(Functional programming),甚至已经使用了一段时间。 但是,你能说清楚,它到底是什么吗? 网上搜索一下,你会轻松找到好多答案。 与面向对象编程(Object
ruanyf
2018/04/13
1.6K0
函数式编程入门教程
读书笔记: 范畴论
一个范畴是一个带标签的有向图,其节点为对象(object),带有标签的有向边为箭头(arrow or morphism)。
绿巨人
2018/12/17
1.5K0
函数式编程入门教程
你可能听说过函数式编程(Functional programming),甚至已经使用了一段时间。
疯狂的技术宅
2019/03/28
1.4K0
函数式编程入门教程
Category Theory: 01 One Structured Family of Structures
\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。
绿巨人
2018/12/17
6930
来看看几种 Monad来看看几种 Monad
https://learnyoua.haskell.sg/content/zh-cn/ch12/a-fistful-of-monads.html
一个会写诗的程序员
2018/12/12
1.2K0
相关推荐
什么是 Monad (Functional Programming)?函子到底是什么?ApplicativeMonad
更多 >
LV.0
这个人很懒,什么都没有留下~
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验