今回は「リスト (List)」というデータ構造を説明します。Scala のリストは「連結リスト (Linked List)」のことです。リストを扱うプログラミング言語といえば Lisp が有名です。SML/NJ, OCaml, Haskell などの関数型言語や論理型言語の Prolog も、組み込みのデータ構造として連結リストをサポートしています。
連結リストは単純なデータ構造ですが、他のデータ構造を実装するときに用いられることがあります。連結リストは基本的で重要なデータ構造の一つなのです。
リストの構造を図で表すと次のようになります。
リストは貨物列車にたとえるとわかりやすいでしょう。車両に相当するものを「コンスセル (cons cell)」といいます。貨物列車には多数の車両が接続されて運行されるように、リストは複数のコンスセルを接続して構成されます。1 つのコンスセルには、貨物(データ)を格納する場所と、連結器に相当する場所があります。
上図では、コンスセルを箱で表しています。コンスセルの左側がデータを格納する場所で、右側が次のコンスセルと連結しています。この例では、3 つのコンスセルが接続されています。それから、最後尾のコンスセルには、リストの終わりを示す特別なデータが格納されます。Scala の場合、要素が一つもないリスト (空リスト) を表すデータ Nil でリストの終端を表します。
Scala のリストは、List(要素1, 要素2, ...) で生成します。次の例を見てください。
scala> val a = List(1,2,3,4) val a: List[Int] = List(1, 2, 3, 4) scala> a(0) val res0: Int = 1 scala> a(3) val res1: Int = 4 scala> a(0) = 10 ^ error: value update is not a member of List[Int] did you mean updated? scala> val b = List("foo", "bar", "baz") val b: List[String] = List(foo, bar, baz) scala> val c = List(1.1, 2.1, 3.1) val c: List[Double] = List(1.1, 2.1, 3.1) scala> val d = List(List(1,2,3), List(4,5,6), List(7,8,9)) val d: List[List[Int]] = List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)) scala> val e = List(1 + 2, 3 * 4, 5 - 6) val e: List[Int] = List(3, 12, -1)
リストの型は List[型] で表します。変数 a のリストは要素が Int なので型は List[Int] になります。List(1) や List(2, 3) も型は List[Int] になります。リストは配列と同様にカッコ ( ) で要素にアクセスすることができます。添字は配列と同様に 0 から数え始めます。a(n) で n 番目の要素を取り出すことができますが、Scala のリストは immutable なデータ構造なので、a(n) = 10 のように値を書き換えることはできません。
リストに格納された要素の個数を「リストの長さ」といいます。リストの型はリストの長さとは関係なく、格納する要素の型によって決まります。変数 b のリストは要素が文字列なので型は List[String] になります。
リストは入れ子にすることができます。変数 d のリストは List(1, 2, 3), List(4, 5, 6), List(7, 8, 9) という List[Int] を格納しています。この場合、型は List[List[Int]] になります。このリストに List(List(7)) を入れることはできません。List(List(7)) の型は List[List[Int]] になるので、要素の型 List[Int] とは異なるからです。また、最後の例のように丸カッコの中に式を書くと、それを評価した値がリストの要素になります。
リストはメソッド head, tail を使って分解し、演算子 :: (コンス演算子) で合成することができます。また、演算子 ::: でリストを連結することができます。次の例を見てください。
scala> a val res3: List[Int] = List(1, 2, 3, 4) scala> a.head val res4: Int = 1 scala> a.tail val res5: List[Int] = List(2, 3, 4) scala> 0 :: a val res6: List[Int] = List(0, 1, 2, 3, 4) scala> List(1,2,3) ::: List(4,5,6) val res7: List[Int] = List(1, 2, 3, 4, 5, 6)
Scala の場合、リストの操作はメソッドで行います。メソッドの呼び出しは リスト + ドット ( . ) + メソッド名(引数, ...) で行います。引数がない場合はカッコを省略することができます。a.head は Lisp の関数 car と同じで、リスト a の先頭要素を取り出します。List(1, 2, 3, 4) の先頭要素は 1 なので、a.head は 1 を返します。
a.tail は Lisp の関数 cdr と同じで、リスト a から先頭要素を取り除いたリストを返します。a.tail は List(1, 2, 3, 4) から 1 を取り除いた List(2, 3, 4) を返します。演算子 :: は Lisp の関数 cons と同じで、リストの先頭にデータを付け加えます。演算子 ::: は Lisp の関数 append と同じで、2 つのリストをつないだ新しいリストを返します。このとき、左辺のリストはコピーされることに注意してください。
head, tail, コンス演算子の関係を図に表すと次のようになります。
この関係はリストを操作する関数を作る場合の基本になります。
要素のないリストを「空リスト」といい、Scala では Nil で表します。次の例を見てください。
scala> Nil val res8: collection.immutable.Nil.type = List() scala> List(1).tail val res9: List[Int] = List() scala> List("foo").tail val res10: List[String] = List()
Scala の場合、Nil はシングルトンオブジェクトとして定義されていて、どのようなリストの型にもあてはまります。REPL では List() と表示されます。要素が一つしかないリストに tail を適用すると空リストになります。次の例は List[Int] に tail を適用したので、List() の型を List[Int] と表示しました。3 番目の例のように、List[String] の空リスト List() は List[String] と表示されます。
コンス演算子を続ける場合は結合規則に注意してください。次の例を見てください。
1::2::3::Nil => (1::(2::(3::[]))) => List(1, 2, 3)
このように、コンス演算子は四則演算とは違って「右結合」になります。また、コンス演算子の右辺はリストでなければいけません。1::2 はエラーになります。実際のプログラムでは、head や tail でリストを分解するよりも「パターンマッチング」を使った方が簡単です。リストのパターンマッチングはあとで詳しく説明します。
リストを操作する関数は再帰定義を使うと簡単に作ることができます。実は、リスト操作と再帰定義はとても相性が良いのです。まずは、リストの長さを求める関数 length を作りましょう。 Sacla には length という同等の機能を持つメソッドが用意されていますが、再帰定義を使えば私たちでも簡単に作ることができます。
まず、いちばん簡単な場合を考えます。引数が空リストであれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト xs の長さを求めるには、リスト xs に tail を適用したリストの長さがわかればいい、と考えるのです。それに 1 を足せば、リストの長さを求めることができます。これをプログラムすると、次のようになります。
scala> def length[A](xs: List[A]): Int = if (xs == Nil) 0 else 1 + length(xs.tail) def length[A](xs: List[A]): Int scala> length(List(1, 2, 3, 4, 5)) val res11: Int = 5 scala> length(Nil) val res12: Int = 0
引数 xs が空リストであれば 0 を返します。そうでなければ、引数 xs に関数 tail を適用して length を再帰呼び出しします。リストに tail を繰り返し適用していくと最後は空リストになります。ここで再帰呼び出しが止まって 0 を返します。そうすると、1 + length(...) によって length の返り値に 1 を足した値を返していきます。すなわち tail した回数だけ 1 が足されるわけです。
length の場合、任意の型 A を格納するリストを引数に取り、int を返すことが示されています。つまり、引数が List[Int] でも List[String] でも、リストであればその長さを返すことができます。このように、length は多相型関数として定義されます。Scala のメソッド head, tail, length も多相型です。
scala> val a = List(1, 2, 3, 4, 5) val a: List[Int] = List(1, 2, 3, 4, 5) scala> val b = List("foo", "bar", "baz") val b: List[String] = List(foo, bar, baz) scala> a.head val res13: Int = 1 scala> b.head val res14: String = foo scala> a.tail val res15: List[Int] = List(2, 3, 4, 5) scala> b.tail val res16: List[String] = List(bar, baz) scala> a.length val res17: Int = 5 scala> b.length val res18: Int = 3
なお、length を末尾再帰で書き直すと次のようになります。
リスト : 末尾再帰版 def length[A](xs: List[A], a: Int = 0): Int = if (xs == Nil) a else length(xs.tail, a + 1)
累積変数 a をデフォルト引数にすると簡単です。xs が空リストでなければ length を再帰呼び出しして、累積変数 a の値を +1 します。これでリストの長さを求めることができます。
次はリストを連結する演算子 ::: と同じ動作をする関数 append を作ってみましょう。引数としてリスト xs と ys を渡し、それを連結したリストを返します。処理手順ですが、簡単な場合から考えていきましょう。まず、リスト xs が空リストならば、リスト ys を返すだけでいいですね。次に、リスト xs に要素が 1 つしかない場合を考えてみます。これは、リスト xs に head を適用して要素を取り出し、それをコンス演算子でリスト ys の先頭に追加すればいいでしょう。
それでは、リスト xs に要素が複数ある場合を考えてください。リスト xs を head と tail で分解します。そして、xs.tail と ys を連結したリストを求め、そのリストの先頭に xs.head を追加すれば xs と ys を連結することができます。xs.tail と ys の連結は再帰呼び出しで実現することができます。これを図に示すと次のようになります。
これをプログラムすると次のようになります。
scala> def append[A](xs: List[A], ys: List[A]): List[A] = | if (xs == Nil) ys else xs.head :: append(xs.tail, ys) def append[A](xs: List[A], ys: List[A]): List[A] scala> append(List(1, 2, 3), List(4, 5, 6)) val res19: List[Int] = List(1, 2, 3, 4, 5, 6) scala> append(Nil, List(4, 5, 6)) val res20: List[Int] = List(4, 5, 6) scala> append(List(1, 2, 3), Nil) val res21: List[Int] = List(1, 2, 3)
引数 xs が空リストであればリスト ys をそのまま返します。これが再帰呼び出しの停止条件になります。そうでなければ、xs.tail を append に渡して再帰呼び出しします。そして、その返り値と xs.head をコンス演算子で接続します。これでリストを連結することができます。なお、append も多相型関数になります。
今度はリストの要素を反転する関数 reverse を作ってみましょう。Scala には reverse という同等の機能を持つメソッドが用意されていますが、私達でも簡単に作ることができます。reverse は引数のリスト xs を head と tail で分解し、xs.head を反転させてから xs.head を最後尾に追加することで実現できます。次の図を見てください。
これをプログラムすると、次のようになります。
scala> def reverse[A](xs: List[A]): List[A] = | if (xs == Nil) Nil else reverse(xs.tail) ::: List(xs.head) def reverse[A](xs: List[A]): List[A] scala> reverse(List(1,2,3,4,5)) val res22: List[Int] = List(5, 4, 3, 2, 1) scala> reverse(List("a", "b", "c", "d")) val res23: List[String] = List(d, c, b, a)
引数 xs が空リストの場合は Nil を返します。そうでなければ、reverse を再帰呼び出しして xs.tail を反転し、演算子 ::: で反転したリストの最後尾に先頭の要素を追加します。reverse も多相型関数になります。
なお、このプログラムはリストを連結する ::: 演算子を使っているので効率的ではありません。末尾再帰で書き直すと次のようになります。
リスト : 末尾再帰版 def reverse[A](xs: List[A], a: List[A] = Nil): List[A] = if (xs == Nil) a else reverse(xs.tail, xs.head :: a)
累積変数 a をデフォルト引数 (初期値 Nil) にすると簡単です。リスト xs の先頭要素を取り出し、コンス演算子で累積変数 a の先頭に追加していけば、xs の逆順のリストを得ることができます。
最後に、リストからデータを探索する関数 member を作ってみましょう。Scala にはリストを線形探索するメソッドがいくつか用意されていますが、ここでは Common Lisp の関数 member と同等の動作をする関数を作ります。member はリストの中にデータがなければ空リストを返します。データを見つけた場合は、その要素を含む残りのリストを返します。つまり、返り値のリストの先頭要素が見つけたデータになります。
プログラムは次のようになります。
scala> def member[A](x: A, xs: List[A]): List[A] = { | if (xs == Nil) Nil | else if (xs.head == x) xs | else member(x, xs.tail) | } def member[A](x: A, xs: List[A]): List[A] scala> val a = List(1,2,3,4,5) val a: List[Int] = List(1, 2, 3, 4, 5) scala> member(1, a) val res0: List[Int] = List(1, 2, 3, 4, 5) scala> member(3, a) val res1: List[Int] = List(3, 4, 5) scala> member(5, a) val res2: List[Int] = List(5) scala> member(0, a) val res3: List[Int] = List()
関数 member はリスト xs の中から x と等しい要素を探します。これは member を再帰呼び出ししてリストを分解し、リストの先頭要素をチェックしていくことで実現できます。xs が空リストの場合は x を見つけることができなかったので Nil を返します。これが再帰の停止条件になります。次に、リスト xs の先頭の要素 xs.head が x と等しいかチェックします。等しい場合は、リスト xs をそのまま返します。そうでなければ、member を再帰呼び出しして次の要素を調べます。
データが見つからない場合、空リストが返されますが、その型は引数のリストと同じ型になることに注意してください。Scala の関数は、異なるデータ型を返すことができません。たとえば、見つけた場合はその要素を返し、見つからない場合は false を返す、ということはできないのです。見つけた要素を返したい場合は Option というクラスを使うと簡単です。
Scala のクラスは型パラメータを使って多相的なデータ構造を定義することができます。これを「多相クラス (polymorphic class)」といいます。Option は多相クラスで、サブクラスに Some と None が定義されています。Some はデータを格納するクラスで、None はデータがないことを表すクラスです。次の例を見てください。
scala> val a: Option[Int] = Some(10) val a: Option[Int] = Some(10) scala> val b: Option[Int] = None val b: Option[Int] = None scala> a.get val res0: Int = 10 scala> b.get java.util.NoSuchElementException: None.get ... 省略 ... scala> a.getOrElse(Int.MinValue) val res2: Int = 10 scala> b.getOrElse(Int.MinValue) val res3: Int = -2147483648 scala> a.isEmpty val res4: Boolean = false scala> a.nonEmpty val res5: Boolean = true scala> b.isEmpty val res6: Boolean = true scala> b.nonEmpty val res7: Boolean = false
Scala は Java と同様にサブクラスのインスタンスをスーパークラスの変数に代入することができます。Some からデータを取り出すにはメソッド get を使います。None.get とするとエラーになります。メソッド getOrEles を使うと、None のときに指定した値を返すことができます。たとえば、b.getOrEles(Int.MinValue) とすると、b は None なので Int の最小値が返ってきます。
このほかに、Some と None をチェックする isEmpty, nonEmpty というメソッドがあります。実際には、次に説明するパターンマッチングを使うと、Some と None のチェックや Some からデータを取得することも簡単に行うことができます。
Option を使って member を書き直すと次のようになります。
scala> def member[A](x: A, xs: List[A]): Option[A] = { | if (xs == Nil) None | else if (xs.head == x) Some(x) | else member(x, xs.tail) | } def member[A](x: A, xs: List[A]): Option[A] scala> val a = List(1,2,3,4,5) val a: List[Int] = List(1, 2, 3, 4, 5) scala> member(1, a) val res8: Option[Int] = Some(1) scala> member(3, a) val res9: Option[Int] = Some(3) scala> member(5, a) val res10: Option[Int] = Some(5) scala> member(0, a) val res11: Option[Int] = None
なお、Scala には member と同じ機能を持つメソッド find が用意されています。また、配列と同様に、メソッド contains, indexOf, count はリストでも使用することができます。
簡単な例を示しましょう。
scala> a val res12: List[Int] = List(1, 2, 3, 4, 5) scala> a contains 1 val res13: Boolean = true scala> a contains 5 val res14: Boolean = true scala> a contains 6 val res15: Boolean = false scala> a indexOf 2 val res16: Int = 1 scala> a indexOf 5 val res17: Int = 4 scala> a indexOf 0 val res18: Int = -1 scala> a count (x => x % 2 == 0) val res19: Int = 2 scala> a find (x => x % 2 == 0) val res20: Option[Int] = Some(2) scala> a find (x => x == 0) val res21: Option[Int] = None
Scala はオブジェクト指向言語なので、クラスを使って新しい型を定義することができますが、「タプル (Tuple)」を使うともっと簡単に新しい型を定義することができます。タプルは関数型言語でよく使われるデータ構造で、複数のデータや式をカンマ ( , ) で区切り、カッコ ( ) で囲んで表します。次の例を見てください。
scala> val a = (1, 2) val a: (Int, Int) = (1,2) scala> val b = (10, 20.5) val b: (Int, Double) = (10,20.5) scala> val c = (1, 2.5, "foo") val c: (Int, Double, String) = (1,2.5,foo) scala> val d = (1 + 2, 3 * 4) val d: (Int, Int) = (3,12)
変数 a のタプル (1, 2) は整数を 2 つ持っていて、型は (Int, Int) になります。変数 b のタプル (10, 20.5) は整数と実数なので (Int, Double) になります。変数 c のタプル (1, 2.5, "foo") は (Int, Double, String) になります。また、最後の例のようにカッコの中に式を書くと、それを評価した値が組の要素になります。なお、タプルは immutable なデータ構造です。配列と違って値を書き換えることはできません。
タプルは入れ子にしてもかまいません。次の例を見てください。
scala> val a = ((1, 2), 3) val a: ((Int, Int), Int) = ((1,2),3) scala> val b = (1, (2, 3)) val b: (Int, (Int, Int)) = (1,(2,3))
変数 a のタプルは、第 1 要素が (Int, Int) のタプルで、第 2 要素が Int です。これを ((Int, Int), Int) と表します。変数 b の組は、第 1 要素が Int で第 2 要素が (Int, Int) のタプルになります。これを (Int, (Int, Int)) と表します。どちらのタプルも 3 つの整数が含まれていますが、型は異なることに注意してください。
タプルの要素はメソッド _1, _2, _3, ... で取り出すことができます。数字が添字を表します。配列と違ってタプルの添字は 1 からはじまることに注意してください。簡単な例を示します。
scala> val c = (10, 20, 30, 40, 50) val c: (Int, Int, Int, Int, Int) = (10,20,30,40,50) scala> c._1 val res0: Int = 10 scala> c._2 val res1: Int = 20 scala> c._3 val res2: Int = 30 scala> c._4 val res3: Int = 40 scala> c._5 val res4: Int = 50
実際には次回で説明するパターンマッチングを使ったほうが簡単です。
タプルを使えば複数の値を返す関数も簡単に作ることができます。次の例を見てください。
scala> def foo(x: Int, y: Int): (Int, Int) = { | if (x == y) (0, 0) | else if (x < y) (-1, y - x) | else (1, x - y) | } def foo(x: Int, y: Int): (Int, Int) scala> foo(10, 20) val res5: (Int, Int) = (-1,10) scala> foo(20, 10) val res6: (Int, Int) = (1,10) scala> foo(20, 20) val res7: (Int, Int) = (0,0)
関数 foo は引数 x と y の差分の絶対値を計算し、符号とその値を返します。x == y ならば (0, 0) を返します。x < y ならば (-1, y - x) を返し、x > y ならば (1, x - y) を返します。このように、タプルを使って複数の値を返すことができます。
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) val x: Int = 1 val xs: List[Int] = List(2, 3, 4, 5) scala> val y::ys = List(1) val y: Int = 1 val ys: List[Int] = List() scala> val z::zs = ys scala.MatchError: List() (of class scala.collection.immutable.Nil$) ... 省略 ...
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 val args: Array[String] = Array() Loading sample0402.scala... object sample0402 scala> import sample0402._ 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", "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 val args: Array[String] = Array() Loading sample0403.scala... object sample0403 scala> import sample0403._ 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 val args: Array[String] = Array() Loading sample0404.scala... object sample0404 scala> import sample0404._ 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)