関数型Scala（５）：内包を理解する - Mario Gleichmann

この記事はMario Gleichmann氏による、「Functional Scala」シリーズの第５回「Functional Scala: Comprehending Comprehensions | brain driven development」を、氏の許可を得て翻訳したものです。（原文公開日：2010年11月21日）

関数型Scalaの第５話にようこそ！

これまでに集合の内包について聞いたことはありますか？そうですね、数学の授業を受けたことがあるなら、きっと聞いたことがあるでしょう。しかし、聞いたことがなくても、怖がることはありません！これは単に、ある集合のメンバが満たさなければならない性質を述べることで、要素の集合を定義する数学的な記法にすぎないのです。この説明があまりに抽象的に思えるなら、単純な例を見てみましょう：

{ x | x ∈ N : x == x² }

ここにあるのは、ある値の集合に関する記述です。その値とは、自然数に含まれていて、自乗したものがそれ自身と等しい数字です。まじめに考えれば、与えられた制約を満たす自然数が２つしかないことにすぐに気づくでしょう。そうです、上記の集合の内包は、集合 {0, 1} のための定義なのです。かっこよくありません？それほどでもないのはわかっています。この集合の内包は単に集合を書き出すだけよりもスペースをとりますから。ただ、要素の集合をすべて列挙したら、集合の内包を使うよりも時間とスペースを使う場合もあるでしょう。これを見てください：

{ x | x ∈ R : x > 0 }

そうです。これは、正の実装すべての集合です。それでは、たっぷりと時間をとって、この集合を直接書き出してみましょう。ちょっと場所が必要かもしれませんね・・・OK、その辺でいいでしょう。しかし、こうしたことは関数型プログラミング全般と、とりわけScalaとは、どう関係するのでしょうか？そうですね、ほとんどの関数型言語は、いわゆるリスト内包と呼ばれる形式を何らかのかたちで提供していることがわかります。集合の内包と対照的に、集合の要素を定義するのではなく、代わりに・・・リストの要素を定義するのです。

それでは、他の例を用いて、Scalaの内包を使うとどのように表現できるのかを見ていきましょう。最初の５つの平方数を定義するリストを試してみましょう。最後に、まずは集合の内包として表現してみましょう：

{ x² | x ∈ N : x > 0 ∧ x < 6 }

これをScalaのリスト内包に翻訳する前に、内包に含まれる個々の要素をより詳細に見ておきましょう。パイプ（|）の手前にあるのは、出力関数と呼ばれるもので、出力変数 x を伴っています。出力関数により、結果として生じるリストの値を算出する方法が決定されます。パイプの後にあるのは、出力変数のドメインを規定する入力集合であり、その後に、与えられたドメインをさらに限定する制約が続きます。出力変数に対する妥当な値と考えられる全ての要素に対して、この制約一式が当てはまらなければなりません。

前節で、「最後に」と言ってしまったのがウソだったことを、私は認めなければなりません。もう一度だけ、前述の集合の内包に変わるバージョンをお見せします。しかし、どうか許して下さい。これはScala風の内包に入りやすくするためだけです：

{ x² | x ∈ { 1 .. 5 } }

なるほど、出力変数のドメインを特徴づけるために別の集合を使えば、前述した制約のいくつかは必要なくなるということを理解して下さい。この観点からすれば、内包は、より一般的な集合から、より特殊な集合を構築するための仕様であると言えるかもしれません。よろしい、Scalaにおける最初の内包を構築するには、これで十分です。内包にある決まった要素を知りたいと思うかもしれませんね。では、見ていきましょう・・・

for( x <- ( 1 to 5 ) ) yield x * x

もう、ウソはついていませんよ、本当です！最初は、for ループのように見えますが、これは純粋な内包です！ただ、個々の要素のための表記法が、最初はすこし奇妙に映るかもしれませんね。明らかに、x は出力変数です。x は、for ブロック内の最初の要素として示され、x のための入力ドメインが後に続きます。出力変数と入力ドメイン間の相関関係は、両者の間の矢印（ <- ）で表現され、両方の要素を互いに接続しています。この場合、入力ドメインは範囲 ( 1 to 5 )によって構築されていますが、これは一般的にScalaでは、ジェネレータ（Generator）と呼ばれています。実際、（後に見ていく、Functor という意味での）メソッド map、（Monad という意味での）メソッド flatMap、メソッド filter を提供する型はどれも、リスト内包におけるジェネレータとして機能します！
入力ドメインは？OK！出力変数は？OK！しかし、結果となるリストの形態を決定する出力関数はどこにあるのでしょう？もうおわかりだと思いますが、 yield に続く内包の最後の部分がそれに当たります。出力関数は、実際、内包表現全体の結果として生み出されるものに対して責任を持つのです。

複数のジェネレータ

さらに先に進みます。出力変数と、それに関連するジェネレータに関しては、１つだけに制限されません。好きなだけ多くの出力変数（と、それに関連するジェネレータ）を、俎上にのせることができるのです。たとえば、１〜３の範囲のペアのデカルト積であれば、次のように生成することができます：

for( x <- (1 to 3 ); y <- (1 to 3) ) yield (x,y) // (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)

それでは、出力変数のとり得る可能性を走査する際の順序を見てみましょう。そう、左から右です。つまり、最初のジェネレータ（左の x ）がある値から次の値に増える前に、後のジェネレータが全てのドメインをいったんすべて走査します。これは、x の次の値、そしてその次の値と続いていきます。さらに理解するためには、ネストされた２つのforループだと考えてもいいかもしれません。最初のジェネレータが外側のループに対して作用し、次のジェネレータが内側のループに対して実行されるのです・・・

なるほど、いいでしょう。（1, 3）と（3, 1）のように順番が入れ替わっただけで値が同じペアのうち、１つだけを残したいと思ったらどうなるでしょう。問題ありません！あるジェネレータよりも前のジェネレータ（つまり外側のループ）で定義された出力変数を参照してもよいということがわかります。その場合、２番目のジェネラータの範囲を定義する際に、現在の x を参照するだけです：

for( x <- (1 to 3 ); y <- (1 to x) ) yield (x,y) // (1,1), (2,1), (2,2), (3,1), (3,2), (3,3)

そして、前に定義されたジェネレータの（中間的な）結果を、後に続くジェネレータで参照できることから、リストに対しても非常に面白いことが実行できます。リストもジェネレータとしてふるまうからです。たとえば、リストのリストで、各サブリストがなんらかの整数値を含んでいるようなものについて考えてみてください。その整数のリストのリストを平坦にして、結果として、すべてのサブリストにある整数値を全て含む単一のリストを作りたいとしましょう。そうです。内包を活用すれば、簡単に実現できます：

val flatten = ( xss :List[List[Int]] ) => for( xs <- xss; x <- xs ) yield x

え、おっと、これだけですか？その通り、こんなに単純なのです！与えられたリストのリストから、新しいリストを作るのに、リストを開梱しただけです。つまり、最初の出力変数は、与えられたリストに含まれる全てのサブリストを辿りました。２番目のジェネレータがそれらのサブリストを参照し、その中身を明らかにしました。そして、その中身は順番に出力関数によってリストとして生成されたのです。

ガード節

ここまでは、与えられた入力ドメインに含まれるすべての要素（つまり、与えられたジェネレータによって生成されるすべての値）を走査する内包だけをつくってきました。集合の内包を振り返ると、出力変数がとり得る妥当な値をフィルタリングするために、制約を宣言することができるということは、すでに見てきました。Scalaでは、内包内でいわゆるガード節を認めているということがわかります。このガード節は、出力変数がとり得る妥当な値に対して成立する、述語の集合を表現するガード節とまったく同じです。

最初の例として、与えられた整数値のための自然因数すべてのリストを生成したいとしましょう。入力ドメインは、何になるでしょうか？そうですね、１から因数を計算したい値までのすべての自然数というのはどうでしょう？いいでしょう。しかし、それでは与えられた整数値に対する自然因数にはなりません（関数への入力を１と２に限定すれば別ですが）。こうした数字が因数となるのは、与えられた値をその数字で割り切ることができるときだけです。ふむ、意味のある理にかなった制約ですね！それでは、書いてみましょう：

val factors = ( n :Int ) => for( x <- ( 1 to n ); if n % x == 0 ) yield x

ご覧の通り、ガード節はジェネレータの直後に、シンプルに宣言されます。もちろん、書けるガード節はひとつだけではありません。必要なだけガード節を追加して構いません（それぞれのガード節はセミコロンで分割されます）。ただ、ある値が妥当な出力変数となるには、すべてのガード節の述語に対して真にならなければならないということを覚えておいてください。理解度を上げるために、もう１つ例を挙げます。ここでは、整数値のリストから素数をフィルタリングします：

val primes = ( xs :List[Int] ) => 

    for ( x <- xs; 
           allFactors = factors( x ); 
           if allFactors.length == 2; 
           if allFactors(0) == 1; 
           if allFactors(1) == x 
        ) 
        yield x ... primes( List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) ) // List(2, 3, 5, 7, 11)

よろしい。どの整数値が出力変数としての資格を得ているかどうかを決定するには、すべての因数を検査しなければなりません。因数が２つしかなく、それが１とその数自体であれば、それは素数です。もちろん、そうです。しかし、ローカルの値である allFactors はどうでしょう？そうですね、これがScalaの内包表記のもう一つの特徴です。後になって参照したいと思うであろうローカルの値を、好きなだけ宣言することができるのです。これは、後に続くジェネレータの中であっても構いません！

すべてのピースを集めて、もう少し複雑な例を用いてこのエピソードを終えましょう。ここでは、Scalaの内包メカニズムを使う、別のユースケースが示されます。次のシナリオには、会社の集合と、従業員の集合があると考えてください。そのために、case クラスを２つ定義しましょう（case クラスについては、代数でデータ型（algebraic datatypes）の話をするときに詳細に見ていきます）。それが、企業（Company）と従業員（Employee）です。そして、企業と従業員のリストを生成します：

case class Company( val name :String, val region :String, val avgSalary :Int ) 

case class Employee( val name :String, val companyName :String, val age :Int ) 
...

val companies = List( Company( "SAL", "HE", 2000 ), 
                                 Company( "GOK", "DA", 2500 ), 
                                 Company( "MIK", "DA", 3000 ) ) 

val employees = List( Employee( "Joana", "GOK", 20 ), 
                                 Employee( "Mikey", "MIK", 31 ), 
                                 Employee( "Susan", "MIK", 27 ), 
                                 Employee( "Frank", "GOK", 28 ), 
                                 Employee( "Ellen", "SAL", 29 ) )

ここで、次の制約を全て満たす従業員全員を取得したいとします：

25歳以上の従業員のみ
地域“DA”にある会社で働いている従業員のみ
勤めている企業の平均月給よりも高い月給をもらっている従業員のみ（従業員の年齢×100 で算出される月給を平均とする）

見つけた従業員すべてに対して、従業員名、勤めている企業名、企業の平均月給をどのくらい上回っているかを取得したいと思います。えっと、ちょっと待ってください。このシナリオでピンときますか？関係データベースとSQLになじみがあれば、このちょっとした難問を一瞬で解決したことでしょう。よろしい、従業員と企業の２つのリストがデータベースから読み込まれ、選択は後でプログラム的に行われると思ってください。しかし、どうやって望みの従業員を取り出せばよいでしょう？うーん。おそらく内包を活用するんでしょうけれど？おお、悪くありません。どうして思いついたんですか？実は、内包を一種のクエリと考えることができるのです。内包にも、select 句（出力関数）、from 句（入力ドメイン）、そして where 句（ガード節）があるのですから。それでは、難しい話は抜きにして、これまで学んだことをすべて考慮に入れ、クエリを内包として表現してみましょう：

val result = 
    for( e <- employees; 
                  if e.age > 25; 
                  salary = e.age * 100; 
           c <- companies; 
                  if c.region == "DA"; 
                  if c.name == e.companyName; // ★  
                  if c.avgSalary < salary 
    ) 
    yield ( e.name, c.name, salary - c.avgSalary ) 


println( result ) // List( (Mikey, MIK, 100), (Frank, GOK, 300) )

なんと、魔法みたいじゃないですか？そんなことないと思ったあなた、正解です。これは単に、問い合わせという特殊な問題に適用された内包にすぎません。しかし、そういう見方をすれば、この内包の各部分をよく知っているクエリと比較することが簡単にできるのです。内部結合に対応するものさえ存在します。おわかりですか？そうです。８行目（★の部分）ですね。ここでは、企業と従業員の間で企業名が関連づけられています。

まとめ

ふう、なんて素晴しい旅だったのでしょう！これまで、Scalaの for 記法のことを、今までのものよりも優れたループであると考えていたなら、少し違う見方ができるようになっていることを望みます。このエピソードの一番最初で言った通り、どちらかと言えば、一般的なデータから、いくらか特殊なデータを取り出す仕組みなのです。そして、ここにも可変なデータは登場しません。あるのは、内包の中に入って行くいくつかの値と、内包の結果から出てくるいくつかの値だけです。これを見ると、関数型プログラミングの基本原則を思い出しませんか・・・？