この章では，以下のメソッドを持つ関数型待ち行列を構成する。
- head : 待ち行列の先頭要素を返す
- tail : 先頭要素を取り除いた形で待ち行列を返す
- enqueue : 指定した要素を末尾に追加した新しい待ち行列を返す
関数型待ち行列とは，オブジェクトに対する操作を行った際に，既存のデータを変更せずに， 新しいデータを生成して返すものである。
- 共通点
- 完全永続
- head, tail をサポートする
- 差異
- 要素の追加 リストは :: を使用して先頭に要素を追加し，関数型待ち行列は enqueue を使用して末尾に追加される。
以降では，関数型待ち行列を効率良く，即ち，head, tail, enqueue の各操作が一定時間で終わるような実装を考える。
- enqueue が一定時間ではない
- head, tail が一定時間ではない
※ 2において，head <-> last, tail <-> init の関係を用いる。
先頭から順に要素を並べたリストと末尾から順に要素を並べたリストを用いる。
- 漸近的計算量ではミュータブルな待ち行列とみなしてよい。
- head, tail, enqueue の呼び出しがほぼ同じ頻度であることを仮定する必要がある。
2点目の仮定については，head が頻繁に呼び出されると，無駄に Queue を作成するコストの高い処理を実行する必要がある。
この課題の改善策については，最後に取り上げられている。
19.1 で実装したサンプルは，処理効率の点では優秀だが，内部実装を公開してしまっている点が欠点である。
そのための 情報隠蔽 を行う手段について示す。
- 基本コンストラクタに private を指定してコンストラクターを隠す。
- 補助コンストラクタを実装する。
- コンパニオンオブジェクトにファクトリメソッドを実装する。
- インターフェイスを定義したトレイトを使用する。
scala にはグローバルメソッドは存在しないが，グローバルオブジェクトに apply を定義すると，
ファクトリーメソッドをグローバルメソッドのように呼び出して使用することができる。
- 19.2 の最後のサンプルにおける Queue はトレイトであって型ではない。
- Queue[T] はトレイト，Queue[String] は型。
- Queue は型コンストラクタ，ジェネリックトレイトとも呼ばれる。
Queue は共変か？
- 共変(covariant): 広い型 (double) から狭い型 (float) へ変換すること。
- 反変 (contravariant): 狭い型 (float) から広い型 (double) へ変換すること。
- 不変 (invariant): 型を変換できないこと。
via Wikipwdia 共変性と反変性
Scala は標準では，ジェネリック型のサブ型に関して，デフォルトでは非変である。
scala においては，型パラメータにプレフィックスを付与することで，変位を指定することができ，
このことを 変位指定 と呼ぶ。
-
共変
trait Queue[+T] {...}
-
反変
trait Queue[-T] {...}
上記のような変位指定に使用する + や - のプレフィックスを 変位指定アノテーション と呼ぶ。
純粋関数型言語においては，共変であることが自然であるが，ミュータブルなデータを扱う scala の場合，同じようにはならない。
- サンプル: 非変(厳格)宣言されている Cell クラス
- 配列をジェネリックに扱う単純な方法のために存在する。
- sort などのために必要だった。
- 現在は，型パラメータを使用すればよいので，配列の共変は必要ない。
- 互換性のために，存在している。
- Java と異なり，Scala の配列は非変である。
- 互換性のために，T型の配列をTのスーパー型の配列に変換する方法も提供されている。
純粋関数型待ち行列においても，変位指定として，共変にはできない。
よくわからないので，省略。。
T, U を型パラメータとし，T は予め定義されているものとする。 U を使用した型パラメータ定義において，U >: T という指定を行うことで， U は T のスーパー型であるという制限を与えることができる。 このとき，T を U の下限境界という。
- 待ち行列を共変にする
- enqueue メソッドにおいて，コンパイルエラーが出る
- コンパイルエラーが出たメソッドにおいて，下限境界を指定することで修正する
xxx駆動設計というよりも，リファクタリングの手順と言ったほうが適切？
T型のオブジェクトx に関して真となる属性を q(x) とする。このときSがTの派生型であれば、S型のオブジェクトy について q(y) が真となる
リスト19.1 のサンプルでは，mirror を呼び出す際に，リストの再構成が行われる可能性があったが，
このサンプルでは，内部の状態を変更する副作用に処理を変えることで，無駄なコピーが行われることを避けている。
T, U を型パラメータとし，T は予め定義されているものとする。
U を使用した型パラメータ定義において，U <: T という指定を行うことで，
U は T のサブ型であるという制限を与えることができる。
このとき，T を U の上限境界という。
T <: Ordered[T] であるような上限境界を指定した List[T] を引数とするマージソート関数。
ref. 16.6.12 項のリスト 16.1 におけるリストのマージソート関数
ただし，List[Int] のような Ordered[T] を継承していない型を持つリストには使用出来ない。
暗黙のパラメータ，可視境界を使用した拡張方法は，21.6節を参照のこと。
省略