原始帰納的関数のPythonでの表現

原始帰納的関数の定義がよくわからなかったので数学事典で調べてみた。数学語で書いてあるけど、Python語に翻訳してみると:

def inc(x):
    return x + 1

def constant(*args):
    return CONSTANT

def choice_K(*args):
    return args[K]

という関数からスタートして(constantとchoiceは返す定数や選ぶ引数の位置によって無数に存在する)

def apply_funcs(*args):
    return REDUCE_FUNC(
        MAP_FUNC_TABLE[0](*args), 
        MAP_FUNC_TABLE[1](*args), ...)

def recursive(*args):
    head = args[0]
    tail = args[1:]
    if head == 0:
        return WHEN_ZERO_FUNC(tail)
    else:
        return OTHERWISE(y, recursive(y - 1, *tail), *tail)

という関数を繰り返し適用して作ることのできるもの、となる。

さて、実際にコードを書いて試してみるために、上のざっくりとしたPython訳をしっかりした訳にしてみよう。主に「constantとchoiceは返す定数や選ぶ引数の位置によって無数に存在する」という日本語で書いてある部分がダメなので、これをコードで表現する。パラメータによって無数に定義の存在する関数ってのはPython語ではクラスっていう。

# -*- coding: utf-8 -*-

def inc(x):
    return x + 1

class Constant:
    def __init__(self, CONSTANT):
        self.CONSTANT = CONSTANT
    def __call__(self, *args):
        return self.CONSTANT

class Choice:
    def __init__(self, WHERE):
        self.WHERE = WHERE
    def __call__(self, *args):
        return args[self.WHERE]

class ApplyFuncs:
    def __init__(self, REDUCE_FUNC, MAP_FUNCS):
        self.REDUCE_FUNC = REDUCE_FUNC
        self.MAP_FUNCS = MAP_FUNCS
    def __call__(self, *args):
        return self.REDUCE_FUNC(
            *[self.MAP_FUNCS[i](*args) for i in range(len(self.MAP_FUNCS))]) 

class Recursive:
    def __init__(self, WHEN_ZERO_FUNC, OTHERWISE):
        self.WHEN_ZERO_FUNC = WHEN_ZERO_FUNC
        self.OTHERWISE = OTHERWISE
    def __call__(self, *args):
        head = args[0]
        tail = args[1:]
        if head == 0:
            return self.WHEN_ZERO_FUNC(*tail)
        else:
            return self.OTHERWISE(head, self(head - 1, *tail), *tail)

# x + yを定義する
add = Recursive(
    # xが0ならyそのもの
    WHEN_ZERO_FUNC=Choice(0),
    # xが0でないならadd(x, y)はinc(add(x - 1, y))
    OTHERWISE=ApplyFuncs(
        REDUCE_FUNC=inc,
        MAP_FUNCS=[Choice(1)]
        ))

print add(2, 3) #-> 5
""" MEMO
add(2, 2)
-> OTH(2, add(1, 2), 2)
-> OTH(2, OTH(1, add(0, 2), 2), 2)
-> OTH(2, OTH(1, 2, 2), 2)
-> OTH(2, inc(Choice1(1, 2, 2)), 2)
-> OTH(2, inc(2), 2)
-> OTH(2, 3, 2)
-> inc(Choice1(2, 3, 2))
-> inc(3)
-> 4
"""

とりあえず、足し算が原始帰納的関数であることまではコードで表現できた。このパズルはけっこう面白い。足し算は何とかなったけど、他にもx * y, x ^ y, x!, min(x, y), max(x, y), abs(x - y), x == y, x < y, xはyで割り切れる, xは素数である, x番目の素数, なども全部原始帰納的だそうな。

---

掛け算も作った。

# x * yを定義する
mul = Recursive(
    # xが0なら0
    WHEN_ZERO_FUNC=Constant(0),
    # xが0でないならmul(x, y)はadd(x - 1, y) + yで、
    # OTH(x, add(x - 1, y), y)の最初の引数を無視して残りにaddを使うために
    # RecursiveのWHEN_ZEROを使う
    OTHERWISE=Recursive(
        WHEN_ZERO_FUNC=add,
        OTHERWISE=Choice(1)))

print mul(5, 7) #-> 35