逆轉序列的遞歸/尾遞歸（+destructuring assignment）實作（JavaScript + ES6）

這裡是用 JavaScript 做的逆轉序列（數組/字元串）的遞歸/尾遞歸實作。另外還嘗鮮用了一下 ES6 的destructuring assignment + spread operator 做了一個更 functional 的版本（隻支援數組）。

正确性能通過測試（參見 放在我 Github 上的 demo，順手寫了一個小小的測試架構），不過效率就要打問号了——特别是用了 ES6 特性的版本。這裡主要是寫來玩 JS 的函數式特性的。

1. 逆轉序列的遞歸實作

先用 Haskell 實作做草稿（因為比較自然），數組版長這樣

reverse' :: [a] -> [a]
reverse' []     = []
reverse' (x:xs) = reverse' xs ++ [x]      

在 JavaScript 裡，數組和字元串都有

slice

和

concat

，是以可以寫成兩種“序列”（在離散數學之類的領域裡經常把兩者合稱為 sequence） 都支援的版本。

Note:

• Array.prototype.slice()

• Array.prototype.concat()

• String.prototype.slice()

• String.prototype.concat()

均出現于 ECMAScript 3，實作于 JavaScript 1.2

對應的 JS 實作如下，把 base case 設定到序列長度小于 1 的時候，這樣縮減了一步遞歸。相比而言還是 Haskell 版比較一目了然啊……

function recursiveReverse(seq) {
    return seq.length > 1 ?
        recursiveReverse(seq.slice(1)).concat(seq.slice(0, 1)) : seq;
}      

經過測試，數組和字元串都能通過。

2. 尾遞歸實作

Haskell 版本長這樣，用一個

ret

傳遞已完成的部分：

reverse' :: [a] -> [a]
reverse' list = rev list []
  where rev []     ret = ret
        rev (x:xs) ret = rev xs (x:ret)      

對應的 JS 版本，這裡用

slice(0, 0)

來避開類型檢查建立空序列。

function tailReverse(seq) {
    return (function rev(seq, ret) {
        return seq.length > 0 ?
            rev(seq.slice(1), seq.slice(0, 1).concat(ret)) : ret;
    })(seq, seq.slice(0, 0));
}      

3. 使用 ES6 新特性的遞歸版本

ES6 引入了 destructuring assignment 和 spread operator，這樣就可以部分地使用函數式程式設計中的模式比對（pattern matching）。不過我在 ES6 的新特性裡還沒找到能在文法層面上讓 JS 的函數像 Haskell 那樣将模式比對融合進重載（overloading）的組合（destructuring assignment 本身就是模式比對的一個子集而已），要重載還是得用目前 JS 裡最常見的解決辦法——if-else或者三目運算符配合類型檢查。這裡因為用法簡單，直接三目運算符就行。

配合 ES6 新特性實作的簡單遞歸版如下，因為 JS 裡數組和字元串沒有通用的功能類似

append

（往後加元素并傳回新的數組）的函數，懶得折騰類型檢查了，是以這裡隻實作了數組版（由于 destructuring assignment + spread operator 的組合

[x, ...xs]

會将字元串分割成

第一個字元，[其他字元組成的數組]

，是以直接給下面的函數傳入字元串之後再将傳回值

join

回字元串也可以達到一樣的效果）。

function pmReverse([x, ...xs]) {
    return typeof x === "undefined" ? [] : pmReverse(xs).concat([x]);
}      

經過測試，數組都可以正常逆轉（隻有在浏覽器打開 ES6 特性的時候這個頁面才會正常跑掉這個版本的測試，不然就隻有一個 alert）。

4. 使用 ES6 新特性的尾遞歸版本

function pmTailReverse(list) {
    return (function rev([x, ...xs], ret) {
        return typeof x === "undefined" ? ret : rev(xs, [x].concat(ret));
    })(list, []);
}      

關于測試頁面

為了友善寫了一個小小的測試架構，參見源代碼。

因為不支援 ES6 的浏覽器在解析 ES6 特性的代碼時會出文法錯誤，用 try-catch 抓不了，這裡用了

window.onerror

來捕捉并提示。不知為何我的 Chrome 開了實驗性 JS 依然打不開 ES6 支援…… FireFox 倒是預設就能用。