9.2 リストクラスの定義Ⅰ:一階メソッド

リストは Scala では組み込み型ではありません。抽象クラス List として定義され、２つのサブクラス :: と Nil があります。以降では、クラス List のツアーに出かけます。

package scala abstract class List[+A] {

List は抽象クラスであり、空の List コンストラクタを呼び出して (たとえば new List )、要素を定義することはできません。クラスには型パラメータ a があります。このパラメータについて共変、つまり S <: T であるような型 S と T について、List[S] <: List[T] です。クラスはパッケージ scala にあります。このパッケージは Scala の最も重要で標準的なクラスを含んでいます。List は多くのメソッドを定義しており、以下でそれを説明します。

リストの分解 最初に、３つの基本的なメソッド isEmpty, head, tail があります。パターンマッチングによるそれらの実装は簡単です。

def isEmpty: Boolean = this match { case Nil => true case x :: xs => false } def head: A = this match { case Nil => error("Nil.head") case x :: xs => x } def tail: List[A] = this match { case Nil => error("Nil.tail") case x :: xs => xs }

次の関数はリストの長さを計算します。

def length: Int = this match { case Nil => 0 case x :: xs => 1 + xs.length }

演習 9.2.1 length の末尾再帰版を設計しなさい。

次の２つの関数は head と tail を補完するものです。

def last: A def init: List[A]

xs.last はリスト xs の最後の要素を返し、一方で xs.init は最後以外の xs の全要素を返します。両関数ともリスト全体をたどる必要があるので、類似の head や tail より効率的ではありません。次は last の実装です。

def last: A = this match { case Nil => error("Nil.last") case x :: Nil => x case x :: xs => xs.last }

init の実装も似ています。

次の３つの関数は、リストの先頭部、末尾部、あるいはその両方を返します。

def take(n: Int): List[A] = if (n == 0 || isEmpty) Nil else head :: tail.take(n-1) def drop(n: Int): List[A] = if (n == 0 || isEmpty) this else tail.drop(n-1) def split(n: Int): (List[A], List[A]) = (take(n), drop(n))

(xs take n) は、リスト xs の最初の n 要素、あるいは長さが n 未満の場合はリスト全体を返します。(xs drop n) は、最初の n 要素を除いた xs の全要素を返します。最後に (xs split n) は、xs take n と xs drop n からなるリストのペアを返します。

次の関数はリストの、与えられたインデックス要素を返します。つまり配列の添字と似ています。インデックスは 0 から始まります。

def apply(n: Int): A = drop(n).head

apply メソッドは Scala では特別な意味を持ちます。apply メソッドを持つオブジェクトはあたかも関数のように引数へ適用されます。たとえば、リスト xs の第 3 要素を選び出すには xs.apply(3) とも xs(3) とも書けます --- 後の式は前の式に展開されます。

take と drop を使って、元のリストの連続した要素からなるサブリストを取り出せます。リスト xs のサブリスト xsm,...,xsn-1 を取り出すには、

xs.drop(m).take(n - m)

リストの ZIP 次の関数は２つのリストを組み合わせて、ペアからなる一つのリストを作ります。２つのリスト

xs = List(x1, ..., xn ) , and ys = List(y1, ..., yn ) ,

に対して、xs zip ys はリスト List (*1) を作ります。もし２つのリストの長さが違う場合は、長い方が切り捨てられます。次は zip の定義です。多相的メソッドであることに注意してください。

def zip[B](that: List[B]): List[(A,B)] = if (this.isEmpty || that.isEmpty) Nil else (this.head, that.head) :: (this.tail zip that.tail)

リストの CONS すべての中置演算子と同じように、:: もオブジェクトのメソッドとして実装されています。この場合、そのオブジェクトは拡張されるリストです。Scala では、文字 ':' で終わる演算子は特別に扱われるため、それが可能です。そのような演算子は、右オペランドのメソッドとして扱われます。たとえば

x :: y = y.::(x) 一方 x + y = x.+(y)

しかし、どちらの場合も二項演算のオペランドは左から右に評価されることに注意して下さい。もし D と E が副作用の可能性のある式なら、D :: E は オペランド評価において、左から右への順序を維持するために、{val x = D; E.::(x)} と変換されます。

':' で終わる演算子と他の演算子とのもう一つの違いは、結合性に関するものです。':' で終わる演算子は右結合で、他の演算子は左結合です。たとえば、

x :: y :: z = x :: (y :: z) 一方 x + y + z = (x + y) + z

クラス List のメソッドとしての :: の定義は、次のようです。

def ::[B >: A](x: B): List[B] = new scala.::(x, this)

:: は、x の型 B がリストの要素型 A のスーパータイプであるような、型 B のすべての要素 x と、List[A] 型のリストに対して定義されていることに注意して下さい。この場合、結果は要素型 B のリストになります。このことは :: のシグネチャにおいて、下限境界 A を持つ型パラメータ B、として表現されています。

リストの連結 :: と似た操作はリストの連結で、':::' と書きます。(xs ::: ys) の結果は xs の全要素に ys の全要素が続いたリストです。コロンで終わるため、::: は右結合であり右オペランドのメソッドとみなされます。したがって、

xs ::: ys ::: zs = xs ::: (ys ::: zs) = zs.:::(ys).:::(xs)

以下は ::: メソッドの実装です。

def :::[B >: A](prefix: List[B]): List[B] = prefix match { case Nil => this case p :: ps => this.:::(ps).::(p) }

リストの逆転 ほかにも有用な操作として、リストの逆転があります。List にはそのためのメソッド reverse があります。実装を与えてみましょう。

def reverse[A](xs: List[A]): List[A] = xs match { case Nil => Nil case x :: xs => reverse(xs) ::: List(x) }

この実装には単純であるという利点がありますが、あまり効率的とは言えません。実際のところ、リストの各要素に対して１回の連結が実行されます。List の連結は、最初のオペランドの長さに比例する時間がかかります。したがって reverse(xs) の計算量は

n + (n − 1) + ... + 1 = n(n + 1)/2

ただし n は xs の長さです。reverse をもっと効率的に実装できますか？線形な計算量しか持たない異なる実装をあとで見ます。