写篇文章再谈谈函数和一等公民，因为我发现了些有趣的东西。
先前想在自己的 函数式方言解释器 里实现
元组 这种数据结构，但是没有什么方向，就去看了下 Scheme 的语法，看了下 Wiki，然后不知不觉间，看到了用 Lisp 实现 Pair。Lisp 你可能听过，这里我们不需要它，但后面的 Pair 是啥，它其实是一种很简单的数据结构，类似这样，用 TyepScript 表示就是这样：
00// 创建一个 pair 01function cons(l: number, r: number) { 02 return [l, r] 03} 04 05// 取出 pair 的左边 06function car(my_pair: number[]) { 07 return my_pair[0]; 08} 09 10// 取出右边 11function cdr(my_pair: number[]) { 12 return my_pair[1]; 13}
闲话一下，scheme 里创建 pair 的函数名就是 cons，还有它的两个操作 car 和 cdr 也是这个名字，因此本文也都用这个名字。
好吧，进入正题，形如上面这种样子的数据结构，叫做
Pair，在很多 js 库里也有它的存在，比如 React.useState 返回的是左边是值，右边是 dispatcher 的 pair。但我们这里讨论的是利用了数组去实现的，有没有别的方法去实现这种数据结构呢？答案当然是有的啦，下文将会给出仅利用函数的方式来实现这种数据结构，以及仅用函数去实现链表、二叉树。
# Pair 的函数式实现 ↵
因为本人一开始是想在自己写的的一个函数式方言的解释器里加上 pair 这个类型的，因此看了 Pair 的函数式实现，如下：
00;; 代码从 Wiki 摘录 01;; https://en.wikipedia.org/wiki/Cons 02 03(define (cons x y) 04 (lambda (m) (m x y))) 05 06(define (car z) 07 (z (lambda (p q) p))) 08 09(define (cdr z) 10 (z (lambda (p q) q)))
翻译成 TypeScript 就是这样：
00// 姑且把 Pair 这种数据结构类型定义为函数 01type Pair = Function; 02 03// 创建一个 cons 04function cons(x: number, y: number): Pair { 05 return (how_to_do_it: Function) => { 06 return how_to_do_it(x, y); 07 } 08} 09 10// 取出 pair 的左值 11function car(pair: Pair) { 12 return pair((l, r) => l) 13} 14 15// 取出 pair 的右值 16function cdr(pair: Pair) { 17 return pair((l, r) => r) 18} 19 20const xy = cons(1, 2); 21// 调用 cons 返回一个函数 22 23const x = car(xy); 24// => 1 25 26const y = cdr(xy); 27// => 2
以上代码完美的体现了函数是一等公民这个概念，因为我们仅利用了函数去实现数据结构，这才是一等公民背后的意义。
# 挑战：函数式链表 ↵
现在，我们有了 Pair，它有两个值，此外，这两个值也是有序的，它可以用来构造链表吗？
当然可以，因为我们没有考虑到它有两个值里的值是啥。Pair 里的左值右值，既可以是数字，也可以是另一个 Pair，也就是说，Pair 里可以嵌套 Pair，据此可以递归地定义链表：
Pair(number, number | Pair | null)
当且仅当右值为 null 的时候，我们才认为链表到达了尽头
由上面的讨论可以很容易的利用 Pair 递归地构造出链表，也就是说，可以仅用函数实现链表。
或许你还没理解所谓递归地定义链表是啥意思，你可以看看下面的代码形式，便一目了然：
cons(1, cons(2, cons(3)))
1 -> 2 -> 3
根据上面的讨论，其 TypeScript 实现如下：
00type Pair = Function; 01 02function cons(x: number, y?: number | Pair): Pair { 03 return (how_to_do_it: Function) => { 04 return how_to_do_it(x, y); 05 } 06} 07 08function car(pair: Pair) { 09 return pair((l, r) => l) 10} 11 12function cdr(pair: Pair) { 13 return pair((l, r) => r) 14} 15 16// 取出链表的第 n 个 17function nth(pair: Pair, n: number) { 18 if (n === 0) { 19 return car(pair); 20 } else { 21 return nth(cdr(pair), n - 1); 22 } 23} 24 25const lst = cons(1, cons(2, cons(3))) 26// 1 -> 2 -> 3 27 28const number = nth(lst, 0); 29// => 1
可以看到，cons 的 y 可以为空或者也是一个 pair 了，这里存在递归，因此取链表的时候用递归实现比较容易。
# 挑战：函数式二叉树 ↵
上面的讨论已经实现了链表，而链表里一个最特殊的地方便是引用，如果引用变成两个，链表就可以推广成二叉树。
以下是我的实现：
00// 在把函数作为一等公民的语言里， 01// 函数是一种数据类型/结构 02type Tree = Function; 03 04// 函数式二叉树 05// 如果不指定范型，则认为树上存的值是数字； 06function Tree<T = number>(v: T, l?: Tree, r?: Tree): Tree { 07 return (how_to_do_it: Function) => { 08 return how_to_do_it(v, l, r); 09 } 10} 11 12// 取左子树 13function lchild(tree: Tree) { 14 return tree((v, l, r) => l); 15} 16 17// 取右子树 18function rchild(tree: Tree) { 19 return tree((v, l, r) => r); 20} 21 22// 取值 23function valOf(tree: Tree) { 24 return tree((v, l, r) => v); 25} 26 27// 函数式二叉树的前序遍历 28function traversal(t?: Tree) { 29 if (!t) return; 30 31 const l = lchild(t); 32 const r = rchild(t); 33 const v = valOf(t); 34 35 console.log(v); 36 37 traversal(l); 38 traversal(r); 39} 40 41// 创建一棵树。。。 42// 虽然有点绕... 43const t = 44 Tree(1, 45 Tree(2, 46Tree(3), Tree(4)), Tree(5, Tree(6))) 47// 结构如下： 48// 1 49// / \ 50// 2 5 51// / \ / 52// 3 4 6 53 54 55// 先序遍历结果 56traversal(t); 57// => 打印：123456
上面的代码实现了二叉树的表示，并给出了二叉树的先序遍历方式。
# 那么，什么是函数呢？ ↵
我还不知道 233，不过时断时续的学习函数式语言，每次都有不同的收获是真。
上面的说明里可以窥见，所谓函数是一等公民，其实意味着函数可以实现编程语言里的其他事物，如数据结构。
这部分涉及到了 Lambda Calculus 这方面我学习的不深。。。。不展开了。