9.1 リストの使用 (Using Lists)

リスト型 配列と同じくリストは 等質 です。つまり、リストの要素はすべて同じ型です。要素型 T のリストの型は List[T] と書きます(Java の T[] は配列です)。

val fruit: List[String] = List("apples", "oranges", "pears") val nums : List[Int] = List(1, 2, 3, 4) val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1)) val empty: List[Int] = List()

リストのコンストラクタ すべてのリストは２つの基本的なコンストラクタである Nil と :: ("cons" と発音する) から作られます。Nil は空リストを表します。中置演算子 :: は、リストの拡張を表します。つまり x :: xs は、最初の要素が x で、その後にリスト xs (の要素) が続くリストを表します。したがって、先ほどのリストの値は、次のようにも定義できます (実際、前述の定義は次の単なる糖衣構文です)。

val fruit = "apples" :: ("oranges" :: ("pears" :: Nil)) val nums = 1 :: (2 :: (3 :: (4 :: Nil))) val diag3 = (1 :: (0 :: (0 :: Nil))) :: (0 :: (1 :: (0 :: Nil))) :: (0 :: (0 :: (1 :: Nil))) :: Nil val empty = Nil

'::' 操作は右結合です。A :: B :: C は A :: (B :: C) と解釈されます。したがって先ほどの定義で、括弧は省略できます。たとえば次のように短く書けます。

val nums = 1 :: 2 :: 3 :: 4 :: Nil

リストの基本操作 リストのすべての操作は、次の三つを使って表現できます。

head : リストの最初の要素を返す。 tail : 最初の要素以外の、すべての要素からなるリストを返す。 isEmpty : リストが空である時、かつその時に限り true を返す。

これらの操作は、リストオブジェクトのメソッドとして定義されています。操作対象のリストから、それらの操作を選択して呼び出してみましょう。たとえば

empty.isEmpty = true fruit.isEmpty = false fruit.head = "apples" fruit.tail.head = "oranges" diag3.head = List(1, 0, 0)

head と tail メソッドは非空リストに対してだけ定義されています。空リストから選択された場合は、例外を投げます。

リストを扱う例として、数のリストを昇順にソートすることを考えましょう。ソートする一つの簡単な方法は 挿入ソート であり、次のようにします。最初の要素が x で残りが xs であるような非空リストをソートするには、残りの xs をソートして、要素 x をその結果の正しい場所に挿入します。空リストのソートは空リストになります。Scala のコードで表現すると

def isort(xs: List[Int]): List[Int] = if (xs.isEmpty) Nil else insert(xs.head, isort(xs.tail))

演習 9.1.1 書かれていない関数 insert を実装しなさい。

リストパターン 実際のところ、:: は Scala の標準ライブラリでケースクラスとして定義されています。ですから、Nil と :: コンストラクタからなるパターンを用いた、パターンマッチングでリストを分解できます。たとえば isort は次のようにも書けます。

def isort(xs: List[Int]): List[Int] = xs match { case List() => List() case x :: xs1 => insert(x, isort(xs1)) }

ただし、

def insert(x: Int, xs: List[Int]): List[Int] = xs match { case List() => List(x) case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys) }