簡單是非

December 15, 2021

從〈是的!不是!〉之後,在需要分支判斷時,會使用 yesnowhen,而 yesno 具有惰性的效果,lambda 演算並不用特別去考慮惰性,實現惰性,只是為了能順利在 JavaScript 環境中運行,以便檢視運算結果來確認正確性,而惰性的實現方式也可以符合 lambda 表示式罷了。

雖然實現了惰性,然而,對於簡單的需求,卻也因此變得麻煩了,例如,如果只是要根據條件傳回 $1$2,也被迫一定要寫為 when(yes)(_ => $1)(_ => $2),而不是簡單地寫為 when(yes)($1)($2),實際的例子就是 not,它被定義為 b => b(_ => no)(_ => yes),而不是 b(no)(yes)

然而在〈是的!不是!〉中談過,將 yesno 暫時實現為 x => y => x()x => y => y(),可以令程式的撰寫直覺一些,事情也不會一開始就變得複雜。

yes/no

現在,為了能在根據條件傳回 $1$2 的場合中,簡單地使用 when(yes)($1)($2),必須將 yesno 改變定義為:

let yes = x => _ => x;
let no = _ => y => y; 

這麼一來,not 就可以定義為:

let not = b => b(no)(yes);

重構

然而,這樣會讓 lensummap 等運算不正確,例如:

// 這一行還不會真的運算出結果
let lazy_len = len(con($2)(con($1)(nil)));

// 這一行才會真的求值
console.log(natural(lazy_len(no_use)));

由於 when 現在只是依 yesno 傳回箭號函式,而不是執行它,len 傳回的值不會是 $0$1 這類的數值,而是傳回箭號函式,然而,呼叫傳回的箭號函式結果會是 1,這並不正確,檢查一下 len 的定義:

let len = l => when(isEmpty(l))
                    (_ => $0)
                    (_ => add($1)(len(tail(l))));

con($2)(con($1)(nil)) 傳入後,isEmpty(l) 會是 no,因此傳回的是 _ => add($1)(len(tail(con($2)(con($1)(nil))))),實際運行求值時,必然會要求 len(tail(con($2)(con($1)(nil)))) 的結果,也就是 len(con($1)(nil)),此時傳回 _ => add($1)(len(tail(con($1)(nil)))),也就是最後運算的結果,其實就是 add($1)(_ => add($1)(len(tail(con($1)(nil))))) 進行運算的結果!嗯?哪邊怪怪的?

len 的定義,遞迴終止時的 _ => $0 沒有被傳回,並非符合遞迴終止條件才傳回結果,無巧不巧地,add($1)(_ => add($1)(len(tail(con($1)(nil))))) 是可以被 natural 計算為 1 的結果,無論傳入多長的 List,結果一定顯示 1。

原因在於之前的 no 被指定的第二個引數會被執行,現在呼叫 len 時,指定的第二個引數並沒有執行,因而0實際上沒有進行遞迴,必須改為底下才可以:

let len = l => when(isEmpty(l))
                    (_ => $0)
                    (_ => add($1)(len(tail(l))))(no_use);

正確的運算結果,應該是 len(tail(con($1)(nil)))) 必須傳回數字結果,若是如此就必須是 len(tail(con($1)(nil))))(no_use),也就是 len 的定義必須改成:

let len = l => when(isEmpty(l))
                    (_ => $0)
                    (_ => add($1)(len(tail(l))(no_use)));

其他遞迴函式,也必須做類似修改,運算結果才會是正確的,來整理全部的程式如下:

let y = f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)));

let unit = _ => _;
let no_use = unit;

let yes = x => _ => x;
let no = _ => y => y; 
let when = unit;

let not = b => b(no)(yes);

let pair = l => r => f => f(l)(r);
let left = p => p(l => _ => l);
let right = p => p(_ => r => r);

let nil = _ => yes;
let con = h => t => pair(h)(t);
let head = left;
let tail = right;

let is_nil = l => l(_ => _ => no);
let isEmpty = is_nil;

let $0 = _ => x => x;
let $1 = f => x => f(x);
let $2 = f => x => f(f(x));
let $3 = f => x => f(f(f(x)));
let is_$0 = n => n(_ => no)(yes);

let $$ = _ => _ => yes;
let is_$$ = n => n(_ => no)(no);

let succ = n => f => x => f(n(f)(x));
let add = m => n => n(succ)(m);

let pair_succ = p => pair(right(p))(succ(right(p)));
let prev = n => left(n(pair_succ)(pair($0)($0)));
let sub = m => n => n(prev)(m);

let len = y(len => l => when(isEmpty(l))
                            (_ => $0)
                            (_ => add($1)(len(tail(l))))(no_use));

let sum = y(sum => l => when(isEmpty(l))
                    (_ => $0)
                    (_ => add(head(l))(sum(tail(l))))(no_use)); 

let rcon = y(rcon => t => h => when(is_$$(h))
                                    (_ => t)
                                    (_ => rcon(con(h)(t)))(no_use));

let rev = y(rev => r => l => when(isEmpty(l))
                                    (_ => r)
                                    (_ => rev(con(head(l))(r))(tail(l)))(no_use));

let reverse = l => rev(nil)(l);

let elems = rcon(nil);

let list = es => reverse(es($$));

let map = y(map => l => f => when(isEmpty(l))
                                    (_ => nil)
                                    (_ => con(f(head(l)))(map(tail(l))(f)))(no_use));

let lt = list(elems($1)($2)($3));
let lt2 = map(lt)(elem => sub(elem)($1));

console.log(natural(len(lt)));
console.log(natural(sum(lt)));
console.log(array(lt2));

function natural(n) {
    return n(i => i + 1)(0);
}

function array(lt) {
    function arr(acc, l) {
        return when(isEmpty(l))
                    (_ => acc)
                    (_ => arr(acc.concat([natural(head(l))]), tail(l)))(no_use);
    }
    return arr([], lt);
}