FP异闻录0x01:我被Monad折磨的日常

本文是一篇极其不正经且naive,too young too simple的文章

Monad说白了不过就是自函子范畴上的一个幺半群而已(这不是我说的)

要讲明白什么是Monad,我们不妨从一个广为人知的Monad说起

一个例子: Promise

要讲Promise就不得不说起一个老生常谈的问题:回调地狱。来看下面一段js代码

1
//假定有这么一个函数readFile, 它的功能是异步的读取文件的内容并把结果或者错误传给callback函数
2
const readFile = (path, callback) => { ... }
3
4
//我要读取一个文件
5
readFile('filename', (data, error) => {
6
    if(error == null) {
7
        ...
8
    } else {
9
        ...
10
    }
11
})

上边的代码很好理解,到目前为止也没有什么问题

那么如果我们有这样一个需求,读取文件a与b并把两个文件的内容合并在一起输出,看代码

1
readFile('a' (data1, error1) => {
2
    if(error1 == null) {
3
        readFile('b', (data2, error2) => {
4
            if(error2 == null) {
5
                console.log(data1 + data2)
6
            } else {
7
                ...
8
            }
9
        })
10
    } else {
11
        ...
12
    }
13
})

可以看到这里的代码一层一层,堆得像山一样(屎山

有没有觉得有点麻烦了呢,在想想假如要读取十个文件并把他们的结果合并呢?是不是觉得有一股坏味道?回调函数一层套一层,这就是所谓的回调地狱

在有了Promise后我们就能这样写了

1
const readFileP = (fileName, acc) => new Promise((resolve, reject) => {
2
    readFile(fileName, (data, error) => {
3
        if(error == null) {
4
            resolve(data + acc)
5
        } else {
6
            reject(error)
7
        }
8
    })
9
})
10
11
const readFileA = () => readFileP('a', '')
12
const readFileB = x => readFileP('b', x)
13
const readFileC = ...
14
const readFileD = ...
15
16
readFileA().then(readFileB).then(readFileC).then(readFileD).then(x => console.log(x))

可以看到代码确实变得简洁了许多,就好像把原有的回调层级拍平(flatten)了一样

Promise到底有什么神奇的地方可以带领我们避开回调地狱呢?先买个关子

再看看下边这个例子

再来一个例子:Option

(scala警告⚠️)

写过scala的童鞋都知道,在scala中,对于可能失败(或者说可能出现结果为空的问题)的计算我们都会选择使用Option,其实Option也是一种Monad,现在不妨就来看看

1
//这个函数的作用是在一个列表中找到指定的数value第一次出现的位置并返回,如果未出现则返回None
2
def findInList(list: List[Int], value: Int): Option[Int] = ???

如果我们要执行这样一种操作,在指定的数组中找到一个元素a第一次出现的位置,然后把它和另一个元素b第一次出现的位置相乘再加一(得有多无聊才会搞这种事情)一般的写法是这样

1
val x = findInList(list, a)
2
val y = findInList(list, b)
3
4
val res = x match {
5
    case Some(v1) => y match {
6
        case Some(v2) => Some(v1 * v2 + 1)
7
        case _ => None
8
    }
9
    case _ => None
10
}

是不是觉得有点麻烦

这里要说明一下为啥这个findInList要返回Option类型而不是在失败的时候传个-1之类的东西
因为对于很多问题搞个魔法值作为失败的情况虽然很爽,但这并不是typesafe的,或者说你拿来作为失败情况的魔法
值是存在安全隐患的,比如对于此处如果找不到就返回-1,你可能会忘记处理失败的情况而使用了错误的结果得出了
错误的结论

换一种写法呢?

1
val x = findInList(list, a)
2
val y = findInList(list, b)
3
4
val res = x.flatMap(m => y.flatMap(n => Some(m * n))).flatMap(t => Some(t + 1))

是不是又把本来的多层级代码拍平(flatten)了

重头戏,到底什么是Monad

看了上边两个例子,你是不是发现了些什么?Option和Promise都是把原本产生问题的部分拿某种结构包裹了起来,然后使用一个函数(flatMap,then)来处理

没错,不准确的说,只要一种结构M满足其内部保存一个值,且这个结构支持flatMap操作(在haskell中叫bind写作>>=),就可以说M是一个Monad

可是上边说了这么多,还是么说清楚monad是什么flatMap是什么

未完待续

Luogu-P3119

题面

很有意思的一道题

约翰有n块草场,编号1到n,这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家,她想到达尽可能多的草场>去品尝牧草。

贝西总是从1号草场出发,最后回到1号草场。她想经过尽可能多的草场,贝西在通一个草场只吃一次草,所以一个草场>可以经过多次。因为草场是单行道连接,这给贝西的品鉴工作带来了很大的不便,贝西想偷偷逆向行走一次,但最多只∂能有一次逆行。问,贝西最多能吃到多少个草场的牧草。

Read More

Luogu-P4832

题面

题目大意是珈百璃不想写作业就把作业交给了你,给你一些形如s+c的式子,其中s代表 $sin\frac{\pi}{7}$ ,c代表 $cos\frac{\pi}{7}$ ,然后你可以从中间选一些式子,要求最后选出的式子之和为整数最大

Read More

Luogu-P1941

题面

题目大意是要玩一个类似Flappy Bird的游戏,输入会给出地图以及每个x坐标对应的数据。小鸟每秒前进一格,可以在1s内连续点很多下让小鸟上升,也可以不点让他下降,对于每个不同的横坐标x上升和下降的值都不同,问你最少点多少下能让小鸟到达终点,如果到不了终点那么最远可以走多远。(具体题目看题面吧)

Read More

Luogu-P5322

题面

题目大意

小C正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡,每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵,可以向第$i$座城堡派遣 $a_i$ 名士兵去争夺这个城堡,使得总士兵数不超过 $m$。
如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得 $i$ 分。

现在小C即将和其他 $s$ 名玩家两两对战,这 $s$ 场对决的派遣士兵方案必须相同。小C通过某些途径得知了其他 $s$ 名玩家即将使用的策略,他想知道他应该使用什么策略来最大化自己的总分。
其中

且有

你需要输出小C总分的最大值

Read More

Luogu-P2979

题面

题意大概为给你一些种类的奶酪,每种奶酪都有自己的价值与高度,要求你用这些奶酪搭建一座奶酪塔,塔高不超过T且要求塔的总价值最大。定义高度超过K的奶酪为大奶酪,大奶酪会将其下边的奶酪高度压缩为原有的4/5(被压缩过则不再压缩)。

Read More

随笔-0X01

我曾在满天烟花中逃离

  昨天去影院看了传的很火的《烟花》。之前听说《烟花》评分并不太高,我看了以后觉得《烟花》在很多方面确实是不如君名,然而这并不是说《烟花》就一无是处,虽然画面稍稍有些欠佳,后半段的3D特效略迷,剧情跳转太突然以外,整体效果还是不错,让人留有几分回味。

Read More

随笔#0X00

你的名字从一开始就深埋我心 ———观《君名》有感

为了爱你,我将和时间对抗,它从你身上夺走的,我会重新嫁接。

  梦这种东西,醒了以后很快就会忘记的。那么,不是梦的话又将如何?
  很多人都自以为自己在反抗命运,可他们不知道的是,他们只是在命运的倾轧之下挣扎。

Read More