在《Real World Hashell》一书里，有一段通过foldr表示foldl的代码

1
2
3
4

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

刚看到这的时候，感觉特别难懂，尤其是之前没有函数式编程的经历，对柯里化了解不深的情况下，更加一头雾水

如果是顺序读这本书的话，我们应该已经知道了foldr的签名

1
2

Prelude> :type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

困惑

这里最让人感到奇怪的有两点

1. foldr的签名是接受三个参数，如下

   1. 一个函数，这个函数接受两个参数，类型a和类型b，返回一个类型b的值
   2. 一个类型b的初始值
   3. 一个可折叠类型a，这里我们简单当作一个列表

   但是，实际上我们传递了四个参数

2. 上面说了，foldr的第一个参数是个函数，接受两个参数，但传递过去的step函数，有三个参数

上述两点，也可以总结成一点：参数个数不匹配。

Currying

要理解这个问题，我们需要一些其他知识，也就是“部分函数应用和柯里化”(Currying)

这部分内容在原书后续有讲到

这两部分是相辅相成的，理解了部分函数应用和柯里化，会更容易弄明白foldr表示foldl；而弄清楚foldr表示foldl，则会对部分函数应用和柯里化有更深刻的理解

在说部分函数应用和柯里化之前，我们先看看一般命令式语言中的现象

比如有如下Java代码，两数相加

1
2
3

private int add(int a, int b) {
    return a + b;
}

这个函数需要两个参数a和b，然后返回两数之和

我们可以通过add(1, 2)的方式调用这个函数，但是，add(1)则是不合法的，因为没有此种方法签名

与Java不同的是，在Haskell中，这是允许的

1
2
3
4
5

Prelude> add a b = a + b
Prelude> :type add
add :: Num a => a -> a -> a
Prelude> :type add 1
add 1 :: Num a => a -> a

在Haskell中，本质上，所有的函数都只接受一个参数

上面的add函数，看上去接受两个类型为a的参数，返回一个类型为a的值，实际上是先接受一个类型为a的参数，返回一个函数，这个函数再接受一个类型为a的参数，返回类型为a的值

就像我们有一个机床，可以将一堆铁疙瘩制作成各种机器，然后我们可以用制造出的机器，将原料加工成成品

现在我们要做衣服，做衣服需要布料，需要使用缝纫机，我们还没缝纫机，不过我们有机床，有铁疙瘩，可以造一个出来，在Haskell里可以表示为

1
2
3
4
5

type Iron = String
type Cloth = String
type Clothes = String

machineTool :: Iron -> Cloth -> Clothes

如果用类似Java语言解释这个签名的话，就是machineTool这个函数需要两个参数，铁和布，将这两个参数同时放进去，会出来一个衣服

在Haskell里，并不需要同时传两个参数，我们可以只传一个

1

sewMachine = machineTool "a piece of iron"

这是合法的，表示给机床一块铁，做出了一台缝纫机，缝纫机是个函数，可以继续接受参数，它现在接受一个Cloth类型的参数，返回Clothes类型的结果

1
2

*Main> :type sewMachine 
sewMachine :: Cloth -> Clothes

这个缝纫机可以接受一匹布，产生一件衣服 sewMachine "a piece of cloth"

解析

回到最初的右折叠表示左折叠问题

1
2

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

再看一下foldr的签名

1
2

Prelude> :type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

foldr第一个参数是函数，其返回值类型为b，和foldr第二个参数，也就是foldr的初始值类型一样，也是b

在foldr step id xs z这里，第二个参数，也就是初始值，是id

1
2

Prelude> :type id
id :: a -> a

我们看到id是一个函数，接受一个类型为a的参数，返回的类型同样也是a（实际上id是identity的缩写，本身的意思，id作用是返回参数本身）

既然初始值类型是函数，那foldr的第一个参数，返回的也是一个函数

我们看到step的定义，它可以接受三个参数，但是在foldr的应用过程中，只会应用两个（列表的从右往左下一个值和初始值或者上一次函数的计算结果），结合函数的部分应用和柯里化，我们知道step函数在应用两个参数后，返回的是另一个函数，这个函数接受一个参数（step函数参数的第三个）

也就是foldr的第一个参数，类型为(a -> b -> b)，在实际执行过程中，a类型是列表内容的类型，第二个参数b类型，第一次是初始值，也就是id，实际类型是一个函数，同时，结果仍然是b，是一个函数，作为下一次计算(a -> b -> b)的第二参数

由于foldr的最终返回结果是一个函数，所以可以应用一个参数，这个参数在foldr step id xs z这里，也就是z，或者说可以把foldr step id xs z看作是(foldr step id xs) z，foldr全部折叠完，其最后结果是一个函数，然后用z作为函数的参数对这个最终函数进行调用

展开

参数个数的问题弄清楚后，我们可以把表达式进行展开，将实际参数带入到表达式的变量中

假设我们现在使用myFoldl对一个列表求和，列表是[1,2]，求和的初始值是0

按照左折叠的规则，我们预期执行顺序应该是((0 + 1) + 2)，从初始值和列表第一个元素开始相加，其和与列表的第二个元素继续相加，如此从左到右一次计算整个列表，并返回最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

-- 我们的调用为
myFoldl (+) 0 [1,2]
-- 参数带入变量
-- f == (+)
-- z == 0
-- xs == [1,2]

-- 也就是
foldr step id [1,2] 0

==> foldr (\x g a -> g (f a x)) id [1,2] 0
-- 参数再带入到变量，列表从右向左
-- x == 2
-- g == id
-- f == (+)

==> foldr (\x g a -> g (f a x)) (\a -> id ((+) a 2)) [1] 0
-- x == 1
-- g == (\a = id ((+) a 2))
-- f == (+)

==> foldr (\x g a -> g (f a x)) (\a -> (\a -> id ((+) a 2)) ((+) a 1)) [] 0

==>     (\a -> (\a -> id ((+) a 2)) ((+) a 1)) 0
--               ↑                  |........|
--               ↑                      ↓
--               a == ((+) a 1)   <----/

==>     (\a -> (id ((+) ((+) a 1) 2))) 0
--              ↑
--              id返回参数本身

==>     (\a -> ((+) ((+) a 1) 2)) 0
--        ↑
--        a == 0

==>     ((+) ((+) 0 1) 2)
-- 改成中缀

==>     ((+) 0 1) + 2
==>     (0 + 1) + 2

经过上述将实际参数带入到变量，推导后，myFoldl的行为确实与预期一样，我们就这样通过foldr表示了foldl

简介

三向切分快排是针对特殊场景的一种优化，比较适合数组中重复元素比较多的时候。

与标准快速排序分为小于等于基准和大于基准两个部分不同，三向切分分为三个部分，也就是小于基准、等于基准和大于基准，也就是把标准快排的等于部分单独拆分出来，这样这部分相同的数据就不用再次比较了，所以，当重复元素比较多时，将会有比较大的性能提升。

实现

先放代码，后面解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public void threeWayPartition(int[] nums) {
    threeWayPartition(nums, 0, nums.length - 1);
}

private void threeWayPartition(int[] nums, int start, int end) {
    if (start >= end) {
        return;
    }
    int lt = start;
    int eq = start;
    int gt = end;
    int base = nums[eq];
    while (eq <= gt) {
        if (nums[eq] > base) {
            swap(nums, eq, gt);
            gt--;
        } else if (nums[eq] < base) {
            swap(nums, lt, eq);
            lt++;
            eq++;
        } else {
            eq++;
        }
    }
    threeWayPartition(nums, start, lt - 1);
    threeWayPartition(nums, gt + 1, end);
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

代码的核心是while循环，主要涉及三个索引变量lt、eq、gt

三个变量可以将数据分为四个部分，除了结果的小于、等于、大于外，还有过程中的未比较部分

也就是

• [start-lt) 代表小于基准的数据
• [lt-eq) 代表等于基准的数据
• [eq-gt] 代表未比较的数据
• (gt-end] 代表大于基准的数据

其中，小于和等于在前半部分，大于在后半部分，为比较在中间，随着比较的进行，小于等于的向后扩展，大于的向前扩展，慢慢吃掉未比较的区域

初始时，所有的数据[start-end]都是未比较的，小于、等于、大于基数的数据都没有，所以lt、eq初始化为0，gt初始化为end

我们先将基准定义为开始第一个元素

我们遍历未比较的数据，也就是[eq-gt]

从第一个元素nums[eq]开始

由于基数就是第一个，自己和自己肯定相等，所以执行else逻辑，也就是和基数相等，相等时，等于基准的数据多了一个，eq索引后移

接下来第二个数与基准元素比较，如果这个数比基准元素大，我们是要把它放到数组的第三部分的，也就是(gt-end]区域，区域不包含qt，也意味着gt代表下一个大于基准的数将要被放入的位置，此时nums[eq]比基准大，所以两数交换位置，交换完成后，大于基准的数多了一个，所以gt前移，而eq位置的数据是从原来的qt来的，还是未比较的，所以eq的位置不动，还需要继续比较

如果num[eq]比基准元素小，我们要把它放入[start-lt)区域，同样，区域不包含lt，lt是下一个比基准小的数的位置，所以交换eq和lt位置的数据，将小于基准的数，也就是num[eq]放到lt那里，此时小于基数的数多了一个，lt前移；由于原始lt放的是等于基准的数据（[lt-eq)），现在到eq这个位置来了，已经不需要再次比较了，相当于把“等于基准的数据”这个集合的第一个数挪到了最后的位置，数量不变，虽然数量不变，但是由于这个集合的位置是在小于基准那个集合的后面，小于基准的集合多了一个，所以eq也要同步后移

继续以相同的逻辑遍历

直到没有未比较的数据，也就是[eq-gt]这个集合为空，所以退出条件是gt > eq

经过一轮遍历后，数组被分为三个部分

也就是

• [start-lt) 代表小于基准的数据
• [lt-eq) 代表等于基准的数据
• (gt-end] 代表大于基准的数据

[eq-gt]已经没有了

等于基准的数据已经不需要再排序了，小于和大于的都只是比基准大或小，内部并不一定有序，所以继续对两个区域用相同的逻辑进行排序

标准快排，只是基准那一个数不需要下次的排序，而不是等于基准的一批数，如果等于基准的数很多，就会造成浪费，而三向切分就是针对这种情况的一个优化。

上篇文章说到了拖延这个话题。

就拿这个博客举例，从十一月中旬搭建完成，本来就是要写东西的，结果后面一直到十二月底才开始写第一个字。

而这篇文章，看时间从19年12月31号开始写，写了一部分后暂停，后面过了个春节，才又开始继续写后面的部分，实在是太拖延了。

前一篇文章提到拖延的时候简单的列举了几条原因，现在来写一写更深层、更系统的原因，以及怎么才能告别拖延症。

拖延症的分类

当我们和其他人讨论一个东西的时候，我们首先需要确保说的是同一个东西，才能继续交流下去。否则就像是聊天不在同一个频道似的，你说你的他说他的，两人还都觉得对方怎么都说不通。

在拖延症这里，可以分为作为心理问题的拖延症和作为社会现象的拖延症。

作为心理问题的拖延症是严肃的，经常伴随着严重的心理问题，需要专业的心理医生或精神科大夫才能对此评判。

而作为社会现象的拖延症就比较轻松，更多的是一种调侃或自嘲。

这里说的只是后者。

下面再聊聊拖延症的诱因和如果克服拖延症，当然，只是理论，起码到目前为止，我还是有着比较严重的拖延症:)

拖延症的诱因

为什么我会拖延？

就是明明有事情做，非要拖着拖着，一直拖到不能再拖的时候，所以有人调侃deadline是第一生产力。

下面这些，也许是常见的造成拖延的原因

诱惑

现在社会诱惑太多、诱惑太近、诱惑太诱人，比如现在，我在电脑上敲这些字，连着网，非常容易的就可以刷刷新闻、刷刷知乎，可以有很多选择。而且我也想这么做。

除开电脑，还有手机，现在基本手机不离身，而手机上有各种推送，像朋友圈这些能刷的东西更多，还有游戏，游戏厂商有着几十几百号运营、策划，这些精英们设计的关卡，可以及时的给人们提供积极的、不确定的反馈，完全贴合人们的生理、心理需要。

这些都是诱惑，很多很近很诱人。

而你知道自己应该干的事情，比如写文章、写文档，往往过程单调，反馈不及时，需要长时间才能看到效果。

有心理学家把大脑分为热系统和冷系统，前者控制着人的本能的反应，自动触发、快速反应，后者控制着理智的部分，需要推理计算，消耗意志力。前者让人及时行乐，后者让人从更长远的眼光看待事情，而不是只看眼前。

刷新闻、刷知乎、刷朋友圈、刷剧打游戏这些是激活的热系统部分，你本能的就喜欢，而你知道自己应该做的事情，是冷系统在管的，你知道这些东西在长远的看来对你是有益的，但是需要意志力的介入才能行动。

压力

前面说到了热系统和冷系统，举得例子都是诱惑，是有吸引力的，刷新闻打游戏这些吸引着我们去做。而还有些东西是有排斥力的，比如说压力。

当一件事情很中性，比如发呆，可能平时我们不想做这件事情，但是如果还有一件有压力的事情让你选的话，没压力的就是有吸引力了。

就像是“趋利避害”，“两害取其轻”这样，当然这里的“害”都是从热系统的角度也就是当前来看。

完美主义

这一点我也很有体会，比如就本博客来说，之前一直拖着，就有个原因是觉得自己写的不好，想等自己写作练好了再发布出来，结果最终就是拖啊拖，越不写越写不好，越写不好越想拖到写好再写。

还有就是开源，本来自己遇到个事情，太麻烦，写个小程序给自已用，自己用完后想，哈哈我是个天才，有了这个东西方便多了，开源吧，看能不能有几个star！但是又想，这里有个坑，我自己用的时候知道有坑，不会让自己掉进去，但是别人不知道啊，等我先填完在开；啊啊啊，又发现了个问题，现在在我这里是这样，到别人那可能会那样，所以我得要灵活一下可配置才行，等我加个feature在发；等等等等，一直想着要写完美了在开源，结果是有事一耽搁，我自己的事情也解决了，这件事就忘了，开源的事也拖在那里了。

控制和反抗

这点主要出现在父母或上司有关的事情中。

比如你正想去写作业，然后，你的父母突然对你说，xxx，赶紧去写作业。这个时候往往你会比较抗拒，因为你本来就是想去的，结果父母叨叨，这个时候去就成了听父母的命令去而不是安自己意愿来。哪怕这个意愿就和父母的要求是一致的。为了反抗或者避免这样的误会（这个误会可能只有自己一个人知道），你可能会再拖一会，用来表达，这是我自己要去写作业的，而不是听你们的话才去的。

还有当你的上司指派给你一个任务时，如果你觉得这个任务很蠢，但又不能不做时，往往会拖一段时间，最好能到deadline，而不是及时完成。用这种方式来表达不满。

小结

有了诱因，就可以针对性的解决了，各个击破。
至于如何击破，留到下次再说吧，这篇已经拖了太久了，再不发出去又要废了。

从博客跑起来到现在也有一个多月了。

本来弄这个博客的目的就是写点什么，但由于拖延癌晚期，一直拖一直拖。

现在回头想想，当时建这个博客的目的是什么，或者说写博客有什么好处呢

1. 练习一下写作
2. 可以整理自己的思路
3. 通过输出倒逼输入
4. 能养成个习惯，而且应该算是好习惯
5. 写出来，能验证自己是真懂了还是自以为懂了（脑子：我懂了。手：你懂个屁）

再想想为什么会一直拖着呢，也许有下面几个原因吧

1. 不知道写什么
2. 害怕自己写的不好，拿不出门
3. 还要开电脑（嗯，不想写，什么都可以是理由）

为什么现在又开始写了呢

1. 又想到了这件事情，想着总不能半途而废吧
2. 改变了不知道写什么的想法，不知道写什么就随便写咯，比如说现在，哪怕是流水账也比没有好
3. 怕写不好所以不写，而不写就会写不好。这是一个死循环。要跳出这个死循环首先得不要怕，先写再说，写的多了自然也就写好了

先这样吧，虽然写的可能确实不好，但是比我写第一个字以前估计的要好多了，起码从字数上来说是这样，之前还想着能不能写50字或100字，现在看看都快500字了，是一个好的开始。嗯，我就是需要给自己一个鼓励。

关于上面拖延的原因，可以深挖一下的，印象里看过关于这个的文章，但是现在已经记不起来具体内容了，如果当时看了，再自己写点什么，也许就不会忘了吧。这也就是上面提到的写点东西的好处吧。

嗯，这个话题就留给下一篇吧。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment