第一天：重新开始学写代码

方：那我们开始了。还记得函数式的约定吗？

学生：记得，数据不可变。

方：好的，那么我估计你现在应该不会写代码了。

学生：？

方：不信？我跟你出道题。请遍历 array = ['a','b','c'] 打印出每一项的值。用 JS 写吧。

学生：简单啊

for(let i = 0; i< array.length; i++){
  console.log(array[i])
}

方：你这么快就忘了约定？数据不可变！

学生：我没改 array 啊

方：i++ 改了 i 的值啊

学生：啊，这也算啊

方：没错。不写 i++，你再来回答一次

学生：那我用 for in

for(let key in array){
  console.log(array[key])
}

方：有点鸡贼，先不说你遍历的顺序无法保证，这个 key 依然在变化哦，key 一开始等于 0 后来等于 1 最后等于 2。再想想吧。

学生：我还有一招：

array.forEach(item => console.log(item))

方：总算摸到边了，这次「你」确实没有改变数据的值

学生：那就是我答对了吗？

方：还差一点。array.forEach 是 JS 内置的数组接口，JS 内部的 C++ 实现很有可能还是用到了 for 循环？你能自己写一个 forEach 吗？满足以下用法

forEach(array, item => console.log(item))

学生：不用数组的 forEach 自己写 forEach 吗……

方：嗯

学生：能用 while 吗

方：不能，while 不也要 i++ 嘛，跟 for 没区别

学生：那用递归？

方：试试

学生：好

let array = ['a','b','c']
let forEach = (array, fn) => {
  if(array.length === 0) return
  fn(array[0])
  forEach(array.slice(1), fn)
}
forEach(array, item => console.log(item))

方：不错，这次你遵守了约定：「数据不可变」。我想知道为什么你最后才给出这种写法呢？

学生：以前有人告诉我尽量不要用递归。

方：我猜猜，那个人是写 JS 或 Java 的？

学生：嗯，而不止一个人这么说。

方：他们给出的理由是什么？

学生：容易「栈溢出」，而且「开销大」「浪费内存」

方：说得不错，但这只是他们的一面之词。我们先来说说「栈溢出」吧。「栈溢出」的前提是得先有「调用栈 callstack」对吧。

学生：当然

方：那你知不道有些语言根本就没有 callstack 呢，比如 Haskell 就没有 callstack，它用图代替了栈。

学生：闻所未闻……

方：另外，如果我们把递归改写为尾递归，甚至循环，就基本可以消除「栈溢出」

学生：可是如果把递归改写成循环，那还不如直接写循环吧？

方：你很敏锐地发现了我的逻辑漏洞嘛，这里的「尾递归变循环」是「编译器」自动实现的！也就是说程序员专心写代码，编译器专心搞性能优化。

学生：什么是「尾递归」？

方：这个我明天再讲，今天我先把你对递归的不信任推翻再说。现在你只需要知道，把递归改写为尾递归，再配合恰当的编译器，「栈溢出」基本不成问题。

学生：JS 或 Java 的编译器不行吗？

方：问得好。实际上编译器和程序员的写法是相辅相成的，不是恒定的。我先问问你

1. 程序员应该记住性能好的代码，就算放弃可读性也值
2. 程序员以可读性为优先，让编译器想办法优化性能

这两个观点你支持哪个？

学生：我不确定，难道不应该尽量挑性能好的代码写吗？

方：哈哈，你以为性能好的代码就是性能好的吗？

学生：这是什么意思？

第二天：递归 & 尾递归

学生：早啊方，今天讲什么？

方：今天讲递归和尾递归吧

学生：数据不可变什么时候讲呀？

方：不急，数据不可变是贯穿始终的，不用特别去讲它。

学生：哦……

方：我先写一个递归形式的阶乘：

f = n => {
  if(n<=1) {
    return 1
  } else {
    return n * f(n-1)
  } 
}

然后用「代入法」来计算一下 f(4)：

f(4) 
= 4 * f(3)
= 4 * (3 * f(2))
= 4 * (3 * (2 * f(1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

注意计算的「形状」，看起来像是一个大于号（>）：

方：先递进，后回归，这就是递归，英文叫做 recursion。

学生：原来还可以这么理解递归。那我可不可以认为：「递」是调用栈压栈的过程，「归」是弹栈的过程。

方：可以，但不够全面，我之前说过，有些语言是没有调用栈的，所以压栈弹栈只是递归的一种实现方式而已，尽管这种方式很主流。

学生：那伪递归是怎么回事呢？

方：还是先给例子，比阶乘还简单

print = (n) => {
  if(n===0){return}
  console.log(n)
  return print(n-1) // 此处 return 可以省略不写，因为没有返回值
}

然后使用「代入法」来计算 print(4)：

print(4)
= print(3) 
= print(2) 
= print(1) 
= 结束 

注意这次计算的形状是「一条直线」：

学生：这也是递归吧？

方：是也不是。

学生：怎么讲？

方：如果你问的是中文概念「递归」，那么这次计算没有「递」和「归」的过程，所以它不算递归。

学生：确实没有先递再归。

方：但如果你问的是递归的英文概念「recursion」，其中文意思是「重现」，那这次计算确实是在不断重现 print 调用，所以它是递归。

学生：你的意思是 recursion 翻译为递归是有问题的？应该翻译为「重现」？

方：我不敢这么说。但为了准确起见，我们用「递归」来表示计算形状为大于号的 recursion，用「尾递归」来表示计算形状为直线的 recursion。「尾递归」的代码特征是 recursion 出现在代码的最后一句（即尾位）

学生：原来是尾巴的「尾」，我还以为是伪装的「伪」。

方：怪我没说清楚咯？

学生：那为什么 return n * f(n-1) 不是尾递归呢？ f(n-1) 不也是写在最后一句吗？

方：因为调用完 f(n-1) 还要将其结果与 n 相乘，所以 f(n-1) 是倒数第二步，不是最后一步，算不得尾递归。

学生：原来如此。那「尾递归」的优点就是不用「归」吗？

方：可以这么理解。

学生：可是，尾递归版的阶乘怎么写？我想不出来

方：多问我你就能写出来了，我先写一个给你看看

f = (n, result = 1) =>
  n > 1 ? f(n-1, result * n) : result

代入运行一下：

f(4) 
= f(3, 4)
= f(2,12)
= f(1,24)
= 24

看，这条线直不直？

学生：啊，你为了不「归」，居然把上一步的计算结果，当做参数，传给了下一次调用

方：对。

学生：我怎么没想到。

方：以后你就会想到了。

学生：那如果是复杂的递归呢？能不能写成尾递归？比如斐波那契：

fib = (n) =>
  n === 0 ? 0 :
  n === 1 ? 1 :
          fib(n-1) + fib(n-2)

求 fib(4) 的过程是这样：

fib(4) 
= f(3) + f(2) // 简写为 f
= (f(2) + f(1)) + (f(1) + f(0))
= ((f(1) + f(0)) + f(1)) + (f(1) + f(0))
= ((f(1) + f(0)) + f(1)) + (1 + 0)
= ((f(1) + f(0)) + f(1)) + 1
= ((f(1) + f(0)) + 1) + 1
= ((1 + 0) + 1) + 1
= (1 + 1) + 1
= 2 + 1
= 3

这种递归不好写成尾递归吧？

方：稍微动点脑不就可以了嘛：

fib = (n, prevResult = 0, result = 1) =>
  n === 0 ? prevResult :
  n === 1 ? result :
    fib(n - 1, result, prevResult + result)

求一下 fib(4) 的值：

fib(4)
= fib(3, 1, 1)
= fib(2, 1, 2)
= fib(1, 2, 3)
= 3

这不就妥了？

学生：好家伙！你把前两次的值，都当作参数，传给了下一次的调用了。而你的 n 只是用来计数的，当 n 等于 1 你就返回上一次的结果！

方：对！是不是很简单？

学生：那……那……那快排有没有尾递归写法？

方：有是有，但我怕你看不懂，所以我先把你昨天写的「递归版」快排放在这里：

/*1*/ quickSort = (array) => {
/*2*/   if(array.length <= 1) {return array}
/*3*/   let [pivot, ...rest] = array
/*4*/   let small = rest.filter(i => i<=pivot)
/*5*/   let big = rest.filter(i => i>pivot)
/*6*/   return [...quickSort(small), pivot, ...quickSort(big) ]
/*7*/ }

要改写成「尾递归」存在两个问题：

1. quickSort(small) 之后必须要回头执行 quickSort(big)
2. quickSort(big) 执行完了之后必须要回头把 quickSort(small)、pivot、quickSort(big)拼接起来

对吧？

学生：是呀，看起来不可能把结果提前算出来，传给下一次函数调用，我不信你这次还能改成尾递归

方：那就不提前算出结果，不就结了

学生：什么叫做不提前算出结果？

方：直接看代码吧：

/*1*/ qs = (array, next) => {
/*2*/     if(array.length <= 1) { return next(array)}
/*3*/     const [pivot, ...rest] = array
/*4*/     const small = rest.filter(i=>i<=pivot)
/*5*/     const big = rest.filter(i=>i>pivot)
/*6*/     qs(small, (sortedSmall)=>{
/*7*/         qs(big, (sortedBig)=>{
/*8*/             next([...sortedSmall, pivot, ...sortedBig])
             })
         })
     }

qs([1,10,5,2,7,3,8,4,9,6], (result)=>{
    console.log(result) 
})

// 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

前面 5 行没有变化，你主要看第 6 ~ 8 行。

学生：好家伙，你把原本的

/*4*/ let small = rest.filter(i => i<=pivot)
/*5*/ let big = rest.filter(i => i>pivot)
/*6*/ return [...quickSort(small), pivot, ...quickSort(big) ]

改成了这个样子

/*6*/ qs(small, (sortedSmall)=>{
/*7*/   qs(big, (sortedBig)=>{
/*8*/     next([...sortedSmall, pivot, ...sortedBig])

这个改动的作用是，把后续的所有操作写成一个函数，当做参数传给下一次的 quickSort！

方：对！

学生：确实，把原来需要回头调用的东西往后传，就不用回头了，太聪明了！我已无话可说……但我总感觉哪里怪怪的。

方：你第一次见这样的代码当然觉得怪咯，习惯就好，这种代码风格叫做 CPS（Continuation-passing style），以后有机会还会再讲。

学生：那，所有的递归，都能改写成尾递归吗？

方：是的，具体的讨论你可以看这个 StackOverflow 上的问答，当然不看也没关系，记住结论就行。

学生：今天的课程让我的脑袋都快炸了，我得去打盘游戏休息一下。

方：行，不过我们最后再复习一下今天所学吧：

1. 递归（recursion）有一种特殊的形式，叫做「尾递归」
2. 递归版阶乘可以写成「尾递归」，方法是把上一次的结果传给下一次调用
3. 递归版斐波那契可以写成「尾递归」，方法是把上两次的结果传给下一次调用
4. 递归版快排可以写成「尾递归」，方法是把后续操作写成一个函数，传给下一次调用（即 CPS）
5. 补充一点：递归改写成尾递归还有其他方法，并不只是我上课讲的这么一点

学生：我们今天就讲了这么点内容？我怎么感觉今天讲了很多东西……

方：就这么点，你不会没记住吧？注意记笔记啊！

学生：下次一定，我先去打游戏了，再见！

前篇：https://juejin.cn/post/6939192091540979725

第三天：从 JS 函数到 Haskell 函数

方：黑眼圈这么重，你昨晚是不是开黑到很晚？

学生： 别取笑我了，今天讲什么呢？

方：今年我教你写函数，先聊聊函数参数吧。

学生：参数有什么好讲的，就是把数据传给函数吧。对了，根据你昨天讲的，函数也可以被当作参数传给另一个函数。

方：先看代码吧：

add = (a, b) => a + b
add(1,2) // 得到 3

add 可以求两数之和。要调用 add，只需要把 1 和 2 传给 add 即可得到 3

学生：嗯，接下来你肯定要整点花里胡哨的写法。

方：那是，继续看代码：

c_add = (a) => (b) => a + b

c_add 也可以求两数之和，要调用 c_add，你需要先传入 1，得到一个函数（记为 temp)，然后把 2 传给 temp，得到 3：

temp = c_add(1)
temp(2) // 得到 3

你也可以连续使用两对括号：

c_add(1)(2) // 得到 3

学生：呃……说实话，我觉得这种写法又难看，又多余。我只在面试题里见过类似的考题，工作中从来不用。

方：确实没有什么用，不过这种写法并没有 bug 对吗？

学生：bug 倒是没有

方：我想告诉你的是，这两种参数写法是等价的：

add = (a, b) => a + b
c_add = (a) => (b) => a+b

学生：等价的？

方：嗯，我说的「等价」是指，两个函数，只要得到相同的输入，就一定得到相同的输出。

学生：哦，你的意思是把函数当成黑盒是吧？

方：对，那现在你看 add 和 c_add，除了传参的「形式」不同，是不是等价的？

add(1,2) // 3
c_add(1)(2) // 3

add(18, 24) // 42
c_add(18)(24) // 42

学生：按你的说法，确实等价。毕竟他们的核心代码都是 a + b 而已。

方：好，接下来我们举更复杂的例子：

multi = (a, b, c) => a * b * c
c_multi = a => b => c => a * b * c

这两个函数，等价吗？

学生：也等价

方：继续，更复杂的例子，我将参数个数拓展到 n 个：

anyFn = (p1, p2, ..., pn) => doSomethingWith(p1, p2, ..., pn)
c_anyFn = p1 => p2 => ... => pn => doSomethingWith(p1, p2, ..., pn)

任何一个「接受 n 个参数的函数」，是否与「分 n 次接受 1 个参数的函数」等价呢？

学生：让我想想哈……按你的说法，看起来是等价的

方：所以，我们能不能说 「多参数函数」一定能改写为「单参数函数」，且其输入输出保持不变。

学生：好像可以……但我从没想过这件事，这样改写有什么意义吗？

方：我们后面才会用到这个定理，我称之为「单参定理」，先记下来。

学生：好，我先记在小本本上。

方：其实，你在做前端开发时，用过单参函数。

学生：哦？我怎么不记得？

方：你用过前端模板吧？比如 Handlebars.js：

template = Handlebars.compile("<div>{{user.name}}</div>"); // 传第一个参数

html1 = template({user:{name:'frank'}}) // 传第二个参数
// html1 为 <div>frank</div>
html2 = template({user:{name:'jack'}}) // 传第二个参数
// html2 为 <div>jack</div>

学生：嗯，用过，看来这个 compile 就是一个单参数函数。

方：没错，其用法是 compile(string)(data)。一般来说，一个函数只会选择一种传参形式，要么是 (string, data)，要么是 (string)(data)。不过如果想要同时支持两种形式，也是可以做到的。

学生：那单参函数有什么优点吗？

方：你如果在网上搜，会看到有人说优点是延迟计算啊、代码复用啊之类的，其实吧，多参数同样可以做到这些。

学生：那就是没什么优点咯？

方：后面用到函数组合的时候就能看出优点，目前讲了你也听不懂。

学生：好吧，那我还是先记在本本上吧，没有优点的东西我大脑记不住

方：我们继续。如果一个函数是多参数形式，比如 add，但是我们需要单参数形式，比如 c_add，该怎么办？

学生：虽然我从来都没有这种需求，不过我听过可以通过柯里化（currify）做到？

方：你懂得挺多，将 add 柯里化确实可以得到 c_add，但是我现在不打算讲柯里化，为了简单起见，我们直接改代码就行了，声明函数的时候手动写成 xxx = a => b => c => ... 的形式即可。

学生：方啊，我总是猜不透你……我还等着你讲柯里化呢

方： 柯里化以后讲啦。好了，今天的第一个内容讲完了，那就是「单参定理」，请你把内容复述一遍。

学生：（拿起本本照着读）「多参数函数」一定能改写为「单参数函数」，且其输入输出保持不变

方：不错

学生：那，第二个内容是？

方：接下来讲函数的类型。直接上 TypeScript 代码：

type Add = (a: number, b: number) => number;
const add: Add = (a, b) => a + b;
// 改成单参
type Add = (a: number) => (b: number) => number;
const add: Add = a => b => a + b;

鉴于浏览器不能直接运行 TS，你可以把代码复制到 CodeSandbox.io 上运行

学生：看起来挺简单，就是给函数、参数和返回值加上类型

方：没错，接下来来个复杂点的，这是一个 CPS 形式的 add，我们来给它加上类型：

const add = a => b => fn => fn(a+b)
add(1)(2)( (result)=> result*2 ) // 得到 6

学生：这个 add 接受三个参数 a、b、fn，然后把 a + b 传给 fn，并返回 fn 的返回值，是吧？

方：嗯，要给 add 添加类型，我们可以先声明一个 Add

type Add = ...
const add: Add = ...

学生：嗯，目前很简单

方：然后添加参数 a、b 的类型

type Add = (a:number) => (b:number) => ...
const add: Add = (a) => (b) => ...

学生：还要加 fn 吧？

方：fn 的类型是个函数： (c:number) => number，加进代码里就是这样：

type Add = (a:number) => (b:number) => (fn: (c:number) => number ) =>
const add: Add = (a) => (b) => (fn) => ...

学生：复杂起来了呢

方：由于 add 的返回值，就是 fn(a+b) 的返回值，所以我们最后可以加上返回值的类型：

type Add = (a:number) => (b:number) => (fn: (c:number) => number) => number
const add: Add = (a) => (b) => (fn) => fn(a+b)

学生：看起来好复杂，加类型有什么意义吗？不写类型代码也能运行不是吗？

方：类型系统是程序员的好帮手，只是需要一点时间来适应而已。现在，我们的第二个知识也讲完了：可以给函数加类型声明。

学生：第三个知识点呢？

方：接下来会讲一点点 Haskell 的语法，因为 JS 在后面的文章中会显得不够用，所以我必须逐渐教你一点 Haskell 了。

学生：新语言啊，来吧。

方：这是一个 Haskell 函数，你应该能看懂：

doubleMe :: Int -> Int 
doubleMe x = x * 2

第一句话表示 doubleMe 的参数是 Int 类型，返回值也是 Int 类型； 第二句话表示 doubleMe x 等价于 x * 2，即，若输入 x ，则输出 x 乘以 2。

学生：看是能看懂，那怎么调用 doubleMe 呢？

方：Haskell 中的函数，与其说是「调用」，不如说是「代入」。比如你想调用 doubleMe(100)，只需要把 100 代入到 doubleMe x = x * 2 等式左边的 x，就能得到等式右边的 100 * 2，也就是 200

学生：倒是挺直白啊。Haskell 中的函数调用不需要括号吗？

方：不需要。括号一般用来表示优先级。比如

  putStrLn (show (doubleMe 100))

就是先执行 doubleMe 100，得到 200；然后执行 show 200，得到字符串 "200"；最后执行 putStrLn "200" 打印出字符串

学生：我用 JS 表示就是 putStrLn(show(doubleMe(100))) 咯？

方：嗯

学生：这样写不觉得傻吗？一层括号套一层括号，Haskell 里直接写 putStrLn show doubleMe 100 行吗？

方：不行，因为这样写的意思是把 show、doubleMe、100 作为参数传给 putStrLn

学生：是哦，那就必须写这么多括号了吗？

方：Hashell 给出了一个 $ 符号，方便我们把上面的代码写成这样

putStrLn  (show  (doubleMe 100))
写为
putStrLn $ show $ doubleMe 100

学生：这么写还行。但是看代码得从右往左看，好麻烦啊

方：就这还嫌麻烦啊，那你可以从上往下写，多加几个中间变量即可

let n = doubleMe 100
let string = show n
putStrLn string

这种从上到下的写法是专门给脑容量较小的新手准备的，因为易于理解

学生：这说得不就是我么……

方：嗯，就是你。对了，如果你学过面向对象，可以写成 n.doubleMe().toString().print()，这叫「链式调用」

学生：这种写法我会！给 n 所属的类添加成员方法就行。

方：你觉得链式调用是不是比 putStrLn $ show $ doubleMe 100 看着舒服

学生：（点头）嗯嗯嗯

方：但是是有代价的哦

学生：什么代价

方：链式调用需要引入 this 或 self 关键字，因为 doubleMe、toString、print 都需要用 this 来获取 n

学生：你不说我都忘了，确实要用到 this

方：顺便提一下，你不觉得 class 那一套面向对象的语法引入的关键字、特殊属性和概念太多了吗？比如 class、extends、interface、this、super、constructor、public、private、继承、实例、成员属性、类属性、静态方法……

学生：用多了还好吧，我基本都背下来了

方：好，那就拿出你背这些概念的精神头来背背函数式的知识，目前只引入了一个 $，不要嫌烦。按你的话说，用多了就好了。

学生：好的好的，我会耐心的

方：最后，把我完整的 Haskell 代码给你，方便你在这个网站上面运行：

doubleMe :: Int -> Int
doubleMe x = x * 2

main :: IO ()
main = putStrLn $ show $ doubleMe 100

学生：咦，这个 main = 我能理解，但是这个 main :: IO() 是指定 main 的类型为 IO() 吗？ IO() 是什么？

方：这个以后再说，看不懂的代码照抄就行。

学生：（打开网站点击Run）我运行成功了！输出 200

方：行，今天我们就从 JS 慢慢往 Haskell 过渡了，以后能用 JS 表示的代码我会用 JS，不能用 JS 表示的我就得用 Haskell 来写了哦。

学生：OK

方：那，明天再见吧。