読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

ScalaでListが共変でなければいけない理由

Scalaに限らず、関数型言語の入門記事には、必ずといっていいほど、最初の方でリスト型が出てきます。不変データ構造として単純なので説明しやすいことや、実際に小さなコレクションとしてリストを使うことが多い事など、理由は色々あるでしょう。

まあ、それはどうでもよくて、今回はScalaにおけるリストの実現であるscala.Listが共変でなければいけない理由をちょっと説明してみようと思います。実は、他の静的型付け関数型言語のリスト型、たとえばSMLやOCamlHaskellにおけるリスト型は共変ではありません*1(そもそもOCaml以外はサブタイプが無いですが…)。共変についての解説は面倒なので省きます。

結論を一言で書くと、共変でなければ空のリスト(Nil)値が簡単に作れないからです。

仮にscala.Listが共変でなかったとします。このとき非常に困るのは、空のListであるNilの型は一体何であるべきか、ということです。Nilはあらゆる型をパラメータに持つListに対して代入可能でなければいけないのですが、困ったことに、Scalaではジェネリックな型を持つ値を作ることができません。そうすると、Nilを値として定義する事はできずに、

val NilValue: List[Nothing]
def Nil[A]: List[A] = NilValue.asInstanceOf[List[A]]

のようなメソッドとして定義しなければいけないのですが、Listの定義側が型安全でなくなってしまいますし、Listを使うのがめんどくさくて仕方ありません。

さて、ここで、Scala (2.9.2) における Listに関係する型と値の定義を見てみましょう。

sealed abstract class List[+A] extends ... { ... }
...

final case class ::[B](private var hd: B, private[scala] var tl: List[B]) extends List[B] { ... }

... 
case object Nil extends List[Nothing] { ... }

ListはLinearSeqなどの型を継承しているのですが、今回の説明には関係ないので省きました。ここで注目したいのは、Nilがcase objectであり(つまり値である)、List[Nothing]を継承している事です。

NothingはScalaにおけるあらゆる型のサブタイプ、つまりどんな型にでもアップキャストできる型であるため、Listが共変であれば、List[Nothing]はあらゆる型のList(たとえば List[Int]List[String] )になれます。

というわけで、scala.Listは、実用上の必然性があって共変になっているのでした。標準ライブラリでは、他にもscala.collection.immutable.Stream等が共変になっていますが、これも同じ理由によるものです。

ちなみに、最初にあげたSML,OCaml,Haskellでは、多相的な値を定義できるために、このような仕組みを必要としません*2。たとえば、Haskellのリストは

data  [a]  =  [] | a : [a]  deriving (Eq, Ord)

のように定義されますが(Haskellではリストは構文上特別な扱いを受けるため、実際のHaskellでは構文エラーですが)、これで、空のリストは任意の型aのリストであるという事を定義できたことになります。

Scalaでは、共変とあらゆる型のサブタイプであるNothingを使って、このような多相的な値をエミュレートしているといえます。

*1:コメント欄でご指摘いただいたように、OCamlのlistは共変です。この点、誤った先入観に基づいた記述でした

*2:OCamlに関してもこの点は当てはまりますが、OCamlでもlistは共変です