今回は「リスト (List)」というデータ構造を説明します。Scala のリストは「連結リスト (Linked List)」のことです。リストを扱うプログラミング言語といえば Lisp が有名です。SML/NJ, OCaml, Haskell などの関数型言語や論理型言語の Prolog も、組み込みのデータ構造として連結リストをサポートしています。
連結リストは単純なデータ構造ですが、他のデータ構造を実装するときに用いられることがあります。連結リストは基本的で重要なデータ構造の一つなのです。
リストの構造を図で表すと次のようになります。
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼─→ Nil (空リスト)
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
図 : リスト内部の構造
リストは貨物列車にたとえるとわかりやすいでしょう。車両に相当するものを「コンスセル (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
-- [E008] Not Found Error: -------------------------------------------
1 |a(0) = 10
|^
|value update is not a member of List[Int] - did you mean a.updated?
1 error found
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, コンス演算子の関係を図に表すと次のようになります。
┌──┐
┌─→│head│→ １ ────┐
│ └──┘ ↓
│ ┌──┐
List(1,2,3,4)─┤ │：：│→ List(1,2,3,4)
│ └──┘
│ ┌──┐ ↑
└─→│tail│→List(2,3,4)─┘
└──┘
図 : リストの分解と合成
この関係はリストを操作する関数を作る場合の基本になります。
要素のないリストを「空リスト」といい、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 の連結は再帰呼び出しで実現することができます。これを図に示すと次のようになります。
┌────────────────────────────┐
│append( [1, 2], [3, 4] ) │
├────────────────────────────┤
│ [ 1, 2 ] │
│ ┬ ───tail─┐ │
│ head ↓ │
│ │ ┌──────────────────────┐│
│ │ │append( [2], [3, 4] ) ││
│ │ ├──────────────────────┤│
│ │ │ [ 2 ] ││
│ │ │ ┬ ─ tail─┐ ││
│ │ │ head ↓ ││
│ │ │ │ ┌────────────────┐││
│ │ │ │ │append( [], [3, 4] ) => [3, 4] │││
│ │ │ │ └────────────────┘││
│ │ │ │ │ ││
│ │ │ └→ :: ←─┘ ││
│ │ │ [2, 3, 4] ││
│ │ └─────┼────────────────┘│
│ └──→ :: ←─┘ │
└──────┼─────────────────────┘
↓
[1, 2, 3, 4]
図 : append の動作
これをプログラムすると次のようになります。
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 を最後尾に追加することで実現できます。次の図を見てください。
[1, 2, 3] [3, 2] ::: [1] => [3, 2, 1]
↓ ↑
[2, 3] [3] ::: [2] => [3, 2]
↓ ↑
[3] [ ] ::: [3] => [3]
↓ ↑
[ ] ──┘
図 : reverse の動作
これをプログラムすると、次のようになります。
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) を返します。このように、タプルを使って複数の値を返すことができます。