在談及函數式程式設計時,總會談到代數資料型態(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]]]] …
可以定義 head
與 tail
,來取得 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
函式很有用,可以有一百萬種過濾方式。
這就是為什麼,有些語言納入了函數式風格之後,會有一些 map
、filter
之類的 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)
。
持續這類的轉換,可以將 list
、elem
也轉換為箭號函式,到最後,你會得到 (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 完全可以理解、執行這堆箭號函式。
上面的式子保留了 nil
、con
、head
與 tail
等函式呼叫尚未轉換,這是因為這幾個函式沒有完全使用箭號函式,這是一開始就說到的,為了讓事情不會在一開始就變得過於複雜,稍微運用一下 JavaScript 的一些語法甜頭,而這部份還可以進一步使用箭號函式定義,直到完全都使用箭號函式表示為止。