Pythonで関数プログラミング流リスト操作を行うで、基本的な関数の準備もできたので、関数プログラミングらしいものを体験してみよう。 まずConsリストの長さを求める関数lengthは、foldlを使って次のように簡単に書ける。

def length(cons):
    def inc(a, b):
        return a+1
    return foldl(inc, 0, cons)

Consリストには依存しないが、繰り返しを行う関数repeatWhile(p, f, a)を作ってみよう。p、fは関数で、pはaを引数に真偽値を返す述語(predicate)関数である。関数repeatWhileは、p(a)が真の間a = f(a)を繰り返す関数だ。再帰バージョンは次のようになる。

# 再帰バージョン
def repeatWhile(p, f, a):
    if p(a):
        return repeatWhile(p, f, f(a))
    return a

この再帰バージョンの方が関数プログラミング的ではあるが、再帰呼び出しでは繰り返し回数が多いとスタックオーバーフローになるので、ループに書き直そう。

# ループバージョン
def repeatWhile(p, f, a):
    while p(a):
        a = f(a)
    return a

関数repeatWhileができたら、関数repeatUntilを作るのは簡単である。関数repeatUntilは、p(a)が偽の間a = f(a)を繰り返す関数だ。

def repeatUntil(p, f, a):
    return repeatWhile(lambda x: not p(x), f, a)

関数repeatUntilができたら、Consリストの最初のn個を捨てる関数dropを作ることができる。

def drop(n, l):
    return repeatUntil(lambda x: x[0] <= 0 and not x[1].isNil(),
                       lambda y: (y[0]-1, y[1].next()), (n, l))[1]

Consリストのn番目の要素の値を取得する関数は次のように作れる。

def at(n, l):
    return take(1, drop(n, l)).value()

次に、二つのConsリストを結合する関数concatを実装しよう。

def concat(a, b):
    if a.isNil():
        return b
    else:
        return Cons.lazyCons(a.value(), lambda: concat(a.next(), b))

ここまでをみると、かなり無駄なくプログラムを再利用できている。しかも、各関数の実装は至極単純だ。しかし、もう少し凝ったプログラムでなければ本当に関数プログラムの生産性が高いか検証できない。別に関数プログラミングでなくたってこの程度のプログラムは十分単純に書ける。最終的には、入力処理(入力処理はさまざまな入力に対して適切に対処しなければならないので、プログラム全体の中でもかなり面倒な処理になりがち)が簡潔に書けなければ、及第点を与えることができないと思う。

さて、今度はPythonの関数mapとfilter相当を実装してみよう。関数consMapは次のようになる。

def consMap(f, cons):
    if cons.isNil():
        return cons
    return Cons.lazyCons(f(cons.value()), lambda : consMap(f, cons.next()))

print strCons(take(10, consMap(lambda x: x*2, seq())))
⇒[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

関数consFilterの実装は次のようになる。

# 再帰バージョン
def consFilter(p, cons):
    if cons.isNil():
        return cons
    v = cons.value()
    if p(v):
        return Cons.lazyCons(v, lambda : consFilter(p, cons.next()))
    return consFilter(p, cons.next())

print strCons(take(10, consFilterR(lambda x: x % 2 == 0, seq())))
⇒[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

この関数consFilterの再帰バージョンは、述語関数pが偽を返す要素が多数連続するとスタックを使い果たす。そこで、いつものようにループに書き直そう。

# ループバージョン
def consFilter(p, cons):
    while not cons.isNil():
        v = cons.value()
        if p(v):
            return Cons.lazyCons(v, lambda : consFilter(p, cons.next()))
        cons = cons.next()
    return cons

さて、ここらで汎用的な関数ではなく、少し実用的な関数を作ってみよう。純粋関数言語の生産性の高さを示すのによく出てくるクイックソートを実装してみよう。

def qsort(cons, comp=cmp): # quick sort
    if cons.isNil():
        return cons
    v = cons.value()
    n = cons.next()
    return concat(qsort(consFilter(lambda x: comp(x, v) < 0, n), comp),
                  Cons.lazyCons(v, lambda : qsort(consFilter(lambda x: comp(x, v) >= 0, n), comp)))

def rand(n): # 乱数発生関数
    import random
    while True:
        yield int(random.random()*n)

randList = Cons.toCons(iter(rand(20)))
print strCons(take(10, randList))
⇒[14, 10, 15, 9, 7, 4, 6, 10, 2, 12]
print strCons(qsort(take(10, randList)))
⇒[2, 4, 6, 7, 9, 10, 10, 12, 14, 15]

このクイックソートの実装と、Pythonによるクイックソートの実装を比べてみると...特に大差ない。これは、関数型言語の生産性が大した事ないというよりも、Pythonが十分関数型言語になっていると考えたほうがいいかもしれない。ひとつ大きな違いがあるとしたら、Consリストを使った実装は、遅延評価を行っていることだ。たとえば、数列の中から最小値を求める関数を次のように実装できる。

def consMin(l):
    sorted = qsort(l)
    if sorted.isNil():
        return None
    return sorted.value()

この関数では、ソート済みリストの先頭の要素しか必要としないので、関数qsortは、実際のところConsリストをすべてソートしない(元の数列の順序によっては完全なソートをする羽目になるが...)。

次はフィボナッチ(fibonacci)数列を求める関数を書いてみよう。遅延リストの遅延評価の式の中で自分自身のノードを参照するので、少し不恰好だ。しかし、先行する2つのフィボナッチ数列を追いかけながら数列を求め続けるというのは、興味深い実装方法ではある。

def fib():
    def _fib(f1, f2):
        result = Cons.lazyCons(f1.value() + f2.value(), None)
        result._next = lambda : _fib(f2, result) # 遅延評価の式の中で自身のノード(result)を参照するため
        return result
    return Cons.cons(0, Cons.lazyCons(1, lambda : _fib(fib(), drop(1, fib()))))

print strCons(take(1, drop(1000, fib())))

しかし、シンプルさ、分かりやすさを考えると素直に次のように書きたい。

def pyfib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b

print strCons(take(10, Cons.toCons(pyfib())))

以上、関数をいくつか書いてみると、見えてくるものもある。Pythonで関数プログラミングは可能だが、Pythonは既に関数プログラミングをある程度取り入れているので、Python流にコードを書いても生産性は高い。Pythonは関数プログラミングに特化した言語ではないので、当然といえば当然。また、同様の理由で、純粋関数型言語ほど遅延評価の記述や実行は効率的ではない。たとえば、Cleanなどではスタックオーバーフローにならない再帰呼び出しも、Pythonではスタックオーバーフローになるのでループで書き直さなければならない。純粋関数型言語とPythonでは、評価・実行の仕組みがそもそも違う。

逆にPythonで関数プログラミングを行うメリットは、モナドや一意性型属性といった難しい概念を習得しなくても、馴染みのある方法で入出力を行うことができる(代わりに評価の順序や参照透明性などを気にしなければならないが...)。