Ｚコンビネーター、ふたたび

９月１２日木曜日、晴れ

夜の『アンダースタンティング　コンピュテーション』の勉強会で、いくたびか目のＺコンビネーターを理解しようという試みに、ちょっと頑張ってみる。

＊　＊　＊

再帰関数を、自分の名前を参照せずに定義するために使えるＺコンビネーターというものがある。（もう少し単純なＹコンビネーターというものもあるけれど、世の中の言語は大抵正格評価のため使えない）

こちらに書いたとおり定義は単純。

「f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))」がＺコンビネーターだ。
「関数を受け取って、一引数の関数を返す」という高階関数を受け取って再帰呼び出し関数を定義するヘルパーとして機能する。

＊　＊　＊

C++ の lambda で実装できないか試してみたけれど、これは通らなかった。

Haskell でも書いてみたけれど、ダメ。

z = \f -> let g = \x -> f (\y -> x x y) in g g

<interactive>:1:25: error:
   • Couldn't match expected type ‘(t2 -> t3) -> t4’
                 with actual type ‘p’
       because type variables ‘t2’, ‘t3’, ‘t4’ would escape their scope
     These (rigid, skolem) type variables are bound by
       the inferred type of g :: (t1 -> t2 -> t3) -> t4
       at <interactive>:1:15-39
   • In the expression: f (\ y -> x x y)
     In the expression: \ x -> f (\ y -> x x y)
     In an equation for ‘g’: g = \ x -> f (\ y -> x x y)
   • Relevant bindings include
       x :: t1 -> t2 -> t3 (bound at <interactive>:1:20)
       g :: (t1 -> t2 -> t3) -> t4 (bound at <interactive>:1:15)
       f :: p (bound at <interactive>:1:6)
       z :: p -> t (bound at <interactive>:1:1)

<interactive>:1:36: error:
   • Occurs check: cannot construct the infinite type:
       t1 ~ t1 -> t2 -> t3
   • In the first argument of ‘x’, namely ‘x’
     In the expression: x x y
     In the first argument of ‘f’, namely ‘(\ y -> x x y)’
   • Relevant bindings include
       y :: t2 (bound at <interactive>:1:29)
       x :: t1 -> t2 -> t3 (bound at <interactive>:1:20)
       g :: (t1 -> t2 -> t3) -> t4 (bound at <interactive>:1:15)

＊　＊　＊

手作業で考えてみる。
Ｚの定義は以下のとおり。

Z = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))

ここで関数ｆにＺを適用（つまり代入して書き換え）すると次のようになる。

Z(f)
= (x => f(y => x(x)(y))) (x => f(y => x(x)(y)))

これは左の (x => f(y => x(x)(y))) がｘという引数を取る関数で、このｘとして右の (x => f(y => x(x)(y))) を渡している、ということ。だからこうなる。（左に出てくるｘを (x => f(y => x(x)(y))) で置き換える）

= f(y => (x => f(y => x(x)(y))) (x => f(y => x(x)(y))) (y))

さて、ここで関数ｆに渡している引数を注意深くみると……

= f(y => Z(f)(y))

ここでＺを適用する関数ｆをこんなものだと考えてみる。

f = zf => x => x == 0 ? 1 : x * zf(x-1)

「Z(f) = f(y => Z(f)(y))」ということを先に確かめている。ここで Z(f) にあらためて factorial という名前をつけてみると、

factorial = f(y => factorial(y))

だとわかる。 f の定義に戻って、第一引数 zf が受け取る関数は「y => factorial(y)」。

factorial
= f(y => factorial(y))
= x => x == 0 ? 1 : x * (y => factorial(y))(x-1)
= x => x == 0 ? 1 : x * factorial(x-1)

この定義は factorial が引数 x を受け取って値「x == 0 ? 1 : x * factorial(x-1)」を返す、と言っている。馴染みのスタイルで書くなら、

function factorial(x) { return x == 0 ? 1 : x * factorial(x-1); }

ということだ。ごく当たり前の再帰関数定義になった。