下面的图都可以点击查看大图

标准

标准地址

1. EventLoop
2. SecAgents

笔记

1. EventLoop是HTML规范，SecAgent、Execute Context、Promise这些是ECMA规范。
2. EventLoop、任务队列、宏任务、微任务等概念，不是简单的一对一关系。一个执行上下文有一个EventLoop，而一个EventLoop可以生成多个任务(Task或MacroTask)队列。宏任务通常指的是任务队列里的任务，而微任务是一个独立的任务列表，可以理解为一个优先任务集合。
3. 大致上以Task -> MicroTask -> render的方式运行每次循环，但render不是必须的。

一些细节：

1. 标准在不同的执行环境上，实现可能不同。比如Promise标准里面没有规定必须是MicroTask，因此有的浏览器版本里面Promise的then方法还是一个MacroTask，不过现在的浏览器都统一了then为一个MicroTask；另外就是node环境和window环境的实现也是不一样的，这是由不同环境的需求决定的。
2. 每个EventLoop都有一个正在运行的Task，Task也可以是null，null后可以开始新的事件循环
3. 每个EventLoop都有一个MicroTask队列，由自定的算法生成MicroTask，每一个TaskQueue（宏任务队列）执行完毕后，就去查看是否有MicroTask等待执行，有的话就执行所有的MicroTask。

处理流程

事件循环的流程、步骤

1. TaskQueue成为一个任务队列，一个任务队列必须包含一个可运行的任务，如果没有，则跳到微任务流程(7)
2. 取任务队列中最老的一个任务(OldestTask)作为第一个可运行的任务，然后从TaskQueue中删除它
3. 设置EventLoop的当前执行任务为这个OldestTask
4. 设置TaskStartTime为当前高分辨时间(current high resolution time)
5. 执行OldestTask
6. 设置EventLoop的当前执行任务为null
7. MicroTask。触发微任务检查，从MicroTaskQueue中查询是否存在微任务，存在则依次取出执行
8. 设置hasARenderingOpportunity = false
9. 设置当前时间为当前高分辨时间(current high resolution time)
10. 计算这个OldestTask执行时间。计算方式：
    10.1 设置top-level browsing contexts为一个空集合
    10.2 设置这个任务相关的执行上下文设置
    10.3 用TaskStartTime、now等参数来计算执行时间
11. 执行渲染(render)。如果是window环境，执行下面的步骤
    11.1 设置docs为该事件循环关联的Document
    11.2 浏览器硬件约束、刷新率等限制了RenderingOpportunity，没有渲染机会的更新，docs会被删掉。关联知识点：渲染阻塞、动画渲染原理、合并渲染等概念
    11.3 如果docs不为空，设置hasARenderingOpportunity = true
    11.4 一些不必要的渲染，会被删掉。（用户代理-UserAgent，认为更新不会有明显效果并且动画帧回调为空）
    11.5 删除一些其他原因被用户代理认为最好删掉的更新。比如：需要合并的帧
    11.6 对每个Document依次运行全局的任务，flush autofocus candidates、resize steps、scroll steps、evaluate media queries and report changes、update animations and send events、fullscreen steps
    11.7 检查canvas相关的方法，并更新
    11.8 运行动画回调(animations frame callbacks)
    11.9 运行update intersection observations stops
    11.10 运行mark paint timing
    11.11 执行渲染，刷新当前状态到画面中
12. 如果满足window环境、当前活跃的Document关联的EventLoop的任务队列没有任务、微任务列表为空、hasARenderingOpportunity = false，则对当前用户代理下的任意Window对象，都执行一个idle period algorithm表示浏览器渲染器空闲
13. 如果是worker线程的EventLoop，那么执行worker相关的流程

微任务检查和执行流程

1. EventLoop如果performing a microtask checkpoint = true，返回
2. 设置performing a microtask checkpoint = true。一个微任务可能生成更多的微任务，因此有一个变量来避免重新进入同一个微任务的执行。
3. MicroTaskQueue不为空：
   3.1 让oldestMicrotask从MicroTaskQueue中出队
   3.2 设置EventLoop的当前执行任务为oldestMicrotask
   3.3 执行oldestMicrotask
4. 对当前EventLoop的每一个环境变量，通知那些reject的任务
5. 清除IndexedDB事物
6. 执行ClearKeptObjects()。和WeakRef.prototype.deref()有关，可以让这个方法返回值被垃圾回收。
7. 设置performing a microtask checkpoint = false

其他要点

浏览器上下文browsing context

浏览器上下文一个执行上下文，如一个页签、一个iframe，和worker的上下文有区别，实现上就是相互独立的。然后event loop是在一个执行上下文下的，同源的浏览器上下文可以共用event loop，这样互相之间就可以通信。

执行栈

JavaScript是单线程的，在函数执行的时候，运行时会有一个Execute context(ECMA标准，执行上下文)，执行上下文存储了函数的参数、局部变量等信息，执行上下文位于栈顶，执行时有新的函数调用，会压栈，函数调用完毕，会弹栈。

疑问

1. 执行dom.style.width = "100px"是同步更新还是异步更新？
   -> 宏任务执行时提交给Render过程，由浏览器渲染线程决定是本次渲染还是合并到下次渲染。是同步过程，但是如果是下一个周期再渲染，看起来就像是异步的。

2. 异步的含义？比如setTimeout
   -> 定时器相当于一个工人，在特定时间会把回调任务加入到任务队列中去，至于任务何时被调用，是不关心的，是由事件循环调度的。

3. 宏任务和微任务的区别？
   -> 大部分操作都会生成新的宏任务：UI事件、键盘事件、原生回调相关的操作、ajax相关操作，宏任务队列可以有多个，而整个线程内的微任务队列只有一个，每个宏任务队列调度完毕都会访问和检查微任务队列。合理运用微任务可以优化我们的代码执行(减少因单线程造成的阻塞)。

4. UI渲染为什么会阻塞JS执行？
   -> 当前执行任务(可以是宏任务，也可以是微任务)结束后会提交给渲染器，渲染器可以合并多次提交来优化渲染流程，但整体来 说虽然渲染器和JS线程是独立线程，但是渲染任务也是属于一次任务的过程，渲染没有完成，下一次宏任务调度就等待。从使用的角度来说，UI渲染和JS完全异步的话，可能会造成我JS取的元素和实际元素有偏差，因此都是按照同步的方式实现的。浏览器通过合并UI计算来减少渲染次数。

5. 动画的第一帧/过渡效果在有些时候没有出现？
   -> 有可能就是因为UI渲染合并了。可以通过设置初始值、增加一个任务(宏任务、微任务)触发回流来让动画不丢帧。

后记

其实搞懂了它的标准，就知道90%的问题答案了。很明显标准里面描述的都是同步执行的过程，是一步步地执行任务、渲染，只是说渲染这个过程，和硬件也有关系，做了一些合并运算的优化而已。另外就是你不管它是宏任务还是微任务，它都是当前执行任务，它产生的不同类型的新任务，会添加到对应的任务队列中去。

什么是λ演算？

箭头函数

ECMAScript 2015规范引入了箭头函数，它没有this，没有arguments。只能作为一个表达式(expression)而不能作为一个声明式(statement)，表达式产生一个箭头函数引用，这个引用仍然有name和length属性，分别表示箭头函数的名字、形参(arguments)长度。

// const语句把表达式x=>x的值输出到标识符id
const id = x => x;
console.log(id.name, id.length) // id 1
const x = id;
console.log(x.name, x.length) // id 1 表明name和length是原始引用携带，不因标识符改变而改变

做一些简单的运算

// 加法
const add_1 = (x, y) => x + y;
const add_2 = x => x + y; // y来自外部(闭包引用外部参数)
const add_3 = x => y => x + y; // 可以用闭包串联参数(即柯里化)
const add_4 = b => a => a + b; // 参数命名和算式结果无关

这是直接针对数字（基本数据类型）的情况，如果是针对函数（引用数据），事情就变得有趣起来了

const fn_1 = x => y => x(y); // 存储函数，延迟执行。这也是函数式编程「惰性计算」的来源
const fn_2 = f => x => f(x); // 替换变量名字，结果一样
const add_1 = (f => f(5))(x => x + 2); // 7 = 2 + 5
const add_2 = (x => y => x + y)(2)(5); // 7 = 2 + 5
const add_3 = (x => x + 2)(5); // 7 = 2 + 5
const add_4 = 2 + 5;

fn类型，表明我们可以利用函数内的函数，当函数被当作数据传递的时候，就可以对函数进行操作（apply），生成更高阶的操作。
add类型表明，一个运算式可以有很多不同的路径来实现。

符号表示

我们回到数学，用抽象符号来表示上面我们用到的运算式

// λx.x
const id = x => x;

1. λ表示后面是一个运算式
2. λx表示这个运算式的输入为x，参数命名可以替换，和我们写函数变量一样
3. .x中.的右半部分表示运算式的主体，这里是直接返回x
4. λx.x整个表示一个lambda表达式
5. λx.x y表示将y传入lambda表达式计算，术语称为应用（apply）

学到这个记法后，我们可以有更多的表示

// λx.x + 1 运算体
const addOne = x => x + 1;
// λx.λy.x + y 多参数表达/等价表示
const add_1 = (x, y) => x + y;
const add_2 = x => y => x + y;
// (λx.λy.x + y) 1 2 表达运算
const three = (x => y => x + y)(1)(2);

lambda表达式是左结合的(left associate)，在不产生歧义的情况下可以去掉括号。也就是说

// (λx.λy.x + y) 1 2 表达运算
// 实际是
// (((λx.λy.x + y) 1) 2) 表达运算
const three = (x => y => x + y)(1)(2);

符号的意义

数学家阿隆佐·邱奇在上世纪30年代提出了λ演算，它可以让我们从抽象的角度来描述「计算」这件事，λ演算和图灵机是等价的，都可以描述我们的计算过程。

比如上面我们提到的加法运算，如果是三位数字参与运算，由于加法有交换律，因此a + b + c和c + a + b得到的结果是一样的，我们更关心「计算」这件事本身，而不是参数的顺序。用λ表示为

// λx.λy.λz.x + y + z
const add = x => y => z => x + y + z;

这是一种抽象的表述，这种抽象可以把复杂的「计算」过程变得更加简单。

组合子

考虑一个运算式

// λx.x 记住，x只是一个记号
// λf.f
const id = x => x;

// λx.x x
const x = 1;
const y = id(x); // 1

// (λx.x x)(λx.x x) 
// 如果用f表示函数，这里会比较清晰一点
// (λf.f x)(λf.f x) f为函数，表示λ运算参数和返回都是函数，x为一个函数
const x = id;
const y = id(x)(id(x)) // id

这个id函数的应用((λx.x x))称为ω 组合子，在很多函数式语言中，被称为identity、id函数，它表明我们运算式可以进行组合。((λx.x x)(λx.x x))被称为Ω。

之前我们讲过monad，monad对自己使用id函数，得到自己。这是一个定律。

应用场景-自运算/简化参数

const arr = ['1', '2', '3']
const res_1 = arr.map(Number) // [1, 2, 3]
const res_2 = arr.map(parseInt) // [1, NaN, NaN]

这里的Number函数就是一个类似的id函数（如果你把Number看成一个Monad类型），它把x映射到Number域上。不过这个比喻并不恰当。

id函数的意义在于创建了一个演算系统的基本数据，比如自然数里面1(0)就是最基本的，只要我们定义+1方法，就可以遍历到所有的自然数。

也就是说数学抽象了基本数据和方法，这对应我们在monad中学到的概念Number(1) -> Just(1)。

const id = x => x
const addOne = f => () => f() + 1;

const zero = id(() => 0); // () => 0
const one = addOne(zero); // () => 1
const tow = addOne(one); // () => 2

柯里化

前面我们提到了柯里化，它把多参数的函数转换为一个单参数函数调用链

// 简单实现
const curry = function (fn) {
    let len = fn.length;
    let params = [];

    return function apply(x) {
        params.push(x);
        if (params.length === len) {
            return fn(...params);
        } else {
            return apply
        }
    }
}

const add = (x, y) => x + y;

const chainAdd = curry(add);

// λx.λy.x + y
chainAdd(1)(2); // 3

映射关系

通过「映射关系」来思考，可以把事情变简单。

// 这个箭头，你可以理解为一个映射: x -> x 从一个域x映射到另一个域x，这里两个x相等
const id = x => x;

// 左边为集合{x, y}，映射到{x + y}：(x, y) -> x + y
const add_1 = (x, y) => x + y;
// 柯里化 x -> y -> x + y;
const add_2 = x => y => x + y;

现在你可以这么理解（就像我们讲范畴论的时候一样），所有的程序都等于一个数据x加上对他的操作E。

也就是λ演算: λx.E。E是对参数x的应用。

λ演算

归纳一些重要的点

1. 特定的符号语法来描述函数之间的转换关系（数据映射）
2. 所有的函数都是匿名的，在实际操作之前，参数的顺序不影响运算结果
3. 一般的函数可以通过柯里化变成lambda函数
4. 有一些规律

实际上，在λx.x中，x大部分情况下都是函数，也就是说一个lambda函数作用于另一个lambda函数，得到新的lambda函数。

更多

等价

λx.x的表示方式和λy.y的表示方式是等价的

自由变量

λx.x不存在自由变量，λx.xy则存在自由变量y

β-归约

(λx.T)S形式的应用可以简化为T[x:=S]形式。其中(T/S都是lambda表达式)

(λx.x)s -> x[x:=s] -> s
(λx.y)s -> y[x:=s] -> y

归约就是不断地代换参数的过程。

上面我们说的id(id)这个是个特殊的规约，永远不会停止。

总结

lambda演算是Haskell的基础。后面我们将学习一下Haskell语言。体会什么叫真正的函数是第一等公民。

总的来说，λ演算就是我们抽象「计算」过程的一种方式，就像我们可以把微积分、复数等概念从自然中抽象出来一样。编程中的核心应用就是一切数据都是函数。

1. 目录：./js-design/json.parse.js和./js-design/json.stringify.js。
2. 感觉还不错
3. 下一步，把这两个方式，用Rust实现一遍

leetcode 1448

解题思路

二叉树要统计xx节点、计算xx高度、进行xx排序，都需要遍历二叉树。就像数组你要排序就总会遍历一下数组本身。这里也是。所以核心是遍历过程中什么可以作为我们的判断依据。

核心：没有比该节点大的数字。暗示了我们在遍历过程中仅需要记录最大值就行了。

代码使用先序遍历，遍历时，给定一个max初始值，每次访问到一个节点，就比较节点和链路max节点的大小，以此更新cnt和max

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var goodNodes = function(root) {
    if (!root) return 0
    let cnt = 0;
    function dfs(root, max) {
        if (!root) return root;
        
        if (root.val >= max) {
            cnt++;
            max = root.val;
        }

        dfs(root.right, max);
        dfs(root.left, max);


    }

    dfs(root, root.val);

    return cnt

};

统一规律

1. 先序遍历、中序遍历、后序遍历，总会用到一个。要不然就是广度优先，使用队列来记录层级
2. 辅助参数：最大值、最小值、深度、标识位等等
3. 缓存数据：记录每个节点、记录节点之间的位置

函数式编程和monads

如果你已经适应了函数式编程，尤其是了解副作用和纯函数，那么你可以跳到"展开讲讲monads"

函数式编程

函数式编程是一个经常有相当多的“包袱”的话题，对monads（单子）来说更是如此。当被这些主题后面的形式化术语或数学轰炸时，就很容易在google搜索中迷失，尤其是很多函数式编程迷都认为形式化术语和数学是了解FP/monads的最基本要求。

听我说：你不需要计算机或者数学的学位证书就可以沉浸于函数式编程，并进一步采用monads相关的思维方式。形式术语和数学在你需要深入了解FP/monads时可以提供更丰富和深入的经验知识，但你并不需要一开始就从它们开始来学习FP/monads（除非你想这样！）

你曾写过这样的代码吗？

const FPBookNames = [];

for (const record of data) {
    if (record.topic == "FP") {
        FPBookNames.push(record.bookName);
    }
}

这就是我们通常意义上说的“命令式”代码风格。这对大多数人来说是熟悉的。但它只关注于如何完成一个任务。为了理解这段代码发生了什么或者为什么这么写，你必须在大脑中执行这段代码并推测它的含义。只有读完这段代码后，你才可能了解到：“这段代码的意思是把主题为FP的记录筛选出来并把它们的bookName放到数组里面去”

如果你的代码可以更“声明式”，并且状态的是什么和为什么可以一瞥下来就更清楚，也不再强调为什么，为什么只作为一个不那么重要的实现细节，会怎么样呢？

这就是函数式编程存在的意义。

从循环到Map和Filter

举个例子，想象你有一个字符串值，你想把它转为大写。

function uppercase(str) { return str.toUpperCase(); }

var greeting = "Hello, friend!";

console.log( uppercase(greeting) );   // HELLO, FRIEND!

这个实现相当直接。当假设你现在有多个字符串要转为大写。你可以手动对每个字符串调用uppercase(..)。但是当我们有多个值，把它们放到数组里面，才是最方便的。处理字符串数组的命令式方式：

// assumed: function uppercase(str) { .. }
// assumed: `listOfStrings` (array of string values)

for (let i = 0; i < listOfStrings.length; i++) {
    listOfStrings[i] = uppercase(listOfStrings[i]);
}

这里，我们修改数组中的原始字符串条目，用大写版本替换它们。在函数式编程中，我们通常更希望不去修改或者重新赋值，而是创建新的值。创建新的值是一种减少那些可以导致程序出现bug的意外的副作用的方式。让我们用这种方式来创建一个list：

// assumed: function uppercase(str) { .. }
// assumed: `listOfStrings` (array of string values)

let listOfUpperStrings = [];

for (let i = 0; i < listOfStrings.length; i++) {
    listOfUpperStrings[i] = uppercase(listOfStrings[i]);
}

这代码相当好。但是当你第一次遇到它，为了了解这段代码是什么，你不得不在脑海中执行该代码并推测它的目的。然后，你可以断言，“这段代码取一个数组中的每个字符串，然后产生一个新的大写版本的字符串数组。”

给数组的每一个值执行一个相同的操作，是一个相当通用的编程任务。以至于我们为这个任务命名并为它发明了众所周知的工具程序map(..)。我们来看一下：

// assumed: function uppercase(str) { .. }
// assumed: `listOfStrings` (array of string values)

const listOfUpperStrings = listOfStrings.map(uppercase);

数组的map(..)操作只有一个单独的函数作为输入，这个函数接受一个单独的值，函数返回一个值。uppercase(..)适合这个参数格式，所以我们就直接传递给map(..)。map(..)给我们一个新的数组，数组的值是所有调用提供的函数uppercase(..)后从原始值生成的新的值。

一个通常的对FP的断言是：一个循环调用数组的机制，这个机制对数组的每个值调用一个函数来处理，众所周知的是这种方式（循环处理）不需要在代码中显式编写。

FP已经识别出了大量这种公共的任务，并将它们命名和实现为了公用的程序。

举个例子，filter(..)做了和map(..)相似的操作，但是它不产出新的值，它只判定一个值是否应该保存在新的数组中。

// assumed: `listOfStrings` (array of string values)

function isLongEnough(str) { return str.length > 50; }

const listOfLongStrings = listOfStrings.filter(isLongEnough);

listOfLongStrings是一个新数组，仅包含原始listOfStrings数组中那些长度大于50的字符串。这个结果应该和我们用for循环命令式地实现等效操作相比而言，更易阅读。

我们甚至可以“组合”map(..)和filter(..)操作：

// assumed: function uppercase(str) { .. }
// assumed: function isLongEnough(str) { .. }
// assumed: `listOfStrings` (array of string values)

listOfStrings.filter(isLongEnough).map(uppercase);

现在我们有一个足够长的大写字符串数组！

这就是进入FP带给你的一些早期的被采用的思维模型。这是巨型冰山的一角。

更多了解函数式编程的方式

如果你好奇，但是FP概念对你来说是新的，我推荐你看一下-至少前几章-我的免费在线FP书Functional-Light JavaScript。

这里有一些high-quality video courses about FP on Frontend Masters，包括：

• Bianca Gandolfo's "From Fundamentals To Functional JS"

• Anjana Vakil's "Functional JavaScript First Steps"

• My "Functional-Light JavaScript" -- a companion course to my book of the same name

我认为你的第一个大目标应该是理解FP并对这些主题感到舒适：

• Side Effects 副作用
• Pure Functions 纯函数
• Higher-order Functions 高阶函数
• Function Composition 函数组合
• Currying 柯里化
• Basic List Operations (filter/map/reduce) 基础的数组操作

我怎么知道我学对了呢？

你怎么知道你是从FP到monads转变过程中走在正确的路线上并且感到舒适？这个指南上，我没有好的方式来回答读者的这个问题。但是我至少希望能够提供一些简要概览或者一些提示给你，而不是留下一些不满意的话，“看情况而定”。

当然，在FP方式中，一开始有很多方法来实现完成FPBookNames代码片段的处理。我不会去断言有一个“最正确的方式”。

但是在FP中有些常见的方式，它依赖链式表达式和组合（柯里化）函数，被称为“point-free风格”，可能就像这样：

const FPBookNames = data
    .filter( 
        compose(
            eq("FP"),
            getProp("topic")
        )
    )
    .map( getProp("bookName") );

再次声明，不要去说这是“最正确”的方式来处理这个逻辑，但是，像这样的代码代表了来自FP的**组合，我认为这将帮助你准备接受monads的概念。特别是我在接下来的部分中将贯通展示它们。

当代码写得就像“和你说话”，我认为是时候带你进入monads的海洋了。

展开讲讲monads

在这份指导之外，我推荐看一下这个视频 recording of my conference talk, "Mo'problems, Mo'nads".

Monad是"范畴论"广泛概念中的一个小概念。你可以简要地、不完整地描述范畴论为一个基于事物在组合和转换中的表现来分类和分组事物的方法。

Monad类型是一种在程序中表示值或者操作的方法，它将某些特性行为和那个值或者操作相关联。通过对原始值增加操作，这些额外的行为作为一种“保证”，规定如何与程序中其他Monad表示的值/操作来进行可预测的交互。

这是概念上定义monads是什么。但你可能想看一些代码。

最简单的js演示

我们在js中能实现这种概念的最简要方式是什么？这个怎么样：

function Identity(v) {
  return { val: v };
}

function chain(m,fn) {
  return fn(m.val);
}

这就是monad最基础的实现。特别的是，“Identity”这个monad，意味着它会保留一个值，在你想要用的时候，不用去直接使用这个值。（而是通过Identity来操作）

const myAge = Identity(41);   // { val: 41 }

我们只在一个对象容器中放置一个值，这样我们就可以识别该值为单子化（monadically）的。这个容器是一个方便的实现单子的方式，但是实际上这不是必须的。

chain(..)函数提供了一个最小的兼容操作monad实例的方式。比如，想象我们想要41的一元表示，并且产生另一个从41增加到42的monad实例。

const myAge = Identity(41);   // { val: 41 }

const myNextAge = chain( myAge, v => Identity(v + 1) );   // { val: 42 }

值得注意的一个重点是，即使我在这里使用Identity和chain，但这只是简单的一个选择而已。Monad对我们用什么命名事物而言，并没有明确的要求。但是如果我们使用他人常用的名字来命名，它有助于创造一个提升我们交流方式的熟悉环境。仅此而已。

chain(..)函数看起来非常基础，但是他是非常重要的（不管你用什么名字来表示它）。我们将深入了解一下它。

我敢肯定这段代码似乎让大多数读者都感到印象深刻。为什么不简单的使用41和42，而要用{val: 41}和{val: 42}呢？使用mondas的为什么好像不是很明确。你必须和我一起再聊聊其他的才能开始谈为什么。

但希望我至少从根本上已经展示给你看了，monad并不是什么神秘或复杂的东西

构建monads

Monads以前被用各种听起来愚蠢的比喻来描述，比如墨西哥卷饼。有的叫monads为“包装盒”或者“盒子”，或者“数据结构”...事实是，这些描述monad的方式都是片面的。就想看一个魔方，你可以从一个面看到方块，然后转向后看另一个不同的面，以得到更整体的认知。

一个完整的理解需要熟悉各个方面，但是完整的理解并不是一个单一的原子事件。它通常是基于许多小的理解建立起来的，就像每次只能看到魔方的一个面一样。

现在，我只想你专注于这个事：你可以给一个值42或者一个操作console.log("Hello, friend")增加/关联额外的行为来增强它们，给他们超能力。

这有另外一个可能的阐释monads的方式，使用Monio带来的能力。

const myAge = Just(41);

Monio相关文档看: Just

上面的代码展示了一个Just(..)函数，它和Identity(..)之前展示的函数很像。Just这个monad的行为就像一个构造器（单元）

并且

const printGreeting = IO(() => console.log("Hello, friend!"));

我们看另一个Monio的IO(..)函数，它表现得像是一个IOmonad的构造器（保留函数）

回想我们之前的草稿，你可以大体认为myAge就像{value: 41}，printGreeting就像{ val: () => console.log("Hello, friend!") }。Monio的表示方式比仅仅一个对象更加复杂，但它的底层并没有什么不同。

我将在这个指南的剩余部分使用Monio。这是很方便来利用的例子，并且更容易来说明。但是请记住在这所有展示之外，我们可以做更直接的事情，比如定义一个对象{val: 41}

深入Map

考虑数组的map(..)方法的概念。它的任务是对所有关联数组的值应用一个映射（值转换）操作。

[ 1, 2, 3 ].map(v => v * 2);   // [ 2, 4, 6 ]

注意：这个功能（map）相关的技术术语是函子（Functor）。事实上，所有的monads都是Functors，但是目前不要太担心这个术语。只需要你脑海有这个概念即可。

这个映射操作在我们数组只有一个元素的时候也当然成立，对吧？

[ 41 ].map(v => v + 1);   // [ 42 ]

一个很容易被我们忽略的极其重要的细节就是，map(..) 函数并不产生42，而是产生[42]给我们。为什么？因为map(..)的任务是产生一个它调用的原始容器相同类型的实例。从这个意义上说，如果你使用数组的map(..)，你就是总会得到一个数组。

但是如果我们的容器是一个monad实例呢？如果这个monad下只有一个值41？因为monad也是一个Functor（可以被映射），我们应该可以期待一个相同类型的输出吧，对吗？

const myAge = Just(41);

const myNextAge = myAge.map(v => v + 1);   // Just(42)

希望这里有实际的意义，myNextAge应该是另一个Just的实例，这个新的Just表示有一个底层的值42

还记得上一章中的这个简单示例吗？

// assumed: function Identity(val) { .. }
// assumed: myAge ==> { val: 41 }

const myNextAge = chain( myAge, v => Identity(v + 1) );   // { val: 42 }

用Monio的实现来替换就是：

const myNextAge = myAge.chain(v => Just(v + 1));

所以map(..)和chain(..)之间的关系是什么？让我们把它们写到一起来看看：

myAge.map(   v =>      v + 1  );    // Just(42)
myAge.chain( v => Just(v + 1) );    // Just(42)

现在你明白了吗？map(..)设定它的返回值需要在一个容器实例中被自动包装，而chain的返回值需要是一个已经被包装为正确容器类型的值。

map(..)函数根本不需要被命名来满足monad实例的Functor行为。实际上，你甚至根本不需要一个map(..)函数，如果你有一个chain(..)函数的话，可以实现一个map(..)：

function JustMap(m,fn) { return m.chain(v => Just(fn(v))); }

fortyOne.map(    v => v + 1);   // Just(42)
JustMap(fortyOne,v => v + 1);   // Just(42)

有一个map(..)函数（不论它真名叫什么）比起chain(..)函数本身来说，是很方便的事情，但map(..)函数并不是必须的。

单子链（monadic chain）

chain(..)函数有时候是另外的名字（在其他库或者语言中对monad概念进行实现时），比如flatMap(..)或bind(..)。在Monio的monads中，所有的这三个方法是等效的，任意选一个来用就行了。

命名flatMap(..)可以加强这个操作和map(..)之间关系的理解。（map(..)自动装箱，flatMap(..)手动装箱）

Just(41).map(     v => Just(v + 1) );    // Just(Just(42)) -- oops!?

Just(41).flatMap( v => Just(v + 1) );    // Just(42) -- phew!

如果我们从map(..)返回一个Just实例，它就会在外层还有一层Just包装，所有我们就得到一个嵌套两层的monad值。这个是合法的操作，有时候我们就希望如此，但通常情况下我们不希望这样。如果我们用flatMap(..)返回相同的类型（也叫chain(..)/bind(..)），这就没有嵌套。本质上，flatMap(..)函数将返回值扁平化了一层！

chain(..)方法旨在为提供的函数返回一个与调用该方法的函数相同类型的monad。然而，Monio通常不执行显示类型强制，因此没有严格组织这种monad类型较差的情况。（比如Just和Maybe）是否遵循这些机制的隐含类型特征取决于开发者自己。

我已经断言chain(..)（不论你称为什么名字）是作为单子（monadic things）最重要的概念。然而，即使像chain(..)看起来实现起来一样简单（see earlier），它却提供了一种特别的方式来保障一个monad如何和其他的monad实例作交互。这些相互作用和转换对于构建一个没有混乱的monads程序而言是至关重要的。

Monad魔方的另一面是这些保证。它们被确保为定律一样的东西，所有符合monad实现的事物都必须遵守：

1. Left Identity 左交换律
2. Right Identity 右交换律
3. Associativity 结合律

这些定律的形式和数学重要性现在并不重要，但是用我们微不足道的Monio的Just（identity monad）来非常简单地说明一下这些定律：

// helpers:
const inc = v => Just(v + 1);
const double = v => Just(v * 2);

// (1) "left identity" law
Just(41).chain(inc);                        // Just(42)

// (2) "right identity" law
Just(42).chain(Just);                       // Just(42)

// (3) "associativity" law
Just(20).chain(inc).chain(double);          // Just(42)
Just(20).chain(v => inc(v).chain(double));  // Just(42)

这里我用Monio的chain方法，这仅仅是个方便的演示说明。monad的定律是用chain操作来表述的，不论你选择怎么称呼它。

回归Monad的核心问题

归根结底的是，Monad类型只是要求做这两件事情：

1. 一个函数作为构造器来构建monad类型（单元构造器，比如Just Maybe）
2. 一个函数来实现chain操作，满足交换律和结合律

你在本指南中的代码片段中看到的，比如包装monad实例、指定方法名称、"friends of monads" behaviors等，所有的方便提供的类型都来自于Monio。

但从这个狭隘的角度来看，一个monad并不需要是一个“容器”（比如包装一个object或class实例），也并不需要一个具体的值（比如42）。一个“包装着一个值的容器”是一个可观察的潜在有用的魔方面（包装的容器是观察理解monad的一个例子），它并不是monad的全部样貌。在你的思维中不要有太多“包装”相关的想法！

但是，我怎么拿到数据？

你可能仍然奇怪：我们如何提取值（比如基本数据类型42）--或者实际上，如何把monad所代表的一切--从单子表示（monadic representation）中提取出来？目前看起来好像每个单子操作都只是产生另一个monad实例。从某种意义上说，我们可能需要一个实际的数字42来打印，或者插入数据库，对吧？！

一个FP的重要概念（尤其是monads里面），是延迟我们对底层值的需求到最后的时刻。对于monads，我们更希望尽可能长地保持所有的“提升”在单子空间（monadic space）。

但又是我们确实需要转换一个monad到“真实”的值。有很多方式可以完成这个操作，但是这有一个方式，预览我们将在talk about later in the guide中说的。为了从一个monad（比如Just） 中“提取”值，我们可以使用一个Monio提供的方法fold(..)

const identity = v => v;

const myAge = Just(41);
const myNextAge = myAge.map(birthday);

// later:
const ageIsJustANumber = myNextAge.fold(identity);
console.log(`I'm about to be ${ ageIsJustANumber } years old!`);
// I'm about to be 42 years old!

所以，这里有一个“逃逸值”（fold(identity)），让我们可以从我们的Just中退出。

但是记住：monads可以和其他monads很好的交互（and their friends!），所以最好的方式是尽可能地保持值在单子空间。让我们推迟丢弃monad表示的方式，直到我们必须这么做！

同时记住：fold(..)方法提供给Monio的众多monads，它并不是Monad类型的行为。它来自于from a friend called Foldable

Maybe单子更进一步

Monio 相关文档看: Maybe

Just单子可能并不那么神奇。它很可爱，也许有点聪明，但它有点不起眼。实践中，我们几乎不会直接创建一个Just单子实例。

这些只是基础。它本身并不应该看起来具有革命性，因为这将呈现出太高的一个悬崖，而我们可能高不可攀。如果您小时候第一个数字不是2或者3，而是 √2或π，你可能会发现在小时候学习基础数学非常难！

如果Just对你来说看起来太简单了，那可能是一件好事！你可能正在“学会”monads。但是不要让它简单到让你觉得枯燥，觉得没有值得你花时间的知识。是有这样的知识的！

在这个基础的monad概念之上，有很多变体/增强的概念，会让事情变得更加有趣。我可以花很多时间和很多页来详细说明他们的例子。但是让我通过简单的演示另外的一些建立在Identity单子之上的monads的例子来逐步进行。

你可能之前命令式的程序里面写过这种样式的代码：

const shippingLabel = (
    (record != null && record.address != null && record.address.shipping != null) ?
        formatLabel(record.address.shipping) :
        null
);

当我们对这些期望他们不是null的值进行操作时，我们必须在整个程序中使用!= null检查来避免js异常。

然而，最新的js（ES2020）增加了一个“可选链”（optional chaining）操作，可以简单地做这些事情：

const shippingLabel = (
    (record?.address?.shipping != null) ?
        formatLabel(record.address.shipping) :
        null
);

?.操作（而不是.），是一个短路操作符，当左值为null时就跳过操作。这意味着我们不需要record != null或者record.address != null检查，因为?.帮我们做了这个事。

我们的操作现在就被保护起来了，不会在null上操作，但record.address.shipping仍然可能是空的，我们想要在这种场景下跳过formatLabel(..)操作，因此最后我们还有一个!= null的检查。

Maybe单子，有时候在其他库和语言内被称为Option或者Optional，允许我们定义一个行为来讲这些!= null完全委托给monad的行为，将我们从这些行为中解放出来。

为了了解Maybe，让我们先在我们之前讨论过的Just Identity单子之外增加一个monad类型：琐碎而不起眼的monad，我们称为Nothing（表示空）。Nothing比Just做的事情还少：它使得你在它上面调用的任意方法短路。就像一个方法黑洞，可以安全地跳过有危害的操作。Nothing是安全的，它就像是单子化的null或者undefined。

Maybe是一个Sum Type，它表示这两种monad类型（Just Nothing）的对偶性。这并不是说Maybe同时是两种类型，而是说它要么是其中一个，要么是其中的另一个。

注意：大多数monad实现不会暴露Just和Nothing作为单独的monad类型，而是只有一个Maybe类型。Monio选择分开表示他们同时也可以用Maybe结合他们，是为了方便演示的目的。

在Maybe:Just和Maybe:Nothing之间做选择在一开始可能会有一些迷惑性。你可能期望决策本身来源于一个单元构造器Maybe(..)。实际上，大多数受欢迎的monad教程/博客都是这么做的，因为这样令Maybe的演示更加方便也令人满意。

但这并不是合适的monad方式。Monio做了更恰当的事情，并将决策从Maybe(..)/Maybe.of(..)构造器转移到一个名为Maybe.from(..)的独立帮助函数中。Maybe.from(null)将得到一个Maybe:Nothing实例，Maybe.from(42)将得到一个Maybe:Just实例。

相比之下，调用Maybe(..)/Maybe.of(..)不会做任何条件选择，而只会将任何非Maybe的值表示为Maybe:Just。

此外，Maybe.from(..)为Nothing.isEmpty(..)代理了这个问题，“它是空的吗？”。Nothing.isEmpty(..)函数会执行== null检查，但是你可以覆盖他以重新定义什么值你想定义为Maybe.from(..)的空。

所以我们用Maybe.from(..)来创建Maybe:Just或Maybe:Nothing实例。下面的代码中，.chain(..)调用将因此带来副作用令一个和另一个相对（Maybe本身仅作为一个薄弱的传递包装器）

const shippingLabel = (
    Maybe.from(record)
    .chain( record => Maybe.from(record.address) )
    .chain( address => Maybe.from(address.shipping) )
    .chain( shipping => Maybe.from(formatLabel(shipping)) )
);

shippingLabel就是一个Maybe类型。它要么表示Maybe:Just，有一个值，要么表示Maybe:Nothing，为空。

但是不论它表示哪个，都不影响我们写monad风格的代码串！如果Maybe.from(..)在这个链的任意位置产生一个Maybe:Nothing，任意子序列的chain(..)操作将跳过，因此把我们的代码从因bull造成异常的情况下保护起来。

Maybe安全抽象了我们之前关于对保护操作不引发异常的条件决策逻辑的担心。

上面的代码可能有些繁琐，让我们用一些帮助函数来清理它：

// assumed:
// function formatLabel(label) { .. }

// helpers:
const getPropSafe = prop => obj => Maybe.from(obj[prop]);
const formatLabelSafe = v => Maybe.from(formatLabel(v));

const shippingLabel = (
    Maybe.from(record)
    .chain( getPropSafe("address") )
    .chain( getPropSafe("shipping") )
    .chain( formatLabelSafe )
);

这代码看起来更棒一些。而且这里没有让我们代码显得杂乱的!= null检查。

我们的shippingLabel单子现在准备好和其他monads行为交互了，并且这些交互会安全可预期，不论它具体是Maybe:Just还是Maybe:Nothing。

我们代码更进一步的提升可以用Monio提供的便利。一个monad的帮助函数，pipe(..)：

const shippingLabel = (
    Maybe.from(record)
    .chain.pipe(
        getPropSafe("address"),
        getPropSafe("shipping"),
        formatLabelSafe
    )
);

我们看到，chain.pipe(..)允许你组合多个.chain(..)序列为一个按序排列参数的调用。在Monio的monads上，你可以用.map.pipe(..)和.ap.pipe(..) .concat.pipe(..)做同样的事情。除了增加便利性之外，在某种程度上，它也稍微更有效率/性能更好。

顺便提一下，Maybe也是Foldable，所以可以用fold(..)退出，获得逃逸值。但因为Maybe是一个Sum Type，这里的fold(..)有两个函数，第一个Maybe:Nothing时调用，第二个Maybe.Just时调用。更多看：using Foldable and other adjacent behaviors later

你可能希望开始看一些monad表示值和表达式带来的更多好处。

我知道，IO很重要

Monio Reference: IO (and variants)

目前为止，我们已经看到那些表示直接基本数据类型比如42或者表示对象的例子。但是monads不仅仅是“值包装器”。

monads也可以被认为是一种“行为包装器”，表示一些操作，比如那些我们认为不可靠的，可能产生副作用的方法或者函数。这就是IO单子所做的事！

Monio的核心是IO单子的实现。它被设计为一个超级强大的Sum Type，它包含了各种有用的行为，有点像Scala's ZIO。我认为Monio的IO是js中最强大的IO实现。但我知道这只是一个令人生畏的主张。

别担心，为了继续，我们现在要专注于一小块IO功能，这样我们就不会不知所措。

你在IO中传入的那个函数，在执行时将开始一些副作用操作。它并不必须是副作用操作。它可以是静态的、纯函数，就像普通函数一样返回一个值。

最重要的概念是IO单子类型是惰性的，它并不即时做任何事情（就像你调用普通方法一样自动执行并返回值）。你必须评估IO能执行的操作。

For example:

const greeting = IO(() => console.log("Hello, friend!"));

// later (nothing has happened yet!)
greeting.run();
// Hello, friend!

An IO, once evaluated, can also produce a value:

一个IO，一但运行了，可以产生一个值。

const customerName = IO(() => (
    document.getElementById("customer-name-input").value
));

customerName.run();  // "Kyle"

run(..)方法可以认为有点像Just和Maybe上的fold(..)。它帮助你执行IO单子，并把副作用行为从单子空间逃逸出来。

就像我们已经断定过几次的那样，“最佳实践”的重要目标是保持我们程序的副作用为IO操作，并只在程序需要的最后一刻消耗他们（逃逸/运行/执行）。

这有个复杂的例子串联一些IO在一起

// helpers:
const getProp = prop => obj => obj[prop];
const assignProp = prop => val => obj => obj[prop] = val;

const getElement = id => IO(() => document.getElementById(id));
const getInputValue = id => getElement(id).map( getProp("value") );
const renderTextValue = id => val => (
    getElement(id).map( assignProp("innerText")(val) )
);


const renderCustomerNameIO = (
    getInputValue("customer-name-input")
    .chain( renderTextValue("customer-name-display") )
);

// later:
renderCustomerNameIO.run();

你可以看到，这里我们组合了一些副作用操作在一起，就像我们之前组合数字和对象一样可预测。monads确实是一种变革性的、革命性的思考我们程序的方式。

为了方便，IO.of(..)通常是IO(() => ..)的等效操作。在两种情况下，你都得到一个惰性的IO。但是请注意细微的差别/陷阱：在IO.of(..)下，任何被提供的表达式都会被立即执行，然而当你用IO(() => ..)，你需要手动装箱你的表达式，不论是什么，都要装箱为一个函数，这样它就不会被立即执行。

这样情况下，IO.of(..)应该仅当你已经有一个固定的非副作用的值表达式时使用，当你的表达式是一个副作用时你应该总是使用IO(() => ..)

但是为什么要IO单子？

为什么要把所有副作用操作都放到IO实例里面？

最根本的回答是：我们需要在不同副作用之间的到一个可预测的交互！（和保证！）。

当副作用直接且同步的，比如从DOM中的到一个元素，或者注入元素内容，可预测性和保证性似乎对我们没有太大的好处。

所以我最想放在这里的问题是：为什么Monio的IO单子是特别的？

我强烈认为我们代码中最复杂的副作用来源于异步操作，比如ajax请求，执行一个定时器，监听一个事件，执行一段动画等等。一个像Monio这样的IO实现可以提供一个处理代码中异步操作的通用模型，因此得到一个在异步操作中可预测和得到保证的程序是一个改变规则的处理方式。

Monio的IO自动转换和消化js的Promise，并在任何异步操作发生时提升一个IO链为一个Promise。对事件流（单Promise不能适用的场景），IOx就像是IO加Observable.

如果这还不足以引起您的兴趣，那么程序面临的另一个挑战（无论您是否意识到），Monio 的 IO 像冠军一样给出：如何将一组操作与环境隔离（如 DOM 等），以便您可以为代码运行提供环境/上下文？这对于防止程序中出现意外副作用至关重要，但它也是创建 TESTABLE 副作用代码的最有效方法。

Monio 的 IO 也包含 Reader monad 类型的行为。这意味着IO（无论链有多长/涉及多长时间）携带一个提供的“环境”，作为参数传递给run（..）。

您可以将整个程序定义为一个“IO”实例，并且如果您调用“run(window)”，您将在浏览器的 DOM 上下文中运行您的程序。但是在您的测试套件中，您可以在同一个 IO 上调用 run(fakeDOMglobal)，现在所有代码和副作用都会自动通过该替代环境进行线程化。

It's effectively passing the entire "global" (aka, universe/scope-of-concern) into your program, whatever appropriate value that is, instead of the program automatically assuming which "global" it should apply against.

它有效地将整个“全局”（global）（又名，universe全局/scope-of-concern关联作用域）传递到您的程序中，无论是什么适当的值，而不是程序自动假设它应该适用于哪个“全局”。

但最终，Monio 的 IO 的真正力量 甚至没有包含在我们迄今为止讨论的内容中。 pièce de résistance 是 IO 提供了一座桥梁，让您回到熟悉和舒适的更命令式编码。

你喜欢使用 if 和 try..catch 和 for..of 循环吗？您可能已经注意到 FP 和 monads 似乎将所有这些东西都扔到了窗外，有利于长链的柯里化和组合函数调用。如果您可以获得“IO”的所有功能，但在有帮助的情况下选择使用更典型的命令式代码风格会怎样？

IO.do(..) 需要一个 JS 生成器，其代码看起来像大多数 JS 开发人员非常熟悉的 async..await 样式。当你 yield 一个值时，如果它是一元的，它会自动链接和解包（就像你有一个 IO 到 chain(..) 的来源）。如果结果是异步的（承诺），生成器内的代码会自动暂停以“等待”完成。

结合其所有方面，Monio 的 IO（和 IOx 超集）是“一个**它们的单子”。

还有一些其他的monads（作为我们的朋友）

好吧，如果你已经做到了这一步，请深呼吸。说真的，也许去散步让其中的一些安顿下来。也许重新阅读它，几次。“一个**他们所有人的单子”。

我们已经看到了单子概念的一个不错的（如果是基本的）说明。而且我们没有涵盖 Either —— 另一个 Sum Type 像 Maybe，但它在双方都持有值。 Either 通常用于表示同步的 try..catch 样式异常处理。我们也没有介绍 AsyncEither，它扩展了 Either 以异步操作（通过 Promise），与 IO 转换/处理它们的方式相同。 AsyncEither 本质上是 Monio 对 Promise/Future 类型的表示。

但是与 monad 适合的范畴论的广阔相比，它本身就是一个相当狭窄的概念。有许多来自范畴论的相邻（并且有些相关）概念，更具体地说，是“代数数据类型”（ADT）——或者至少是从它的一部分改编而来的。这些“朋友”包括：

• Foldable 可折叠 - 用于逃逸值
• Concatable (aka, Semigroup) 可连接 幺半群 - 链式操作
• Applicative 可应用 - 应用其他monad的方法

那里还有很多很多其他主题，但这是 Monio 关注的主要三个“朋友”（并与它的 monad 混合）

需要明确的是，这三个不是单子行为。我称它们为“单子的朋友”，因为我发现单子与这些其他行为混合在我的 JS 代码中比单独的单子（或任何其他类型）更有用/实用；我认为正是这些类型行为的组合使 monad 对我们的程序具有吸引力和强大的解决方案。

我知道 FP 领域的许多人更喜欢完全独立地考虑每种类型。如果它对他们有效，那没关系。但我发现这些组合更具吸引力。

Foldable可折叠

混入（大部分）Monio 的 monad 中的 fold(..) 方法正在实现“可折叠”类型的行为。值得注意的是，IO 及其变体不是直接可折叠的，但那是因为当您调用 run(..) 时，IO 的本质已经在做某种 fold(..)。

我们已经看到了前面几次引用的 fold(..)。这只是 Monio 提供的名称，但就像 chain(..) vs flatMap(..) vs bind(..)，名称本身并不重要，只有预期的行为.

我们没有谈论 List 类型的 monad（因为 Monio 不提供这样的），但当然可以存在。在这种 List monad 的上下文中可折叠将在列表中的所有值上应用提供的函数，通过将每个值折叠到累加器中来逐步累加单个结果（任何类型）。 JS 数组有一个 reduce(..) 方法，它基本上是 List 的可折叠的实现（Foldable）。

相比之下，在单值 monad（如 Just）的上下文中，Foldable 使用其单个关联/基础值执行提供的函数。它可以被认为是通用 List 可折叠的一个特例，因为它不需要跨多次调用“累积”其结果。

类似地，像 Maybe 和 Either 这样的 Sum Types 在 Monio 中也是可折叠的；这是进一步的特化，这里的 fold(..) 有两个函数，但只会执行其中一个。如果关联值为“Maybe:Nothing”，则应用第一个函数，否则（当关联值为“Maybe:Just”时），应用第二个函数。 Either:Left 调用第一个函数和 Either:Right 调用第二个函数也是如此。

但是我们如何实际使用 Foldable 呢？

正如我在本指南前面几次暗示的那样，一种这样的转换是通过将标识函数（例如，v => v）传递给 fold (..)。

Just(42).fold(identity);   // 42

Rather than using Foldable to extract the value itself, we'll more often prefer to use fold(..) to define a natural transformation from one kind of monad to another. To illustrate, let's revisit this example from earlier:

现在，如果你仔细观察，像 Just、fold(..) 和 chain(..) 这样的单值 monad 似乎具有相同的行为（甚至实现几乎相同）。你可能想知道为什么我们应该在 Just 上提供看似重复的 fold(..) 而不是仅提供 chain(..)？

正如我在单子链里解释的，chain(..)函数总是返回一个和调用container相同的container类型（函数签名）。换句话说，haskell风格的类型签名本质上是chain: m a -> (a -> m b) -> m b。类型/种类 m 的 monad 可能在内部与在 chain(..) 调用之前到之后的不同类型值（a 与 b）相关联，但它仍然应该是一个m 种单子。

所以调用 Just(42).chain(identity) 得到逃逸值违反了这个隐含的类型签名——尽管 Monio 没有强制执行它并且操作可以正常工作。另一方面，fold(..) 没有那种隐含的类型签名，因为它旨在让您“折叠”（取到内部值）到任何任意类型，而不仅仅是另一个 monad 实例。 fold(..) 是一个更灵活的路径，它允许我们“提取”关联/基础值。

此外，Foldable 在 Sum Types Maybe 和 Either 上的 fold(..) 与它们的 chain(..) 方法有一个非常不同的签名，因此它们根本不会相互重复.

与其使用 Foldable 来提取值本身，我们更喜欢使用 fold(..) 来定义从一种 monad 到另一种的自然转换。为了说明，让我们回顾一下之前的这个例子：

// assumed:
// function formatLabel(label) { .. }

// helpers:
const getPropSafe = prop => obj => Maybe.from(obj[prop]);
const formatLabelSafe = v => Maybe.from(formatLabel(v));

const shippingLabel = (
    Maybe.from(record)
    .chain.pipe(
        getPropSafe("address"),
        getPropSafe("shipping"),
        formatLabelSafe
    )
);

如果我们想渲染shipping标签，但前提是它实际上是有效/定义的，否则打印默认通知，我们可以像这样安排我们的程序：

// assumed:
// function formatLabel(label) { .. }

// helpers:
const identity = v => v;
const getPropSafe = prop => obj => Maybe.from(obj[prop]);
const assignProp = prop => val => obj => (
    Maybe.from(obj).map(o => o[prop] = val)
);
const getElement = id => IO(() => document.getElementById(id));
const renderTextValue = id => val => (
    getElement(id).map(el => (
        Maybe.from(el).fold(
            IO.of,
            assignProp("innerText")(val)
        )
    ))
);
const formatLabelSafe = v => Maybe.from(formatLabel(v));


// ----

const renderShippingLabel = v => (
    v.fold(
        () => IO.of("--no address--"),
        identity
    )
    .chain( renderTextValue("customer-shipping-label") )
);

const renderIO = renderShippingLabel(
    Maybe.from(record)
    .chain.pipe(
        getPropSafe("address"),
        getPropSafe("shipping"),
        formatLabelSafe
    )
);

renderIO.run();

A key aspect of the snippet is Maybe's fold(..) call in the renderShippingLabel(..) function, which folds down to either a fallback IO value if the shipping address was missing, or the computed IO holding the valid shipping address, and then chain(..)s off whichever IO was folded to. There's a similar thing happening in renderTextValue(..). Both fold(..) calls are expressing a natural transformation from the Maybe monad to the IO monad.

Again, Foldable is distinct from monads. But I think this discussion illustrates how useful it is when paired with a monad. That's why it's an honored friend.

花点时间阅读和分析该代码。它说明了我们的 monad 类型如何以有用的方式进行交互。我保证，即使一开始这段代码看起来令人头晕目眩——它对我来说确实如此！ -- 最终你会理解甚至更喜欢这样的代码！

这段代码片段的一个关键方面是 renderShippingLabel(..) 函数中的 Maybe 的​​ fold(..) 调用，如果shipping address丢失，它会折叠为备用 IO 值，或者计算出的 IO 包含有效的送货地址，然后 chain(..) 关闭任何 IO 被折叠到的位置。在 renderTextValue(..) 中也发生了类似的事情。两个 fold(..) 调用都表达了从 Maybe monad 到 IO monad 的自然转换。

同样，Foldable 与 monad 不同。但我认为这个讨论说明了与 monad 配对时它是多么有用。这就是为什么它是尊敬的朋友。

可连接/幺半群

Concatable，正式称为 Semigroup（幺半群），是 monad 的另一个有趣的朋友。您不一定会经常看到它显式使用，但它可能很有用，尤其是在使用 foldMap(..)（它是 reduce(..) 的抽象）时。

Monio 选择在其 monad 上实现 Concatable 作为 concat(..) 方法。该名称不是类型所必需的，当然，Monio 就是这样做的。

这里的基本**是一个值类型是“可连接的”，如果它的两个或多个值可以连接在一起。例如，原始的、非 monad 值类型（如字符串和数组）是可连接的，实际上它们甚至公开了相同的 concat(..) 方法名称：

"Hello".concat(", friend!");     // "Hello, friend!"
[ 1, 2, 3 ].concat( [ 4, 5 ] );  // [1,2,3,4,5]

由于 Monio 的所有 monad 都是可连接的，它们都有 concat(..) 方法。因此，如果任何这样的 monad 实例与一个值相关联，该值也有一个符合 concat(..) 方法的值——例如，另一个 monad，或者像字符串或数组这样的非 monad 值——然后调用monad 的 concat(..) 方法将委托对关联/基础值调用 concat(..)。这个对底层 concat(..) 的委托是递归的。

For example:

Just("Hello").concat(Just(", friend!"));        // Just("Hello, friend!")
Just([1,2,3]).concat(Just([4,5]));              // Just([1,2,3,4,5])

Just(Just([1,2,3])).concat(Just(Just([4,5])));  // Just(Just([1,2,3,4,5]))

// `fold(..)` and `foldMap(..)` provided in
// Monio's util module
fold(Just("Hello"),Just(", friend!"));          // Just("Hello, friend!")

foldMap(
    v => v.toUpperCase(),
    [
        Just("Hello"),
        Just(", friend!")
    ]
);                                              // Just("HELLO, FRIEND!")

与 chain(..) 一样，Monio 的 concat(..) 应该用于两个相同种类的 monad 之间。但是没有明确的类型强制来防止交叉类型（例如，在 Maybe 和 Either 之间）。

注意： 尽管名称重叠，但 MonioUtil 模块提供的独立 fold(..) 和 foldMap(..) 实用程序不 与 [可折叠类型](# foldable) 的 fold(..) 方法出现在 Monio monad 实例上。

单体/Monoid

此外，术语 Monoid 表示可连接/半群加上连接的“空”（恒等式）值。例如，字符串连接是一个带有空 "" 字符串的幺半群。数组连接是一个带有空 [] 数组的幺半群。即使是数字加法也是一个带有“0”“空”数字的幺半群。

将这种幺半群的概念扩展到最初看起来不像“可连接”的东西的一个例子是将多个布尔值组合在一个 && 或 || 逻辑表达式中。对于逻辑与运算，“空”值为“真”，而对于逻辑或运算，“空”值为“假”。这些值的“连接”是计算的逻辑结果（true 或 false）。

Monio 提供 AllIO 和 AnyIO 作为 IO 变体，它们是 monoids —— 同样，“空”值和 concat(..) 方法。特别是，这两个 IO 变体上的 concat(..) 方法旨在计算两个布尔结果 IO 之间的逻辑与/逻辑或（分别）。这使得 AllIO 和 AnyIO 易于与前面提到的 fold(..) 和 foldMap(..) 实用程序一起使用。

Monio Reference: AllIO, AnyIO

下面是通过 fold(..) / foldMap(..) 连接这些 monoid 的示例：

const trueIO = IO.of(true);
const falseIO = IO.of(false);

fold( AllIO.fromIO(trueIO), AllIO.fromIO(falseIO) ).run();  // false
fold( AnyIO.fromIO(falseIO), AllIO.fromIO(trueIO) ).run();  // true

const IObools = [
    trueIO,
    trueIO,
    trueIO,
    falseIO,
    trueIO
];

foldMap( AllIO.fromIO, IObools ).run();   // false
foldMap( AnyIO.fromIO, IObools ).run();   // true

作为额外的便利，Monio 的 IOHelpers 模块还提供了 iAnd(..) 和 iOr(..)，它会自动应用此逻辑与/逻辑-或 foldMap(. .) 对两个或更多提供的 IO 实例的逻辑：

const trueIO = IO.of(true);
const falseIO = IO.of(false);

iAnd( trueIO, trueIO, falseIO, trueIO ).run();  // false
iOr(  trueIO, trueIO, falseIO, trueIO ).run();  // true

我正在说明使用直接的 true 和 false 值创建 IO 实例，但这并不是您实际使用这些机制的方式。由于它们都是 IO 实例，因此布尔结果（true 或 false）可以在它们各自的 IO 中延迟（并且异步！）计算，即使是由于复杂的副作用。

例如，您可以定义代表 DOM 元素状态的几个 IO 实例的列表，如下所示：

// helpers:
const getElement = id => IO(() => document.getElementById(id));
const getCheckboxState = id => getElement(id).map(el => !!el.checked);

const options = [
    getCheckboxState("option-1"),
    getCheckboxState("option-2"),
    getCheckboxState("option-3")
];

const allOptionsChecked = iAnd( ...options ).run();    // true / false
const someOptionsChecked = iOr( ...options ).run();    // true / false

额外练习：考虑在没有选中任何复选框时如何计算 noOptionsChecked - true。

可应用

Applicative 比 Semigroup 更不寻常（根据我的经验，不太常见）。但有时它会有所帮助。 Monio 选择使用 ap(..) 方法在其大多数 monad 上实现此行为。

Applicative 是一种模式，用于在 monad 中保存一个函数，然后“应用”来自另一个 monad 的值作为函数的输入，将结果返回给另一个 monad。如果该功能需要多个输入，则可以多次执行此“应用程序”，一次提供一个输入。

但我认为解释 Applicative 的最佳方式是只显示具体代码：

const add = x => y => x + y;

const addThree = Just(add(3));     // Just(y => 3 + y)
const four = Just(4);              // Just(4)

addThree.ap(four);                 // Just(7)

如果一个 monad 持有一个函数，例如这里显示的 curried/partially-applied add(..)，你可以将它“应用”到另一个 monad 中持有的值。注意：我们在源函数持有的 monad (addThree) 上调用 ap(..)，而不是在目标值持有的 monad (four) 上调用。

这两个表达式大致等价

addThree.ap(four);

four.map( addThree.fold(fn => fn) );

回想一下 可折叠，将标识函数传递到 Monio monad 的 fold(..) 中，本质上是从 monad 中提取值。如图所示，ap(..) 有点像“提取”第二个 monad 中保存的映射函数，并针对第一个 monad 中保存的值运行它（通过 map(..)）。

用单个表达式表达上述内容的另一种方式：

const add = x => y => x + y;

Just(add)               // Just(x => y => x + y)
    .ap( Just(3) )      // Just(y => 3 + y)
    .ap( Just(4) );     // Just(7)

我们将 add(..) 本身放入了 Just 中。第一个 ap(..) 调用“提取”该函数，将 3 传递给它，然后使用返回的 y => 3 + x 函数创建另一个 Just。然后第二个 ap(..) 调用与前面的代码片段执行相同的操作，提取 y => 3 + x 函数并将 4 传递给它。 4 => 3 + 4 的最终结果是 7，然后将其放回到 Just 中。

与 chain(..) 和 concat(..) 一样，Monio 的 ap(..) 应该 传递与调用方法相同类型的 monad。但是没有明确的类型强制来防止交叉类型（例如，在 Maybe 和 Either 之间）。

Monio 的所有非IO monad 都是 Applicative。同样，您可能不会非常频繁地使用这种行为，但希望您现在能够在它出现时认识到需求。

总结

我们现在已经触及了 monad（以及几个 朋友）的表面。这绝不是对该主题的完整探索，但我希望你开始觉得它们不那么神秘或令人生畏了。

monad 是与值（数据值）或操作（函数）相关联的一组狭窄的行为（“几个定律”要求）。范畴论产生了其他相关的行为约束，例如可以增强这种表示的能力的可折叠（Foldable）和可连接（Concatable）。

这组特定的行为改进了其他monad或者按monad约定的数据结构之间的协调/交互操作，使得结果更可预测。这些行为还提供了许多机会来抽象（转变为行为定义）某些通常会使我们的命令式代码混乱的逻辑（例如空值检查）。

Monads 当然不能解决我们在代码中可能遇到的所有问题，但我认为通过进一步探索它们有很多有趣的力量可以解锁。我希望本指南能激励您继续挖掘，也许在您的探索中，您会发现 Monio 库很有帮助。

重要问题

1. 环检测
2. 有多少个环
3. 其他

leetcode-1559 二维网格探测环形结构

关键词：并查集 find union，环检测

/**
 * @param {character[][]} grid
 * @return {boolean}
 */
var containsCycle = function(grid) {


    // 并查集-查询 得到任意元素的根结点位置
    function find(x, parent) {
        // 根结点
        if (parent[x] === x) {
            return x;
        } else {
            // 更新根节点
            // 路径压缩算法，可以让平均查找根节点的速度变快
            parent[x] = find(parent[x], parent);
            return parent[x]
        }
    }

    // 并查集-合并 合并任意两个元素为同一个集合，相当于树合并
    function union(x, y, parent) {
        let xRoot = find(x, parent);
        let yRoot = find(y, parent);

        // x y本来就属于同一个集合
        if (xRoot === yRoot) {
            return true;
        } else {
            // 把x的根结点挂载到y的根结点上
            // 挂载后x，y拥有同一个根节点
            parent[xRoot] = yRoot;
            return false;
        }
    }

    let m = grid.length;
    let n = grid[0].length;

    // 并查集，parent为不交集森林，每个元素都是唯一的一棵树，自己为根结点
    // 我们需要搜索二维数组，但是并查集是一维的不交集森林
    let parent = new Array(m * n).fill(0).map((_, len) => len);
    // 从左上角遍历到右下角，任意元素都更新到对应的树里面（任意树的各个元素拥有相同的字符）
    // 角标映射公式
    // k = i * n + j
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            // 上边
            // 上下字符一样，则执行一次合并
            if (i > 0 && grid[i][j] === grid[i - 1][j]) {
                if (union(i * n + j, (i - 1) * n + j, parent)) {
                    // 合并前两个元素的根就一样，说明就是同一个树上
                    // 由于我们的路径只能查找上边和左边的元素是否相同，碰到两个树的根相等，就说明环路已经形成
                    return true
                }
            }
            // 左边
            if (j > 0 && grid[i][j] === grid[i][j - 1]) {
                if (union(i * n + j, i * n + (j - 1), parent)) {
                    return true;
                }
            }
        }
    }

    return false

// let a = containCycle([
//     ["c","c","c","a"],
//     ["c","d","c","c"],
//     ["c","m","e","c"],
//     ["c","c","c","c"]
//   ]);
// let b = containCycle([
//     ["a","s","a","a"],
//     ["a","s","b","a"],
//     ["a","b","b","a"],
//     ["a","a","a","a"]
//   ])

// console.log(a, b)
};

后台

• fastify.js：高性能/现代化web服务。
• nest.js ：高效、可扩展web框架。底层可以用express/fastify，受angular启发

编辑器

• tiptap
• codemirror
• Lexical
• slatejs
• draftjs

最近有大佬开源了完全lua的neovim配置，昨天(2022/01/13)参照这个配置把自己的dotfile改了，很不错，推荐使用。

1. translate-shell
2. tldr: 一个man命令的替代，快速掌握unix命令用法
3. gtop: rust写的一个top命令替代，图形界面好用
4. tmux: 终端分形神器，现在已经离不开了，配合neovim使用，替换掉vscode
5. gitui: 图形化的git命令行

方法类型

黑盒测试

把软件当作一个黑盒子，从软件的行为而不是内部结构的角度来测试软件。现在大多数的测试手段（俗称点点点测试），都是黑盒测试，测试人员是不懂得软件内部结构的，只是测试这个软件的行为是否符合预期效果。

白盒测试

设计者可以看到软件系统的内部结构，并且使用软件的内部知识来指导测试数据及方法的选择。白盒测试需要测试人员了解软件的内部结构，从软件本身的结构角度来测试。java测试人员要读懂java代码，js测试人员要读懂js代码，并根据语音和结构来选择测试方式。

灰盒测试

介于黑盒和白盒之间

流程类型分类

手动测试

点点点测试，人工进行各种条件的触发，并观察软件的运行效果

自动化测试

使用软件代替人工，触发不同的场景。（API测试）

目的类型分类

单元测试

开发人员对自己编写的方法或函数进行软件测试。
单元测试是保证软件功能的第一步，前端的单元测试可以选择的有Mocha、Jest等

功能测试

测试人员对功能模块进行测试

集成测试

测试人员对几个集成在一起的功能模块进行测试。
前端有e2e端到端测试，还有一些自动化测试工具：Enzyme等

场景测试

具体业务场景流程测试

系统测试

对系统全功能测试。前后端应用一般有一个集成环境，用于测试。
对前端页面来说，系统集成测试，也可以用自动化的手段来触发，并使用window.performance来记录运行的流畅度。

alpha测试

测试人员对生产环境的软件进行系统、全面的测试

beta测试-公测

用户在生产环境测试

压力测试

验证软件在超过负载设计的情况下仍能返回正确的结果，没有崩溃。
压力测试一般是针对服务器进行的，服务器有QPS指标，每秒访问的量增大后看服务器是否崩溃。
前端页面一般没有压测的概念，前端的页面一般用首屏渲染时间、流畅度帧数FPS等来衡量。
大公司一般在上线前都会有压力测试，压力测试时看服务器的CPU、内存、硬盘等指标，同时看请求的响应速度有没有下降。

负载测试

测试软件在特定负载情况下能否正常工作。
通常不限制软件的吞吐量，在一定的负载情况下判断系统的瓶颈在哪。比如是缺内存，还是缺算力（CPU），还是硬盘容量不够用。

性能测试

测试软件的性能。比如聊天软件，通常服务器服务1000个人同时聊天，性能测试的时候就跑满甚至超出这个量，持续运行，看服务的性能指标有没有下降。比如消息处理速度、发送速度、查询速度等。

冒烟测试

开发人员对软件的功能做一个自我验证。开发每日构建版本，进行主功能测试，不用做深入的测试。这一步最好是用自动化手段来实现。

1. 每日构建
2. 针对每日构建自动执行主流程验证
3. 涉及到前端的可以用脚本来触发验证

回归测试

对一个新的版本，重新运行以往的测试用例，看看新版本和已知的版本相比是否有退化 (regression)

partial函数划分区域

生命游戏

今天做了这么个比较，发现还是原生js牛逼一点，这给了我极大的困惑。看来要专门找一下这方面的资料了！

chroma.js 色彩管理库，加深变淡

按16年去海能达报道的日子，目前已经工作整五年了。五年光阴啊！希望下一个五年，是一个新纪元！

官网：TAURI

• 如何评价tauri

主要是和electron比较，使用的Chromium + nodejs和Rust + webview是两种不同的跨平台方案。区别主要是不同平台的适配程度、打包大小、系统API调用能力以及语言上的区别。

• 你真的了解webview吗

作为原生API和JS之间的桥梁，挂载方法到window上给js使用，webview大致等于一个DOM渲染 + js运行时

• beta版本发布2021年初

因为是webview的，体积小、内存占用小，未来可以支持ios和android

• git

很快将支持ios和安卓

对我来说，目前最主要的是去做。

• react
• webpack
• Rxjs

原理

• react hook简介
• react hook原理-数组-链表
• react fiber架构

实践

• react hooks的几个灵魂问题

leetcode 133.cloneGraph
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

关键点 记录遍历过的节点，防止重复访问

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    const cloned = new Map();
    
    if (!node) return node;

    return bfs(node)

    function dfs(n) {
        // 已经克隆过，直接返回
        if (cloned.has(n)) return cloned.get(n);
        if (n) {
            const m = new Node(n.val, []);
            // 记录克隆事件
            cloned.set(n, m)
            for(const x of n.neighbors) {
                const y = dfs(x);
                if (y) {
                    m.neighbors.push(y);
                }
            }
            return m
        }
    }

    function bfs(n) {
        // 第一个节点先克隆
        const queue = [n];
        cloned.set(n, new Node(n.val, []))
        while(queue.length) {
            // 当前节点。宽度优先队列，优先访问邻接节点，然后增加克隆节点的对应邻接节点值
            const x = queue.shift();
            // 遍历到邻接节点y
            for(const y of x.neighbors) {
                // 没克隆过（没访问过）
                if (!cloned.has(y)) {
                    // 克隆（访问）
                    const z = new Node(y.val, [])
                    cloned.set(y, z);
                    // 入队（便于访问他的邻接节点）
                    queue.push(y);
                }
                // 当前节点增加邻接节点
                cloned.get(x).neighbors.push(cloned.get(y))
            }
        }

        return cloned.get(n)
    }

};

JS语言发展迅速，各种框架层出不穷，我们有这么一个形象的描述。

但我坚信，所有的高级描述都需要坚实的基础来夯实。因此我还是坚持学习基础，今天我们要学习编译原理和JSON的序列化和反序列化。

首先，我个人对编译原理也只是一种“还没开始学习或正在入门”的阶段，因此我讲这个的话，可能会有很多谬误，所以我就选择最简单的，找了一个架构图，我们来看着架构图来读我们的js代码。

这个图我们可以随时回来看一下，明确我们的工作已经做到哪一步了。

两个概念

• DSL(Domain Specific Language)：特定领域语言，典型的就像我们工作中用的最多的sql、xml、json、yaml、html等，他们都是针对特定的业务场景设计来使用的。
• GPL(General Purpose Language)：通用用途语言。我们的日常开发语言(js、ts、java、python等)都是GPL语言，是图灵完备的。

图灵完备：在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。---wikipedia

图灵机：由一些基本演算规则定义的一系列演算过程，可以模拟真实世界的任意演算过程。 --- 我的归纳

图灵机等价性：等价的计算模型有λ演算，生命游戏···

DSL有很多好处，比如JSON格式目前在我们用到的主流编程语言里面都得到了支持，实际上它就可以作为不同的语言、服务器之间通信的桥梁，至少比单纯的二进制或者文本要易懂得多。

如果要开发一门DSL语言，在前端场景下，可能有这么一些用法

• 将java bean自动转为typescript interface，这个dsl作为中间桥梁，即java -> dsl -> typescript。自动转换接口模型，让前后端省去对接的最后一步（复制、粘贴、转换模型）
• 简化对象描述。比如我们压缩字符串aaabbbccc为a2b2c2，或者像graphql(也是一种DSL)一样用。

词法解析

词法解析过程就是一个一个字符地把数据录入，当然，会根据一定的规则，忽略掉空格。

var name = "wander";
function sayHello(to) {
	console.log(name, ": Hello, ", to);
}

sayHello("JDT")

比如这一段代码，var，name，=，"wander"等你能看到的独立的一串字符都会被解析为token。就像我们自然语言里面可以划分主语、谓语、宾语等，是一个意思，这里实际上就是模拟我们的自然语言。

语法解析

有了一些符号，编译器就可以每次从数组里面取一个或一系列的token，看是否可以构成语义。在javascript语言环境下，语义就包括了我们的块级上下文（比如语法规则里面await暂时不能用于顶级模块），语句（条件控制语句、赋值语句、声明语句），表达式（运算符连接，产生运算结果，运算结果可以作为语句的一部分，比如const a = 1 + 1;整体是个赋值语句，但右侧为一个表达式）
等。

   {
  "type": "Program",
  "start": 0,
  "end": 100,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 20,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 4,
          "end": 19,
          "id": {
            "type": "Identifier",
            "start": 4,
            "end": 8,
            "name": "name"
          },
          "init": {
            "type": "Literal",
            "start": 11,
            "end": 19,
            "value": "wander",
            "raw": "\"wander\""
          }
        }
      ],
      "kind": "var"
    },
    {
      "type": "FunctionDeclaration",
      "start": 21,
      "end": 83,
      "id": {
        "type": "Identifier",
        "start": 30,
        "end": 38,
        "name": "sayHello"
      },
      "expression": false,
      "generator": false,
      "async": false,
      "params": [
        {
          "type": "Identifier",
          "start": 39,
          "end": 41,
          "name": "to"
        }
      ],
      "body": {
        "type": "BlockStatement",
        "start": 43,
        "end": 83,
        "body": [
          {
            "type": "ExpressionStatement",
            "start": 46,
            "end": 81,
            "expression": {
              "type": "CallExpression",
              "start": 46,
              "end": 80,
              "callee": {
                "type": "MemberExpression",
                "start": 46,
                "end": 57,
                "object": {
                  "type": "Identifier",
                  "start": 46,
                  "end": 53,
                  "name": "console"
                },
                "property": {
                  "type": "Identifier",
                  "start": 54,
                  "end": 57,
                  "name": "log"
                },
                "computed": false,
                "optional": false
              },
              "arguments": [
                {
                  "type": "Identifier",
                  "start": 58,
                  "end": 62,
                  "name": "name"
                },
                {
                  "type": "Literal",
                  "start": 64,
                  "end": 75,
                  "value": ": Hello, ",
                  "raw": "\": Hello, \""
                },
                {
                  "type": "Identifier",
                  "start": 77,
                  "end": 79,
                  "name": "to"
                }
              ],
              "optional": false
            }
          }
        ]
      }
    },
    {
      "type": "ExpressionStatement",
      "start": 85,
      "end": 100,
      "expression": {
        "type": "CallExpression",
        "start": 85,
        "end": 100,
        "callee": {
          "type": "Identifier",
          "start": 85,
          "end": 93,
          "name": "sayHello"
        },
        "arguments": [
          {
            "type": "Literal",
            "start": 94,
            "end": 99,
            "value": "JDT",
            "raw": "\"JDT\""
          }
        ],
        "optional": false
      }
    }
  ],
  "sourceType": "module"
}

可以看到，AST对不同的字符串，标记了不同的类型，甚至还包括了起始和终止位置。这个时候如果我们去修改AST的话，比如把name属性改为n属性（js代码压缩的原理也是在此），最后得到的代码就和我们最原始的不一样了（但结构还是一样的），像babel拿到AST之后，有很多插件就可以在这一步介入，比如修改class语法为prototype实现以适配更多的浏览器版本，这个时候我们拿到的最后结果，就连结构也和源代码不一样了。

语义分析

语法产生了AST，让我们知道一个源码的代码结构，但仅有结构也不足以让你的代码能够正常运行。比如

好了

这样一句话，人类可以根据语境上下文去判定它的主语，比如（您要我办的事）好了，（我的代码）好了（可以运行）。但计算机不行，计算机的上下文是在硬件资源里面的，必须要我们去设定一个软件变量的上下文。比如

// es5

a = 1; // 🙆‍♂️ 可以生效，语义上没有发现变量声明，但是发现了变量赋值，通过作用域链找到了上下文window，并默认把变量赋值的语义改为window.a = 1;

// es6+

a = 1; // 🙅‍♂️ 不可以生效，在es6的语义中，a的作用域内没有找到变量声明，就即时抛出错误，并不会挂载到window上

也就是说我们的很多js语法错误，都是在这个阶段产生的，编译器已经不认识你的意图了，比如上面的es6语境下，编译器可以识别到“你正在给一个作用域内没有发生过变量声明的变量进行赋值”，就可以抛出错误了。其实这个也好理解，变量声明会在栈内存内开辟一个空间用于存储这个变量，而变量赋值会去栈内存上寻找这个地址，找到了就赋值给它，就像是邮寄包裹，如果没有这个地址，你的包裹也就无从寄出。

IR

经过上面的那些步骤，生成的代码已经可以给机器识别了（词法合格，语法合格，带有语义），这个时候的代码，可以经过多次中间处理来产生不同的结果，一般来说从一门语言编译到另一门语言，会经过这一步，而且IR是可以多次进行的，你可以有不同的IR。比如

# WebAssembly技术，从一门语言编译到另一门语言
rust -> compiler -> wasm
c++ -> compiler -> wasm

# 理论上来说还可以这么玩
c -> compiler front -> compiler back -> IR -> IR -> ... -> IR -> JavaScript

编译器后端

编译器后端对合法的语法进行优化，比如我们的V8引擎里面的Turbo Fan，它可以把循环调用优化为机器码，直接给机器运行，这是一种IR结果，引擎的其他部分有的可以把JavaScript直接解释执行，有的可以把JavaScript代码编译为字节码，比直接解释执行更高效

实现JSON的序列化和反序列化

终于到了我的主题。以上的各个章节都属于笔记类型，下面开始我的输出。

语法规则

首先是要明确我们的词法，语法和语义，JSON的格式非常简单，支持对象嵌套、数组嵌套、基本的几种数据类型，不支持函数类型，key也要包裹双引号，字符串都使用双引号。

{
   "name": "wander",
   "age": 20,
   "male": true,
   "companies": [
        {"name": "hytera", years: 2 },
        {"name": "jdt", years: 2.7 }
    ],
   "desc": {
     "hobby": ["code", "cook", "fitness"],
     "website": "https://github.com/WanderHuang",
     "haircut": "short",
     "favico": "xxx"
    }
}

实现一个JSON.stringify

原生的stringify还支持replacer函数和indent空格缩进的参数，我们为了简单起见，先不支持这些，仅支持input -> JsonString

首先，我们有明确一下输入，原生的代码是可以支持对象和数组以外的数据类型的

JSON.stringify(true) // "true"
JSON.stringify(false) //  "false"
JSON.stringify(null) // "null"
JSON.stringify(undefined) // 没有输出
JSON.stringify(1) // "1"
JSON.stringify("2") // "\"2\""

除了字符串类型额外增加了转义字符之外，其他基本类型的值基本都是调用String(x)的结果(除了undefined类型不处理)

因此我们先来实现这些primitive值的转换。

// 字符串类型，直接增加一个转义字符，并输出
function string2String(obj) {
    return `\"${obj}\"`;
}

![js布尔](https://user-images.githubusercontent.com/18475942/126030779-4e3ba0c4-c84e-493f-8d1b-ba5c5e8f1443.png)


// 布尔类型，直接调用String，装饰为字符串
function boolean2String(obj) {
    return String(obj);
}

// 数字类型，直接调用String，装饰为字符串
function number2String(obj) {
    return String(obj);
}

然后我们来看对象的定义，首先对象由一对大括号包裹{}，其次，大括号内的数据为:分隔的键值对，其中键值对的键由字符串包裹，右边部分递归定义为JSON数据。

JsonObject ->
    Key -> JsonObject

然后就是语句分隔（一对合法的键值对分隔）使用,。

由于存在递归定义，我们实现的时候也需要递归调用

// 处理Json对象转为字符串，不同类型调用不同的处理器
function object2String(obj, str = "") {
    if (isPrimitive(obj, "string")) { // 字符串类型
      str += string2String(obj);
    } else if (isPrimitive(obj, "boolean")) { // 布尔类型
      str += boolean2String(obj);
    } else if (isPrimitive(obj, "number")) { // 数字类型
      str += number2String(obj);
    } else if (is(obj, "Object")) { // 对象类型
      str += "{";
      let cache = [];
      for (const [key, value] of Object.entries(obj)) {
        if (obj.hasOwnProperty(key)) {
          if (!is(value, "Function") && !is(value, "Undefined")) {
            let row = "";
            row += string2String(key);
            row += ":";
            row = object2String(value, row);
            cache.push(row);
          }
        }
      }
      if (cache.length) {
        str += cache.join(",");
      }
      str += "}";
    } else if (is(obj, "Array")) { // 数组类型
      str += array2String(obj);
    } else if (is(obj, "Null")) { // Null类型
      str += "null";
    } 
   
    // 其他类型直接略过不处理，比如我们之前讨论到的undefined类型

    return str;
  }

然后是数组。数组也是类似的递归调用，我们这里直接给答案

// 数组的递归实现
function array2String(obj) {
    let res = "[";
    for (const [i, o] of obj.entries()) {
      if (!is(o, "Undefined")) {
        res = object2String(o, res); // 递归处理每一个元素，每个元素都是JsonObject来处理
      } else {
        res += "null";
      }
      if (i !== obj.length - 1) {
        res += ",";
      }
    }

    res += "]";

    return res;
}

以上代码的辅助函数(比如is函数，判断是否是xxx类型)没有给出，可以自己实现。
最终就把数据直接通过object2string返回

function stringify(obj) {
  return object2String(obj);
}

小结

写一个见到的JSON.stringify没有想象中那么难，主要要理清楚词法和语法规则，然后就是递归地处理每一种数据类型。

测试代码

var obj = {
  name: "wander",
  age: 20,
  male: true,
  companies: [
    { name: "hytera", years: 2 },
    { name: "jdt", years: 2.7 },
  ],
  desc: {
    hobby: ["code", , "cook", "fitness"],
    website: "https://github.com/WanderHuang",
    haircut: "short",
    favico: "xxx",
  },
  x: null,
  y: undefined,
  say: function () {
    console.log("u can't c this function");
  },
};

var arr = [1, 2, null, undefined, obj, [1, 2]]

// 转换对象
console.log(stringify(obj));
console.log(JSON.stringify(obj));
console.log(JSON.parse(stringify(obj)));

// 转换数组
console.log(stringify(arr));
console.log(JSON.stringify(arr));
console.log(JSON.parse(stringify(arr)));

// 转换字符串
console.log(stringify("123"))

// 转换数字
console.log(stringify(123))

// 转换空值
console.log(stringify(null))
console.log(stringify(undefined))

// 转换函数
console.log(stringify(function call() {console.log("call function")}))

这里由于我是一个简单的实现，默认数据来源和JSON.stringify一致，只需要去实现序列化就行了。实际上如果你要实现编译器，读入一个.json文件，再输出转换的结果，你就需要逐个字符地去读，然后给对应的每种类型赋值。

好在JSON.parse有点类似于这种模式，我们来看一下吧。

实现一个JSON.parse

我们实现JSON.parse，是可以通过生成token的方式，不过json数据本身就只有几种数据类型，直接输出也可以。

首先我们需要厘清最基本的一些状态

1. 当前读到哪个字符，不同的方法需要同一个全局i变量
2. 空格在JSON内是语法无关的，因此在词法和语法外的空格，我们应该可以去掉(i++)，合理的空格至少有" "和\n
3. 对象和数组的分隔符，要可以跳过,
4. 不同类型可以用不同的方法来处理

先来实现一个全局环境

// 转换字符串
function parse(str) {
  // 1. 强转为字符串，比如parse(null) => "null"，让方法能够对不同类型输出
  str = String(str);
  // 2. 全局变量，当前读到第几个数字
  let i = 0;
  let len = str.length;
  // 最外层的数据格式
  let top;

  // 3. 去掉空格 
  if (i < len) {
    filterSpace();
  }

  // 4. 空指针判定
  if (i < len) {
    if (str[i] === "{") { // 对象
      top = parseObject();
    } else if (str[i] === "[") { // 数组
      top = parseArray();
    } else { // 字符串
      top = parseString();
    }
  }

  return top;
}

以上方法对第一层，也就是传入的数据做了解析。当然4.步应该可以用while替换

然后我们来实现一些辅助函数（空格过滤）

/** 过滤空格符号 */
function filterSpace() {
  while (i < len && (str[i] === " " || str[i] === "\n")) {
    i++;
  }
}

/** 过滤逗号 */
function filterColon() {
  while (str[i] === ",") {
    i++;
  }
}

实现基本数据的转换

1. 注意到布尔函数和数字是由String(x)得到的，我们可以用对应的方式转回来。数字直接用Number(x)，布尔函数用true|false直接转
2. 对象以{开头，以}结尾，递归调用
3. 数组以[开头，以]结尾，递归调用
4. 任意token直接至少是可以过滤空格的，使用filterSpace方法
5. 任意字符串以"包裹

字符串类型

/** 转换String类型 */
function parseString() {
  let res = "";
  if (str[i] === '"') {
    i++;
  }
  // char[i] => String
  // 这里有个坑，那就是转义字符在这里要提前结束掉字符串匹配，目前还没有处理。比如`'"' === "\""`为true
  while (str[i] !== '"' && i < len) {
    res += str[i++];
  }
  i++;

  return res;
}

数字类型

function parseNumber() {
    let x = i;
    // 语法条件，没有碰到结尾符号，就一直算作当前的token
    while (
      i < len &&
      str[i] !== "," &&
      str[i] !== " " &&
      str[i] !== "}" &&
      str[i] !== "]"
    ) {
      i++;
    }
    let y = i;
    // 取巧的方式转换为数字
    return Number(str.substring(x, y)); 
  }

数字类型可用的解析规则

对象转换

/** 转换对象 */
function parseObject() {
  // 1. 返回值
  let obj = {};
  // 2.起始判定
  if (str[i] === "{") {
    i++;
  }

  // 3. 没有到语法结束，则一直读取
  while (str[i] !== "}" && i < len) {
    filterSpace(); // 空格过滤
    // 4. 对象的键。也有"\""的坑需要填
    if (str[i] === '"') {
      i++;
    }

    let key = parseString();
    filterSpace();
    // 5. 键值对分隔符
    if (str[i] === ":") {
      i++;
    }
    filterSpace();
    // 6. 值读取。前面说到值也是递归定义的JsonObject，因此下面的一段都是递归调用
    if (str[i] === '"') { // 字符串
      obj[key] = parseString();
    } else if (str.substring(i, i + 4) === "true") { // "true"
      obj[key] = true;
      i += 4;
    } else if (str.substring(i, i + 5) === "false") { // "false"
      obj[key] = false;
      i += 5;
    } else if (str[i] === "{") { // 对象
      obj[key] = parseObject();
    } else if (str[i] === "[") { // 数组
      obj[key] = parseArray();
    } else if (
      str[i] === "-" ||
      str[i] === "+" ||
      (Number(str[i]) >= 0 && Number(str[i]) <= 9)
    ) {  // 数字
      obj[key] = parseNumber();
    }
    // 语法无关字符过滤
    filterSpace();
    filterColon();
    filterSpace();
  }

  filterSpace();
  filterColon();
  filterSpace();
  if (str[i] === "}") { // 对象结束
    i++;
  }

  return obj;
}

数组转换，和对象一样，进行递归调用

/** 数组类型解析 */
function parseArray() {
    // 1. 数组开始
    if (str[i] === "[") {
      i++;
    }

    let res = [];
    filterSpace();
    // 2. 语法环境没有结束
    while (str[i] !== "]" && i < len) {
      filterSpace();
      if (str[i] === ",")  { // 空字符
         res.push();
         i++;  
      } else if (str[i] === '"') { // 字符串
        res.push(parseString());
      } else if (str.substring(i, i + 4) === "true") { // "true"
        res.push(true);
      } else if (str.substring(i, i + 5) === "false") { // "false"
        res.push(false);
      } else if (str[i] === "{") { // 对象
        res.push(parseObject());
      } else if (str[i] === "[") { // 数组
        res.push(parseArray());
      } else if (
        str[i] === "-" ||
        str[i] === "+" ||
        (Number(str[i]) >= 0 && Number(str[i]) <= 9)
      ) { // 数字
        res.push(parseNumber());
      }
    }

    filterSpace();
    // 3. 语法环境结束
    if (str[i] === "]") {
      i++
    }

    return res;
}

小结

核心要点

1. 逐个字符读取
2. 维护一个单独的语境的开始和结束
3. 对不同的语境调用不同的处理方法进行转换

测试代码

var obj = {
    name: "wander",
    age: 20,
    male: true,
    companies: [
        { name: "hytera", years: 2 },
        { name: "jdt", years: 2.7 }
    ],
    desc: {

      hobby: ["code", "cook", "fitness"],
      website: "https://github.com/WanderHuang",
      haircut: "short",
      favico: "xxx"

    }
}

var str = JSON.stringify(obj);

var o = parse(str) // 用我们自己写的parse，可以把原生的JSON.stringify序列化的数据解析出来

console.log(str)
console.log(o)

console.log(parse(true), parse(false), parse(1), parse(" t.")) // 它也可以很好地解析数字类型、布尔类型、字符串类型

后记

之前有调研过JSON Schema的格式，其实这也是一种DSL，属于对JSON的一种加强，想要达到的效果是从JSON 或者JSON Schema格式读取token然后转为typescript的interface类型。不过当时由于一些原因搁置了，下半年这个可以是一个研究的方向。目标就是让前端的模板代码解放人手写。当然前端本身会有一些自己的类型需要处理，如果做的好，也可以给前端自己用。

1. in quest to / lifelong learner / keep up with / date with

Some of the top developers are lifelong learners. They are always in the quest to learn new skills and keep themselves up to date with the current trends.

一些顶尖的开发人员是终身学习者。他们一直在寻求学习新技能并保持与时俱进的最新动态。

订阅发布的优雅实现模式-架构设计
tapable
核心原理、运行流程
webpack源码

太阳照常升起

妈

mao/cn/dang。最善良和赤诚的初心，在非尽头（sulian）受震撼、美好的世界破碎。(年轻人-阿廖沙和喀秋莎都在边境-中苏-死去)。从火车产子开始，逐步进入疯癫状态，并在世人眼见之外构建了一个乌托邦(洞穴)，最后自杀表明时代结束了，乌托邦内也被行了苟且之事，梦境落幕。资本(唐妻、天鹅绒)开始进入底层(李东方、草纸)。妈给儿子造了一个乌托邦，在儿子发现那天，她自杀了，儿子毁了乌托邦，也毁了自己。

李东方

农民。东方就是太阳升起的地方，照常升起表明这些日子啥都没有变，李东方十年后还是啥也不知道，历史停止。魔幻化出生代表最开始是有希望的。

李叔

军队。拥护和崇拜（说妈把婴儿一个人带到村里 不可思议） mao/dang

梁老师

知识分子，软弱代表。环境把人逼疯、自杀。

唐老师

知识分子，圆滑代表。在环境中得过且过，随波逐流，内心饱含对真实世界的排斥。搞破鞋、打猎（老婆出轨、枪杀农民）

林大夫

破鞋代表（皮鞋刚开始不能穿、唐老师搞大一号）不关心政治，或者说是被政治逼到回归私欲，纵欲，反政治代表

学校领导

知识分子，堕落代表。只会歌功颂德，甩锅，伟光正，奴颜

黑脸女

压抑的女性代表。每天过政治生活，没有个人私欲，嫉妒压抑下人格扭曲

打猎小朋友们

代表十年间毁掉的一代，只会爬树偷鸟蛋，回到原始社会

唐妻

女知识分子代表，独立人格，不关心政治和军队，只关心生活（怕枪声、穿着得体、喂野鸡、私欲放纵-由时代逼迫）

算命的

上帝视角，世界变成这个样子，是人们自作自受，人格、家庭、社会是自己放弃自己。

李不空

实际是空的，但是叫不空。表明是人们想要证明存在，但并不存在的价值，比如“最可爱的人”（政治口号，让女人们去爱这些军人，形成畸形的婚姻：崇拜和遗弃。疯妈和唐妻），比如和苏联的感情（苏联人检查所有信件，意味着不信任），越是想要证明存在的价值，它越没有价值，人们都成了它的牺牲品。

场景

结婚

大跃进开始、欢乐进入共产主义

火车生孩

农民被资本主义抛弃，被社会主义拾起，起名东方，寓意希望。一切的出发点是好的

疯妈回村

代表社会主义开始探索 受到军队拥护 逐步政治化

鱼鞋

原始人性，鞋丢了 人疯了

砸算盘瓷器

捯四旧、反传统

洞穴房

乌托邦、一个喷嚏就破碎，mao想象中的**，在这乌托邦里最后行苟且之事，表面一切，十几年的光阴，什么都没有变过，被压抑的的情绪总有一天会爆发

黄鹤楼

对传统和美好记忆的追思，空悠悠，逝去的不会再回来

红土地

红色(dang)代表什么不言而喻，赤脚在上面走，表明要鱼水相亲

河

虚幻的世界。儿子在游泳，妈在上面刨，“大海航行靠舵手”，上门有个舵手，下面的人就自由自在。但这一切是想象中的，因为舵手用的是锄头，但没有打到儿子身上。

漂浮的衣物

多次出现，整洁的衣物代表权威仍然在(tian an men, bing guan)，但在水里，会逐步远去，最终唐老师（知识分子）崩了小队长（农），旧世界彻底落幕

天鹅绒

新奇和流行（去北京找天鹅绒）的世界，资本主义（外地才有）的世界、私欲（女性的肚皮）的世界。小队长拿了锦旗以为是天鹅绒，表明绝大多数农min知识水平、认知都被这十几年禁锢了，愚昧和蒙蔽的日子将永远下去，于是唐老师开抢了。

东南西北

寓意整个**，其中北，用的是gugong，寓意很明确，朋友告诉唐老师的话，寓意领导对这十几年的定性（弯路、自己犯的错）。南部是愚昧（乡村）、西部是激进（石油）、东部是小资（学校）、北部是政治（故宫）。

春夏秋冬

寒来暑往，十几年，年轻人的信念、青春、理想一步步消逝

前端优化方案

针对每个问题的性能分析方案

卡顿、不流畅

页面运行时用户觉得卡顿、不流畅，原因有很多，根本原因

1. javascript运行时间太长阻塞ui渲染
2. UI重排重绘太多

排查方法

1. 审查电脑配置。CPU -> 决定脚本运行速度。Memory -> 决定运行时堆内存(对象、数组、游离字符串)分配
2. 开发者工具需要关注
   2.1 Memory 内存占用。一般的web应用100MB就已经很高了，500MB算是顶天
   2.2 Performance 性能考察。可以定时检测页面性能，顶部有选项可以模拟降低CPU执行效率或者网络状况
   2.3 Application 应用。关注localStorage、sessionStoage、cookie等数据存量(安全性同理)
   2.4 Network 网络。关注每个请求的等待时间和响应时间，数据量大小，Gzip等等
3. 其中最重要的是Performance。里面有很多指标可以考察
   3.1 FP first paint 首次渲染
   3.2 FCP first contentful paint 内容开始渲染
   3.3 LCP largest contentful paint 最大内容渲染量
   3.4 DCL DOMContent Loaded Event dom数据加载完成事件
   3.5 Network 每个时段发生了什么网络事件
   3.6 Frames 页面帧数
   3.7 Interactions 交互、动画
   3.8 Main 主线程事件
   3.9 GPU 显卡效率
   3.10 JS Heap 堆内存
   3.11 Documents 文档
   3.12 Nodes 节点
   3.13 Listeners 监听器
   3.14 GPU Memory 显寸
   3.15 Summary 总结。内有脚本时间，渲染时间，绘制时间，空闲时间等
   3.16 Bottem-up 可以看到脚本的各个方法执行时间(调用栈)
   3.17 Call Tree 函数调用链
   3.18 Event Log 事件
4. 除了上述的方式，我们也可以自定义对一个方法、脚本的检测

// 堆内存限制
performance.memory.jsHeapSizeLimit
// 总占用堆内存
performance.memory.totalJSHeapSize
// 存活堆内存
performance.memory.usedJSHeapSize
// 从系统运行到当前的时间
performance.now()
// 各个数据的时间线, 文档加载完成、事件完成、网络请求耗时等等，都可以计算
performance.timing

// 可以前后加performance.now()，计算方法执行时间 单位为ms
let start = performance.now();
run()
console.log(performance.now() - start);

5. 从业务上思考有一些影响运行速度的因素
   5.1 数据量很大。其实大量的数据，如果是公式化的处理，比如图片的数据处理(Buffer)，因为浏览器本身有优化，不会有太大的耗时。但是一般我们的业务代码都是对象数组，就可能存在大量耗时操作(对象读写耗时)
   5.2 循环嵌套。这就要用到算法分析的思路了，n和n^2是不一样的效率，应该尽量减少循环
   5.3 递归嵌套。递归会有更多的函数栈开辟、保存和恢复的操作，本身是比循环要慢一些，可以尝试优化为循环。
   5.4 同步操作。一些不相关的操作，如果不是非常必要，可以拆分为异步执行的，充分利用setTimeout和Promise机制
   5.5 渲染阻塞。DOM操作如果大量在对元素进行增减、样式变更，会触发大量的重排重绘，造成页面卡顿。
   5.6 网络请求。网络请求太多也会影响加载，尽量把数据放在页面，并利用ajax发起异步请求，减少请求，对请求做缓存、gzip等等方式可以减少请求带来的影响
   5.7 重复操作。一般这是由不当操作造成的，比如react频繁重绘
6. 除了上述的方案，我们还可以记录用户客户端的信息，这样避免了每次线上问题都要现场定位。
   6.1 可以用上面我们提到的performance来上报。
   6.2 定义脚本，全局捕获错误、内存占用量，定时上报
   6.3 console打印日志，让客户导出发送给我们
   6.4 日志存储到indexDB，长久保存，方便排查
   6.5 制作浏览器插件，帮助分析页面状态，上报服务器(插件是另外的线程)

解决方案
上面已经提及了的问题发声方式，基本都有对应的解决方案。另外还有一些方案可以采用

1. lighthouse 谷歌出的页面性能分析工具
2. react性能分析
3. DOM内容优化
4. 多级缓存方案。可以利用的缓存有：LRU内存内缓存方案、localStorag、sessionStorage、indexDB、nginx cache等等
5. GPU加速。方案有利用transform对单个元素进行动画运算、canvas利用等

彩色版本

文字版本

// 堆排序算法
// 1. 堆分为最大堆，最小堆，根据顶层元素来划分
// 2. 堆也是一个二叉树

// ====================
// === heap maximum ===
// ====================

const source = [5, 1, 7, 8, 3, 2, 0, 9, 6, 4];

//             5
//         /       \
//        1         7
//      /   \      / \
//     8     [3]  2   0
//    / \   /
//   9  6  4

// 上面明显不是一个最大堆，最大堆特性
// 1. 顶层元素为最大啊
// 2. 两个子元素都比父节点小
// 这里的[3]是一个特殊元素，在他以前的元素都存在子节点，在他之后的元素都没有子节点
// 注意，二叉树在数组里面的序号要保持为

//            0
//         /    \
//        1      2
//      /   \   / \
//     3     4  5  6
//    / \   /
//   7  8  9
//  === 第i个元素关系式
// 1. 左节点 2 * i + 1
// 2. 右节点 2 * i + 2

function swap(arr, i, j) {
  arr[i] = arr[i] ^ arr[j];
  arr[j] = arr[j] ^ arr[i];
  arr[i] = arr[i] ^ arr[j];
}

/**
 * 构建一个最大堆其实分步骤
 * 1. 由于叶子节点无需进行父子交换，因此，可以从第一个没有叶子节点的元素开始，依次往前遍历
 * 2. 每一次遍历就是调整当前元素的父子元素大小关系的过程
 * @param {*} arr
 * @param {*} start
 */
function maxHeapFromArray(arr) {
  const length = arr.length;
  let i = Math.floor(arr.length / 2);
  for (; i >= 0; i -= 1) {
    step();
  }

  /**
   * 一次遍历，实际上是从i节点开始，依次考察他的子节点
   * 存在比arr[currentIndex]大值的数，会被交换到arr[currentIndex]
   * 因此执行一次step后，i为根的二叉树里面，arr[i]是最大值
   * 这样就能保证，递归到顶层时，从上往下能满足最大堆的特性
   * @param {*} currentIndex 当前节点缓存
   */
  function step() {
    let currentIndex = i;
    // 缓存当前值
    const value = arr[currentIndex];
    // left 2 * i + 1;
    // right 2 * i + 2;
    // 依次下沉考察节点值，从左节点开始
    for (let j = currentIndex * 2 + 1; j < length; j = j * 2 + 1) {
      // 存在右节点，且右节点大于左节点
      if (j + 1 < length && arr[j] < arr[j + 1]) {
        j++;
      }

      // 子节点比父节点大
      // 子节点数据上浮，currentIndex下沉(currentIndex实际上代表最初那个数)
      if (arr[j] > value) {
        arr[currentIndex] = arr[j];
        currentIndex = j;
      } else {
        // 父节点比子节点大，跳出循环
        break;
      }
    }

    // currentIndex实际上被交换到最小位置
    arr[currentIndex] = value;
  }

  return arr;
}

console.log(maxHeapFromArray(source));

// input  [5, 1, 7, 8, 3, 2, 0, 9, 6, 4];
// output [9, 8, 7, 6, 4, 2, 0, 1, 5, 3];

// |                5          |                |                9            |
// |            /     \        |                |             /     \         |
// |           1       7       |                |           8        7        |
// |         /   \    / \      |      ===>      |         /   \     / \       |
// |        8     3  2  0      |                |        6      4  2   0      |
// |       / \   /             |                |      /  \    /              |
// |      9  6  4              |                |     1    5  3               |

• professional wods 专业词汇
• syntactic 句法语法
  There are two syntactic forms(句法形式) for creating an array
• expression 表达式
  A repeat expression [x; N], which produces an array with N copies of x. The type of x must be 'Copy'
• inclusive 包括的
  [0, 10] means 0(inclusive) to 10(inclusive)
• oop: encapsulation abstraction inheritance polymorphism.封装 抽象 继承 多态
• stream processing 流处理 一种开发范式
• substitute 替代、代换。 名词：substitution，代换式。比如函数式编程内的可替换性
• oriented 以...为方向的. people-oriented 以人为本的、object-oriented 面向对象的，去掉短杠表示名词意义
• research and development 研发。research 研究、development 开发、R & D缩写、software development 软件开发
• phone screen 电话面试
• work overtime 加班。名词状态overtime work。overtime 超过规定时间之外的时间
• system design 系统设计
• Circular Queue 循环队列

函子

函子是范畴论的一个概念，理解函子，先要理解范畴。基本的概念我们从wiki获得，然后再加上我（非数学专业/计算机专业毕业）的理解。

范畴论

范畴论（英语：Category theory）是数学的一门学科，以抽象的方法处理数学概念，将这些概念形式化成一组组的“对象”及“态射”。数学中许多重要的领域可以形式化为范畴。使用范畴论可以令这些领域中许多难理解、难捉摸的数学结论更容易叙述证明。

范畴最容易理解的一个例子为集合范畴，其对象为集合，态射为集合间的函数。但需注意，范畴的对象不一定要是集合，态射也不一定要是函数；一个数学概念若可以找到一种方法，以符合对象及态射的定义，则可形成一个有效的范畴，且所有在范畴论中导出的结论都可应用在这个数学概念之上。

注意几点：

1. 范畴论基本等于对象 + 态射。
2. 态射大部分为映射函数，但态射不等于函数。
3. 可以用形象化的例子来解释范畴：集合为范畴对象，集合间映射为范畴态射。

函子 Functor

在范畴论中，函子是范畴间的一类映射。函子也可以解释为小范畴范畴内的态射。

函子首先现身于代数拓扑学，其中拓扑空间的连续映射给出相应的代数对象（如基本群、同调群或上同调群）的代数同态。在当代数学中，函子被用来描述各种范畴间的关系。“函子”（英文：Functor）一词借自哲学家鲁道夫·卡尔纳普的用语[1]。卡尔纳普使用“函子”这一词和函数之间的相关来类比谓词和性质之间的相关[2]。对卡尔纳普而言，不同于当代范畴论的用法，函子是个语言学的词汇。对范畴论者来说，函子则是个特别类型的函数。

注意几点

1. 函子是范畴间的一类映射
2. 函子可以理解为一个特殊的函数

我们再来看一下数学定义：

明确几点数学定义

1. 函子把数据从C范畴映射到D范畴
2. C范畴内的数据态射（函数）f可以被映射到D范畴上
3. 被映射的态射满足条件：id函数自等；组合函数结合律
4. id函数满足后意为自函子
5. 组合函数：g . f = x => g(f(x))

再看一下haskell中的定义

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$) :: a -> f b -> f a

haskell的函子是一个类，并带有两个方法

1. fmap：得到一个映射关系a -> b，和一个函子f a，输出一个函子f b
2. <$：这是haskell的中缀表达式，用前缀表达式表示就是id函数，表示函子值为a(f a)，并接受一个函子f b，返回f a

也就是说，如果我们把代码放到范畴下解决，所有的数据都统一为函子的话，函子和函子之间可以使用fmap和id函数通信。当然，我们需要给函子扩展更多的函数才能满足程序中奇奇怪怪的需求，但这不在本文讨论中。我们只关注函子。

函子的定律haskell实现

id :: a -> a
fmap id = id
fmap (f . g) = fmap f . fmap g

JavaScript实现

直接上代码

// Just为我们的一个“函子”
function Just(value) {
    return {
        value, // 保存值
        // 值为基本数据，支持映射到范畴（Just）内其他元素
        // addOne = x => x + 1
        // 比如 Just(1).map(addOne)    -> Just(2)
        map: function map(fn) {
            return Just(fn(value))
        },
        // 值为基本数据，支持映射到自身范畴
        // 比如 Just(1).flatMap(addOne)    -> 2
        flatMap: function flatMap(fn) {
            return fn(value);  
        },
        // 值为函数（映射），支持映射到范畴（Just）内的其他元素
        // 比如Just((x) => x + 1).fmap(Just(2))     -> Just(3)
        fmap: function fmap(just) { // 函子 Just(compose(b, a)) = composeJust(Just(b), Just(a));
            return just.map(value)
        }
    }
}

实现了fmap之后，我们要实现复合函数compose

// compound 复合函数 属于Number范畴
function compose(g, f) {
    return x => g(f(x))
}

// compound 复合函数  属于Just范畴
function composeJust(Justg, Justf) {
    return jx => Justg.fmap(Justf.fmap(jx))
}