7.7. 型の族

添字付けされた型の族は、型レベルのプログラミングを容易にするための新しいGHC拡張である。型の族は、関連データ型(“Associated Types with Class”, M. Chakravarty, G. Keller, S. Peyton Jones, and S. Marlow. In Proceedings of “The 32nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'05)”, pages 1-13, ACM Press, 2005)および関連型シノニム(“Type Associated Type Synonyms”. M. Chakravarty, G. Keller, and S. Peyton Jones. In Proceedings of “The Tenth ACM SIGPLAN International Conference on Functional Programming”, ACM Press, pages 241-253, 2005)の一般化である。型の族自体は論文“Type Checking with Open Type Functions”, T. Schrijvers, S. Peyton-Jones, M. Chakravarty, and M. Sulzmann, in Proceedings of “ICFP 2008: The 13th ACM SIGPLAN International Conference on Functional Programming”, ACM Press, pages 51-62, 2008 Functional Programming”, ACM Press, pages 241-253, 2005)に記述されている。型の族は、要するに、型で添字付けされたデータ型と、型についての名前の付いた関数を提供する。これらは、総称(generic)プログラミングや高度にパラメタ化されたライブラリインタフェース、さらには、依存型と同様に、インタフェースにより多くの静的な情報を与えるのに有用である。また、型の族は関数従属の代わりとなるものとも見なされている。関数従属では型レベルのプログラミングを関係的に行うのに対して、型の族はより関数的な様式を可能にする。

添字付けされた型の族(indexed type family)、短くいうと型族(type family)は、型の集合を表すような型構築子である。集合の要素は、型族構築子に型引数(型添字と呼ぶ)を与えることで記述される。通常のパラメタ付きの型構築子と族構築子との違いは、パラメタ多相な関数と型クラスの(アドホック多相な)メソッドとの違いによく似ている。パラメタ多相な関数はあらゆる具体的な型に対して等しく振る舞うのに対し、クラスのメソッドはクラスの型パラメタに依存して振る舞いを変える。同様に、通常の型構築子はあらゆる具体的な型に対して同じデータ表現を使うことになるが、型族構築子は異なる型添字に対して異なる表現型を持つことができる。

添字付けされた型の族には二つの系統がある。データ族型シノニム族である。これらは、それぞれ代数的データ型と型シノニムを添字付けされた型の族にしたものである。データの族のインスタンスとしてはデータ型とnewtypeがありえる。

型の族は-XTypeFamiliesフラグによって有効になる。GHCで型の族を使うことについてのさらなる情報が型の族についてのHaskell wikiのページにある。

7.7.1. データ族

データ族には次の二つの系統がある。(1)最上位で定義されるもの (2)型クラスの中に現れるもの(この場合、これは関連型と言われる)。前者の方が一般性の高い系統である。なぜなら、型添字がクラスのパラメタと一致する必要がないからである。一方、後者の方が明確に構造化されたコードにつながりやすく、なんらかの型インスタンスが(もしかすると意図せずに)省略された場合、コンパイラが警告を発する。以下では常に、まず一般的な最上位の形式について議論し、その後で関連型に課せられる追加の制約を扱う。

7.7.1.1. データ族宣言

添字付けされたデータ族は次のようなシグネチャによって導入される。

data family GMap k :: * -> *

この特別なfamilyが、族を標準的なデータ宣言から区別する。結果の種注釈は省略可能であり、省かれた場合は通常同様に*が使われる。例を示す。

data family Array e

名前の付いた引数にも必要なら明示的な種シグネチャを与えることができる。[http://www.haskell.org/ghc/docs/latest/html/users_guide/gadt.html GADT宣言]の場合と同様、名前付き引数は完全に省略可能なので、Arrayを次のように宣言することもできる。

data family Array :: * -> *

7.7.1.2. データインスタンス宣言

データとnewtypeの族についてのインスタンス宣言は、通常のデータおよびnewtypeの宣言と良く似ている。違いが二つだけあって、dataあるいはnewtypeキーワードの後にinstanceが書かれることと、型引数の一部または全てが変数でない型であってもよいということである。ただし、これにforall型や型シノニム族が含まれていてはいけない。しかし、一般にデータ族が型パラメタ中にあってもよく、型シノニムも、それが完全に適用されていて、しかも展開結果が合法であるなら、認められる。これはクラスインスタンスのパラメタにおいて型シノニムが現れてよい条件と全く同じである。例として、GMapEitherインスタンスは次のようになる。

data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)

この例では、宣言にただ一つのvariantしかないが、一般にはいくつあってもよい(訳注: データ構築子が複数あってもいいということ?)。

データインスタンス宣言およびnewtypeインスタンス宣言は適切な族宣言がスコープにある場合のみ認められる。これはちょうど、クラスインスタンス宣言にクラス宣言が可視であることが必要なのと同じである。さらに、各インスタンス宣言は、その族宣言によって決まる種に準拠していなければならない。つまり、インスタンス宣言のパラメタの個数は、その族の種から決まるアリティと一致するということである。

データ族インスタンス宣言は、通常のdatanewtype宣言が持つ表現力を完全に利用できる。

  • データ族は「data」キーワードを使って導入されるが、族のインスタンスdataであってもnewtypeであってもよく、両者の混合であってもよい。例を示す。

    data family T a
    data    instance T Int  = T1 Int | T2 Bool
    newtype instance T Char = TC Bool
    

  • data instanceはデータ構築子にGADT構文を使うことができ、また実際にGADTを定義することができる。例。

    data family G a b
    data instance G [a] b where
       G1 :: c -> G [Int] b
       G2 :: G [a] Bool
    

  • data instancenewtype instance宣言にderiving節を使うことができる。

型族が最上位の宣言によって定義されている場合でも、異なる族インスタンスに対して異なる計算を行う関数は相変らず型クラスのメソッドとして定義されねばならないことがある。特に、以下は不可能である。

data family T a
data instance T Int  = A
data instance T Char = B
foo :: T a -> Int
foo A = 1             -- 間違い: この二つの等式をいっしょにすると...
foo B = 2             -- ...型エラーが発生する

代わりに、fooをクラスの演算として書かなければならないだろう。

class Foo a where
  foo :: T a -> Int
instance Foo Int where
  foo A = 1
instance Foo Char where
  foo B = 2

(GADT(一般化代数的データ型)の提供する機能を見ると、上のような定義が可能であるべきだと思えるかもしれない。しかし、型族は、GADTとは対照的に、開かれている。つまり、常に新しいインスタンスを加えることが可能な(しかも別モジュールでかもしれない)のである。異なるデータインスタンスに跨がるパターン照合に対応するには、一種の拡張可能なcase構造が必要になることだろう。)

7.7.1.3. データインスタンスの重複

一つのプログラムの中で、あるデータ族のインスタンス宣言に少しでも重複部分があってはならない。このことは関連族であるかそうでないかによらない。型クラスのインスタンスの場合と異なり、これは単なる整合性の問題ではなく、型安全性の問題である。

7.7.2. シノニム族

型族が出現する方法には二通りの系統がある。(1)最上位で定義されるか、(2)型クラスの内部に出現する(この場合、これは関連型シノニムと言われる)かである。前者の系統は、型添字がクラスパラメタと一致しなければならないという制限がないので、より一般性が高い。一方、後者の方が明確に構造化されたコードにつながりやすく、なんらかの型インスタンスが(もしかしたら意図せず)省略された場合、コンパイラが警告を発する。以下では常に、まず一般的な最上位の形式について議論し、その後で関連型に課せられる追加の制約を扱う。

7.7.2.1. 型族宣言

添字付けされた型族は次のようなシグネチャによって導入される。

type family Elem c :: *

この特別なfamilyによって、通常の型宣言と族宣言が区別される。結果の種注釈は省略可能であり、通常と同様に、省略された場合は*が使われる。例えば次のようになる。

type family Elem c

必要ならパラメタにも明示的な種シグネチャを付けることができる。型族宣言におけるパラメタの数をその族のアリティと呼び、その型族の適用は全てそのアリティに対して完全に飽和していなければ(訳注: つまり部分適用であっては)ならない。この制限は通常の型シノニムにはないものである。これにより、型族の種を知っただけではその族のアリティを決定できないので、型族の適用が正しいものかどうかも一般的には判断できない。例として、次の宣言を考える。

type family F a b :: * -> *   -- Fの種は全体として見れば * -> * -> * -> *
                              -- しかし、アリティは2である

この宣言のもとで、以下に正しい型と間違った型の例を示す。

F Char [Int]       -- 正 種: * -> *
F Char [Int] Bool  -- 正 種: *
F IO Bool          -- 誤 最初の引数で種が不一致
F Bool             -- 誤 適用が飽和していない

7.7.2.2. 型インスタンス宣言

型族のインスタンス宣言は通常の型シノニム宣言によく似ている。違いは、typeキーワードの後にinstanceが書かれることと、型引数の一部または全部が変数でなくてもよいことの二点だけである。ただし、型引数は、forall型や型シノニム族を含んでいてはならない。一方、一般にデータ族はあってもよく、型シノニムも、完全に適用されており、かつ展開結果が合法であるなら認められる。これらはデータインスタンスの場合と全く同じ制限である。例として、[e]Elemインスタンスは次のようになる。

type instance Elem [e] = e

型族インスタンス宣言は、適切な族宣言がスコープにあるときのみ認められる。これはちょうど、クラスインスタンスにはクラス宣言が可視であることが必要なのと同じである。さらに、個々のインスタンス宣言は、その族宣言によって決まる種に準拠していなければならず、インスタンス宣言の型パラメタの数は族宣言の型パラメタの数と一致していなければならない。最後に、型インスタンスの右辺は単相型でなければ(つまり、forallを含んでいては)ならず、また飽和した通常の(訳注: vanilla; 型シノニム族でない)型シノニムを全て展開した時点で、族シノニム以外のシノニムが残っていてはならない。許される型インスタンスとそうでない型インスタンスの例をいくつか挙げる。

type family F a :: *
type instance F [Int]              = Int         -- OK!
type instance F String             = Char        -- OK!
type instance F (F a)              = a           -- 誤: 型パラメタが型族に言及している
type instance F (forall a. (a, b)) = b           -- 誤: 型パラメタの中にforall型がある
type instance F Float              = forall a.a  -- 誤: 右辺がforall型であってはならない

type family G a b :: * -> *
type instance G Int            = (,)     -- 誤: 引数は二つでないといけない
type instance G Int Char Float = Double  -- 誤: 引数は二つでないといけない

7.7.2.3. 型シノニムインスタンスの重複

ある一つのプログラム内で使われる型族のインスタンス宣言に関して、重複が許されるのは、重複するインスタンスの右辺が共通部分の型に対しては一致する場合だけである。より形式的に言うと、二つのインスタンス宣言が重複するとは、インスタンスの左辺を構文的に一致させるような代入(substitution)が存在するときである。これに該当する場合は必ず、この同じ代入のもとでインスタンスの右辺も構文的に同じにならなければならない。この条件は族が関連族であるかどうかに拠らない。また、これは単なる整合性の問題ではなく、型安全性の問題である。

重複が許される条件を説明するために二つの例を用意した。

type instance F (a, Int) = [a]
type instance F (Int, b) = [b]   -- 重複が許される

type instance G (a, Int)  = [a]
type instance G (Char, a) = [a]  -- 非合法な重複、[Char] /= [Int]であるため

7.7.2.4. 型シノニムインスタンスの決定可能性

型族の存在下での型推論が決定可能であることを保証するため、型インスタンス宣言の形式に追加で制限を課す必要がある。(“Type Checking with Open Type Functions”のDefinition 5 (Relaxed Condition)も参照)。インスタンス宣言の一般形式は次の通りである。

type instance F t1 .. tn = t

ここで、t中のすべての型族適用(G s1 .. sm)に対して、以下のことを要求する。

  1. s1 .. smに、型族構築子が一つも含まれない。

  2. s1 .. sm中のシンボル(データ型構築子および型変数)の数が、t1 .. tnにおける数よりも厳密に小さい。

  3. 全ての型変数aについて、aがs1 .. smに現れる回数が、t1 .. tnに現れる回数を超えない。

これらの制限は容易に検査することができ、型インスタンスが停止することを保証する。しかし、a ~ [F a]のように、型構築子が族適用とデータ構築子適用の下にある、いわゆる「ループ的同値」の存在下では、型推論の完全性を保証するのに足りない。詳細については上で挙げた論文を参照のこと。

-XUndecidableInstancesオプションがコンパイラに渡されると、上記の制約は強制されず、型推論中に型族の正規化が停止することを保証するのはプログラマの責任になる。

7.7.3. 関連データ族と関連型族

データまたは型シノニムを型クラスの一部として宣言することができる。次にように。

class GMapKey k where
  data GMap k :: * -> *
  ...

class Collects ce where
  type Elem ce :: *
  ...

このようにするとき、「family」キーワードは使わない。

型パラメタはもちろん全て型変数でなければならない。そして、そのうちのいくつか(全部でなくてよい)はクラスパラメタであってよい。個々のクラスパラメタは関連型一個につき高々一回しか使われてはならないが、使われないものがあっても良いし、クラス頭部とは違う順番であっても良い。よって、次の不自然な例は許容される。

  class C a b c where
    type T c a x :: *

ここでcaはクラスパラメタであるが、この型は第三のパラメタxによっても添字付けされている。

7.7.3.1. 関連インスタンス

関連データ族インスタンスや関連型シノニムインスタンスが型クラスインスタンスの中で宣言される場合、族インスタンスにおけるinstanceキーワードは使わない。

instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where
  data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)
  ...

instance (Eq (Elem [e])) => Collects ([e]) where
  type Elem [e] = e
  ...

関連族インスタンスに関して最も重要な点は、クラスパラメタに対応する型添字が、インスタンス頭部で与えられる型と同一でなければならないということである。この例ではこれはGMapの第一引数であるEither a bであるが、これは(一つしかない)クラスパラメタと同じになっている。

関連族のインスタンスは、その族が宣言されたクラスのインスタンス宣言の一部としてしか現れることができない。これはクラスのメソッドの等式と同じである。また、これもメソッドの扱いと対応するが、クラスインスタンスにおいて関連型の宣言を省略することができる。関連族インスタンスが省略された場合、それに対応するインスタンス型は無内容(not inhabited)になる。すなわち、undefinedなどの発散する式のみがその型を持てる。

珍しいことだが、単一のインスタンス宣言の中に、ある関連族のインスタンスが複数あってもよい。たとえば、次のものは合法である。

instance GMapKey Flob where
  data GMap Flob [v] = G1 v
  data GMap Flob Int = G2 Int
  ...

ここでは二つのデータインスタンス宣言を与えている。片方では最後のパラメタが[v]であり、もう片方ではIntである。これ以降に(GMap Flob ...)のインスタンスを与えることができないので、この機能は、自由な添字変数の種が(*とは違って)有限個の選択肢から成る場合に最も便利である。

7.7.3.2. 関連型シノニムのデフォルト

関連型を定義するクラスは、関連型インスタンスのためにデフォルトを指定することができる。よってこれは問題ない。

class IsBoolMap v where
  type Key v
  type Key v = Int

  lookupKey :: Key v -> v -> Maybe Bool

instance IsBoolMap [(Int, Bool)] where
  lookupKey = lookup

重複部分がない限り、一つの型に複数のデフォルトがあっても良い。

class C a where
  type F a b
  type F a Int  = Bool
  type F a Bool = Int

関連データ型についてはデフォルト宣言は認められない。

7.7.3.3. クラスパラメタのスコープ規則

クラスパラメタが関連族インスタンスの右辺から可視かどうかは、そのデータ族のパラメタのみによって決まる。例として、次の単純なクラス宣言を考える。

class C a b where
  data T a

二つのクラスパラメタのうち一つだけがデータ族のパラメタになっている。このため、次のインスタンス宣言は不正である。

instance C [c] d where
  data T [c] = MkT (c, d)    -- 間違ってるよ!!  「d」はスコープにない

ここでは、データインスタンスの左辺に現れない型変数dが右辺で言及されている。このようなデータインスタンスを認めると型安全性を犠牲にすることになるので、これは認められていない。

7.7.4. インポートとエクスポート

エクスポートリストのための規則(Haskell Reportの5.2節)は、型族を扱えるように調整する必要がある。

  • T(..)という形、ただしTはデータ族。これはTと、Tのデータインスタンスである構築子のうち(修飾形であれ非修飾形であれ)スコープにあるもの全てを指名する。

  • T(.., ci, .., fj, ..)という形、ただしTはデータ族。これは通常と同様に、Tと、指定された構築子ciおよびフィールドfjを指名する。構築子とフィールドはTのデータインスタンスのいずれかに属していなければならないが、同じものに属している必要はない。

  • C(..)という形、ただしCはクラス。これは、クラスCと、そのメソッド全てと、その関連型を指名する。

  • C(.., mi, .., type Tj, ..)という形、ただしCはクラス。これは、クラスCと、指定されたメソッドmiおよび関連型Tjを指名する。データ構築子と区別するために、型には「type」キーワードが必要である。

7.7.4.1. 例

ここまで使ってきたGMapKeyクラスの例を思い出して欲しい。

class GMapKey k where
  data GMap k :: * -> *
  insert :: GMap k v -> k -> v -> GMap k v
  lookup :: GMap k v -> k -> Maybe v
  empty  :: GMap k v

instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where
  data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)
  ...method declarations...

以下に、エクスポートリストいくつかと、その意味を記す。

  • module GMap( GMapKey ): クラス名のみをエクスポートする。

  • module GMap( GMapKey(..) ): クラス、関連型GMap、メンバ関数emptylookupinsertをエクスポートする。GMapのデータ構築子(この場合はGMapEither)はエクスポートされない。

  • module GMap( GMapKey( type GMap, empty, lookup, insert ) ): 前項と同じ。「type」キーワードに注意。

  • module GMap( GMapKey(..), GMap(..) ): 前項と同じだが、GMapの全ての構築子、つまりGMapEitherもエクスポートする。

  • module GMap ( GMapKey( empty, lookup, insert), GMap(..) ): 前項と同じ

  • module GMap ( GMapKey, empty, lookup, insert, GMap(..) ): 前項と同じ

注意点を二つ。

  • GMapKey(type GMap(..))と書くことはできない。つまり、内容指定は入れ子にできない。GMapのデータ構築子を指定するなら、それを別に書かねばならない。

  • 次の例を考えよ

      module X where
        data family D
    
      module Y where
        import X
        data instance D Int = D1 | D2
    

    モジュールYは、Yで定義された全ての実体をエクスポートする。つまりデータ構築子D1およびD2をエクスポートするが、データ型族Dはエクスポートしない。これは(うっとおしいことに)「import Y( D(D1,D2) )」としてYを選択的にインポートすることができないこをと意味する。YがDをエクスポートしていないからである。こうする代わりに、エクスポートリストを明示的に指定するべきである。次のように。

            module Y( D(..) ) where ...
    または  module Y( module Y, D ) where ...
    

7.7.4.2. インスタンス

クラスインスタンスと同様に、族インスタンスは暗黙にインポートされる。ただし、これはインスタンスの頭部についてだけ適用される。インスタンスが定義するデータ構築子には適用されない。

7.7.5. 型族とインスタンス宣言

型族のもとでは、インスタンス頭部の形式についての規則(7.6.3.1. インスタンス頭部に関する規則の緩和で与えられている)を拡張する必要がある。特に、

  • データ型族はインスタンス頭部に現れてもよい

  • 型シノニム族はインスタンス頭部に(全く)現われてはいけない

後者の制約があるのは、インスタンスが適合しているか検査する方法がないからである。次の例を考えよ。

   type family F a
   type instance F Bool = Int

   class C a

   instance C Int
   instance C (F a)

ここで、(C (F Bool))という制約は両方のインスタンスに適合する。F Boolの型インスタンスは別のモジュールにあるかもしれず、さらにはまだ書かれていないモジュールにあることさえあり得るので、この状況は特にまずい。

一方、データ族のインスタンスについての型クラスインスタンスは、通常のデータ型とほとんど同じに書ける。例えば次のように言うことができる。

data instance T Int = T1 Int | T2 Bool
instance Eq (T Int) where
  (T1 i) == (T1 j) = i==j
  (T2 i) == (T2 j) = i==j
  _      == _      = False

クラスのインスタンスになるのは常にデータ族の特定のインスタンスであって、族全体ではないのに注意。これは要するに、一つの型族の異なる構築子に対してパターン照合を行う最上位関数を定義できないのと同じ理由による。これをするには拡張可能なcase構造が必要になるだろう。

データインスタンス宣言はまた、deriving節を持っていても良い。例えば次のように書くことができる。

data GMap () v = GMapUnit (Maybe v)
               deriving Show

これは次の形のインスタンスを暗黙に定義する。

instance Show v => Show (GMap () v) where ...