写给前端工程师看的函数式编程对话 - 4

第4天：数据与函数

学生：方，今天讲什么？

方：你先说说前面三天学了什么

学生：学了

1. 递归不可怕，某些语言的递归性能慢只是因为这些语言不提倡用递归所以没优化，而不是因为递归慢。
2. 递归有一种特殊形式叫尾递归，能避免爆栈
3. 函数可以单参形式，可以加类型
4. 还有一点点 Haskell 知识，比如 $ 符号

方：嗯，你看，我们学的东西是不是很少

学生：……你说是就是吧……

方：今天我们来学习一下稍微复杂一点的结构，之前我们涉及到的数据只有数字、字符串和函数。虽然也用到了数组，但其实是只在 JS 里用过，还没在 Haskell 里用过。

学生：等下，我有个问题哈，你说函数是数据，这是什么意思？

方：这节课我会告诉你答案。

学生：有点意思，那开始吧。

方：先来讨论一种最简单的复合数据结构：(a, b)，举例：

• 可以用 (4, 2) 表示 x 坐标为 4，y 坐标为 2 的点；
• 可以用 (2, 4) 表示 x 坐标为 2，y 坐标为 4 的点；
• 可以用 ("方", "应杭") 表示姓和名；
• 可以用 (1, "one") 表示 1 和 "one" 的对应关系；

这种数据只能有两个元素，两个元素的类型可以不同。这种数据结构叫做二元组或有序对，英文叫 pair。注意，这是一种抽象的数据结构，并不局限于 Haskell。

学生：JS 里没有这种数据结构，但是看起来像是长度固定为 2 的数组？

方：你可以这么理解。

学生：那 pair 有哪些 API？

方：只有两个 API：first 和 second

// JS 风格的 API
const pair = createPair(1, 2)
first(pair) // 得到 1
second(pair) // 得到 2

-- Haskell 风格的 API
let pair = (1, 2)
fst pair -- 得到 1
snd pair -- 得到 2

方：如果我让你用 JS 来实现 pair，你会怎么做？

学生：这样行不行：

createPair = (a, b) => [a, b]
first = pair => pair[0]
second = pair => pair[1]

方：嗯不错，我提供你另一种思路，看你能不能看懂：

createPair = (a, b) => 
                    n => 
                      n === 0 ? a : b
first = pair => pair(0)
second = pair => pair(1)

学生：这是啥？你的 createPair 返回的是个函数？

方：嗯。

学生：这个 pair 函数接收到 0 就返回 a，接受到其他就返回 b？

方：嗯。

学生：等下，我一时还没接受 pair 是个函数……它不是个数组或者对象吗？

方：那是你自己先入为主了，你是不是认为函数是函数，数据是数据？

学生：难道不是吗？

方：你仔细看看这三种代码：

array[0]
object[0]
fn(0)

是不是把参数 0 传给 3 个东西，这 3 个东西为什么不能「都是函数」呢？

学生：等下，你这么一说我好像悟到了！array[0] 确实可以看做是 array(0)，array 就是个函数了。那 array.length 怎么办？莫非我们的函数支持添加属性？

方：不需要，你把 array.length 看成 array('length') 即可

学生：原来还可以这么理解，那 array、object、fn 本质上岂不是没有区别？

方：我觉得是。

学生：有点意思

方：刚才的 createPair 代码其实我还留了一手，你看看这样写你能不能看懂：

createPair = (a, b) => fn => fn(a, b)
first = pair => pair((x,y) => x)
second = pair => pair((x,y) => y)

学生：让我先看看。（两分钟后）好家伙，

1. createPair 接受 a、b、fn然后调用 fn(a, b)，看似什么都没做
2. 但是当你调用 first(pair) 的时候，fn 被赋值为 (x, y)=> x
3. 最终把 a、b 代入到 x、y，得到 a
4. 也就是说 first(pair) 会得到 a
5. 同理，second(pair) 会得到 b

我自己肯定想不到可以这么写，我要是这么写我的同事肯定也看不懂

方：分析的不错，只要善用「代入法」就好理解，否则很难懂。

学生：「代入法」确实好，一开始我想直接看懂代码，发现不行。后来用代入法在纸上一写就懂了：

pair = createPair(1, 2)
= fn => fn(1, 2)

first(pair)
= first(pair)
= pair ((x,y) => x)
= (fn => fn(1, 2)) ((x,y) => x)
= ((x,y) => x) (1, 2)
= 1

方：那我们的第一个知识点就学完了：用函数可以表示二元组（pair）。同时我们再一次用到了「代入法」。但是要注意，Haskell 中的 createPair、first、second 不一定是这样实现的，我们只是为了学习目的才写这样的代码。

学生：我现在有点理解你最开始说的话了「学这些知识不会对日常工作有帮助，但是能从另一个角度来理解代码。」

方：接下来我们开始学习第二种数据结构，列表（list），你也可以把它叫做数组（array）。同样，这是一种抽象的数据结构，不局限于某种语言。举例：

• [ ] 表示空列表
• [1, 2, 3, 4, 5] 表示五个数字
• ["hi", "hi"] 表示两个字符串
• [1, "hi"] 包含不同类型的元素，我们不讨论这种 list

list 是有序的，其 API 有：

• head list - 获取第 1 个元素
• last list - 获取最后一个元素
• tail list - 获取除了第一个之外的元素
• get n list - 获取第 n 个元素

你能用 JS 实现一个 createList 吗？

学生：这还不简单，这玩意不就是 JS 的数组吗：

const createList = (...args) => [...args]
const list = createList(1,2,3,4,5)

const head = list => list[0]
const tail = ([first, ...rest]) => rest
const last = list => list[list.length - 1]
const get = (n, list) => list[n]

这样行不？

方：确实符合要求，但是你使用来太多 JS 内置的功能了。看看我这个：

const cp = createPair
const list = cp(1, cp(2, cp(3, cp(4, cp(5, null)))))

const head = list => list((x,y) => x) // head 跟 first 等价
const tail = list => list((x,y) => y) // tail 跟 second 等价
const last = list => tail(list) === null ? head(list) : last(tail(list))
const get = (n, list) => n === 1 ? head(list) : get(n-1, tail(list))

学生：你的 list 是个二元组，二元组的第二项还可以是另一个二元组？

方：嗯，每个二元组其实就是 (data, next)，data 表示数据，next 则指向下一项。为了方便你理解，我用图 1 来展示一下：

// 图 1
list -> (1, ↓)
           (2, ↓) 
              (3, ↓) 
                 (4, ↓) 
                    (5, 空) 

学生：这个就是数据结构里的链表吧！但是为什么不用连续的内存表示呢……连续的内存效率更高不是吗？

方：连续的内存在「插入数据」和「扩容」的时候效率超低不是吗？只是 index 的时候效率高而已。另外，我没有说 list 的内存形式吧……它可以是顺序存储，也可以是链式存储，我不关心。

学生：不关心内存？

方：没错。你应该试着脱离「内存」来思考，你以前对数据结构的理解都依托于「内存」，比如，数组是一段连续排列的内存，对象是在堆内存中随机存储的数据。

学生：好像是诶，你不说我都没发现。

方：从现在开始，我们不聊内存，行吗。

学生：好吧，我尽量。不过，cp(1,cp(2, ... 这样的代码写起来好麻烦

方：我们加点「语法糖」就行了：

let list = 1:2:3:4:5:[]

这句话要从右往左看：

5:[] -- 等价于 cp(5, null)，得到 [5]
4:5:[] -- 等价于 cp(4, cp(5, null))， 得到 [4,5]
3:4:5:[] -- 得到 [3,4,5]
2:3:4:5:[] -- 得到 [2,3,4,5]
1:2:3:4:5:[] -- 得到 [1,2,3,4,5]

甚至还提供了你想要的写法：

let list = [1,2,3,4,5]

但是你要记住，它表示的意思并不是连续的内存[1]，而是类似于元组里面套元组[2]的意思（见图1），至于内存到底连续不连续，答案是可以连续，也可以不连续，目前我们不关心。

学生：意思我懂了，但是这代码看起来有点傻啊

方：你天天都写这样的代码，你忘了？

学生：才没有呢，不可能

方：那我问你，你最近是不是在用 React？

学生：嗯，咋了

方：你是不是天天写这样的代码：

return (
  <div class="wrapper">
    <div class="box">
      <span class="title"> 标题 </span>
    </div>
  </div>
)

学生：嗯，挺好的呀

方：上面代码是不是等价于

const h = React.createElement
return (
  h('div', {className:'wrapper'},
    h('div', {className:'box'},
      h('span', {className:'title'}, '标题')
    )
  )
)

学生：转译之后是的！

方：那你这代码跟我的代码

const list = cp(1, 
               cp(2, 
                 cp(3, 
                   cp(4, 
                     cp(5, null)
                   )
                 )
               )
             ) 

有毛区别？

学生：好吧！原来我早就爱上了这种傻代码，傻子竟是我自己……

方：React 不过是把你构造 UI 的嵌套代码简化成了 JSX，看起来不那么繁琐而已

学生：看来我还是容易被代码表面的写法所迷惑

方：那么，我们的第二个知识点也讲完了：用嵌套的 pair 来实现 list。并且我叫你不要再去关心内存形式了，因为抽象数据结构的内存形式可以是连续的，也可以是不连续的。这说明函数式的思想是更加「高级」的，它关注的是「抽象」的东西，而不是内存这么「具体」的东西。

学生：「更抽象的」就是「更高级的」吗？

方：是的，但你要知道，「高级」在编程领域里是个「中性词」，高级语言与低级语言是等价的，只是关注的点和表现的形式不一样而已。

学生：今天还有内容吗？

方：没有，不过有随堂作业哦。

学生：来吧，我试试

方：题目是，给下面的函数加上类型（只考虑 number），并改成单参形式

createPair = (a, b) => fn => fn(a, b)
first = pair => pair((x,y) => x)
second = pair => pair((x,y) => y)

学生：来了：

type Fn = (x: number) => (y: number) => number
type Pair = (fn: Fn) => number

type CreatePair = (a:number) => (b:number) => Pair
const createPair: CreatePair = a => b => fn => fn(a)(b)

type First = (pair: Pair) => number
const first: First = pair => pair(x => y => x)

type Second = (pair: Pair) => number
const second: Second = pair => pair(x => y => y)

还别说，加上类型之后，反而更容易理解这三个函数了。

1. CreatePair 接受两个 number，返回一个 Pair
2. Pair 接受一个 Fn，返回一个 number
3. First 接受一个 Pair，给 Pair 传一个 Fn，返回一个 number
4. Second 跟 First 一样

不过，pair 是一个函数这一点，我还是难以接受。而且我必须给 pair 传一个函数才能得到一个 number，也挺难以理解的

方：虽然你可以写出代码，但是你不理解含义对吧

学生：是的

方：你上次有这种感觉是不是在你学数学的时候

学生：对啊，反正代入公式，结果就出来了

方：那就对了，对新手来说，函数式就是这种感觉。

学生：那我什么时候才能真正理解「二元组 pair 是个函数」呢

方：你现在可以简单的认为，这个函数把数据藏起来了，不让你看见

学生：好像有点那么个意思

方：我们后面还会讨论这个问题，今天就到这里吧

学生：好的，再见！

脚注

1. 实际上，JS 的 [1,2,3] 也不是连续存储的，而是用对象来模拟的，所以是随机存储的
2. 实际上 Haskell 内部是怎样实现 list 的？我们目前不讨论这个话题