関数型言語の場合、リスト操作関数の多くは高階関数として定義されています。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 は奇数になります。
[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]
・・・分割を繰り返していく・・・
図 : クイックソート
それでは簡単な例題として、高速なソートアルゴリズムとして有名な「クイックソート (quick sort)」を作ってみましょう。クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。
リスト : クイックソート
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)