Scala は「パターンマッチング (pattern matching)」を使って条件分岐を行うことができます。また、リストもパターンマッチングで分解することができます。これらの機能は論理型言語 Prolog のパターンマッチングと大変よく似ています。パターンマッチングは Scala だけではありません。Erlang, SML/NJ, OCaml, Haskell など関数型言語の特徴のひとつで、とても便利で強力な機能です。
Scala の場合、val や var で変数を宣言するとき、パターンマッチングを使うことができます。次の例を見てください。
scala> val (a, b) = (1, 2) val a: Int = 1 val b: Int = 2 scala> val (c, d) = ((1, 2), 3) val c: (Int, Int) = (1,2) val d: Int = 3 scala> val ((e, f), g) = ((1, 2), 3) val e: Int = 1 val f: Int = 2 val g: Int = 3
右辺 (a, b) がパターンを表します。要素が 2 つ並んでいるので、2 要素のタプルを表すパターンになります。パターン (a, b) と左辺の (1, 2) を照合して、変数部分に対応する要素を取り出して変数にセットします。次の例のように、(c, d) と ((1, 2), 3) を照合すると、c は (1, 2) になり、d は 3 になります。
パターンは入れ子にしてもかまいません。((e, f), g) と ((1, 2), 3) を照合すると、e = 1, f = 2, g = 3 となります。このように、パターンを使ってタプルの要素を取り出すことができます。ただし、型が違うと照合に失敗してエラーになるので注意してください。
リストもパターンマッチングを使って要素を取り出すことができます。リストのパターンはコンス演算子 :: を使って表します。次の例を見てください。
scala> val x::xs = List(1, 2, 3, 4, 5) -- Warning: --------------------------------- ... 省略 ... val x: Int = 1 val xs: List[Int] = List(2, 3, 4, 5) scala> val y::ys = List(1) -- Warning: --------------------------------- ... 省略 ... val y: Int = 1 val ys: List[Int] = List() scala> val z::zs = ys -- Warning: --------------------------------- ... 省略 ... scala.MatchError: List() (of class scala.collection.immutable.Nil$) ... 省略 ...
Scala3 では Warning が表示されますが、ここでは無視してください。x::xs がパターンを表します。このパターンはリストとマッチングして、先頭の要素が x に、先頭要素を取り除いた残りのリストが xs に束縛されます。リストの要素が 1 つしかない場合、y::ys は y が 1 とマッチングして、ys は空リストとマッチングします。また、z::zs は空リスト ys とはマッチングしません。マッチングエラーが送出されます。このように、関数 head や tail を使わなくてもリストを分解することができます。
match 式を使うと、パターンマッチングで条件分岐を行うことができます。match 式の構文を示します。
式0 match {
case pattern_1 => 式1
case pattern_2 => 式2
...
case pattern_n => 式n
}
case で区切られた部分をマッチング節 (matching clause) といいます。match 式は式 0 の評価結果とパターンを照合し、マッチングする節を選択して実行します。たとえば、式 0 の結果と pattern_1 がマッチングした場合、式 1 を評価してその結果が match 式の返り値になります。マッチングしない場合は次のパターンを調べます。マッチングするパターンが見つからない場合はエラーになります。
なお、一度マッチング節が選択された場合、それ以降の節は選択されません。また、式 1 から式 n の結果は同じ型でなければいけません。ご注意ください。
簡単な例を示しましょう。match 式を使って階乗を求める関数 fact を定義すると次のようになります。
scala> def fact(n: Int): BigInt = n match {
| case 0 => 1
| case m => m * fact(m - 1)
| }
def fact(n: Int): BigInt
scala> fact(10)
val res0: BigInt = 3628800
scala> fact(20)
val res1: BigInt = 2432902008176640000
パターンが定数の場合、同じ値とマッチングします。最初の定義はパターンが 0 なので、引数 n が 0 の場合にマッチングします。パターンが変数の場合はどんな値とでもマッチングします。そして、変数はその値に初期化されます。したがって、n が 0 以外の場合は 2 番目のパターンと一致して、変数 m の値は n になります。ここで再帰呼び出しが行われます。なお、変数の有効範囲はそのマッチング節の中だけになります。
変数 m は n と同じ値なので、パターンにワイルドカード ( _ ) を使って次のように定義してもかまいません。
case _ => n * fact(n - 1)
このように、if を使わなくてもパターンマッチングでプログラムを作ることができます。
パターンマッチングを使うときは、マッチング節を定義する順番に気をつけてください。fact の場合、最初にパターン m や _ を定義すると、引数が 0 の場合でもマッチングするので、パターン 0 のマッチング節が実行されることはありません。特定のパターンから定義するように注意してください。
次はリストのパターンマッチングについて、もう少し詳しく説明しましょう。たとえば、パターンを使って関数 append を定義すると次のようになります。
scala> def append[A](xs: List[A], ys: List[A]): List[A] = xs match {
| case Nil => ys
| case z::zs => z :: append(zs, ys)
| }
def append[A](xs: List[A], ys: List[A]): List[A]
scala> append(List(1,2,3), List(4,5,6))
val res2: List[Int] = List(1, 2, 3, 4, 5, 6)
scala> append(Nil, List(1,2,3))
val res3: List[Int] = List(1, 2, 3)
最初のパターンは、xs が空リストのときにマッチングします。2 番目のパターンはリスト xs を先頭要素 z と残りのリスト zs に分解します。このように、match 式を使うとリストを簡単に分解することができます。
リストを表すパターンは x::xs だけではありません。よく使われるパターンを次に示します。
(1) x::Nil 要素が 1 つのリストとマッチング (2) x::y::Nil 要素が 2 つのリストとマッチング (3) x::xs 要素が 1 つ以上あるリストとマッチング (4) x1::x2::xs 要素が 2 つ以上あるリストとマッチング (5) x1::x1::xs エラー
(5) のように、パターンの中に同名の変数を使うことはできません。この場合、x1::x2::xs とマッチングさせてから x1 と x2 が等しいかチェックします。このような場合、パターンの後ろで if を使うと便利です。if の構文を示します。
case パターン if (条件式) => 式
このようなマッチング節を「ガード付き節」といいます。パターンとの照合に成功して、かつ if の条件式が真を返す場合に限り式が評価されます。たとえば、if を使って (5) を実現すると次のようになります。
case x1::x2::xs if (x1 == x2) => 式1 case x1::x2::xs if (x1 < x2) => 式2 case x1::x2::xs => 式3
パターンとの照合に成功して、x1 == x2 の場合は式 1 が評価されます。x1 < x2 の場合は式 2 が評価され、それ以外の場合は式 3 が評価されます。
また、もっと複雑なリストもパターンで表すことができます。
(1) (x, y)::xs 要素がタプルのリストとマッチング
ex) List((1, 2), (3, 4), (5, 6)) => x = 1, y = 2, xs = List((3, 4), (5, 6))
(2) (x::xs)::ys 要素がリストのリスト ('a list list) とマッチング
ex) List(List(1, 2, 3), List(4, 5), List(6)) => x = 1, xs = List(2, 3), ys = List(List(4, 5), List(6))
ご参考までに、関数 length, reverse, member をパターンマッチングを使って書き直してみましょう。
リスト : パターンマッチングの使用例
object sample0402 {
def length[A](xs: List[A]): Int =
xs match {
case Nil => 0
case _::ys => 1 + length(ys)
}
def reverse[A](xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => reverse(ys) ::: List(y)
}
def member[A](x: A, xs: List[A]): Option[A] =
xs match {
case Nil => None
case y::ys if (x == y) => Some(y)
case y::ys => member(x, ys)
}
}
scala> :load sample0402.scala // defined object sample0402 scala> import sample0402._ scala> length(List(1,2,3,4,5)) val res4: Int = 5 scala> reverse(List(1,2,3,4,5)) val res5: List[Int] = List(5, 4, 3, 2, 1) scala> member(3, List(1,2,3,4,5)) val res6: Option[Int] = Some(3)
Option もパターンマッチングすることができます。次の例を見てください。
scala> def foo(a: Option[String]): String = a match {
| case None => "oops!"
| case Some(mes) => mes
| }
def foo(a: Option[String]): String
scala> foo(None)
val res7: String = oops!
scala> foo(Some("hello"))
val res8: String = hello
パターンマッチングで Some と None を区別するだけではなく、Some(mes) のように変数 mes を指定すると、Some の値を mes に取り出すことができます。
それでは簡単な例題として、「連想リスト (association list : a-list)」を作ってみましょう。連想リストは Lisp でよく用いられるデータ構造で、Scala ではキーとデータのタプルを要素とするリストで実現できます。データ型で記述すると List[(A, B)] になり、A がキーで B がデータに対応するデータになります。次の図を見てください。
┌────┬────┬────┬──→ データ
│ │ │ │
連想リスト => [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
│ │ │ │
└────┴────┴────┴──→ キー
図 : 連想リストの構造
上図の場合、文字列 "a", "b", "c", "d" がキーで、整数 1, 2, 3, 4 がデータとなります。一般に、キーには文字列を用いることが多く、データは何でもかまいません。
それでは連想リストを操作する関数を作りましょう。関数名は Common Lisp から拝借しました。次のリストを見てください。
リスト : 連想リスト
object sample0403 {
def acons[A, B](x: A, y: B, xs: List[(A, B)]): List[(A, B)] = (x, y) :: xs
def pairlis[A, B](xs: List[A], ys: List[B]): List[(A, B)] =
(xs, ys) match {
case (Nil, _) | (_, Nil) => Nil
case (x::xs1, y::ys1) => (x, y)::pairlis(xs1, ys1)
}
def assoc[A, B](key: A, xs: List[(A, B)]): Option[B] =
xs match {
case Nil => None
case (y, v)::ys if (y == key) => Some(v)
case _::ys => assoc(key, ys)
}
}
関数 acons はキー x とデータ y と連想リスト xs を受け取り、xs の先頭に x と y を追加します。これは簡単ですね。関数 pairlis は 2 つのリストを受け取り、第 1 引数のリストの要素がキー、第 2 引数のリストの要素がデータとなる連想リストを生成します。引数のリストの長さが違う場合は短い方に合わせます。
pairlis の match が照合する式の値はタプルになるので、パターンにはタプルを使います。最初の節の | は OR の意味で、左右どちらかのパターンがマッチすれば、その節が選択されます。つまり、xs または ys のどちらかが空リストであれば Nil を返します。
関数 assoc は指定したキーと等しいデータを探します。見つけた場合、値を Some に格納して返します。見つからない場合は None を返します。このように、パターンマッチングとガード節を使うと簡単にプログラムを作ることができます。
それでは、簡単な実行例を示します。
scala> :load sample0403.scala
// defined object sample0403
scala> import sample0403._
scala> val alist = pairlis(List("foo", "bar", "baz"), List(1,2,3))
val alist: List[(String, Int)] = List((foo,1), (bar,2), (baz,3))
scala> assoc("foo", alist)
val res9: Option[Int] = Some(1)
scala> assoc("bar", alist)
val res10: Option[Int] = Some(2)
scala> assoc("baz", alist)
val res11: Option[Int] = Some(3)
scala> assoc("oops", alist)
val res12: Option[Int] = None
scala> val alist1 = acons("oops", 4, alist)
val alist1: List[(String, Int)] = List((oops,4), (foo,1), (bar,2), (baz,3))
scala> assoc("oops", alist1)
val res13: Option[Int] = Some(4)
もう一つ簡単な例題としてリストをソートする関数を作ってみましょう。ソート (sort) は、ある規則に従ってデータを順番に並べ換える操作のことです。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。Scala のライブラリにはリストをソートする関数がありますが、私達でも簡単に作ることができます。今回は「挿入ソート (insert sort)」を取り上げます。
挿入ソートの考え方はとても簡単です。ソート済みのリストに新しいデータを挿入していくことでソートを行います。たとえば、List(2, 4, 6) に 5 を挿入する場合、リストの要素 n と 5 を順番に比較して、5 < n を満たす位置に 5 を挿入すればいいわけです。この場合は、4 と 6 の間に 5 を挿入すればいいですね。
ソートするリストは tail で分解していくと空リストになります。これをソート済みのリストと考えて、ここにデータを挿入していきます。プログラムは次のようになります。
リスト : 挿入ソート
object sample0404 {
def insertSort(xs: List[Int]): List[Int] = {
def insertElement(x: Int, xs: List[Int]): List[Int] =
xs match {
case Nil => List(x)
case y::ys => if (x < y) x::y::ys else y::insertElement(x, ys)
}
xs match {
case Nil => Nil
case y::ys => insertElement(y, insertSort(ys))
}
}
}
関数 insertSort は引数のリスト xs を再帰呼び出しで分解します。insertSort を再帰呼び出ししてリスト ys をソートし、そのリストに先頭要素 y を関数 insertElement で挿入します。
局所関数 insertElement は再帰呼び出しでリストをたどり、データ x を挿入する位置を探します。引数のリストが空リストであれば、x が一番大きなデータです。List(x) を返します。これで、リストの最後尾に x を挿入することができます。次の節でリストを分解して、x が先頭の要素 y よりも小さい場合は、その位置に x を挿入します。そうでなければ、insertElement を再帰呼び出しします。
それでは実行してみましょう。
scala> :load sample0404.scala // defined object sample0404 scala> import sample0404._ scala> insertSort(List(5,6,4,7,3,8,2,9,1,0)) val res14: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) scala> insertSort(List(9,8,7,6,5,4,3,2,1,0)) val res15: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) scala> insertSort(List(0,1,2,3,4,5,6,7,8,9)) val res16: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。挿入ソートは簡単ですが遅いアルゴリズムなのです。
なお、次のように比較関数 (引数 lt) を渡すと多相型関数として定義することができます。
リスト : 挿入ソート (多相型)
def insertSort[A](lt: (A, A) => Boolean, xs: List[A]): List[A] = {
def insertElement(x: A, xs: List[A]): List[A] =
xs match {
case Nil => List(x)
case y::ys => if (lt(x, y)) x::y::ys else y::insertElement(x, ys)
}
xs match {
case Nil => Nil
case y::ys => insertElement(y, insertSort(lt, ys))
}
}
簡単な実行例を示します。
scala> insertSort((x:Int,y:Int) => x < y, List(5, 4, 3, 2, 1)) val res0: List[Int] = List(1, 2, 3, 4, 5) scala> insertSort((x:Double,y:Double) => x < y, List(5.5, 4.4, 3.3, 2.2, 1.1)) val res1: List[Double] = List(1.1, 2.2, 3.3, 4.4, 5.5)