頭尾成對

December 14, 2021

在〈代數資料型態〉最後談到,nilconheadtail 還可以進一步使用箭號函式定義,直到完全都使用箭號函式表示為止,暫時使用 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);

成對的結構會有左值與右值,因此有 lr 代表左與右,這可以理解,那第三個參數 f 是怎麼一回事?以 pair(1)(2) 呼叫後,會傳回一個函式,而這個函式形成 Closure 攜帶了 lr,因此,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

有了 pairleftright,現在可以重新定義 nilconheadtail 了:

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

實際上 headleft 別名,而 tailright 的別名,因此也可以寫為:

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

然而留下了 nilconheadtail 未轉換,現在可以進一步處理了,轉換結果會是:

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