SetがFunctorではない理由を延々と説明します。最初これ
http://failex.blogspot.jp/2013/06/fake-theorems-for-free.html
を訳そうとしましたが、英語力と理解力のなさにより断念し、中途半端な翻訳になるなら、自分なりに書き下そうという結論になりました。内容は上記の記事と半分以上被ると思います。あと、上記の記事書いた人は「Scalazのコミッターであり、おそらくekmettの同僚であり、ermine-languageのコミッター」な人です。よってオススメなので、そっちも読みましょう。*1
以下、Scala以外の言語でも大概は当てはまると思いますが、一応Scala(というか、Scalaz)を念頭において書いていきます。
さて、プログラミングにおいて、Setとは一体何でしょうか？
とりあえず「要素の重複を持たないデータ構造」といえるでしょう。*2
では「要素の重複」とは？つまり「重複しているかどうか？」を判断できないといけませんね。
さて、Javaには、Object#equalsというメソッドがあります。他の言語でも、大概似たようなものがあるでしょう。
がしかし、HaskellやScalazなどでは
「すべての型のオブジェクト同士が比較できる」という前提を置きません。
まずここが大きなポイントです。
さて、それが「SetがFunctorかどうか？」と、どのように関わってくるのでしょうか？
ここで、ScalaでのFunctorの定義を見てみましょう*3
trait Functor[F[_]] { def map[A, B](fa: F[A])(f: A => B): F[B] }
F[A]というオブジェクトと、"A => B"という「Aを引数にとって、Bを返す関数」が存在した場合に、必ずF[B]が得られる、ということです。*4これは、"A => B"という関数さえあれば、Bの具体的な型には、なにも制約はありません。*5
さて、ここでまた話を変えてSetについて考えます。Setの実装方法には、HashSetとTreeSetの２種類が代表的でしょう。*6
Set自体を実装するには「要素の型同士が比較できる」ことが必ず必要な条件です。しかし、それだけだととても使いものにならないような遅い実装になってしまうので、Hash値をつかうか、「順序付けができる性質を利用しTree上に格納」することによって、効率のよい実装をします。
さて、ここからやっと本題に入る感じになりますが、ScalaのSetのFunctorを実装してみると、ScalaのSet自体はもともとmapメソッドを持っているので、以下のように簡単に実装できそうに思えます。
val setFunctor = new Functor[Set] { def map[A, B](fa: Set[A])(f: A => B): Set[B] = fa.map(f) }
しかし「Set[B]の要素が比較可能である」というのをどうやって保証するのでしょうか？Scalaにおいて、デフォルトでスコープに入っているSetは、HashSetです。そしてScalaのHashSetでは、内部でObject#equalsやObject#hashCodeが使われています。*7
Scalaz的な考えでは「Object#equalsやObject#hashCodeは使ってはいけません！」
それらは、暗黙的にすべてのオブジェクトに適用できてしまうことにより、型安全ではないからです(比較するべきでないもの同士も比較できてしまうから)
Scalazに独自のHashSet実装は現在のところありませんが、もし独自にHashSetを実装するとしたら、以下のような形になるでしょう。
trait Equal[A]{ // 内部省略。Equalは現在も存在する } trait Hash[A] extends Equal[A]{ // hash値を計算できること、を示す型クラス // Equalとの関係性から、おそらくEqualを継承することになるはず def hash[A](a: A): Int // hash値返す。IntでなくLongでもいいかも } class HashSet[A](implicit H: Hash[A]){ // 生成時に、要素の型のHash型クラスを要求 // 内部省略 }
さて、もし上記のような「Hash型クラスを要求するHashSet」だとしたら、Functorのインスタンスは作れません。
もし以下のように、「implicitパラメータを１つ追加した微妙にシグネチャが異なるFunctor」だったら、インスタンスを生成できることになりますが、これは、もとのFunctorとは別物です
trait Functor[F[_]] { def map[A, B](fa: F[A])(f: A => B)(implicit H: Hash[B]): F[B] }
これは、TreeSetについても同様で、ScalaのTreeSetはscala.Orderingが作成時に必要です。なので、本当のFunctorのインスタンスは作れず、もし任意のBに対してつくるとしたら、以下のようになっていないといけません。
trait Functor[F[_]] { def map[A, B](fa: F[A])(f: A => B)(implicit O: scala.Ordering[B]): F[B] // ここは、scalaz.Orderを要求でもscala.Orderingでも、どちらでもいいですが }
このように、Setは「要素の型に対して制限が必要」なためFunctorにはなれません。*8
一方たとえばListなどは、文字通り
「List[A]という型のオブジェクトと、"A => B"という関数」
という2つのものさえあれば、Bがどんな型であろうとも必ずList[B]が生成できます。これが、ListはFunctorになれるのに、SetはFunctorになれないという意味です。
というわけで、昔はScalazにSetのFunctorのインスタンスが存在したのですが、現在ではなくなっています。
https://github.com/scalaz/scalaz/pull/276
