関数型Scala(6):高階関数 - Mario Gleichmann

この記事はMario Gleichmann氏による、「Functional Scala」シリーズの第6回「Functional Scala: High, Higher, Higher Order Functions | brain driven development」を、氏の許可を得て翻訳したものです。(原文公開日:2010年11月28日)




関数型Scalaの第6話にようこそ!


今回は、このシリーズでほぼ毎回、何度も言及してきた強力な概念について詳しく見ていきましょう。それが、高階関数です。かっこよくありません?そうでもないですよね。名前がかっこいいだけでは、あなたを興奮させることはできませんから。そこでこれから、どうかっこいいのかを実演し、「高階関数は、関数型プログラミングにおいて、エレガントに、コンパクトに、そして効率的に書くための基本原則の1つである」という、少なからぬ声の原因となっている本質的な側面を示しましょう。


さて、それでは高階関数とは何でしょう?高階関数にはなんらかのメタマジックがあるのでしょうか?あるいは、なぜ高階(higher ordered)と呼ばれるのでしょうか?まずは一般的な問題に焦点を合わせることで、高階関数に対する感覚をつかみましょう。一般的な問題とはすなわち、コードの重複です。単純な関数を書くところから始めましょう。次のコードは整数値のリストに適用できる関数で、結果として入力されたリストのうち偶数の値だけを含むフィルタリングされたリストを生成します。:

val filterEven = ( xs :List[Int] ) => {     

    for( x <- xs; if x % 2 == 0 ) yield x 
}

こうなりますね。この単純な関数は、整数値のリストを受け取り、その整数値のリストは内包の中でジェネレータとして使われます。素晴らしいですね。すでに前回、Scalaの内包モデルについて解説していますので、ここで何が起きているのかを理解するのに、なんら問題がありません。つまり、出力変数 x(ジェネレータに由来する)がとり得るすべての値を走査し、与えられたガード節が与えられた述語を満たす値だけを出力関数に渡します。そして、述語 x % 2 == 0 を満たすのは・・・ジャジャーン・・・偶数です。


ちなみに、結果となるリストのために選択される適切な値を検出するという、きわめて重要な部分は、ガード節で用いられる述語であるようです。述語を取り巻くそれ以外のものは、どれも必要なものとそうでないものを振り分けるための機械的な仕組みにすぎず、重要な決定は述語によって行われるのです。ここで述語が持っている例外的な位置づけを強調するために、述語を取り出して独自の関数に入れることができます:

val filterEven = ( xs :List[Int] ) => { 
    val even = ( x :Int ) => x % 2 == 0 
    for( x <- xs; if even( x ) ) yield x 
}

ここまでは、本当に刺激的なことは起きていません。ただ、述語を抜き出して、ローカル関数として定義しただけです(クロージャを扱った際にローカル関数についてはすでに見ました)。こうすることで、後に出て来る内包のガード節でローカル関数を参照することができます。また、内包の式は関数の中にある最後の式であるため、この式の値は自動的に関数全体の結果となります。これはすなわち、内包によって作られる、フィルタリングされたリストにすぎません。


いいでしょう。では、ちょっと面白半分に、整数値のリストをもう一度フィルタリングしてみましょう。ただ今度は、入力されたリストのうち、奇数の値だけを出力します。すでに、フィルタリング関数を書くことについては、すでにいくらか経験を積んでおり、いくつかフィルタを書き足すのは本当に楽しい練習ですので、この課題は朝飯前でしょうし、私が「ボブはあなたのおじさんです」と言い終わる前に書くことができるでしょう:

val  filterOdd = ( xs :List[Int] )  =>  { 
    val odd  =  ( x :Int )  =>  x % 2 == 1 
    for(  x <- xs;  if odd( x )  )  yield x
}

・・・「ボブはあなたのおじさんです」


おお、あっという間で、本当に楽しいですね!いいでしょう。もう少したくさんフィルタを書くこともできますね。たとえば、素数、特定の範囲の数字、5の倍数、特定のチェックサムを持つ数字、フィボナッチ数、特定の数字の自然因数・・・それでも、まだ楽しめますか?これは、時間の経つのが遅い、長く寒い夜のことかもしれません。しかし、他の人が皆寝静まっている以上、このフィルタリングをするための雛形を何度も何度も繰り返し書くという作業を避ける方法はないのでしょうか?その繰り返しの作業を避ける方法がありますか? すでにおわかりの通り、変化するのは、これら別々のフィルタのための述語だけです。それでは、フィルタリングというタスク(出力すべきものとそうでないものを区別するという純粋なふるまい)を抽象化して、どれを出力するかを決めるタスクと区別することがどうしてできないのでしょうか?


残念ながら、述語を表現する関数をフィルタの残りの部分から切り離すことはできないんですよね・・・ん、ちょっと待った!関数がファーストクラスの値であると言いませんでしたか?言いました!では、関数も他の値と変わらないんですよね?その通り。型が違うだけです。型の違いを別にすれば、特別なことは何もありません。たとえば Int 型と同じです。そうであれば、List[Int] 型とも同じですか?その通り!ということは、List[Int] 型の値をフィルタ関数に引数として渡すことができるならば、それが意味するのは・・・それが意味するのは・・・?その通り、わかりましたね!それが意味するのは、ここに書かれた述語関数のような関数も、ある関数に対する普通の引数と同じように渡すことができるということなのです!


唯一残っている疑問は、フィルタリング関数に対して述語関数を新たな引数として追加する際、それをどうやって宣言するかです。述語関数の正確な型を知る必要があります。中間のステップとして、前述した最後の関数を拡張し、述語関数の型を明示的に記述することができます:

val  filterOdd = ( xs :List[Int] )  =>  { 
    val odd : Int => Boolean  =  ( x :Int )  =>  x % 2 == 1
    for(  x <- xs;  if odd( x )  )  yield x
}

なるほど。述語が、Int 型の値が結果となるリストに入るかどうかを(true か false か)決定するものである限り、明らかに述語関数は、Int => Booleanという具体的な型になります。あとは、その関数(と必要な値)をフィルタ関数の引数のリストに、もう1つの入力される値として追加するだけであり、それは次のようになります:

val filter = ( predicate :Int => Boolean, xs :List[Int] ) => { 

    for(  x <- xs;  if predicate( x )  )  yield x 
}

おめでとうございます。はじめての高階関数を作ったことになります!難しいことは何もありません。高階関数とは、引数として他の関数を受け取る関数にすぎないのです。そして、関数が引数の値を結果の値に紐づけるものである一方(関数も値です。念のため)、関数の結果が関数になるのも完全に正当なのです。そこで、関数がその引数のうちの1つとして別の関数をとるか、結果として別の関数を返すようになると、ただちにそれが高階関数と呼ばれます。それだけですよ、皆さん!


高階関数について、これほどのお祭り騒ぎが繰り広げられているのがなぜなのか、今は不思議に思うかもしれませんね。でもちょっと待ってください。今はただ表面をひっかいて、高階関数が主に適用される領域への扉を開いただけなのです(これについては、今後のエピソードで1度ならず取り上げていきます)。私たちがちょうど今発見した新しいツールは、後になれば、非常に柔軟で、しかも強力だということがわかるということです。マクガイバー*1が関数型プログラマであったら、この高階関数をお気に入りのツールの1つに選ぶでしょう。仮にペーパー・クリップを使ったとしても、マクガイバーがそこから何を生み出せるのか、あなたはご存知ですよね?


後には何が残るでしょう?整数値のリストをフィルタリングするための純粋な仕組みを、単一の関数 filterカプセル化することに成功しました。その際に、フィルタの述語(結果となるリストに残るのがどの値かを決める責務を持つ)は、独自の関数に抽象化されて切り出されました。そして、このフィルタ関数は、今や望みのフィルタ述語を使ってパラメタ化できるので、私たちはこの同一のフィルタ関数を参照し、別々の述語関数を渡すことによって、さまざまな用途に使うことができるのです。:

val even = ( x :Int ) => x % 2 == 0 
...

val odd = ( x :Int ) => x % 2 == 1 
...

val candidates = List( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ) 

val evenValues = filter( even, candidates ) 
val oddValues = filter( odd, candidates ) 

いいでしょう。では最後にもう1つ、もう少し複雑なことを練習してみましょう。これがわかれば、高階関数の基本はすべて身につけたことになるでしょう!素数のリストをフィルタリングできるように、もう1つフィルタ述語を書いてみましょう。これは、少なくとも2段階で行い、これまでに学んだ概念をいくつか活用してみましょう。まず第一に、素数として認められる数字の性質について考えましょう。2から、その数の半分までの間に自然因数があってはならないという事実に合意できるでしょうか?よろしい!


それでは、素数の述語に戻る前に、固定の整数に対する自然因数になるであろう数字のリストをふるい分ける関数を書いてみます。通常であれば、引数を2つとる関数を書きます。つまり、最初の引数は任意の数をあらわし、2つめの引数はその数字がとり得る因数をあらわします:

val isFactor = ( num: Int, factor :Int ) => num % factor == 0 

残念ながら、この関数はフィルタ述語として使うことができません。フィルタは、 Int => Boolean 型の関数を要求するからです(今書いた関数の型は、(Int, Int) => Boolean です)。そのため、たとえば100のすべての因数からなる整数値のリストをフィルタリングしたければ、次のような述語関数を書く必要があります:

val isFactorOfHundred = ( factor :Int ) => 100 % factor == 0 

これでいいですか?次に、99、そして1000、その次が1558で、その次が・・・うーん、使いやすそうですか?ここで書いた filter 関数と同じで、因数のリストをフィルタリングしたいすべての数字に対して、新しい述語関数を書きたいとは思えません。ここで高階関数が救いの手を差し伸べます!任意の数字を受け取って、別の関数を返すような関数はどうでしょう?ここで返される別の関数が、他の数を受け取って、それが最初の数の因数かどうかを評価するのです。ややこしいですか?実際にその関数を見れば、すぐに明確になります:

val isFactorOf  =  ( num :Int ) => {

    ( factor :Int ) => num % factor == 0
}
...
val isFactorOfHundred = isFactorOf( 100 )
val isFactorOfNinetyNine = isFactorOf( 99 )
val isFactorOfThousand = isFactorOf( 1000 )

ちょ、ちょ、ちょっと待ってください!どういうワザですか?ここに書いた関数 isFactorOf は、単なる高階関数です。ただ、今回の場合、結果が別の関数になることからそう呼ばれるのです。本体の中にあるのは、もう1つの関数の定義にすぎません。この関数は、isFactoryOf が呼び出されるたびに構築されるのです。そして、その関数定義が関数本体における最後の式であるため、その式の値(つまり関数の値)は、関数全体の結果となります。同時に、結果として生じる関数は、クロージャと呼ぶことができます。なぜかわかりますか?そうですね、引数として宣言されていないことから、num は自由変数です。この場合、囲い込みが行われて、自由変数は周囲を取り巻く関数の引数に束縛されます。こうすることで、任意の数の因数となる整数のリストをフィルタリングできるようになりました。:

val factorsOfHundred =  filter( isFactorOf( 100 ), candidates ) 

ここにも、特筆すべきものはありません。何が起きているかを完全に理解するために必要な素材はすでに手のうちにあります。ここで本当に興味深いのは、第一引数だけです。isFactorOf を値 100 に適用し、その結果は関数になります。その関数が今度は別の整数値をとり、100の因数かどうかを決定します。その都度生成されるこの関数は、Int => Boolean 型であり、したがって、フィルタの述語関数として用いることができます。そこで、フィルタは渡された述語関数を使い、入力されたリストのどの数字が出力されるリストに入るのかを決定します。


この述語関数メーカーを用いることにより、私たちは頭を切り替えて、再び素数をフィルタリングするためのメインの述語に集中できます。ある数字を素数であると判定する上で、関数メーカーがどう役に立つかを考えてみましょう。2から問題となる数字の半分の範囲で、因数があってはならないという事実については、すでに合意しています。これでピンときますか?整数値のコレクションの中に因数がないことは、どうやって調べることができるでしょうか?それでは、その数字の因数だけを取り出すような適切な述語を使って、そのコレクションをフィルタリングするというのはどうでしょう?フィルタリングされたリストが空であれば、その範囲内にある数字には明らかに因数がないことになります。それゆえ、その数字は間違いなく素数です:

val prime = ( num :Int )  =>  num > 1  &&  filter( isFactorOf( num ), (2 to num/2).toList ).isEmpty

いかがでしょう。フィルタリングに基づいて素数かどうかを判定する述語関数ができました。この関数が今度はフィルタリングに使用されるのです。

まとめ

今回のエピソードを通じて、高階関数と呼ばれるものの意味がわかりました。今回は主に、他の関数を受け取るか、関数を返すような関数という基本的な特徴について焦点を合わせてきましたが、それがどういう力を発揮するのか、あなたがたは少しわかっているのではないかと思います。実際、関数型プログラミングの世界における演算作業の多くにとって、(すでに見た通り)高階関数は欠かせません。高階関数によってもたらされるのは、新しい抽象化のやり方(たとえば、Scalaローンパターン*2と呼ばれるリソース制御)や、ある種の状態のシミュレーションもしくは捕捉(差分リストについて考える際に見ていきます)だけでなく、関数型プログラミングが他にも持っている、よく知られた強力な特徴(たとえば、いずれ見ていくカリー化など)の基礎にもなっているのです。

付録

Scalaオブジェクト指向と関数型の特徴を併せ持つハイブリッド言語であるため、Scalaの List型は(実は、List型コンストラクなのですが、これはまた別の機会に)すでに、汎用的な filter メソッドを提供しています。つまり、整数値のリスト(List[Int] 型のオブジェクト)があれば、そのオブジェクトの filter メソッドを呼び出し、Int => Boolean 型の任意の述語関数を渡すことができるのです(これは、前述した filter 関数で行ったのと同様です)。

val candidates = List( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ) 
val evenValues = candidates.filter( even ) // List( 2, 4, 6, 8, 10 ) 
val oddValues = candidates.filter( odd ) // List( 1, 3, 5, 7, 9 ) 
val factorsOfTwelve = candidates.filter( isFactorOf( 12 ) ) // List( 1, 2, 3, 4, 6 ) 
val primes = candidates.filter( prime ) // List( 2, 3, 5, 7 ) 

お望みなら、このメソッドを高階メソッドと呼ぶこともできるかもしれません。


参考文献

プログラミングScala

プログラミングScala

Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)

Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)

*1:訳註:アメリカのドラマで、邦題「冒険野郎マクガイバー」の主人公の名前。紹介サイトによれば、「手近にある材料を使って、悪の陰謀を打破する」タイプのアクションドラマで、「ペーパークリップで核ミサイルの発射を食い止めたり」できるそうです。日本ではちょうど「特攻野郎Aチーム」の後にテレビ放送されたみたいですね。私は見たことがありません。

*2:ローンパターンとは、オープン・クローズが必要なリソースに対して、それを制御する関数がリソースを「貸し出す」というもの。詳しくは「Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)」(p.167)を参照。