Scalaの標準ライブラリにNonEmptyListを組み込もうとして、とりあえず簡単にはできないことがわかったという話

scala

これ
Option.getとかFuture.getとかList.headとかunsafePerformIOとか最終的にCopointedとか色々
のこのあたり

の会話を聞いていて、思いつく↓

Cons ってつまり scala.collection.immutable. は、Listの親クラスのメソッドをほとんどoverrideしていないし、CanBuildFromを定義していない(そもそもコンパニオンオブジェクトを定義していない)ので、mapやfilterのメソッドの戻り値の型が ::[A] 型ではなくList[A]型で返ってくるわけですが*1、構造的には、オブジェクトが生成された時点で head が存在することが必ず保証されている NonEmptyList なわけで・・・という。

とりあえず、ListのコンパニオンオブジェクトがSeqFactoryを継承しているので、同じように以下のようにしてみる↓

object :: extends SeqFactory[::]{ outer =>
  import scala.collection.{Iterable, Seq, IndexedSeq}

  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ::[A]] =
    ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, ::[A]] = new Builder[A,::[A]]{
    private val buf = new ListBuffer[A]
    def +=(elem: A): this.type  = { buf += elem ; this }
    def clear(): Unit = buf.clear()
    def result(): ::[A] = ::(buf.head,buf.tail.result)
  }

  override def empty[A]: ::[A] = sys.error(":: empty is not defined")

  override def apply[A](xs: A*): ::[A] = ::(xs.head,xs.tail.toList)
}
  • emptyとapply定義しないといけないけれど、emptyはエラーにするしかないし、applyもエラー起きる可能性あるものを定義するしかないじゃん・・・
  • newBuilderも、result呼び出したときにエラー起きる可能性・・・
  • もうちょっとコンパニオンオブジェクトの定義工夫したほうがいいのか・・・？

とりあえず上記の点は置いておいて、コンパイルしてみる
↓
しかしこれだけではコンパイル通らなくて、以下のようなエラー

[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/immutable/List.scala:371: error: type arguments [scala.collection.immutable.::] do not conform to class SeqFactory's type parameter bounds [CC[X] <: Seq[X] with scala.collection.generic.GenericTraversableTemplate[X,CC]]
[scalacfork] object :: extends SeqFactory[::]{ outer =>
[scalacfork]                   ^
[scalacfork] one error found

何言ってるかわかりづらいですが、
case class ::[B]
が
case class ::[+B]
じゃないとだめっていう話ですね。なので、共変にして、もう一度コンパイル

[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/immutable/List.scala:325: error: covariant type B occurs in contravariant position in type B of value hd_=
[scalacfork] final case class ::[+B](private var hd: B, private[scala] var tl: List[B]) extends List[B] {
[scalacfork]

「共変の型のものをvarにできません」的なこと(?)言われました(´・ω・｀)そういえば、 :: のコンストラクタのフィールドはなぜか var になってる・・・serializeのためか？と予想し、このあたり
https://github.com/scala/scala/blob/v2.9.1/src/library/scala/collection/immutable/List.scala#L395-416
を消して、以下のようにしてコンパイル

final case class ::[+B](override val head: B, override val tail: List[B]) extends List[B] {
  override def isEmpty: Boolean = false
}

結果↓

[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:93: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]         current.tl = list
[scalacfork]                 ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:151: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]         cursor.asInstanceOf[::[A]].tl = newElem
[scalacfork]                                    ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:171: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]       last1.tl = last0
[scalacfork]             ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:236: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]           cursor.asInstanceOf[::[A]].tl = newElem
[scalacfork]                                      ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:273: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]         cursor.asInstanceOf[::[A]].tl = cursor.tail.tail
[scalacfork]                                    ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:302: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]       last0.tl = xs
[scalacfork]             ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:332: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]       cursor.asInstanceOf[::[A]].tl = cursor.tail.tail
[scalacfork]                                  ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:357: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]         if (z.tl == last0)
[scalacfork]               ^
[scalacfork] /Users/kenji/scala-scala/src/library/scala/collection/mutable/ListBuffer.scala:359: error: value tl is not a member of scala.collection.immutable.::[A]
[scalacfork]         z.tl = cursor.tail.tail
[scalacfork]           ^
[scalacfork] 9 errors found

(つд⊂)ｺﾞｼｺﾞｼ・・・(ﾟдﾟ)!?
serializeのためだけではなくて、ListBuffer で、tlに代入してたの！？

ListBuffer 内で直接代入しているのが、パフォーマンスのためにしかたがなくこうなっているのか、古い設計を引きずってるのか、理由はよくわかりませんが。
いわゆる関数型のListはimmutableで、ScalaのListの解説でも「ScalaのListはimmutableです」っていうのがほとんどですが、ScalaのListは、内部的にはこんな気持ち悪いことになっていたんですね・・・。*2まぁList生成した後は、その中身を書き換えるメソッドや関数は標準ライブラリ中に存在しないはずなので、ユーザーからは常にimmutableなものとして扱えるはずで、意識する必要のない部分ですが。

で、ListBuffer まで影響してきて、もうこれ以上めんどくさくなったので、だいぶ中途半端だけれども、標準ライブラリそのものをいじってみた結果をとりあえず書いてみたという

*1: CanBuildFromを使って、あまり重複したコードを書かずに戻り値の型を同じにする仕組みについては、これ http://scalajp.github.com/scala-collections-impl-doc-ja/ とかこれ http://scalajp.github.com/scala-collections-doc-ja/ を参照

*2: tlがscala package内でprivateなので、例えばこんな関数をつくるだけで、tailを書き換えることができてしまう・・・ https://gist.github.com/2015513 おそらくheadもリフレクションつかえば書き換えられますね・・・