再談函式和一等公民
本文首發自本人部落格eczn.github.io/blog/cc2509… 以下是原文：
寫篇文章再談談函式和一等公民，因為我發現了些有趣的東西。
先前想在自己的函式式方言直譯器
裡實現元組
這種資料結構，但是沒有什麼方向，就去看了下 Scheme 的語法，看了下 Wiki，然後不知不覺間，看到了用 Lisp 實現 Pair。
Lisp 你可能聽過，這裡我們不需要它，但後面的 Pair 是啥，它其實是一種很簡單的資料結構，類似這樣，用 TyepScript 表示就是這樣：
// 建立一個 pair
function cons(l: number, r: number) {
return [l, r]
}
// 取出 pair 的左邊
function car(my_pair: number[]) {
return my_pair[0];
}
// 取出右邊
function cdr(my_pair: number[]) {
return my_pair[1];
}
複製程式碼
閒話一下，scheme 裡建立 pair 的函式名就是 cons，還有它的兩個操作 car 和 cdr 也是這個名字，因此本文也都用這個名字。
好吧，進入正題，形如上面這種樣子的資料結構，叫做Pair
，在很多 js 庫裡也有它的存在，比如 React.useState 返回的是左邊是值，右邊是 dispatcher 的 pair。
但我們這裡討論的是利用了陣列去實現的，有沒有別的方法去實現這種資料結構呢？答案當然是有的啦，下文將會給出僅利用函式的方式來實現這種資料結構，以及僅用函式去實現連結串列、二叉樹。
Pair 的函式式實現
因為本人一開始是想在自己寫的的一個函式式方言的直譯器里加上 pair 這個型別的，因此看了 Pair 的函式式實現，如下：
;; 程式碼從 Wiki 摘錄 ;; https://en.wikipedia.org/wiki/Cons (define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q))) 複製程式碼
翻譯成 TypeScript 就是這樣：
// 姑且把 Pair 這種資料結構型別定義為函式
type Pair = Function;
// 建立一個 cons
function cons(x: number, y: number): Pair {
return (how_to_do_it: Function) => {
return how_to_do_it(x, y);
}
}
// 取出 pair 的左值
function car(pair: Pair) {
return pair((l, r) => l)
}
// 取出 pair 的右值
function cdr(pair: Pair) {
return pair((l, r) => r)
}
const xy = cons(1, 2);
// 呼叫 cons 返回一個函式
const x = car(xy);
// => 1
const y = cdr(xy);
// => 2
複製程式碼
以上程式碼完美的體現了函式是一等公民這個概念，因為我們僅利用了函式去實現資料結構，這才是一等公民背後的意義。
挑戰：函式式連結串列
現在，我們有了 Pair，它有兩個值，此外，這兩個值也是有序的，它可以用來構造連結串列嗎？
當然可以，因為我們沒有考慮到它有兩個值裡的值是啥。Pair 裡的左值右值，既可以是數字，也可以是另一個 Pair，也就是說，Pair 裡可以巢狀 Pair，據此可以遞迴地定義連結串列：
Pair(number, number | Pair | null) 當且僅當右值為 null 的時候，我們才認為連結串列到達了盡頭
由上面的討論可以很容易的利用 Pair 遞迴地構造出連結串列，也就是說，可以僅用函式實現連結串列。
或許你還沒理解所謂遞迴地定義連結串列是啥意思，你可以看看下面的程式碼形式，便一目瞭然：
cons(1, cons(2, cons(3))) 1 -> 2 -> 3
根據上面的討論，其 TypeScript 實現如下：
type Pair = Function;
function cons(x: number, y?: number | Pair): Pair {
return (how_to_do_it: Function) => {
return how_to_do_it(x, y);
}
}
function car(pair: Pair) {
return pair((l, r) => l)
}
function cdr(pair: Pair) {
return pair((l, r) => r)
}
// 取出連結串列的第 n 個
function nth(pair: Pair, n: number) {
if (n === 0) {
return car(pair);
} else {
return nth(cdr(pair), n - 1);
}
}
const lst = cons(1, cons(2, cons(3)))
// 1 -> 2 -> 3
const number = nth(lst, 0);
// => 1
複製程式碼
可以看到，cons 的 y 可以為空或者也是一個 pair 了，這裡存在遞迴，因此取連結串列的時候用遞迴實現比較容易。
挑戰：函式式二叉樹
上面的討論已經實現了連結串列，而連結串列裡一個最特殊的地方便是引用，如果引用變成兩個，連結串列就可以推廣成二叉樹。
以下是我的實現：
// 在把函式作為一等公民的語言裡，
// 函式是一種資料型別/結構
type Tree = Function;
// 函式式二叉樹
// 如果不指定範型，則認為樹上存的值是數字；
function Tree<T = number>(v: T, l?: Tree, r?: Tree): Tree {
return (how_to_do_it: Function) => {
return how_to_do_it(v, l, r);
}
}
// 取左子樹
function lchild(tree: Tree) {
return tree((v, l, r) => l);
}
// 取右子樹
function rchild(tree: Tree) {
return tree((v, l, r) => r);
}
// 取值
function valOf(tree: Tree) {
return tree((v, l, r) => v);
}
// 函式式二叉樹的前序遍歷
function traversal(t?: Tree) {
if (!t) return;
const l = lchild(t);
const r = rchild(t);
const v = valOf(t);
console.log(v);
traversal(l);
traversal(r);
}
// 建立一棵樹。。。
// 雖然有點繞...
const t =
Tree(1,
Tree(2,
Tree(3), Tree(4)), Tree(5, Tree(6)))
// 結構如下：
//1
///\
//25
/// \/
// 346
// 先序遍歷結果
traversal(t);
// => 列印：123456
複製程式碼
上面的程式碼實現了二叉樹的表示，並給出了二叉樹的先序遍歷方式。
那麼，什麼是函式呢？
我還不知道 233，不過時斷時續的學習函式式語言，每次都有不同的收穫是真。
上面的說明裡可以窺見，所謂函式是一等公民，其實意味著函式可以實現程式語言裡的其他事物，如資料結構。
這部分涉及到了 Lambda Calculus 這方面我學習的不深。。。。不展開了。