頭尾成對

December 14, 2021

在〈代數資料型態〉最後談到，nil、con、head、tail 還可以進一步使用箭號函式定義，直到完全都使用箭號函式表示為止，暫時使用 JavaScript 的陣列語法，只是為了不要在一開始就讓事情變得複雜：

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

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

定義 pair

如果不想使用 [] 來定義 List，那要怎麼使用箭號函式來定義 List 呢？仔細看看，每個 List 都有頭、尾，也許只要有個成對的結構，就可以定義 List？那就來定義個 pair 吧！

let pair = l => r => f => f(l)(r);

成對的結構會有左值與右值，因此有 l、r 代表左與右，這可以理解，那第三個參數 f 是怎麼一回事？以 pair(1)(2) 呼叫後，會傳回一個函式，而這個函式形成 Closure 攜帶了 l 與 r，因此，pair(1)(2) 的傳回值為 f => f(1)(2)，確實攜帶了左值與右值的資訊，而且別忘了，JavaScript 支援一級函式，也就是函式也是值，pair 以函式作為傳回值並不奇怪。

由於 pair(1)(2) 的傳回值為 f => f(1)(2)，這表示 f 必須是個函式，可以接受 1，傳回值接著接受 2，如果 f 實際上是 l => r => l 會如何？(l => r => l)(1)(2) 將 1 套用至 l，結果會是 (r => 1)(2)，接著將 2 套用至 r，結果傳回 1，這不就是取到 pair(1)(2) 的左值嗎？

也就是 pair(1)(2)(l => r => l) 可以取到 pair(1)(2) 的左值，如果 p 代表 pair(1)(2)，p(l => r => l) 就可以取到左值，那就可以定義一個 left 函式了：

let left = p => p(l => _ => l);

對於 left 來說，實際上不關心右值，因此用個 _ 來表示就可以了，類似地，由於 pair(1)(2) 的傳回值為 f => f(1)(2)，如果 f 如果是 l => r => r，也就是一定傳回 r，就可以用來取得右值，因此可以定義一個 right 函式：

let right = p => p(_ => r => r);

nil、con、head、tail

有了 pair、left、right，現在可以重新定義 nil、con、head 與 tail 了：

let nil = pair(undefined)(undefined);
let con = head => tail => pair(head)(tail);
let head = lt => left(lt);
let tail = lt => right(lt);

實際上 head 是 left 別名，而 tail 是 right 的別名，因此也可以寫為：

let nil = pair(undefined)(undefined);
let con = head => tail => pair(head)(tail);
let head = left;
let tail = right;

在〈代數資料型態〉最後看到 map(list(elems(1)(2)(3)))(elem => elem - 1) 可以轉換為：

(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)`

然而留下了 nil、con、head 與 tail 未轉換，現在可以進一步處理了，轉換結果會是：

(f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(map => lt => f => (lt => (lt => (p => p(l => _ => l))(lt))(lt) === undefined)(lt) ? ((l => r => f => f(l)(r))(undefined)(undefined)) : (head => tail => (l => r => f => f(l)(r))(head)(tail))(f((lt => (p => p(l => _ => l))(lt))(lt)))(map((lt => (p => p(_ => r => r))(lt))(lt))(f)))((elems => (lt => (f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rev => r => l => (lt => (lt => (p => p(l => _ => l))(lt))(lt) === undefined)(l) ? r : rev((head => tail => (l => r => f => f(l)(r))(head)(tail))((lt => (p => p(l => _ => l))(lt))(l))(r))((lt => (p => p(_ => r => r))(lt))(l)))((l => r => f => f(l)(r))(undefined)(undefined))(lt))(elems()))((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rcon => tail => head => head === undefined ? tail : rcon((head => tail => (l => r => f => f(l)(r))(head)(tail))(head)(tail)))((l => r => f => f(l)(r))(undefined)(undefined))(1)(2)(3)))(elem => elem - 1)

List 翻譯機

然而，這樣已經完全看不出結果會是什麼了對吧！來借助一下 JavaScript 寫個 array，將 List 轉換為 JavaScript 陣列：

function array(lt) {
    let pair = l => r => f => f(l)(r);
    let left = p => p(l => _ => l);
    let right = p => p(_ => r => r);

    let nil = pair(undefined)(undefined);
    let con = head => tail => pair(head)(tail);
    let head = left;
    let tail = right;

    let isEmpty = lt => head(lt) === undefined;

    function arr(acc, l) {
        if(isEmpty(l)) {
            return acc;
        } else {
            return arr(acc.concat([head(l)]), tail(l));
        }
    }
    return arr([], lt);
}

這個函式跟想要探討的 lambda 演算沒有關係，只是方便觀看轉換結果是不是正確而已，為了令其成為可獨立運作之函式，pair 等定義也寫在其中了，有了這個 array 函式，要觀看結果就方便多了。例如結合 array 與以下程式，結果會顯示 [ 0, 1, 2 ]：

console.log(array((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(map => lt => f => (lt => (lt => (p => p(l => _ => l))(lt))(lt) === undefined)(lt) ? ((l => r => f => f(l)(r))(undefined)(undefined)) : (head => tail => (l => r => f => f(l)(r))(head)(tail))(f((lt => (p => p(l => _ => l))(lt))(lt)))(map((lt => (p => p(_ => r => r))(lt))(lt))(f)))((elems => (lt => (f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rev => r => l => (lt => (lt => (p => p(l => _ => l))(lt))(lt) === undefined)(l) ? r : rev((head => tail => (l => r => f => f(l)(r))(head)(tail))((lt => (p => p(l => _ => l))(lt))(l))(r))((lt => (p => p(_ => r => r))(lt))(l)))((l => r => f => f(l)(r))(undefined)(undefined))(lt))(elems()))((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rcon => tail => head => head === undefined ? tail : rcon((head => tail => (l => r => f => f(l)(r))(head)(tail))(head)(tail)))((l => r => f => f(l)(r))(undefined)(undefined))(1)(2)(3)))(elem => elem - 1)))

分享到 LinkedIn 分享到 Facebook 分享到 Twitter