ラムダはいいぞ

一応(!プログラマー&&競プロer)あたりの人に、C++、もといプログラミング豆知識を披露してあわよくば役立てていただければ良いなというモチベーションで記事を書いている。しかし、先週の記事のラムダとか関数オブジェクトとかあの辺りは端折る必要があり、かなり説明不足感があったことは否めない。それではあまりにも不誠実であると感じたので今回はこいつらにフォーカスを当てて話していきたい。

ラムダ式とは何者なのかくらいから簡単なラムダ式ならかける程度までの習熟を目指す。

ラムダ式 is 何？

そもそもラムダ式のラムダとはなんだろう？正解をいうとギリシャ文字$\lambda$(ラムダと読む)のことである。もちろんそんなくだらないトートロジカルな議論など求められていないことぐらいわかっている。

起源を調べてみた。ソースはwiki[1](迫真)。あと『プログラミングHaskell』[2]。そもそもの発想自体はAlonzo Churchという数学者が$\lambda$計算というものを考えだしたところに端を発する。例えば以下のように記述するらしい。

$Y= \lambda f.(\lambda f(xx))(\lambda x.f(xx))$

$\lambda$計算の影響を受けたLispという言語が1950年代に誕生したということだ。

さて、そういう背景を踏まえて以下のHaskellのコードを読んでほしい。実は以下のコードはHaskell流のラムダ式の書き方だ(コードはすごいH本[3]のp73から取材した。)

map(\x -> x+3)

これで$f(x)=x+3$と同等の働きをする。入力は以下のように行う。4つの変数が格納されたリスト、$[1,6,3,2]$を渡してみる

map(\x -> x+3)[1,6,3,2]

出力は以下のようになる

[4,9,6,5]

上の式をあえて自然言語で書くと以下のような感じか。

map(\引数-> 返り値)[実際に渡す値]

こうして渡した値が、定義されているような処理を経て返された。

さて、いわゆる普通の関数(上記の例では$f(x)=x+3$)とラムダ式を行き来したところで冒頭の問いに答えをだしてみる。ラムダ式のラムダとは、map(\x -> x+3)の"\"部分のことである。なんでも"\"が$\lambda$そっくりだからとか[3]。「結局よくわからん」という声が聞こえてきそうだ。僕もそう思う(´；ω；｀)。

僕がここで伝えたかったのは「ラムダ式 is 何?」という問いかけからではきっと満足できるような答えは得られないと思うよということである。
確かにC++のラムダ式の文法を貼り付けるのは簡単だけど、きっとそれでは腑に落ちていないからこの記事を読んでいる読者が大勢いると思ったのでこういう人を喰ったような書きっぷりをしている。
僕の場合はPythonのラムダ式の定義を読んでもJavaのラムダ式の定義を読んでもC++のラムダ式の定義を読んでも結局腹落ちすることがなかった。
結局のところ書いてるうちになんとなくわかるようになってそれを紡いで言った感じだ。きっとこういう全く未知のものを演繹的なアプローチで理解するのは違うと思っていて、例を沢山みて、いろいろ書いてみて自分なりに全体像を掴む帰納的なアプローチによってわかるものだと思ってる
だから次節からはWikiではなく自分のコードをたくさん書くことでラムダ式とは何かを掴んでいってもらいたい。

実際に見てみよう(Python編)

この記事の最終目標はC++でラムダ式をかけるようになることではあるが、Pythonのコードを間に挟んだほうが理解が進むと思ったのでまずはPythonのコードをみてもらう。

以下のようなソースを入力してみた。

>>> (lambda a:a+3)(5)

この式の出力は以下のようになる。

8

ここで一節前のHaskellの例を再掲する。

map(\引数-> 返り値)[実際に渡す値]

この例のようにPythonの文法を書き直すと以下のようになるだろうか

(lambda 引数:返し値)(実際に渡す値)

mapの例では「\引数」としているところをPythonでは「lambda 引数」という形で表しているのである。\が$\lambda$に見えたから\が採用された話を思い出してみると、両者結局「$\lambda$ 引数」の形をしていることがわかる。

map(\引数-> 返り値)[実際に渡す値]
(lambda 引数:返し値)(実際に渡す値)

ラムダは無名関数と言われているのを聞いたことがあるかもしれないが、確かに(lambda a:a+3)には名前がついていない。こんな寿命が1行で終わる関数役に立たないだろ!!と思うかもしれないが(最初の頃僕は思っていました)、実は無名関数に名前をつけることができたりする。(このあたりのややこしさもラムダ式が馴染みづらい原因な気がしている)。ラムダ式が有名(名が有る)関数であるということではなく、無名関数に名前をつけるのである。

Pythonの例になるが、例えば以下のように名前を付けて使い回すことができる。先程までは後ろに渡す値を記述していたが、名前をつけてからは、普通の関数likeに引数を渡すことができるようになる点に注意だ。

>>> test=lambda a:a+3
>>> test(1)
>>> test(2)
>>> test(10)
>>> test(100)

出力は

4
5
13
103

となるはずである。このようにラムダ式を使い回せる。

実際に見てみよう(C++編)

さて、C++である。 まずは基本的なラムダ式の形からおさらいする。 型推論によっていろいろ省略できたりするので、書きっぷりはいろいろあろうが一つの例として以下を書く。

[](引数){処理}(実際に渡す値)

もはや\が$\lambda$と似ているいうアナロジーすら消失してしまっている。これは名前を持たない単なる無名関数である点に注意してください。

これまでの例に則った例を書くならこんな感じか。

  [](int a){return a+3;}(1);

いろいろテストしてみよう。

#include <iostream>

int main(){
#include <iostream>


int main(){
  std::cout<<[](int a){return a+3;}(1)<<std::endl;
  std::cout<<[](int a){return a+3;}(2)<<std::endl;
  std::cout<<[](int a){return a+3;}(10)<<std::endl;
  std::cout<<[](int a){return a+3;}(100)<<std::endl;
}

これの出力は以下のようになる。

4
5
13
103

Pythonの例と比較するために、名前を付けていろいろテストしてみる

#include <iostream>


int main(){
  auto test = [](int a){return a+3;};
  std::cout<<"引数: "<<1<<" 返り値: "<<test(1)<<std::endl;
  std::cout<<"引数: "<<2<<" 返り値: "<<test(2)<<std::endl;
  std::cout<<"引数: "<<10<<" 返り値: "<<test(10)<<std::endl;
  std::cout<<"引数: "<<100<<" 返り値: "<<test(100)<<std::endl;

}

出力結果は以下。

引数: 1 返り値: 4
引数: 2 返り値: 5
引数: 10 返り値: 13
引数: 100 返り値: 103

これでPythonと同じ挙動が再現できた。C++はキャプチャとかミュータブルがどうとかの話もあると思うけど、それはとりあえずおいておきましょう。(ラムダ式と本質的に関係ないので)。C++のラムダ式に関してもう少し込み入った話に興味があるひとは江添さんの記事(例えばこの記事[4]とかこの記事[5]とか)がいい感じです。

ラムダ式 is 何故？

最後に少し歴史のお勉強をしよう。なぜラムダ式という概念が全く思想の違うC++やJavaに組み込まれたのだろうが。組み込まれたことでどのような問題が解決したのだろうが。

例えばC++が現れたのは1985年、35年前のことである[6]。しかし、ラムダ式がC++の仕様に組み込まれたのは2011年、C++11のことだ。何故2011年にもなってラムダ式が組み込まれることになったのだろうか。

実は仕様策定の過程は大体の言語でオープンになっており、C++も例外ではない。こちらもC++のリファレンスから閲覧できるようになっている[7]。

Motivationでいろいろ書いてあるが、結局は様々な処理を簡潔にかける点が強調されている。

C++から遅れること3年、Javaでの策定では簡潔にできる点と直列化したオブジェクトを並列で処理したいために関数型の書き方を取り入れるためにそれを容易に実現したい旨が書いてある[8]。

入門書ではラムダの文法はauto f=[](引数)->型{処理}だーと書かれているが、競プロ文脈でラムダ式を定義して使いまわすことってあまりないと思う。短いが複雑なコードを要求される競プロという競技の性質上、ラムダ式より普通の関数を使うほうが優れていると思う。

一方で、関数オブジェクトとして関数の引数にラムダ式を渡す使い方(前の記事のsort()の例をみよ)は、関数を簡潔に書けること等メリットが大きいので使えるようになるといろいろ助かることがあるかもしれない。

歴史を振り返ってみても、ラムダ式を使い回すという前者の使い方よりは種々のコードを簡潔に書くみたいな後者の目的で取り入れられたものだったことがわかる。そして多分競プロで必要になってくるラムダ式の使い方は関数の引数としての関数オブジェクトを簡潔に書く後者の使い方だと思う。(茶色並みの感想)。

出典

[1] https://en.wikipedia.org/wiki/Anonymous_function
[2]Graham Hutton(2009)「プログラミングHaskell」
[3]Lipovaca,Miran(2012)「すごいHaskellたのしく学ぼう！」
[4]https://cpp.rainy.me/017-lambda.html#%E5%9F%BA%E6%9C%AC
[5]https://cpplover.blogspot.com/2009/11/lambda.html
[6] https://en.wikipedia.org/wiki/C%2B%2B
[7] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1958.pdf
[8] http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-final.html