1. ラムダ式
C言語やその類の言語を使いこなしてる人にとってはラムダ式、と言う機能は相当理解しづらいブツらしい。
例えば2014年に登場のJava 8に於いてラムダ式が導入されたが、これによる混乱、と言うのは記憶に新しいトコロである。
当時のJava界隈では「ラムダ式って何?」と言うトピックが取りざたされていた。JavaScriptにとってはそうではない(※1)が、Javaに於いては大きなパラダイム変換、に匹敵するような機能の追加だったのである。
誤解のないように言っておくと、ラムダ式自体の歴史は長い。関数型言語の文脈に於いては・・・現代的なラムダ式、と言う前提では少なくとも40年以上の歴史を持っている。
言い換えると、手続き型言語やオブジェクト指向言語は、実は40年分くらい関数型言語の「機能追求」に比べると「遅れている」と言う事実がまずあるのだ(※2)。
敢えて言うと、関数型言語は「最先端」であるが故、コンピュータのリソースをクソみたいに食い尽くしてきた。つまり、最先端のマシンじゃなきゃ扱えない、と言うのが長い間の原則だった故、手続き型言語やらオブジェクト指向言語に於いて「フツーに扱える」ようになったと言うのは、この20年くらいで我々が入手可能なPCの性能がやっとこさ上がった、と言う事に他ならない。
C言語が得意な人程、ラムダ式、または「無名関数」の存在を疑問に思うらしい。一体「名前がない関数」なんてどんな用途があるのだろうか、と。
しかし、一つ言っておかなければならないのは、実の事言うと、C言語は高級言語の中では「あまりにも機能が少ない」言語ではあるのである。Pascalに比べても機能的には負けてる、ってのがC言語で、それはPascalはローカル関数が使えるけど、Cにはそんな機能がない、と言うのだけでも分かると思う。
あくまでC言語とはアセンブリ代わりに使える、って程度の言語であって、実は数ある高級言語の中では機能が「あまりにもない」言語なのだ。
従って、ハッキリ言うけど、こんな「ないないづくし」の言語はプログラミング言語教育の「基礎」たり得ないと思う。既に現代の状況から言っても基本、にはならないのだ。
機能が少ない、と言う事は色んな事を行う為の抽象化も出来ない、と言う事を意味する。つまり、ユーザーは抽象的に考える事が出来ない。直接にハードウェアを弄るには向いてるが、それが故に抽象的思考には向かない言語なのである。
要するに関数がファーストクラスオブジェクト(※3)ではないC言語だと抽象化に充分な機能を擁していない。
関数がファーストクラスオブジェクトだ、と言う事は関数の引数に関数を取れるし、関数の返り値を関数にする事も可能だ。そしてそれとラムダ式の組み合わせはプログラミング言語における強力な抽象化能力を提供する。
それらはC言語の枠組みだと簡単に想像の範囲外、と言う事になってしまうのだ。
2. 高階関数
さて、上に書いた「関数を引数に取る関数」そして「関数を返り値とする関数」を高階関数と呼ぶ。今回は前者を扱ってみようと思う。
ところで、以前書いたCPS(継続渡し方式)と言うのも当然高階関数の一種である。
# 一番簡単なCPS
def foo(x, cont):cont(x)
Pythonで書かれた上の関数が一番簡単なCPSであり、ある意味一番簡単な高階関数でもある。引数に一引数関数であるcontを受け取る関数ではあるが、具体的には何もしない。単にもう一つの引数であるxを受け取り、粛々とその値をcontに受け渡すだけ、である。
>>> foo(1, print)
1
>>>
CPSに於いてはcontは本体の中で計算としては使われない。言い方を変えると、本体の中で計算に使われれば単なる高階関数、計算に使わないで「計算を受け渡す対象」として関数の引数が使われればCPSだと言う、それだけの違いでしかない。単純な話である。
ただ、これだけじゃ「なるほど」なだけで、クソも面白くない。
そこで今回は「繰り返しの抽象化」と言う議題を取り上げよう。
何故ならみんな繰り返しが嫌いだから、である。
3. 抽象化
ところで、「抽象化」とは何だろうか。
言い方を変えると「プログラミングに於いて頻出のパターンを取り出し定式化する」と言う事である。
例えば、特にプログラミングでは、まずは「繰り返し」自体が頻出であり、そしてこれは基本的に嫌われる。何故ならみんな必ず、と言って良い程「間違える」からだ。
まず前提を確認しておく。
機械語やアセンブリのレベルだと、繰り返しはジャンプと言う形式で記述される。
ところがこれがややこしい。まずこの時点でプログラミングのミスが頻出する。
そこで、C言語なんかの高級言語では、これをまずは「抽象化」した。ジャンプするから間違えるんだろ、ってんでジャンプ臭さを排してfor文とかwhile文なんかを構文として提供して、ジャンプで起きる間違いを減らそうとしたわけだ。
ところがこれでも人間は間違えるのだ。配列を舐める際に境界線を飛び超えてセグメンテーション・フォールトにお目にかかる、なんつーのは日常茶飯事だろう。達人なら避けられる、ってワケでもなく、逆にプログラミングに慣れれば慣れる程このテのエラーに事欠かない。
さて、そうなると、我々に出来る事は、
- より簡単な繰り返し方法を考案する
- あきらめる
のどっちかしかない。
ぶっちゃけ、C言語ユーザーの殆どは2番目を採用する。「そういうモンなんだからしゃーねぇよな」と。大体、先程にも書いたが、C言語が提供するものは「抽象化」に役立つものが殆どない。あくまで言語設計の方針は「アセンブリが出来る事」の抽象化でしかないのだ。逆に言うと「具体性」の言語なのである。
1. の立場が、言い換えると「さらなる抽象化への挑戦」である。素のままに繰り返しをすれば間違えやすいので、もっと間違えないような機能を提供出来ないか、考えるわけだ。これが現代的な、C言語ユーザー「以外の」人の考え方である。
ここで登場する一つの方法論が高階関数である。
ところで、forやwhileなんかでの単純な数のインクリメント、デクリメント、なんかじゃあそうそう人間は間違えない。
問題は、先にも見た通り、配列のようなデータ型相手に繰り返し操作をする時に人間は良く間違える、と言う事だ。
そして、関数型言語の先駆者達は、この配列系データの繰り返し作業に於いて、ある特定のパターンを4つ抽出したのである。
- ソーティング
- フィルタリング
- マッピング
- フォールディング
この4つが繰り返しに良く現れ、逆に、このパターンに属さないモノは単純に繰り返しのお世話にならなければならない、と言う事だ(※4)。
これらは実際、C言語なんかでは頻出する割には一々書かなければならないのがメンド臭い。そして、関数型言語では「高階関数」としてこの4つの「定番メニュー」を抽象化して料理する事と相成ったのである。
1番はプログラミングの宿題で良く出る問題にもなってる。しかし同時に、ホント書くのがメンド臭いので、C言語でさえ標準ライブラリ(stdlib.h)に含まれている(qsort)。Pythonでは破壊的変更を伴うsortと非破壊的なsortedと言う組み込み関数が用意されている。
2番はある条件を満たした場合、その要素を削除するか、あるいはその要素以外を削除する。それは実装によるが、いずれにせよ、文字通りフィルタリングである。しかし、これは素のC言語だとPythonのリストのような可変長配列を持たないのでライブラリにはなっていないし、実装も難しい。少なくとも連結リストを実装するか、あるいは外部ライブラリでの連結リストを用いないと実装出来ないだろう。ある意味、「C言語以上の高級言語」の高階関数ならでは、の機能である。
Pythonではfilterと言う関数が用意されている。Python2.0ではフツーの関数だったがPython3.0以降だとイテラブル(※5)を返すようになった。
いずれにせよ、このfilterでは通常「条件」をラムダ式で与えるし、この4つの中では一番高階関数らしい高階関数だろう。
さて、1. と 2. は言わば単一の目的の為に使われる関数だが、3. と 4. はちょっと毛色が違う。この二つはそれこそ「繰り返しをより抽象化」した関数である。要するに「もっと簡単に繰り返しをしたい」と言う要求により作られたモノだ。このテのブツをイテレータと呼ぶ。
実は「イテレータ」が何であるのか、これも厳密な定義がない。日本語では「繰り返し子」とか「反復子」とか訳されるが、じゃあ、C言語のfor文とかwhile文がイテレータなのか、と言うと良く分からん。定義がないから、だ。
一般的には「違う」となるのではないか。
また、イテレータが何に属するのか、と言うのも良く分からない。プログラミング言語上で定義されてる構文なのか、関数なのか、はたまたオブジェクト指向言語に於いてあるクラス内で定義されてる反復処理用のメソッドなのか。やはり定義がハッキリせんから良く分からんのだ。
このようにプログラミング用語ではバズワードを基とした言い回しが拡散しちゃって「何となく」使われてるモノが多い(※6)。
いずれにせよ、ここでは「繰り返しの抽象度を一段階上げて簡易化したもの」と言う意味で使っている。
なお、Pythonでは3.のマッピング関数も4.のフォールディング関数もやはり組み込み、あるいはビルトインライブラリとして提供されている。ただ、関数型言語の学習ではこの二つの関数は一回は自作してみる、と言うネタになっている。まぁ宿題か(笑)。
その一つの理由は、「再帰を使った問題」としてはかなりの良問になってる、からだ。もう一つの理由は、こんな宿題でも出さんとC言語のように宿題が出せないからだ(笑)。貧弱なC言語で宿題を出せば大学で一学期はもつが、パワフルな関数型言語だとその程度のネタは全部ビルトインだったりするのだ。しかも実用性が有りまくりなわけで、このテの高階関数には汎用化出来る未知の領域がまだあるかもしれないけど、現時点でこのマッピング関数とフォールディング関数はプログラム史上ある種最高傑作なのだ。よって自作に挑戦する、と言うのはそれなりに意味はある・・・・・・多分。
ちなみに、4.のフォールディング関数は言語によってはreduceと呼ばれ、Pythonでもreduceの名を冠して搭載されている。そしてマッピング関数mapとフォールディング関数reduceはGoogleのMapReduceと言う名前の元ネタとなっている。
4. マッピング関数
まずはマッピング関数から。
マッピングとは何だろうか?
昔の3DダンジョンRPGをやったことがある人だと、ダンジョンマップを方眼紙上に作る事、と思うだろう。地図化だよな。
確かに英語にはそういう意味があるけれど。
実はここで言うマッピングとは数学用語である。誤解を畏れずに言うと線形写像の事だ。
Wikipediaには次のように書かれている。
Pythonで言うリスト等の可変長配列をベクトルに見立てて、と言う事なんだが、まぁ、名前の由来と理屈はさておき、確かに繰り返しではこういうパターンが頻出するのである。
# 繰り返しで良く見るパターン
acc = []
for item in lst:
acc.append(func(item))
Pythonだからまだ短く見えるが、いずれにせよ、プログラムを書いてて同じパターンを10回以上見かければいい加減「抽象化すべきだろ」ってなるのは難しくない。と言うか関数型言語の先達は「いい加減このパターンを書くのを飽きて」マッピング関数を発明したのだ。
>>> list(map(lambda x: x ** 2, [1, 2, 3]))
[1, 4, 9]
>>>
Pythonのmapも3.0になってイテラブルを返すようになったので、計算結果を見るにはひと手間必要になったが、使い方そのものは難しくないだろう。
上の例は与えられたリスト[1, 2, 3]の各要素を二乗したリストを返している。
もちろんfor文でも書けるが、ワンライナーで処理出来る為、一々大げさにせんでも目的を達成できる辺りに価値があるのである。
ここでもラムダ式は「各要素に対してどう言った関数を適用するのか」指定する役目を果たしている。そしてこの程度の計算だったらわざわざ別立てで関数を書く必要もない、ってのが分かるだろう。「無名関数」はこの程度の簡単な事をやらせる為だけにまずは存在しているのである。
さて、本来ならmapの第二引数であるイテラブルは可変長引数で、何個もイテラブルを受け取れるのだが、ここでは簡単な、リストしか受け取れなく、しかも単体しか受け取れない関数、mapcarを実装してみよう(※7)。
# 再帰版
def mapcar(func, lst):
if lst == []:
return lst
else:
return [func(lst[0])] + mapcar(func, lst[1:])
# CPS版
def mapcar(func, lst, cont):
if lst == []:
cont(lst)
else:
mapcar(func, lst[1:], lambda u:
cont([func(lst[0])] + u))
# 末尾再帰版
def mapcar(func, lst, acc = []):
if lst == []:
return acc
else:
return mapcar(func, lst[1:], acc + [func(lst[0])])
# 反復版
def mapcar(func, lst, acc = []):
while True:
if lst == []:
return acc
else:
acc += [func(lst[0])]
lst = lst[1:]
非常に単純な手法で、繰り返しの「良くあるパターン」を抽象化してるのが分かるだろうか。
Pythonだと末尾再帰最適化の機能がないので結果、「反復版」が一番望ましいスタイルだ、と言う事にはなるのだが、いずれにせよ、「抽象化とはこうあるべき」と言う説得力があるアイディアにはなってると思う。
気が向いた人は「リストが可変長引数である」mapの実装に挑戦してみても良いだろう。
5. フォールディング関数
関数型言語の高階関数で、ある意味最強なのがこのフォールディング関数である。Pythonではfunctoolsライブラリでreduceと言う名前で提供されているのは上で書いた通りだ。
このフォールディング関数は日本語では「畳込み関数」と訳される。
この高階関数は驚くほど高機能なんだけど、内部動作を想像するのがちと難しい。
ちょっと動作例を見てみようか。
>>> import functools
>>> functools.reduce(lambda x, y: x + y, [1, 2, 3, 4], 0) # リストの要素の総和を取る
10>>> functools.reduce(lambda x, y: [y, x], [1, 2, 3, 4], [])
[4, [3, [2, [1, []]]]]>>> functools.reduce(lambda x, y: [y] + x, [1, 2, 3, 4], []) # リストを反転する
[4, 3, 2, 1]>>> functools.reduce(lambda count, x: count + 1 if isinstance(x, str) else count, [5, 4, "c", 3, "b", 2, "a", 1], 0) # リスト内の文字列の個数
3>>> functools.reduce(lambda max_len, s: max(max_len, len(s)), ["abcde", "fg", "hijklmn", "opqr", "stu" "vwx", "yz"], 0) # リスト内の最長の文字列の長さ
7>>> functools.reduce(lambda l, x: l + [x]if x % 2 == 0 else l, [1, 2, 3, 4], []) # リストから偶数を抽出する
[2, 4]
これは恐るべき結果なのではないか。
functools.reduceは驚異的な汎用性を備えてるイテレータで、他の関数や高階関数の基本的枠組みさえ提供出来る「高階関数中の高階関数」だと言える。
同時に、初見では使い方がイマイチピンとこない。必要とするラムダ式は最低でも2引数になるが、ここの書き方、引数の受け渡しとその計算にアタマを捻る事となるだろう。
実は、functools.reduceの使い方に難しさを覚える最大の理由は、functools.reduce上での第二引数(リスト)と第三引数(アキュムレータ)の順序とラムダ式の二つの引数が、直感的には逆順になってるからだ。これが混乱の元となっている。
ここでは関数名をfoldとしてまたもや一番単純な、アキュムレータとリストを一つだけ引数に取る高階関数の実装方法を紹介する(※8)。上の例を見るとさぞかしfoldないしはreduceは高機能で複雑な実装になるように思うかもしれないが、実は基本的には極めて単純な実装だ、と言う事が分かるだろう。単純な抽象化で最大限の効果をあげる、と言うお手本のような関数がこのフォールディング関数なのである。
# 再帰版
def fold(func, acc, lst):
if lst == []:
return acc
else:
return func(lst[-1], fold(func, acc, lst[:-1]))
# CPS版
def fold(func, acc, lst, cont):
if lst == []:
cont(acc)
else:
fold(func, acc, lst[:-1], lambda u:
cont(func(lst[-1], u)))
# 末尾再帰版
def fold(func, acc, lst):
if lst == []:
return acc
else:
return fold(func, func(lst[0], acc), lst[1:])
# 反復版
def fold(func, acc, lst):
while True:
if lst == []:
return acc
else:
acc = func(lst[0], acc)
lst = lst[1:]
見てみれば分かるが、おっそろしく単純な実装なのに、ラムダ式等の関数引数の組み合わせで千差万別、融通無碍の働きをするのがこのフォールディング関数の恐ろしいトコである。
と言うわけで、ラムダ式と高階関数による「繰り返しの抽象化」はお楽しみ頂けただろうか。
まずはforやwhileが出てきそうな場面でmapを使いまくる練習をする事。10回もやってれば「何でいままでforやwhileで書いてたんだっけ?」とか思うようになる。
そうすればシメたモンである(※9)。貴方はもう元には戻れない。
次は関数設計して、中に繰り返しがあり、なおかつmapでは上手く行かない場合。functools.reduceが使えるかどうか挑戦してみよう。これもあっと驚くような汎用化能力がある高階関数である。使い方は最初は慣れないが、ハマればこれ無しに考えられなくなる事請け合いである。
いずれにせよ、かまうこたぁない。
何でもmapしまくりreduceしまくろうじゃないか。
※1: ある種常識ではあるが、JavaScriptは名前に反してJavaの仲間ではない。そして構文的にはC言語系を模してはいるが、事実上JavaScriptは関数型言語の仲間である。
開発者のブレンダン・アイクと言う人は関数型言語Schemeのファンであり、平たく言うと「C言語のフリをした」Schemeを作ろうとしたのだ。
※2: 実の事を言うと、オブジェクト指向でさえ、90年代にいきなりJavaによって登場したワケではない。オブジェクト指向の雛形は1967年のSimulaまで遡る。と言う事はオブジェクト指向と言うアイディアが市井の人々に受け入れられて使われるまで、30年近くの時を要した、と言う事である。
この様に「研究・実験」段階から「実用」段階に持ち込まれるまで、意外と長い時間がかかる、と言う割に当たり前の話ではある。
※3: ファーストクラスオブジェクト、と言うがこの場合のオブジェクトはオブジェクト指向のオブジェクトを示していない。プログラミング言語用語だと実の話、オブジェクトが何を指すのか合意に至ってない。要するに定義らしい定義がないのだ。
ここでは緩やかに「データ型」と同義だ、と思って欲しい。つまり、ある種の言語では関数はデータ型の一種ではなく、別種の言語では関数はデータ型の一種である、と捉えて良く、後者の場合、「関数がファーストクラスオブジェクト」と言う言い回しになる。
※4: 敢えて5つ目を挙げると与えられた配列系データの要素が「全て何らかの条件を満たす」か、あるいは「いくつかが何らかの条件を満たす」か調べるパターンがある。
Pythonだとallやanyと言った組み込み関数が提供されてはいるが、高階関数じゃない為意図不明になってて使いづらい(リスト内包表記と組み合わせる前提かもしれない)。よって練習問題代わりに自作してみても良いだろう。
※5: イテラブル、と言うのも一種のデータ型で「繰り返し演算ではあるが結果をまだ計算してないオブジェクト」と言う意味である。Python3.0ではいくつかの組み込み関数がイテラブルを返す関数(Python用語ではジェネレータ等と呼ぶ)として設計しなおされた。これも関数型言語の影響で、「指示するまで計算せずにいる状態」を「遅延評価」と呼ぶ。
※6: 恐らく「イテレータ」と言う単語がはじめて登場したのは1974年に発表されたCLUと言う言語から、である。この時は汎用のforやwhileと言うような「構文」ではなく、データ構造に専用反復処理が付属する、と言うカタチで、今で言うオブジェクト指向のクラスに付属する反復処理メソッド的なモノをそう呼んだらしい。
※7: 関数名mapcarはプログラミング言語、ANSI Common Lispのマッピング関数から借りてきた。mapcarも本来なら、受け取るリストは可変長引数である。
※8: ここで実装するfoldはfunctools.reduceとは異なる引数の順序とする。すなわち関数型言語でお馴染みのfold(関数引数, アキュムレータ, リスト)の順にするが、それでも与えるラムダ式の引数の順番と逆になってしまう。
また、これも本来はリスト部分は可変長引数で、興味がある人は可変長引数版を実装してみたら良いだろう。
ちなみに、実はfoldには与えられたリストを左から走査するバージョンと右から走査するバージョンと二つ存在して、返り値が数値であるアキュムレータの場合、計算結果は同じだが(数学での交換法則により)、一方、返り値がリストであるアキュムレータの場合、計算結果が異なったりするのだ。
ここでは、基本の「左から舐める」実装法にした。
「右から舐める」実装も練習代わりにやってみれば良いと思う。
※9: なお、Pythonでは、本当の事を言うと、mapやfilterを使う以上にリスト内包表記を使うべきである。
