代數資料型態

在談及函數式程式設計時，總會談到代數資料型態（Algebraic Data Type, ADT），簡單來說，是基於資料的結構來構成型態，新型態的構成來自於型態與型態的結合，因而拿到一個資料時，就能利用其結構的規律性來進行處理。

想深入探討代數資料型態，最好的方式是從一門函數式語言下手，然而這並不是這系列文件的重點，因而這邊會從一個 List 的結構開始探討，從而在後續各個文件中，逐步將各個元素，都化為代數資料型態….

〈Haskell〉文件的〈代數資料型態〉，談到了定義代數資料型態時，常見的 sum 型態與 product 型態，想從一門函數式語言下手的話可以參考。

List 有頭有尾

以 List 為例，以代數資料型態的概念來定義時，會透過一個 con 函式，指定首元素與子 List 來構造一個新 List：

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

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

建構 List

接著必須定義一個 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 而尾 List 為 xs，要怎麼計算傳回的結果？對 x 加一，然後使用 xs 再次呼叫 addOne 方法，接著使用 con 方法將兩者的結果組為一個新 List。

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) 來表達。

代數資料型態

List 有頭有尾

建構 List

流程抽象化

更多匿名函式