Programming in Scala, First Edition: Chapter 22

22. Implementing Lists
  Listはこの本の何処にでも出てくる。
  Listはscalaで一番よく使われるデータ構造だから。
  今回はListの実装について言及する。
  Listを効率良く使えるようになる。
  自分のlibraryを作る時の参考に出来る。
  Listを実例としてscalaの型システムの概念を学べる。

22.1 The List class in principle
  Listは組み込み型ではない。
  abstract classとして実装されている。
    subclassは::とNil
    ** memberではなくてsubclassと言うのが面白い。
  abstract class List[+T] {..}
    +Tはcovariantを示す。
    val xs: List[Any] = List(1, 2, 3)が可能。
    isEmpty, head, tailが基本関数。
      class Listではabstractで定義されている。
      subclass ::, Nilで実装されている。
  The Nil object
    case object Nil extends List[Nothing] {..}
    covariantなのでList[Nothing]は全てのList[T]と互換性がある。(代入出来る)
    headはNothingを返す必要があるが、それは不可能なので例外を投げるしかない。
      tailは逆に例外ではなくてNilを返すと言う仕様もあり得る。
  The :: class
    final case class ::[T](head: T, tail: List[T]) extends List[T] {..}
    consと呼ばれる。constructの意味。
    constructor :: をpattern matchingで使えるようにcase classで定義する。
    finalを付けることでsubclassの作成(実装の変更)を禁止。10.10参照。
    head, tailはパラメタ無抽象methodをfieldで実装している。20.3参照。
  Some more methods
    他の全てのmethodはhead,tail,isEmptyを使う事で実装出来る。
  List construction
    ::,:::は:で終わっているのでreceiverは右辺値になる。
      ::はclass ::のconstructorでもあるが、同名のmethodでもある。
    Listの要素が異なるtypeの場合は、共通のsuper classがListのtypeになる。
      def ::[U >: T](x: U): List[U] = new scala.::(x, this)
      UはTとxの共通のsuper typeになる。
    :::も同様。
      def :::[U >: T](prefix: List[U]): List[U] =
        if (prefix.isEmpty) this
        else prefix.head :: prefix.tail ::: this

22.2 The ListBuffer class
  import scala.collection.mutable.ListBuffer
  "buf += elem"が出来る。
  Listを生成する時に、要素を末尾に追加していける。
  生成したらtoListでListにする。
  通常のListを使ったら非常に非効率。
  tail recursive ではない呼び出しだと30,000-50,000位でstackが溢れる。

22.3 The List class in practice
  実際のListの実装は効率のためにListBufferとloopを使っている。
    stack overflowを避けるために再帰呼び出しを使わない様にしている。
    tail recursiveに出来れば同様に効率的に出来る。
  ListBufferのtoListの計算量は少ない。
    長さに無関係に少ない数のサイクルしか掛からない。
  実際の::の実装はtailがprivate[scala] varで実装されている!!
    private[scala]でpackage scala内でのアクセスに制限している。
      ユーザからはアクセスできない。
      ListBufferからアクセス可能。
  ListBufferはtailを書き換えてつなぎかえるようにしている。
    Listの構成を保ったまま拡張しているのでList化の計算コストはO(0)
  ?? 一旦List化した後の追加は高コストとあるが、何故??

22.4 Functional on the outside
  Listはoutsideからはpurely functionalだがinsideではmutableな実装をしている。
  scalaでは典型的な戦略。
    impureな操作の影響を注意深く取り除く事でpureでefficientな実装にする。
  purityは重要。
    purityがcopy無でListの共有を可能にする。
      効率的で分かりやすい実装が出来る。
    val ys = 1 :: xs; val zs = 2 :: xsでysのxs部分を書き換えたらzsに影響する。
      影響させないためにはcopyする必要があり、効率が悪くなる。
  scalaでは末尾に追加する生成方法のためにListBufferを用意している。
    Listのpurityを保つために分離して提供しているのが重要。
    JavaのStringとStringBuffer/StringBuildersと同様の発想。
  ::はrecursive algorithmsで分割統治styleを使う場合に適している。
  ListBufferはloopのstyleに適している。

22.5 Conclusion
  Listの実装は洗練されている。
  外部からはfunctionalに見えるようにしている。
  内部では効率のためにmutableなListBufferを使っている。