はじめに
「関数型プログラミングとは何か？」や「関数型プログラミングの仕方」についての記事は既に沢山あるのでそちらを参考にしてください。
この記事は関数型プログラミングで主要テクニックとしてよく取りあげられるmap, filter, reduceの3つの関数を自ら作ることを通じて関数型プログラミングに親しむことを目標とします。
ただし組み込み関数として提供されているmap関数が内部でどのように定義されているのかを解き明かすものではありません。
例えばmap関数は実際の所、引数としてiterable objectを受け取り、返り値はiteratorとなっているのでgeneratorで次のように簡単に定義できます。
def my_map(f, iterable):
for it in iterable:
yield f(it)
しかし本記事ではgeneratorなどを使わず、関数型プログラミングらしく再帰関数で定義したいと思います。そのため効率性とかは度外視しているので実用的なものではない事だけ予めご了承ください。また分かりやすさを優先させるため、iterable objectでなくリストを想定しています。
iteratorやgeneratorを絡めてmap関数などを理解したい人は、関数型プログラミング HOWTOを読むことをお勧めします。
使用言語はpythonです。
対象読者
- 組み込み関数のmap, filter, reduceを何となく使っている人
- 関数型プログラミングに興味がある人
関数を自分で作ってみよう
map
map関数では第一引数には関数、第二引数にはリストを渡します。
組み込みのmap関数を使ってリストの各要素を2乗させるプログラムは次の通りです。
>>> list(map(lambda x: x*x, [1,2,3,4,5]))
[1, 4, 9, 16, 25]
自作mapは次のようになります。
# 入力：関数とリスト
# 出力：全要素に関数が適用されたリスト
def my_map(f, lst) -> list:
if len(lst) <= 0: # リストの空チェック
return [] # 空リストを返す
return [f(lst[0])] + my_map(f, lst[1:]) # 先頭要素のみに関数を適用し、残りのリストは再帰呼び出しの引数に使う
print(my_map(lambda x: x*x, [1,2,3,4,5])) # [1, 4, 9, 16, 25]
少し分かりにくいかもしれませんが、関数型プログラミングらしく再帰関数で定義しています。
先頭要素のみを取り出して関数の引数に渡して、残っているリストで再帰させています。
関数型プログラミングは関数でプログラムが構成されています。
関数型プログラミングにおいて、関数を定義する際に大切なのは関数内部の処理手順以上に、入力と出力だと思っています。
このmy_map関数を例に考えると、入力が関数とリストで出力が関数が適用された後のリストです。出力が決まれば関数内部の処理をどうすれば良いかの見通しが立ちます。
[f(lst[0])]
の部分でリストの先頭要素のみに対して関数を適用しています。出力はリストなので括弧を付けてリストにしています。
このリストに
my_map(f, lst[1:])
を結合させています。my_mapの出力はリストなのでリスト同士を足し合わせて出力をリストにしています。
再帰呼び出しで自分自身を呼び出していますが、引数に渡すリストが1要素分だけ短くなるので再帰がいずれ停止することが保証されています。
言葉では伝えにくいのですが、my_mapの出力がリストであることが自分自身の再帰によって保証されていることが美しいですよね。
このようにどのような入力に対して、何を出力してほしいのかを意識して関数を定義していく事が関数型プログラミングを理解する上で重要かもしれません。返り値の型を書くことはよくあることですが、型だけじゃなくて関数の入力、出力が何かを言語化しておくと分かりやすいのでお勧めです。
filter
filter関数もmapと同様に第一引数に関数を、第二引数にリストを渡します。
組み込み関数を使った例は次の通りです。
>>> list(filter(lambda x: x > 0, [-2, 4, -6, 6, 7, -10]))
[4, 6, 7]
この例ではリストから正の数だけ取り出しています。
自作filterは次の通りになります。
# 入力：フィルターとなる関数と対象となるリスト
# 出力：フィルターを通り抜けた要素からなるリスト
def my_filter(pred, lst) -> list:
if len(lst) <= 0:
return []
if pred(lst[0]): # 先頭要素がフィルターを通り抜けた場合
return [lst[0]] + my_filter(pred, lst[1:])
else: # 先頭要素がフィルターを通り抜けなかった場合
return my_filter(pred, lst[1:])
これは上のmapを理解できたら問題ないかと思います。フィルターを通り抜けた場合のみ先頭要素を追加して、フィルターに引っ掛かった場合は先頭要素を追加せずに再帰呼び出しのみを返します。
reduce
mapとfilterは比較的わかりやすかったのですが、reduceは少し分かりにくいです。reduceは畳み込み関数と呼ばれたします。関数型言語ではreduceではなく、foldという名前が使われることが多い気がします。foldにはfold_rightとfold_leftがあり、リストを一列に並べたときに右側にある要素を先に畳み込むのがfold_rightで左側にある要素を先に畳み込むのがfold_leftです。実際に手を動かしてみた方が分かると思うのでこの時点で理解できていなくても問題ありません。
pythonで提供されているreduce関数は標準ライブラリのfunctoolsモジュールにて定義されているので、インポートする必要があります。次のようにして使うことができます。
>>> from functools import reduce
>>> reduce(lambda acc, cur: acc + cur, [1,2,3,4,5], 0)
15
このreduce関数はfold_left、つまり左側から先に畳み込むようになっています。
それでは自分で作ってみましょう。
# 入力：2つの引数を取り1つの値を返す関数。リスト。初期値。
# 出力：畳み込ん処理結果（値）
def my_reduce(f, lst, init):
if len(lst) <= 0:
return init
return my_reduce(f, lst[1:], f(init, lst[0]))
print(my_reduce(lambda acc, cur: acc + cur, [1,2,3,4,5], 0)) # 15
以下詳しく説明します。
まず注意する点としては、reduce関数に渡す関数fはmap, filterとは異なり二つの引数を取るものであるという事です。この例では
lambda acc, cur: acc + cur
という2つの引数を足し合わせるlambda式を渡しています。acc, curという引数名にも意味があります。accはaccumulationの略で累積値、curはcurrentの略で現在の値を意味します。accにはこれまでの畳み込み処理の結果（累積値）が渡されて、curにはリストの要素でこれから畳み込もうとしている値（リストの先頭要素）が渡されます。
一連の処理の手順を次のように考えると畳み込むというイメージを掴みやすいかもしれません。
(((((0 + 1) + 2) + 3) + 4) + 5) # acc: 0, cur: 1
((((1 + 2) + 3) + 4) + 5) # acc: 1, cur: 2
(((3 + 3) + 4) + 5) # acc: 3, cur: 3
((6 + 4) + 5) # acc: 6, cur: 4
(10 + 5) # acc: 10, cur: 5
15 # return 15
ここまでくれば自作my_reduceが何をしているのか分かるのではないでしょうか。
因みにこのmy_reduceのようにreturnで返すのが自分自身になっている再帰関数を末尾再帰と呼んだりします。
番外編: fold rightについて
pythonのreduceはfold leftなので直接的には関係ないのですが、ここではfold rightについても自分で作ってみます。fold leftが理解できたならそれほど難しくはありません。
# 入力：2つの引数を取り1つの値を返す関数。リスト。初期値。
# 出力：畳み込ん処理結果（値）
def fold_right(f, lst, init):
if len(lst) <= 0:
return init
return f(lst[0], fold_right(f, lst[1:], init))
print(fold_right(lambda cur, acc: cur + acc, [1,2,3,4,5], 0))
fold rightは右側から先に畳み込みます。なのでリストが空になるまでfold_right関数をどんどん呼び出して、リストの最後の方から計算していきます。fold_rightに渡す関数fは同様に2つの引数を取りますが、先程とは違い1つ目が現在の値で2つ目が累積値になります。一連の処理の流れは次のようになります。
(1 + (2 + (3 + (4 + (5 + 0))))) # cur: 5, acc: 0
(1 + (2 + (3 + (4 + 5)))) # cur: 4, acc: 5
(1 + (2 + (3 + 9))) # cur: 3, acc: 9
(1 + (2 + 12)) # cur: 2, acc: 12
(1 + 14) # cur: 1, acc: 14
15 # return 15
fold_rightは末尾再帰ではありません。
fold leftかfold rightかの違いが重要になってくるのは関数fの演算が可換でない時です。
演算が可換であるとは、x + y = y + xのように交換法則が成り立つことを指します。
上の例では足し算だったのでfold leftでもfold rightでも計算結果が同じになりました。しかしこれを引き算にすると結果は次のようになります。
>>> from operator import sub
>>> my_reduce(sub, [1,2,3,4,5], 0)
-15
>>> fold_right(sub, [1,2,3,4,5], 0)
3
引き算はx - y = y - xが必ずしも成立しないため可換ではありません。そのために結果が異なりました。
まとめ
やっぱり物事を理解するには自分で作ってみるのが一番ですね。
本記事ではmap, filter, reduceの3つの関数を取りあげましたが、それらは関数型プログラミングのほんの一部でしかありません。関数型プログラミングは奥が深く、僕もまだ勉強し始めたばかりなので継続して学んでいきたいです。
意見のある方、間違いを発見した方はぜひコメントしてください。