初入 lambda 演算


在談及函數式程式設計時,總會談到代數資料型態(Algebraic Data Type, ADT),就程式面來說,運用代數資料型態,可以輕易地察覺基本的資料結構及規律性,你可以從一個最基本的代數資料型態實例出發,然後依相同結構與規則得到更多代數資料型態實例。

以 List 為例,不同於熟悉的索引方式,可以定義清單就是一個首元素加上子 List 來組成:

let con = head => tail => [head, tail];

雖然在這邊直接使用了 JavaScript 的陣列實字,基本上,這邊定義的 List 與 JavaScript 陣列沒有太大關係,這只是稍微運用一下 JavaScript 的一些語法甜頭,讓事情不會在一開始就變得過於複雜,讓焦點集中在代數資料型態的概念說明上,對於 [head, tail],實際上完全可以用箭號函式進一步定義,不過這邊還不打算深入到那個程度。

接著必須定義一個 List 實例的出發點,也就是空 List,沒有頭也沒有尾:

let nil = [undefined, undefined];

有了空 List 的定義之後,接下來要建立只有一個元素的 List:

let lt1 = con(1)(nil);

也就是說,只有一個元素的 List,就是 [1, nil],如果是具有元素 2 與 1 的 List 呢?

let lt2 = con(2)(lt1);

具有元素 2 與 1 的 List 就是 [2, [1, nil]],依此類推的話,具有元素 3、2、1 的 List 就會是 [3, [2, [1, nil]]],具有元素 4、3、2、1 的 List 就會是 [4, [3, [2, [1, nil]]]] …

可以定義 headtail,來取得 List 中的首元素或尾 List,以及用來判定是否為空 List 的 isEmpty

let head = ([h, _]) => h;
let tail = ([_, t]) => t;
let isEmpty = lt => head(lt) === undefined;

有了這些函式,就可以開始逐一擴展想要做的事情了,con(1)(con(2)(con(3)(nil))) 表示含有元素 1、2、3 的 List,然而為了便於建立 List,有個 elems(1)(2)(3) 形式的寫法會比較方便,而這意謂著,elems 接受一個元素之後,必須傳回函式,然後接受一個元素之後又傳回函式 …

持續地傳回函式?想想看,若有個箭號函式 let f = a => b => f(a)f(1) 傳回什麼呢?一個函式!f(1)(2) 呢?還是一個函式,f(1)(2)(3) 呢?還是一個函式…太棒了…只要函式每次傳回自身部份套用後的結果,就可以達到這樣的連續呼叫形式。

先前的 con 第一個參數接受 head 元素,用它作為基礎來寫個 rcon,使得 rcon 每次部份套用後,都可以接受 head 元素,並傳回部份套用之後的結果:

let rcon = tail => head => head === undefined ? tail : rcon(con(head)(tail));

rcon(nil)(1)(2)(3)() 做的會是 con 的相反動作,這就是為什麼叫它 rcon 的原因,為了最後能建立 List,最後若呼叫函式時沒有指定元素,就將建立的 List 傳回而不再是傳回函式。

因為 rcon(nil)(1)(2)(3)()con 的相反動作,實際上建立的 List,元素順序會是 3、2、1,這在閱讀上並不直覺,可以寫個 reverse 把它反過來:

let rev = r => l => isEmpty(l) ? r : rev(con(head(l))(r))(tail(l));
let reverse = lt => rev(nil)(lt);

接著可以寫個 list 來傳回 List:

let elems = rcon(nil);
let list = elems => reverse(elems());

就 lambda 演算的角度來看,直接使用 elems() 不夠嚴謹,然而,由於實際上確實是借助了 JavaScript 的環境,令像是 lambda 表示式的箭號函式,可以獲得執行而得到結果,適時地放寬一些限制,可以讓事情簡單一些,然後看看可以逼近 lambda 演算到什麼程度。

現在,想要建立含有元素 1、2、3 的 List,可以先用 elems 列舉,再透過 list 來得到了:

let lt = list(elems(1)(2)(3));

有了便於建立 List 的 list 函式了,下一步會想知道的是,一個 List 的長度是多少呢?

let len = lt => isEmpty(lt) ? 0 : 1 + len(tail(lt));

len(list(elems(1)(2)(3))) 會傳回 3 的結果。如果要加總一個 List 呢?

let sum = lt => isEmpty(lt) ? 0 : head(lt) + sum(tail(lt)); 

sum(list(elems(1)(2)(3))) 會傳回 6 的結果。看起來還不錯,接著想想看,怎麼定義一個 addOne 函式,可以對傳入 List 中每個元素加一後傳回新 List 呢?

這個問題的其中一個子問題是,如果是空 List 的話,結果會傳回什麼?就只是 nil!另一個子問題是,如果傳入的 List 中,首元素為 x 而尾清單為 xs,要怎麼計算傳回的結果?對 x 加一,然後使用 xs 再次呼叫 addOne 方法,接著使用 con 方法將兩者的結果組為一個新清單。

let addOne = lt => isEmpty(lt) ? nil : con(head(lt) + 1)(addOne(tail(lt)));

類似地,如果想定義一個函式,將 List 中每個元素減 2 後傳回新 List,那麼就只要將程式碼中 (+ 1) 的部份改為 (- 2),而函式名稱 addOne 改為 subtractTWO。如果想將 List 中每個元素乘 3 後傳回新 List,只要將程式碼中 (+ 1) 改為 (* 3),並將函式名稱 addOne 改為 multiplyByThree

看出什麼了嗎?如果 (+ 1)(- 2)(* 3) 是可傳入的一級函式(First-class function),那麼這個程式碼流程樣版就可以重用,於是我們有了 map 函式:

let map = lt => f => isEmpty(lt) ? nil : con(f(head(lt)))(map(tail(lt))(f));

如果 lt 參考至某 List,若要對全部元素加 1,就只要 map(lt)(elem => elem + 1),若要對全部元素減 2,就只要 map(lt)(elem => elem - 1),若要對全部元素乘 3,就只要 map(lt)(elem => elem * 3)

這種 map 函式很有用,可以有一百萬種使用方式。類似地,如果想將 List 中大於 3 的元素過濾出來成為新 List 呢?可以寫如下的程式碼:

let greaterThanThree = lt  => isEmpty(lt) ? nil : 
         head(lt) > 3 ? con(head(lt))(greaterThanThree(tail(lt))) : 
                        greaterThanThree(tail(lt));

如果想將 List 小於 10 的元素過濾出來成為新 List 呢?只要將 (> 3) 改為 (< 10) 就可以了,也就是說,如果可以傳入函式,由該函式來判斷是否要留下,就可以使用一個通用的函式,來完成各種過濾需求:

let filter = lt => f => isEmpty(lt) ? nil : 
         f(head(lt)) ? con(head(lt))(filter(tail(lt))(f)) : 
                       filter(tail(lt))(f);

如果 lt 參考至某 List,要找出大於 3 的數,只要寫 filter(lt)(elem => elem > 3) 就可以了,這個 filter 函式很有用,可以有一百萬種過濾方式。

這就是為什麼,有些語言納入了函數式風格之後,會有一些 mapfilter 之類的 API 可以使用。不過,這邊並不是要再談函數式程式設計,而是想表達一件事,使用箭號函式,可以表達出「找出 List 中大於 3 的數」、「將 List 中每個元素減 2」之類的運算。

例如,「List 中有 1、2、3,將 List 中每個元素減 1」,可以使用 map(list(elems(1)(2)(3)))(elem => elem - 1) 來表達,接著將 map 轉換為箭號函式,然而,因為 map 會遞迴,因此必須使用〈Y Combinator〉中定義的 y 函式,轉換的結果會是 y(map => lt => f => isEmpty(lt) ? nil : con(f(head(lt)))(map(tail(lt))(f)))(list(elems(1)(2)(3)))(elem => elem - 1)

進一步地,將 isEmpty 轉換為箭號函式,結果會是 y(map => lt => f => (lt => head(lt) === undefined)(lt) ? nil : con(f(head(lt)))(map(tail(lt))(f)))(list(elems(1)(2)(3)))(elem => elem - 1)

然後再將 y 也轉換為箭號函式,得到 (f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(map => lt => f => (lt => head(lt) === undefined)(lt) ? nil : con(f(head(lt)))(map(tail(lt))(f)))(list(elems(1)(2)(3)))(elem => elem - 1)

持續這類的轉換,可以將 listelem 也轉換為箭號函式,到最後,你會得到 (f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(map => lt => f => (lt => head(lt) === undefined)(lt) ? nil : con(f(head(lt)))(map(tail(lt))(f)))((elems => (lt => (f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rev => r => l => (lt => head(lt) === undefined)(l) ? r : rev(con(head(l))(r))(tail(l)))(nil)(lt))(elems()))((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rcon => tail => head => head === undefined ? tail : rcon(con(head)(tail)))(nil)(1)(2)(3)))(elem => elem - 1),這結果看來神秘,然而 JavaScript 完全可以理解、執行這堆箭號函式。

上面的式子保留了 nilconheadtail 等函式呼叫尚未轉換,這是因為這幾個函式沒有完全使用箭號函式,這是一開始就說到的,為了讓事情不會在一開始就變得過於複雜,稍微運用一下 JavaScript 的一些語法甜頭,而這部份還可以進一步使用箭號函式定義,直到完全都使用箭號函式表示為止。