PythonでCleanやHaskellのリスト相当を準備で、関数プログラミングの準備ができたので、いよいよ関数プログラミングにチャレンジしてみよう。その前に、「関数プログラミングって何がどういいの?」という人は、 なぜ関数プログラミングは重要かを一読しておこう。

まず、Consリストを生成するいくつかの関数を定義しよう。手始めに、指定された値の無限長のConsリストを生成する関数repeat()を作る。

def repeat(v):
    return Cons.lazyCons(v, lambda: repeat(v)) # 一見再帰呼び出しのようだがそうではない

次に等差数列を生成する関数を定義する。

def seq(start=0, step=1):
    return Cons.lazyCons(start, lambda: seq(start+step, step))

Pythonのzip関数に類似した、二つのConsリストを、二つの要素のタプルの単一のConsリストに変換するzipCons関数を定義する。

def zipCons(a, b):
    if a.isNil() or b.isNil(): # どちらかのConsリストが終了するまで
        return Cons.nil()
    return Cons.lazyCons((a.value(), b.value()),
                         lambda : zipCons(a.next(), b.next()))

次に、Consリストを操作する基本的な関数foldrを定義しよう。なぜ関数プログラミングは重要かでは、reduceという名で定義されている関数だ。foldrの実行例を示す。

def add(a, b):
	return a + b

foldr(add, 0, Cons.toCons(iter([1, 2, 3])))

上記の呼び出しは、次のように評価される。

add(1, add(2, add(3, 0)))

上記の式を見てわかるように、リストが右(right)から畳み込まれる(fold)。だからCleanでは、関数名はfoldrと呼ばれる。 関数foldrの実装は次のようになる。

def foldr(f, x, cons):
    if cons.isNil():
        return x
    else:
        return f(cons.value(), foldr(f, x, cons.next()))

foldrは、Consリストを右から畳み込むのでConsリストが長すぎるとスタックオーバーフローを起こす。これは、純粋関数言語のCleanでも同様のことが起きる。Cleanで下記のように無限に続く整数リストを足していくと("[1..]"は1,2,…という無限に続くリストを表す)、"Stack overflow."となる。

Start = foldr (+) 0 [1..]

同じようにConsリストを畳み込む関数として、関数foldlを考えてみよう。名前から想像できるようにこの関数はConsリストを左から畳み込む。

foldl(add, 0, Cons.toCons(iter([1, 2, 3])))

上記の呼び出しは、次のように評価される。

add(add(add(0, 1), 2), 3)

foldlは、Consリストの先頭から処理を行うため、無限に続くConsリストに対して(処理を完了することはできないが)処理を開始することができる。関数foldlを実装してみよう。

# 再帰バージョン
def foldl(f, x, cons):
    if cons.isNil():
        return x
    return foldl(f, f(x, cons.value()), cons.next())

このfoldlの実装は、foldr同様再帰呼び出しを行っているため、長いリストにfoldlを適用するとスタックオーバーフローとなる。これはかなり困ったことだ。幸い、左から畳み込む場合、再帰を使わなくても計算を行うことができる。上記の下線部に注目しよう。下線部の計算が済めば、このConsノードに関する文脈を保存する必要はない。一方foldrの場合は、右側のConsノードに対する計算が終わった後現在のノードに関する計算を行うため、現在のノードを処理する文脈を保存する必要がある。foldlは行きがけに計算する、foldrは帰りがけに計算する関数といえるだろう。行きがけに計算する再帰は末尾再帰(再帰呼び出しが末尾に来るから)と呼ばれる。C言語とかでも条件が整えばgccは末尾再帰をループに展開する最適化を行い、スタックを消費しないコードを出力する。末尾再帰はループで書き直すことができるということだ。foldlをループを使って再実装してみよう。

# ループバージョン
def foldl(f, x, cons):
    while not cons.isNil():
        x = f(x, cons.value())
        cons = cons.next()
    return x

以上で、Consリストを操作する基本的な関数群が出来上がった。早速これらを使っていくつか関数を作ってみよう。まず、Consリストを読みやすい文字列に変換するstrCons関数を作ろう。

def strCons(cons):
    def sep():
        return Cons.cons("", repeat(", "))
    def concat(s, v):
        return s + v[0] + str(v[1])
    return foldl(concat, "[", zipCons(sep(), cons)) + "]"

最後に、Consリストの先頭のnノードからなるConsリストを返す関数take()を作る。これまで、無限に続くConsリストを扱ってきたので、この関数がないといつまでたっても処理が終わらないからね。 これで、やっとこれまで作ってきたConsリストを操作する関数の動作を確認することができる。

def take(n, cons):
    if n > 0 and not cons.isNil():
        return Cons.lazyCons(cons.value(), lambda: take(n-1, cons.next()))
    return Cons.nil()

いくつか動作確認してみよう。

print strCons(take(10, repeat("*")))
⇒[*, *, *, *, *, *, *, *, *, *]
print strCons(take(10, seq(10, 2)))
⇒[10, 12, 14, 16, 18, 20, 22, 24, 26, 28]
print strCons(take(5, zipCons(seq(1), seq(10, 2))))
⇒[(1, 10), (2, 12), (3, 14), (4, 16), (5, 18)]

このように、Pythonでもかなり関数型言語的な記述ができることがわかる。今のところどの関数もシンプルに実装できている。しかし、関数プログラミングに慣れていない頭には、シンプルだけど難しく感じられる。上記のコードを書いていると、普段使っていない脳細胞を使っている感じがする。