インスタンス導出の仕様

インスタンス導出とは、データまたはnewtype宣言から自動的に生成されるインスタンス宣言である。インスタンス導出のコード本体は対応する型の定義から文法的に導出される。インスタンス導出はコンパイラが知っているクラスに対してのみ可能である。このようなクラスはPreludeまたは標準ライブラリで定義されている。この章では、Preludeによって定義されたクラスの導出について説明する。

Tが次のように定義された代数的データ型であるとする:

data cx => T u1 ... uk = K1 t11 ... t1k1 | ... | Kn tn1 ... tnkn
    deriving (C1, ..., Cm)

(ここで、m ≥ 0であるとする。また、m = 1のときは括弧は省略できる)

そしてクラスCに対するインスタンス導出宣言は次の条件を満たすときに可能である:

  1. CはEq, Ord, Enum, Bounded, Show, Readのいずれかである
  2. 文脈cx'であって、cx' => C tijが構成に使われているすべての型tijについて成り立つようなものが存在する
  3. CがBoundedであるとき、型は列挙型である(どのコンストラクタもパラメーターを持たない)か、唯一のコンストラクタをもつ
  4. CがEnumであるとき、型は列挙型である
  5. T u1 ... ukがCのインスタンスになるような明示的なインスタンス宣言がプログラムのどこにも存在しない
  6. データ宣言がコンストラクタをもたないとき(上でn = 0のとき)、どのクラスも導出可能でない(m = 0である)

インスタンスを導出するという目的から、newtype宣言はdata宣言で1つコンストラクタをもつものとして扱われる。

derivingの形があるとき、各クラスCiに対するT u1 ... ukのインスタンス宣言は自動的に生成される。どれかのCiに対してインスタンス宣言が導出不可能であるとき、静的エラーが返る。インスタンス導出が必要でないときは、derivingの形は省略されるか、deriving ()が使われることもある。

それぞれの導出されたインスタンス宣言は instance (cx, cx') => Ci (T u1 ... uk) where { d } の形をしている。ただしdはCiとTのデータ型宣言に依存して自動的に導出される(これについてはこのセクションの残りで説明する))。

コンテキスト cx'は上の(2)を満たす最小のコンテキストである。相互再帰データ型でこれを計算するためにコンパイラは不動点の計算を行う必要があることがある。

Preludeのクラスで導出可能なそれぞれについてのインスタンス導出の詳細をここで与える。ここでの説明で登場する自由変数とコンストラクタはすべてPreludeで定義されたものを指している。

EqとOrdのインスタンス導出

EqとOrdのインスタンス導出によって自動的に導入されるクラスメソッドは (==), (/=), compare, (<), (<=), (>), (>=), max, minである。最後の7つの演算子は各コンストラクタの集合ごとに辞書順で比較を行うように定義される。すなわち、データ型宣言で先に書かれたコンストラクタは後に書かれたコンストラクタよりも小さい値として扱われる。例えば、Boolデータ型に対して、(True > False) == Trueが成り立つ。

導出された比較はコンストラクタを常に左から右に向かって走査する。このことは次の例から確かめられる:

(1,undefined) == (2,undefined) =>    False
(undefined,1) == (undefined,2) =>    ⊥

導出されたクラスEqとOrdの演算はいずれも引数に対して正格である。例えば、FalseはBool型の最初のコンストラクタであるがFalse <= ⊥は⊥である。

Enumのインスタンス導出

Enumのインスタンス導出宣言は列挙型(すべてのコンストラクタが引数をとらないようなデータ型)に対してのみ可能である。

引数をとらないコンストラクタはは左から右に向かって0からn-1までナンバリングされていると仮定する。このナンバリングの仕組みの下でsuccとpredは値の次の値と前の値を与える演算子である。succを最大の要素に適用したときとpredを最小の要素に適用したときはエラーになる。

toEnumとfromEnumは列挙された値をIntへ、またはIntから変換する演算子である。toEnumはIntの引数に一致するコンストラクタの番号がない場合は実行時エラーになる。

他のメソッドの定義は次である:

enumFrom x           = enumFromTo x lastCon
enumFromThen x y     = enumFromThenTo x y bound
    where  
        bound
            | fromEnum y >= fromEnum x = lastCon
            | otherwise                = firstCon
enumFromTo x y       = map toEnum [fromEnum x .. fromEnum y]
enumFromThenTo x y z = map toEnum [fromEnum x, fromEnum y .. fromEnum z]

ここで、firstConとlastConはそれぞれdata宣言にある最初と最後のコンストラクタである。例として、データ型

data Color = Red | Orange | Yellow | Green deriving (Enum)

が与えられたとき、次のようになる:

[Orange ..]         ==  [Orange, Yellow, Green]  
fromEnum Yellow     ==  2

Boundedのインスタンス導出

BoundedクラスはminBoundとmaxBoundをクラスメソッドとして導入するが、これはそれぞれその型の最小、最大の要素を定めるメソッドである。列挙型に対しては、data宣言にある最初と最後のコンストラクタが境界になる。コンストラクタが1つの型に対しては、コンストラクタを構成型の教会に適用したものになる。例として、次のデータ型を考える。

data Pair a b = Pair a b deriving Bounded

これは次のようなBoundedインスタンスを生成する:

instance (Bounded a,Bounded b) => Bounded (Pair a b) where  
    minBound = Pair minBound minBound  
    maxBound = Pair maxBound maxBound

ReadとShowのインスタンス導出

ReadとShowのインスタンス導出で自動的に導入されるクラスメソッドはshowsPrec, readsPrec, showList, readListである。これらは値を文字列に変換し、文字列をパースして値にするために使われる。

関数showsPrec d x rは優先度d(0から11の間の数値をとる)、値x、文字列rを受ける。これはrにxの文字列表現を結合したものを返す。showsPrecは次の規則を満たす: showsPrec d x r ++ s == showsPred d x (r ++ s) この表現は、xのトップレベルコンストラクタの優先度がdよりも小さいときは括弧で囲われる。追加のパラメータrは木などの構造を木のサイズに対して二次関数的でなく線形時間で出力するためには必須になる。

関数readsPrec d sは優先度d(0から10の数値をとる)と文字列sを受け取り、文字列の先頭から値をパースすることを試み、(パースされた値, 残りの文字列)なるペアのリストを返す。パースに成功することがない場合、返却されるリストは空になる。括弧のない中置演算子の適用のパースが成功するのは演算子の優先度がd以上の時だけである。

次が成り立つ。

(x,"") は (readsPrec d (showsPrec d x "")) の要素である

つまり、readsPrecはshowsPrecによって生成された文字列をパースでき、showsPrecに初めに渡された値が得られるべきである。

showListとreadListは標準的でない表示を使ってオブジェクトのリストを表現できるようにする。

readsPrecは文字列以外の標準的な型のどんな有効な表現もパースできる。文字列に対してはクォートされた文字列のみが許され、他にはリストに対しては、ブラケットで囲まれた形[...]のみが許される。詳細は9章([訳注] リンク)を見よ。

showの結果は、結合性の宣言がその型が宣言された時点で有効になっている場合であれば、定数のみを含んだHaskellの文法的に正しい式になる。戻り値は、データ型で定義されたコンストラクタの名前と括弧、スペースのみを含む。ラベル付きコンストラクタフィールドが使われているときは、波括弧、コンマ、フィールド名、等号も使われる。括弧は結合性を無視して必要なところでだけ追加される。showの戻り値は、すべてのコンポーネント型がread可能ならばreadできる。(これはPreludeで定義されたすべてのインスタンスに対しては正しいが、ユーザーによって定義されたインスタンスではそうとは限らない。)

Readのインスタンス導出によって、次のようなことが仮定される。そしてこれらの過程はShowのインスタンス導出も従う:

  • コンストラクタが中置演算子として定義されているならば、Readインスタンスの導出はコンストラクタの(前置形ではなく)中置適用のみをパースする。

  • 結合性は括弧を減らすためには使われないが、優先度はそうと使われる場合がある。例として

    infixr 4 :$
data T = Int :$ T | NT

    があったとき、

    • show (1 :$ 2 :$ NT)は文字列"1 :$ (2 :$ NT)"を生成する。
    • read "1 :$ (2 :$ NT)"は成功し、当然の結果を返す。
    • read 1 :$ 2 :$ NTは失敗する。

  • コンストラクタがレコード構文により定義されている場合、導出されたReadはレコード構文の形のみパースし、さらにフィールドは元々の宣言と同じ順番でしか与えることはできない。

  • Readインスタンスの導出は入力文字列のトークンの間に任意のHaskellの空白を許す。余分な括弧も許される。

ReadとShowインスタンスの導出が不適切なケースもある。次のような問題がある:

  • 循環構造はこれらのインスタンスによっては出力、読み取りできない。
  • 出力によって部分構造の共有が失われる。つまり、オブジェクトが出力された表現は必要より遥かに大きくなる場合がある。
  • readで使われるパースの方法は非常に非効率的であるので、巨大な構造の読み取りは非常に遅い場合がある。
  • Preludeで定義された型の出力はユーザーによる制御ができない。例えば、浮動小数点数のフォーマットを変える方法がない。

例

完結した例として木構造を考えよう:

data Tree a = Leaf a | Tree a :^: Tree a
    deriving (Eq, Ord, Read, Show)

Treeは列挙型でもなければコンストラクタが1つでもないので、BoundedとEnumのインスタンスの自動導出はできない。Treeのインスタンス宣言の完全なものはFigure 11.1にある。デフォルトクラスメソッド定義に注意せよ。例えば、Ordに対しては<=のみが定義されており、ほかのクラスメソッド(<,>,>=,max,min)はFigure 6.1に示されている、クラス宣言で与えられたデフォルト値によって与えられている。

Figure11.1: インスタンス導出の例

infixr 5 :^:  
data Tree a =  Leaf a  |  Tree a :^: Tree a  
 
instance (Eq a) => Eq (Tree a) where  
        Leaf m == Leaf n  =  m==n  
        u:^:v  == x:^:y   =  u==x && v==y  
             _ == _       =  False  
 
instance (Ord a) => Ord (Tree a) where  
        Leaf m <= Leaf n  =  m<=n  
        Leaf m <= x:^:y   =  True  
        u:^:v  <= Leaf n  =  False  
        u:^:v  <= x:^:y   =  u<x || u==x && v<=y  
 
instance (Show a) => Show (Tree a) where  
 
        showsPrec d (Leaf m) = showParen (d > app_prec) showStr  
          where  
             showStr = showString "Leaf " . showsPrec (app_prec+1) m  
 
        showsPrec d (u :^: v) = showParen (d > up_prec) showStr  
          where  
             showStr = showsPrec (up_prec+1) u .  
                       showString " :^: "      .  
                       showsPrec (up_prec+1) v  
                -- Note: right-associativity of :^: ignored  
 
instance (Read a) => Read (Tree a) where  
 
        readsPrec d r =  readParen (d > up_prec)  
                         (\r -> [(u:^:v,w) |  
                                 (u,s) <- readsPrec (up_prec+1) r,  
                                 (":^:",t) <- lex s,  
                                 (v,w) <- readsPrec (up_prec+1) t]) r  
 
                      ++ readParen (d > app_prec)  
                         (\r -> [(Leaf m,t) |  
                                 ("Leaf",s) <- lex r,  
                                 (m,t) <- readsPrec (app_prec+1) s]) r  
 
up_prec  = 5    -- :^: の結合優先度
app_prec = 10   -- 適用はどんな結合優先度の高い演算子よりも優先度が高い