関数型言語の場合、リスト操作関数の多くは高階関数として定義されています。Scala の場合も、リスト操作用メソッドの多くは高階関数として定義されています。今回はよく使われる高階関数として、マッピング、フィルター、畳み込み (縮約) について説明します。
まず最初に、リストの各要素を関数 f に渡し、その評価結果をリストに格納して返す関数を作ってみましょう。このような操作を「マッピング (写像)」といいます。なお、関数に引数を与えて呼び出すことを、関数型言語では「適用」といいます。本稿でも関数呼び出しの意味で適用を使うことにします。
次のリストを見てください。
リスト : マッピング def mapcar[A, B](f: A => B, xs: List[A]): List[B] = xs match { case Nil => Nil case y::ys => f(y) :: mapcar(f, ys) }
関数名は mapcar としました。名前は Common Lisp から拝借しました。なお、Scala には同じ機能を持つメソッド map があります。
第 1 引数 f が関数型 A => B で第 2 引数 xs がリスト List[A] になります。関数 f はリストの要素を受け取るので、関数 f の引数の型とリストの要素の型は一致します。これを型パラメータ A で表しています。同様に、関数 f の返り値の型と mapcar の返り値のリストの要素の型は一致します。これを型パラメータ B で表しています。このように、mapcar は多相型関数として定義されます。
プログラムは簡単です。パターンマッチングで引数のリストを先頭の要素 y と残りのリスト ys に分解します。そして、y に関数 f を適用した結果と mapcar(f, ys) の結果をコンス演算子 :: で結合します。引数のリストが空リストの場合が再帰呼び出しの停止条件になります。
簡単な実行例を示します。
scala> mapcar((x: Int) => x * x, List(1, 2, 3, 4, 5)) val res0: List[Int] = List(1, 4, 9, 16, 25) scala> mapcar((x: Int) => Math.sqrt(x), List(1, 2, 3, 4, 5)) val res1: List[Double] = List(1.0, 1.4142135623730951, 1.7320508075688772, 2.0, 2.23606797749979)
Scala の場合、マッピングはメソッド map を使います。
scala> List(1,2,3,4,5).map(x => x * x) val res2: List[Int] = List(1, 4, 9, 16, 25) scala> List(1,2,3,4,5).map(x => Math.sqrt(x)) val res3: List[Double] = List(1.0, 1.4142135623730951, 1.7320508075688772, 2.0, 2.23606797749979)
ここで便利な機能を紹介しましょう。無名関数の引数が式の中で一度しか使われない場合、引数をアンダーバー ( _ ) で代用することができます。これを「プレースホルダー」と呼びます。
たとえば、無名関数 (x: Int, y: Int) => x + y は、式の中で引数 x と y が 1 回ずつしか現れていないので、プレースホルダーを使って表すことができます。次の例を見てください。
scala> val f1:(Int, Int) => Int = _ + _ val f1: (Int, Int) => Int = $Lambda$1166/0x0000000840566840@225e09f0 scala> f1(10, 20) val res4: Int = 30 scala> val f2 = (_: Int) + (_: Int) val f2: (Int, Int) => Int = $Lambda$1177/0x000000084064a040@5383bf08 scala> f2(100, 200) val res5: Int = 300
変数 f1 に関数型を指定すると、式はプレースホルダーを使って _ + _ と表すことができます。引数が複数ある場合、左側から見て最初の _ が第 1 引数に、2 番目の _ が第 2 引数に対応します。また、f2 のように _ で型を指定することもできます。
マッピング (map) の例題で、無名関数 x => x * x は引数 x が 2 回現れているのでプレースホルダーは使えませんが、x => Math.sqrt(x) はプレースホルダーを使って Math.sqrt(_) と表すことができきます。
フィルター (filter) は、引数の関数が真を返す要素だけをリストに格納して返す働きをする関数です。関数型言語では、真または偽を返す関数のことを「述語 (predicate)」といいます。ここでは簡単な例題として、フィルターとは逆の働きをする関数、つまり述語が真を返す要素を削除する関数 removeIf を作ってみましょう。名前は Common Lisp から拝借しました。
リスト : 要素の削除 def removeIf[A](f: A => Boolean, xs: List[A]): List[A] = xs match { case Nil => Nil case y::ys if (f(y)) => removeIf(f, ys) case y::ys => y :: removeIf(f, ys) }
mapcar と同様に removeIf も簡単です。引数 f の型は A => Boolean で、引数 xs の型は List[A] になります。f の引数の型とリストの要素の型は同じになります。f(y) が真ならば y を返り値のリストに加えません。偽ならば y を返り値のリストに加えるだけです。
簡単な実行例を示します。
scala> removeIf((_: Int) % 2 == 0, List(1, 2, 3, 4, 5)) val res0: List[Int] = List(1, 3, 5) scala> removeIf((_: String) == "bar", List("foo", "bar", "baz")) val res1: List[String] = List(foo, baz)
最初の例では偶数の要素が削除されます。次の例は文字列 "bar" が削除されます。
もちろん、フィルターも簡単に定義することができます。removeIf とは逆に、述語が真を返すとき要素をリストに追加し、偽を返すときはリストに加えません。
リスト : フィルター def filter[A](f: A => Boolean, xs: List[A]): List[A] = xs match { case Nil => Nil case y::ys if (f(y)) => y :: filter(f, ys) case _::ys => filter(f, ys) }
簡単な実行例を示しましょう。
scala> filter((_: Int) % 2 == 0, List(1, 2, 3, 4, 5)) val res2: List[Int] = List(2, 4)
Scala のライブラリには、メソッド filter, filterNot が用意されています。
scala> List(1, 2, 3, 4, 5).filter(_ % 2 == 0) val res3: List[Int] = List(2, 4) scala> List(1, 2, 3, 4, 5).filterNot(_ % 2 == 0) val res4: List[Int] = List(1, 3, 5)
2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を下図のように適用します。
(1) (a1, a2, a3, a4, a5) => f( f( f( f( a1, a2 ), a3 ), a4 ), a5 ) (2) (a1, a2, a3, a4, a5) => f( a1, f( a2, f( a3, f( a4, a5 ) ) ) ) 図 : 関数 reduce の動作
関数 f を適用する順番で 2 通りの方法があります。図 (1) はリストの先頭から f を適用し、図 (2) はリストの後ろから f を適用します。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。
f(x, y) = x + y の場合 reduce => a1 + a2 + a3 + a4 + a5
このように、reduce はリストのすべての要素を関数 f を用いて結合します。このような操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は下図に示す動作になります。
(1) (a1, a2, a3, a4, a5) => f( f( f( f( f( g, a1 ), a2 ), a3 ), a4 ), a5 ) (2) (a1, a2, a3, a4, a5) => f( a1, f( a2, f( a3, f( a4, f( a5, g ) ) ) ) ) 図 : reduce() の動作 (2)
ここでは簡単な例題として、上図 (1) の動作を行う関数 foldl と、上図 (2) の動作を行う関数 foldr を作ってみましょう。
プログラムは次のようになります。
リスト : 畳み込み def foldl[A, B](f: (A, B) => A, a: A, xs: List[B]): A = xs match { case Nil => a case y::ys => foldl(f, f(a, y), ys) } def foldr[A, B](f: (B, A) => A, a: A, xs: List[B]): A = xs match { case Nil => a case y::ys => f(y, foldr(f, a, ys)) }
第 1 引数 f が適用する関数、第 2 引数 a が初期値、第 3 引数がリストです。foldl と foldr の返り値は初期値 a の型 A と同じになります。つまり、リストの要素と同じ型である必要はありません。そして、渡される関数の型にも注目してください。foldl の場合、関数の第 1 引数と初期値の型が同じです。第 1 引数に今までの処理結果が渡されて、第 2 引数にリストの要素が渡されることがわかります。これに対し、foldr は逆になっていることに注意してください。
最初のマッチング節は再帰呼び出しの停止条件ですが、foldl (foldr) に空リストが与えられた場合にも対応します。この場合は初期値 a を返します。次のマッチング節でリストの要素を取り出して関数 f を呼び出します。
たとえば、リストが [1, 2, 3] で a が 0 とします。最初は f(0, 1) が実行され、その返り値が foldl の第 2 引数に渡されます。次は f(a, 2) が実行されますが、これは f(f(0, 1), 2) と同じことです。そして、その結果が foldl の第 2 引数になります。最後に f(a, 3) が実行されますが、これは f(f(f(0, 1), 2), 3) となり、上図 (1) と同じ動作になります。
foldl の場合、リストの要素が関数 f の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。これに対し、foldr の場合は逆になり、関数 f の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。これで上図 (2) の動作を実現することができます。
簡単な実行例を示します。
scala> foldl((_: Int) + (_: Int), 0, List(1, 2, 3, 4, 5)) val res5: Int = 15 scala> foldr((_: Int) + (_: Int), 0, List(1, 2, 3, 4, 5)) val res6: Int = 15
Scala のライブラリには、メソッド foldLeft, foldRight が用意されています。
scala> List(1, 2, 3, 4, 5).foldLeft(0)(_ + _) val res7: Int = 15 scala> List(1, 2, 3, 4, 5).foldRight(0)(_ + _) val res8: Int = 15
ところで、foldl, foldr と 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。最初に length の例を示します。
scala> foldl((a: Int, x: Int) => a + 1, 0, List(1, 2, 3, 4, 5)) val res9: Int = 5 scala> foldr((x: Int, a:Int) => a + 1, 0, List(1, 2, 3, 4, 5)) val res10: Int = 5 scala> def length[A](xs: List[A]): Int = foldl((a: Int, x: A) => a + 1, 0, xs) def length[A](xs: List[A]): Int scala> length(List(1, 2, 3, 4, 5, 6)) val res11: Int = 6
foldl で length を実現する場合、初期値を 0 にして第 1 引数の値を +1 することで実現できます。foldr の場合は第 2 引数の値を +1 します。
次に map の例を示します。
scala> foldr((x: Int, a: List[Int]) => (x * x)::a, Nil, List(1,2,3,4,5)) val res12: List[Int] = List(1, 4, 9, 16, 25) scala> def mapcar[A,B](f: A => B, xs: List[A]): List[B] = | foldr((x: A, a: List[B]) => f(x) :: a, Nil, xs) def mapcar[A, B](f: A => B, xs: List[A]): List[B] scala> mapcar((x: Int) => x * x, List(1, 2, 3, 4, 5)) val res13: List[Int] = List(1, 4, 9, 16, 25)
map の場合は foldr を使うと簡単です。初期値を Nil にして第 1 引数の計算結果を第 2 引数のリストに追加するだけです。
次に filter の例を示します。
scala> foldr((x: Int, a: List[Int]) => if (x % 2 == 0) x::a else a, Nil, List(1, 2, 3, 4, 5)) val res14: List[Int] = List(2, 4) scala> def filter[A](f: A => Boolean, xs: List[A]): List[A] = | foldr((x: A, a: List[A]) => if (f(x)) x::a else a, Nil, xs) def filter[A](f: A => Boolean, xs: List[A]): List[A] scala> filter((x: Int) => x % 2 == 0, List(1, 2, 3, 4, 5)) val res15: List[Int] = List(2, 4)
filter の場合も初期値を Nil にして、第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。
最後に述語が真となる要素の個数を求めてみましょう。これは Common Lisp の関数 count-if と同じです。
scala> foldl((a: Int, x: Int) => if (x % 2 == 0) a + 1 else a, 0, List(1, 2, 3, 4, 5)) val res16: Int = 2 scala> def countIf[A](f: A => Boolean, xs: List[A]): Int = | foldl((a:Int, x:A) => if (f(x)) a + 1 else a, 0, xs) def countIf[A](f: A => Boolean, xs: List[A]): Int scala> countIf((x: Int) => x % 2 == 0, List(1, 2, 3, 4, 5)) val res17: Int = 2
このように、畳み込みを使っていろいろな処理を実現することができます。
副作用を目的とした高階関数を作ることもできます。foreach はリストの要素に関数を適用しますが、その返り値をリストに格納することはしません。次のリストを見てください。
リスト : foreach def foreach[A](f: A => Unit, xs: List[A]): Unit = xs match { case Nil => () case x::ys => { f(x); foreach(f, ys) } } // 別解 def foreach[A](f: A => Unit, xs: List[A]) { for (x <- xs) f(x) }
最初は再帰定義でプログラムしています。関数 f の型は A => Unit になります。xs が空リストの場合は Unit の値 () を返します。そうでなければ、リストを x::ys で分解して、ブロックの中で f(x) を呼び出したあと、foreach を再帰呼び出しします。別解は for ループでプログラムしたものです。for 式で取り出した要素 x を関数 f に渡して呼び出すだけです。
それでは実行してみましょう。
scala> foreach(println, List(1,2,3,4,5)) 1 2 3 4 5
このように、foreach に println を渡すとリストの要素を表示することができます。
なお、Scala のライブラリには同じ機能を持つメソッド foreach が用意されてます。
scala> List(1,2,3,4,5).foreach(println) 1 2 3 4 5
Scala でリストを操作する場合、高階関数だけではなく「for 内包表記 (for comprehensions)」を使うことができます。基本的な構文を次に示します。
for (パターン <- コレクション [if (条件式)]) yield 式
"パターン <- コレクション" の部分を「ジェネレータ」とか「生成器」といいます。for 式は変数の定義でパターンマッチングを使うことができます。ジェネレータのあとには "if (条件式)" を付けることができます。これを「フィルター」といいます。これは match 式のガード節と同じ意味で、条件式を満たす変数が for の本体 "yield 式" に送られます。yield は式を実行し、その結果を新しく生成したコレクションに格納します。ジェネレータに与えるコレクションの型がリストであれば、生成されるコレクションの型もリストになります。
簡単な例を示しましょう。
scala> val a = List(1, 2, 3, 4, 5, 6, 7, 8) val a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8) scala> for (x <- a) yield x * x val res20: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64) scala> for (x <- a if x % 2 == 0) yield x * x val res21: List[Int] = List(4, 16, 36, 64) scala> for (x <- a if x % 2 != 0) yield x * x val res22: List[Int] = List(1, 9, 25, 49)
最初の例は要素を 2 乗したリストを生成します。次の例は、偶数の要素を取り出して 2 乗します。最後の例は奇数の要素を取り出して 2 乗します。これらの動作は高階関数 mapcar や filter と同じです。
for 内包表記は複数の生成器を指定することもできます。次の例を見てください。
scala> for (x <- List(1,2,3); y <- List(4,5,6)) yield (x, y) val res23: List[(Int, Int)] = List((1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6))
最初に、x に 1 がセットされ、次にリスト List(4, 5, 6) の要素が y にセットされるので、タプル (1,4), (1,5), (1,6) が生成されます。次に、x の値が 2 にセットされてから、再度 y に List(4, 5, 6) の要素が順番にセットされるので、タプル (2,4), (2,5), (2,6) が生成されます。最後に、x が 3 にセットされてタプル (3,4), (3,5), (3,6) が生成されます。
また、それぞれの生成器のあとに条件式を設定することもできます。簡単な例を示します。
scala> for (x <- a if x % 2 == 0; y <- a if y % 2 != 0) yield (x, y) val res24: List[(Int, Int)] = List((2,1), (2,3), (2,5), (2,7), (4,1), (4,3), (4,5), (4,7), (6,1), (6,3), (6,5), (6,7), (8,1), (8,3), (8,5), (8,7))
タプルの第 1 要素 x は偶数、第 2 要素 y は奇数になります。
それでは簡単な例題として、高速なソートアルゴリズムとして有名な「クイックソート (quick sort)」を作ってみましょう。クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
[5, 3, 7, 6, 9, 8, 1, 2, 4] 5 を枢軸に分割 [3, 1, 2, 4] 5 [7, 6, 9, 8] 3を枢軸に分割 7を枢軸に分割 [1, 2] 3 [4] | 5 | [6] 7 [9, 8] ・・・分割を繰り返していく・・・ 図 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。
リスト : クイックソート def quickSort(xs: List[Int]): List[Int] = xs match { case Nil => Nil case p::ys => { val a = for (y <- ys if y < p) yield y val b = for (y <- ys if y >= p) yield y quickSort(a) ::: List(p) ::: quickSort(b) } }
引数のリスト xs が空リストであれば空リストを返します。そうでなければ、リストの先頭要素 p を枢軸として、内包表記で p より小さい要素と p 以上の要素に分けます。あとは quickSort を再帰呼び出しして、その結果を List(x) をはさんで演算子 ::: で連結するだけです。ただし、リスト ys を二分割するとき、ys を 2 回走査することに注意してください。
簡単な実行例を示します。
scala> quickSort(List(5,4,6,3,7,2,8,1,9,0)) val res25: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) scala> quickSort(List(9,8,7,6,5,4,3,2,1,0)) val res26: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) scala> quickSort(List(0,1,2,3,4,5,6,7,8,9)) val res27: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
正常に動作していますね。
クイックソートの実行時間は、データ数を N とすると平均して N * log2 N に比例します。ところが、枢軸の選び方によっては、最悪で N の 2 乗に比例するところまで劣化します。つまり、挿入ソートと同じくらい遅くなってしまうのです。たとえば、リストの先頭要素を枢軸として選ぶ場合、リストの要素が昇順または降順に並んでいると最悪の結果になります。
このため、クイックソートをプログラムする場合、枢軸の選び方を工夫するのが一般的です。たとえば、データの中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸に選びます。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は減少しますが、中間の値を選ぶのに時間がかかってしまいます。実際には、3 つから 5 つの要素を選んで、その中で中間の値を枢軸とする場合が多いようです。
ただし、この改良方法はリストには不向きであることに注意してください。リストはデータ数が多くなるほど、後ろのデータを取り出すのに時間がかかるようになります。先頭から 3 つのデータを取り出して枢軸を選んだとしても、降順または昇順に並んだデータには効果が無いのは明らかです。このため、リストのソートはクイックソートよりも「マージソート (merge sort)」の方が適しているといわれています。
もうひとつ簡単な例題として、リストを平坦化する関数 flatten を作ってみましょう。簡単な動作例を示します。
flatten(List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))) => List(1, 2, 3, 4, 5, 6, 7, 8, 9) flatten(List(List(1, 2, 3), Nil, List(4, 5, 6), Nil, List(7, 8, 9))) => List(1, 2, 3, 4, 5, 6, 7, 8, 9)
プログラムは次のようになります。
リスト : リストの平坦化 def flatten[A](xs: List[List[A]]): List[A] = xs match { case Nil => Nil case ys::zs => ys ::: flatten(zs) } // 内包表記 def flatten1[A](xs: List[List[A]]): List[A] = for (ys <- xs; y <- ys) yield y
flatten はリストの先頭要素 ys を取り出して、ys と次の要素を演算子 ::: で結合すればいいわけです。for 内包表記を使うともっと簡単になります。リスト xs から要素 ys を取り出し、ys からさらに要素 y を取り出します。あとは、y をリストに格納して返すだけです。
それでは実行してみましょう。
scala> flatten(List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))) val res28: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> flatten1(List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))) val res29: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> flatten(List(List(1, 2, 3), Nil, List(4 ,5, 6), Nil, List(7, 8, 9))) val res30: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> flatten1(List(List(1, 2, 3), Nil, List(4, 5, 6), Nil, List(7, 8, 9))) val res31: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
正常に動作していますね。なお、Scala のライブラリにもメソッド flatten が用意されています。
scala> List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)).flatten val res32: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> List(List(1, 2, 3), Nil, List(4, 5, 6), Nil, List(7, 8, 9)).flatten val res33: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
変数の有効範囲を表す用語に「スコープ (scope)」があります。この用語を使うと、厳密ではありませんが、変数の有効範囲は「レキシカルスコープ (lexical scope)」と「ダイナミックスコープ (dynamic scope)」の 2 つに分けることができます。伝統的な Lisp、たとえば Emacs Lisp はダイナミックスコープですが、現在の Scheme や Common Lisp はレキシカルスコープです。Scala もレキシカルスコープを採用しています。
それでは、レキシカルスコープについて詳しく見てみましょう。フィールド変数 x を表示する関数 foo を定義します。
リスト ; レキシカルスコープ object sample0503 { var x = 10 def foo() = println(x) def foo1() = { val x = 100 println("local value: " + x) foo() } def main(args: Array[String]): Unit = { println("call foo") foo() println("call foo1") foo1() } }
$ scalac sample0503.scala $ sample0503 call foo 10 call foo1 local value: 100 10
関数 foo には局所変数 x を定義していないので、foo を実行した場合はフィールド変数の値を参照します。その結果 10 が表示されます。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 には let で局所変数 x を定義します。この場合、foo はどちらの値を表示するのでしょうか。実際に試してみると、10 と表示されました。
このように、foo1 で定義した局所変数 x は、foo から参照することはできません。次の図を見てください。
上図では変数の有効範囲を枠で表しています。foo1 の val で定義した局所変数 x は、それを定義したブロックの枠の中でのみ有効です。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。順番に外側の枠を調べていくと、最後には関数定義の枠に行き着きます。ここで変数(引数)が見つからない場合はフィールド変数を調べます。
関数 foo は関数定義の枠しかありません。そこに変数 x が定義されていないので、フィールド変数を調べることになるのです。このように、関数 foo から foo1 の枠とブロックの枠を超えて変数 x にアクセスすることはできないのです。これを「レキシカルスコープ」といいます。レキシカルには文脈上いう意味があり、変数が定義されている構造の範囲内 (枠内) でないと、その変数にアクセスすることはできません。
ところが伝統的な Lisp の場合、foo1 で定義した変数 x は呼び出された関数 foo からアクセスすることができます。これを「ダイナミックスコープ」といいます。foo1 で定義された変数 x は、foo1 の実行が終了するまで存在します。そして、foo1 から呼ばれた関数ならば、どこからでも参照することができるのです。もしも、foo1 をダイナミックスコープの処理系、たとえば Emacs Lisp で実行するならば、foo で表示される x の値は 100 になります。
それでは、関数の中で定義された局所関数や無名関数の場合はどうなるのでしょうか。次の例を見てください。
scala> def timesElement(n: Int, xs: List[Int]): List[Int] = | xs.map((x: Int)=> x * n) def timesElement(n: Int, xs: List[Int]): List[Int] scala> timesElement(10, List(1,2,3,4,5)) val res0: List[Int] = List(10, 20, 30, 40, 50)
無名関数の引数は x だけなので、変数 n はフィールド変数を参照するように思われるかもしれません。ところが、変数 n は関数 timesElement の引数 n を参照するのです。これを図に示すと、次のようになります。
ポイントは、無名関数が timesElement 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。無名関数はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義された無名関数は、そのとき有効な局所変数にアクセスすることができるのです。
これは def で定義された局所的な関数も同じです。timesElement は次のように書き換えることができます。
scala> def timesElement1(n: Int, xs: List[Int]): List[Int] = { | def timesN(x: Int): Int = x * n | xs.map(timesN) | } def timesElement1(n: Int, xs: List[Int]): List[Int] scala> timesElement1(10, List(1, 2, 3, 4, 5)) val res1: List[Int] = List(10, 20, 30, 40, 50)
局所関数 timesN は timesElement 内で定義されているので、timesN から timesElement の引数 n を参照することができます。
Lisp などの関数型言語では、関数を生成する関数を簡単に作ることができます。このとき使われる機能が「クロージャ (closure)」です。クロージャは評価する関数と参照可能な局所変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに参照可能な局所変数を保持するところが異なります。参照可能な局所変数の集合を「環境」と呼ぶことがあります。
Scala の関数はカリー化できるので、関数を返す関数はとても簡単に作成することができます。また、Scala は関数型言語でもあるので、当然ですがクロージャも使うことができます。Scala でクロージャを生成するには「無名関数」を使うか、局所的な関数を定義して、その関数を返します。たとえば、「引数を n 倍する関数」を生成する関数は、無名関数を使うと次のようになります。
scala> def foo(n: Int): (Int => Int) = (x: Int) => x * n def foo(n: Int): Int => Int scala> val foo10 = foo(10) val foo10: Int => Int = $Lambda$1094/0x0000000840608840@47f0f414 scala> foo10(1) val res2: Int = 10 scala> foo10(2) val res3: Int = 20 scala> val foo5 = foo(5) val foo5: Int => Int = $Lambda$1094/0x0000000840608840@10ba9780 scala> foo5(10) val res4: Int = 50 scala> foo5(20) val res5: Int = 100
関数 foo は引数を n 倍する関数を生成します。関数 foo の型は、引数 Int を受け取り Int => Int という関数を返すことを表しています。変数 foo10 に foo(10) の返り値をセットします。すると、foo10 は引数を 10 倍する関数として使うことができます。同様に、変数 foo5 に foo(5) の返り値をセットすると、foo5 は引数を 5 倍する関数になります。
無名関数を生成するとき、評価する関数のほかに、そのとき参照可能な局所変数、つまり「環境」もいっしょに保存されます。この場合、参照可能な局所変数は foo の引数 n です。そして、クロージャを実行するときは、保存されている局所変数を参照することができるのです。
foo(10) を実行して無名関数を生成するとき、定義されている局所変数は n で、その値は 10 ですね。この値がクロージャに保存されているので、foo10 の関数は引数を 10 倍した結果を返します。foo(5) を評価すると n の値は 5 で、それがクロージャに保存されているので、foo5 の関数は引数を 5 倍した結果を返すのです。
また、def で局所的な関数を定義して、その関数を返すとクロージャを生成することができます。def を使った例を示します。
scala> def foo(n:Int):(Int => Int) = { | def bar(x:Int):Int = x * n | bar | } def foo(n: Int): Int => Int scala> val foo20 = foo(20) val foo20: Int => Int = $Lambda$1106/0x0000000840566840@5605a59b scala> foo20(11) val res6: Int = 220 scala> foo20(22) val res7: Int = 440
def で局所関数 bar を定義して、bar を返します。すると、foo は「引数を n 倍する関数」を生成する関数になります。
もっとも、Scala では関数を部分適用するだけで同様の関数を作ることができます。
scala> def foo(n: Int)(x: Int): Int = n * x def foo(n: Int)(x: Int): Int scala> val foo100 = foo(100)_ val foo100: Int => Int = $Lambda$1112/0x0000000840107040@8829ecd scala> foo100(111) val res8: Int = 11100 scala> foo100(222) val res9: Int = 22200
このように、Scala は関数の部分適用により目的の関数を簡単に生成することができます。
クロージャを理解する場合、環境を「連想リスト (association list : a-list)」で考えるとわかりやすいと思います。
一般に、関数を呼び出す場合、関数を評価するための環境は空リストです。最初に、引数がこの環境に追加されます。val や var で定義される局所変数もこの環境に追加されます。もしも、環境に該当する変数が存在しない場合は大域変数を参照します。
たとえば、foo(5) と呼び出すと環境は次のようになります。
foo(5) ==> 環境 : [(n, 5)]
連想リストのキー n が変数名で、その値が 5 です。クロージャを生成するとき、この連想リストを保持すると考えてください。そして、クロージャを評価するときは、保存していた環境を使います。したがって、foo5(11) を評価すると、環境 [(n, 5)] に引数 x の値が追加され、[(x, 11), (n, 5)] になります。この環境で式 n * x を評価するので、5 * 11 = 55 を返すわけです。
関数の評価が終了すると、環境に追加された変数は削除されます。foo5(11) の評価で追加された変数は x なので、(x, 11) が削除され [(n, 5)] になります。このように、クロージャに保存された環境は変化しません。
最後に、クロージャの応用例として「ジェネレータ (generator)」というプログラムを紹介しましょう。ジェネレータは、呼び出されるたびに新しい値を生成していきます。Scala の場合、ジェネレータと同じことは「イテレータ (Iterator)」を使って行うことができますが、クロージャでも簡単にプログラムすることができます。
簡単な例題として、奇数列 ( 1, 3, 5, ..... ) を発生するジェネレータを作ってみます。関数名は genOddNumber としましょう。genOddNumber は呼び出されるたびに新しい奇数を返します。いちばん簡単な実装方法は、返した値を大域変数に記憶しておくことです。genOddNumber のプログラムは次のようになります。
リスト : 奇数を発生するジェネレータ object sample0504 { var prevNumber = -1 def genOddNumber(): Int = { prevNumber += 2 prevNumber } }
scala> :load sample0504.scala val args: Array[String] = Array() Loading sample0504.scala... object sample0504 scala> import sample0504._ import sample0504._ scala> for (i <- 1 to 10) println(genOddNumber()) 1 3 5 7 9 11 13 15 17 19
フィールド変数 prevNumber は、genOddNumber が返した値を記憶します。新しい値は、この prevNumber に 2 を足せばいいのです。
このように、大域変数を使うと簡単にジェネレータを作ることができますが問題点もあります。それは、複数のジェネレータが必要になる場合です。単純に考えると、必要な数だけ大域変数と関数を用意すればいいのですが、数が増えると大域変数や関数を定義するだけでも大変な作業になります。
ところがクロージャを使うと、もっとスマートにジェネレータを用意できます。まず、ジェネレータを作る関数を定義します。
リスト : ジェネレータを作る関数 // sample0504 に追加 def makeGen(): (() => Int) = { var prevNumber = -1 () => { prevNumber += 2 prevNumber } }
関数 makeGen はクロージャを返します。そして、このクロージャがジェネレータの役割を果たすのです。それでは、実際に実行してみましょう。
scala> val g1 = makeGen() val g1: () => Int = sample0504$$$Lambda$1153/0x0000000840646c40@174e1b99 scala> g1() val res0: Int = 1 scala> g1() val res1: Int = 3 scala> g1() val res2: Int = 5 scala> g1() val res3: Int = 7 scala> val g2 = makeGen() val g2: () => Int = sample0504$$$Lambda$1153/0x0000000840646c40@3958db82 scala> g2() val res4: Int = 1 scala> g2() val res5: Int = 3 scala> g2() val res6: Int = 5
makeGen で作成したクロージャを変数 g1 にセットして実行します。実行するたびに 1, 3, 5 と奇数列を生成していますね。次に新しいクロージャを変数 g2 にセットします。このクロージャを実行すると、新しい奇数列を生成します。確かにジェネレータとして動作しています。
このプログラムのポイントは局所変数 prevNumber です。クロージャで保存される環境は変数 prevNumber です。この値は makeGen が実行されたときに -1 で初期化されています。クロージャにはこの値が保存されます。
次に、g1 にセットしたクロージャを実行します。匿名関数は、クロージャに保存された局所変数にアクセスするので、prevNumber += 2 の値は 1 になり、クロージャに保持されている prevNumber の値は 1 に更新されます。
環境はクロージャによって異なります。g1 のクロージャが評価されると、そのクロージャの環境が更新されるのであって、ほかのクロージャに影響を与えることはありません。したがって、ジェネレータが発生する奇数列が、ほかのジェネレータに影響を与えることはないのです。あとは必要な数だけジェネレータを makeGen で作り、そのクロージャを変数に格納しておけばいいわけです。
次は、奇数列を最初に戻す、つまり、ジェネレータをリセットすることを考えてみましょう。この場合、クロージャ内の変数を書き換えるしか方法はありません。そこで、makeGen の返り値を 2 つに増やすことにします。最初の返り値は奇数列を発生するジェネレータで、2 番目の返り値はジェネレータをリセットする関数とします。プログラムは次のようになります。
リスト : ジェネレータのリセット // sample0504 に追加 def makeGen1(): (() => Int, () => Unit) = { var prevNumber = -1 (() => { prevNumber += 2 prevNumber }, () => prevNumber = -1) }
返り値の型はタプルで、奇数列を返す関数 () => Int とジェネレータをリセットする関数 () => Unit を格納します。どちらの関数も無名関数を使って簡単に定義することができます。あとは、それをタプルに格納して返すだけです。
それでは実行してみましょう。
scala> val (gen, reset) = makeGen1() val gen: () => Int = sample0504$$$Lambda$1193/0x0000000840667440@5f67181f val reset: () => Unit = sample0504$$$Lambda$1194/0x0000000840667840@1169fdfd scala> gen() val res0: Int = 1 scala> gen() val res1: Int = 3 scala> gen() val res2: Int = 5 scala> reset() scala> gen() val res4: Int = 1 scala> gen() val res5: Int = 3 scala> gen() val res6: Int = 5 scala> gen() val res7: Int = 7
正常に動作していますね。
クロージャは少し難しいかもしれませんが、 便利で面白い機能です。少々歯応えがありますが、 これもプログラミングの面白いところだと思います。興味のある方はいろいろと試してみてください。
ご参考までに、Scala のイテレータを簡単に説明しておきます。Scala の場合、データ (オブジェクト) にメソッド iterator があれば、そのデータをイテレータに変換することができます。イテレータの型は "Iterator[型]" で表され、メソッド has.Next でデータの有無を判定し、メソッド next でイテレータからデータを順番に取り出すことができます。
簡単な例を示しましょう。
scala> val iter = Range(1, 10, 2).iterator val iter: Iterator[Int] = <iterator> scala> iter.hasNext val res8: Boolean = true scala> iter.next() val res9: Int = 1 scala> iter.next() val res10: Int = 3 scala> iter.next() val res11: Int = 5 scala> iter.next() val res12: Int = 7 scala> iter.next() val res13: Int = 9 scala> iter.hasNext val res14: Boolean = false
数列を表す Range を iterator でイテレータに変換し、変数 iter にセットします。すると、iter.next が数列の要素を一つずつ順番に取り出すことができます。リストや配列もイテレータに変換することができますし、自分でイテレータを作ることもできます。詳細はオブジェクト指向のところで説明する予定です。