The Haskell 98 Report
top | back | next | contents | function index


3  

この節では、Haskell のの構文と非形式的セマンティクスにつ いて説明する。また、必要な個所では、Haskell カーネルへの変換について も説明する。let 式の場合をのぞけば、これらの変換は静的なセマ ンティクスと動的なセマンティクスの両方を保存する。 これらの変換のなかで用いられる自由変数と構成子は常に Prelude で定義されたものを参照する。たとえば、 リストの内包表記(3.11 節) の変換で使用される "concatMap" の意味は Prelude で 定義された concatMap である。これは、識別子 "concatMap" がそのリスト内包表記が使われているスコープにあるかどうかは関係なく、 また、もしスコープ内にあった場合でもそれが束縛されているものには関係 ない。

以下の構文には、優先レベルのインデックスが(右肩に)ついた非終端記号 の族がいくつかある。同様に非終端記号 opvarop および conop にはインデックスが 2 つ付くものがある。片方の文字 l および r は、それぞれ左結合性、右結合性を、文字 n は結合 性がないことを示し、もう一方は優先レベルを示している。優先レベル変数 i は 0 から 9 までの範囲であり、結合性変数 a{l, r, n} のうちどれかである。したがって、たとえば、

aexp -> ( expi+1 qop(a,i) )

i について 10 通り、a について 3 通りの全部で 30 通りの式が生成される。

exp -> exp0 :: [context =>] type (expression type signature)
| exp0
expi -> expi+1 [qop(n,i) expi+1]
| lexpi
| rexpi
lexpi -> (lexpi | expi+1) qop(l,i) expi+1
lexp6 -> - exp7
rexpi -> expi+1 qop(r,i) (rexpi | expi+1)
exp10 -> \ apat1 ... apatn -> exp (lambda abstraction, n>=1)
| let decls in exp (let expression)
| if exp then exp else exp (conditional)
| case exp of { alts } (case expression)
| do { stmts } (do expression)
| fexp
fexp -> [fexp] aexp (function application)
aexp -> qvar (variable)
| gcon (general constructor)
| literal
| ( exp ) (parenthesized expression)
| ( exp1 , ... , expk ) (tuple, k>=2)
| [ exp1 , ... , expk ] (list, k>=1)
| [ exp1 [, exp2] .. [exp3] ] (arithmetic sequence)
| [ exp | qual1 , ... , qualn ] (list comprehension, n>=1)
| ( expi+1 qop(a,i) ) (left section)
| ( lexpi qop(l,i) ) (left section)
| ( qop(a,i)<-> expi+1 ) (right section)
| ( qop(r,i)<-> rexpi ) (right section)
| qcon { fbind1 , ... , fbindn } (labeled construction, n>=0)
| aexp<qcon> { fbind1 , ... , fbindn } (labeled update, n >= 1)

中置演算子を含くむ式は演算子の結合性 (4.4.2 節を見よ)により曖昧性がとりのぞか れる。同じ優先レベルの演算子が括弧なしで連続するときには、構文エラー を避けるためには、そのどちらの演算子も左もしくは右結合性をもたなけれ ばならない。括弧のない式 "x qop(a,i) y qop(b,j) z" では i=j で、 a=b=l または a=b=r ではなければ、"x qop(a,i) y" のまわりか、"y qop(b,j) z" のまわりに括弧が必要である。

符号反転演算子は Haskell では唯一の前置演算子で、プレリュード内で中 置の - 演算子と同じ優先レベルをもつものとして定義されている。 (4.4.2 節, 図 4.1 を参照せよ)

この文法はλ抽象、let式、条件式の拡張については曖昧である。この曖昧 さは各構成ができるだけ右へ拡張されるというメタ規則により解決される。

構文解析の例を以下にしめす。

これは このように構文解析される
f x + g y (f x) + (g y)
- f x + y (- (f x)) + y
let { ... } in x + y let { ... } in (x + y)
z + let { ... } in x + y z + (let { ... } in (x + y))
f x y :: Int (f x y) :: Int
\ x -> a+b :: Int \ x -> ((a+b) :: Int)

構文解析に関するノート let/lambda メタルールにある結合性の 相互関連は構文解析が難しい。例えば、式

  let x = True in x == x == True

は、次のような意味にはならない。

  let x = True in (x == x == True)

なぜなら、(==) は結合性をもたない演算子であるから、この式は 以下のように構文解析されなければならないからだ。

  (let x = True in (x == x)) == True

しかしながら、実装では、結合性を扱うためにうまく構文解析後のパスをう まく使うことができる。プログラマは let/lmabda メタルールの結合性(の欠 如)の相互関係を含むような構成を避けたほうが良い。

明解であることを旨とし、この節の以下の部分では式の構文を優先レベル なしでしめすこととする。

3.1  エラー

式の評価中のエラー(_|_ と表示する)は、停止しないことと Haskell のプログラムには、区別できない。 Haskell は遅延評価の言語であるから、すべての Haskell の型は _|_ を含む。すなわち、すべての型の値は、必要があれば、結果がエ ラーになる計算に束縛されうる。評価時のエラーは、ただちにプログラムは 停止させ、ユーザが補足することはできない。プレリュードでは、このよう なエラーを直接引き起こすための関数が 2 つ用意されている。

error     :: String -> a
undefined :: a

error の呼び出しはプログラムの実行を停止させ、オペレーティン グシステムに適切なエラー表示を返す。この関数は、同時に文字列をなんら かのシステムに依存した方法で画面に表示する。undefined が使わ れた場合のエラーメッセージはコンパイラが生成する。

3.2  変数、構成子、演算子、リテラル

aexp -> qvar (variable)
| gcon (general constructor)
| literal
gcon -> ()
| []
| (,{,})
| qcon
var -> varid | ( varsym ) (variable)
qvar -> qvarid | ( qvarsym ) (qualified variable)
con -> conid | ( consym ) (constructor)
qcon -> qconid | ( gconsym ) (qualified constructor)
varop -> varsym | `varid ` (variable operator)
qvarop -> qvarsym | `qvarid ` (qualified variable operator)
conop -> consym | `conid ` (constructor operator)
qconop -> gconsym | `qconid ` (qualified constructor operator)
op -> varop | conop (operator)
qop -> qvarop | qconop (qualified operator)
gconsym -> : | qconsym

Haskell では中置記法をサポートする特別な構文が用意されている。 演算子は中置構文(3.4 節) で適用できる関数であり、また、セクション (3.5 節)を使って部分適用可能である。

演算子は、+$$ のような演算子シ ンボル、あるいは、`op` のように、通常の識別子をバックク オートでかこったもののどちらかである。たとえば、前置適用 op x y のように書くかわりに x `op` y のように中置適用に書くことも できる。もし、`op` に対して、結合性宣言がなければ、これは デフォルトで最も高い優先どと左結合性をもつ。 ( 4.4.2 節を見よ。)

その逆に、演算子シンボルは括弧でかこむことで通常の識別に変換するこ とができる。たとえば、(+) x yx + y と同等である。また foldr (*) 1 xsfoldr (\x y -> x*y) 1 xs と 同等である。

組み込み型のいくつかの構成子に対しては、命名に特別な構文を用いる。 これは、gcon および literal の生成ルールに現われる。こ れらについては 6.1 節で説明する。

整数リテラルは、Integer 型の対応する値への、関数 fromInteger の適用を表現している。同様に、浮動小数リテラルは fromRationalRational (すなわち、 Ratio Integer) 型の値への適用を表わす。

変換:

整数リテラル ifromInteger i と同等でる。ここでは fromIntegerNum クラスのメソッドである(6.4.1 節を見よ)。

小数リテラル fromRational (n Ratio.% d) と同等である。ここでは、 fromRationalFractional のメソッドであり、 Ratio.%Ratio ライブラリに定義されているように、 二つの整数から有理数を構築する。整数 ndn/d = f となるように選ばれる。

3.3  カリー化された適用とラムダ抽象

fexp -> [fexp] aexp (function application)
exp -> \ apat1 ... apatn -> exp (lambda abstraction, n>=1)

関数適用は、 e1e2 と書く。適用は左 結合性をもつので、(f x) y の括弧は省略することができ る。e1 はデータ構成子である可能性もあるので、 データ構成子の部分適用は許されている。

ラムダ抽象は \ p1 ... pn -> e と書く。ここで、piパターンである。 \x:xs->x のような式は構文としては正しくない。正しくは、 \(x:xs)->x と書く。

パターンの集合は線形でなければならない。すなわち、集合の中 で 2 回以上出現してはならない。

変換:

以下の同一性が保存される:
\ p1 ... pn -> e = \ x1 ... xn -> case (x1, ..., xn) of (p1, ..., pn) -> e
ここで、xi は新しい識別子である。

3.17.3 節で解説するが、この case 式とパターン照合のセマンティクスを組合せるこの変換は、もし、パター ン照合に失敗すると、_|_となる。

3.4  演算子適用

exp -> exp1 qop exp2
| - exp (prefix negation)
qop -> qvarop | qconop (qualified operator)

e1 qop e2 という 形式は二項演算子 qop の式 e1 および e2 への中置適用である。

特別な形式 -e は前置の符号判定演算子を表わす。この 演算子は Haskell における唯一の前置演算子であり、 negate (e)という意味の構文である。二項演算子 - はプレリュード中の - の定義への参照を必要としない。 モジュールシステムにより再束縛される。いっぽうで、単項演算子 - は常にプレリュード中で定義された negate 関数を参照する。 - 演算子の局所的な意味と単項の符号反転演算との間にはなんの結び つきもない。

前置の符号反転演算子はプレリュード中に定義されている中置演算子 - と同じ優先順位である (表 2 を見よ)。 e1-e2 は二項演算子 e1-e2 の中置適用として構文解析さ れるので、これを単項演算子として構文解析させるためには、 e1(-e2) と表記しなければならない。(-) は、他のすべ ての中置演算子と同様に、 (\ x y -> x-y) という意味の構文であり、 (\ x -> -x)ということではない。後者の意味 を用いるのなら negate を使わなければならない。

変換:

以下の同一性が保存される:
e1 op e2 = (op) e1 e2
-e = negate (e)

3.5  セクション

aexp -> ( expi+1 qop(a,i) ) (left section)
| ( lexpi qop(l,i) ) (left section)
| ( qop(a,i)<-> expi+1 ) (right section)
| ( qop(r,i)<-> rexpi ) (right section)

セクション( op e ) あるいは ( e op ) のように書く。ここで、op は 二項演算子であり、e は式である。セクションは二項演算子の部分適 用をあらわすのに便利な構文である。

セクションに適用される構文上の優先順位は以下の通りである。 (op e) は、 (x op e) が、(x op (e)) として構文解析されるとき、そのとき に限り、正しい。 (e op) についても同様である。 たとえば、 (*a+b) は構文上あやまりであるが、(+a*b) および (*(a+b)) は構文上正しい。(+) は左結合性をも つので、(a+b+) は構文的に正しいが、(+a+b) は正しく ない。後者は (+(a+b)) と書くことで正しい構文になる。

もうひとつ例をあげよう。次の式

  (let n = 10 in n +)

は、正しくない。それは、let/lambda メタルール (3 章)により、式

  (let n = 10 in n + x)

は、

  (let n = 10 in (n + x))

と構文解析され、

  ((let n = 10 in n) + x)

と構文解析されるわけではないからである。

- は文法上、特別扱いで、(- exp) はセクションではなく、前節で説明したように前置の符号反転演算子の適用 である。しかしながら、subtract 関数は、プレリュードでは (subtract exp) が上で許されていなかったセク ションの代りにつかえるように定義されている。式 (+ (- exp)) を同じ目的で使用できる。

変換:

以下の同一性が保存される
(op e) = \ x -> x op e
(e op) = \ x -> e op x
ここで、op は二項演算子、e は式、xe 中で自由変数ではない。

3.6  条件式

exp -> if exp1 then exp2 else exp3

条件式if e1 then e2 else e3 という形式をもち、 e1 の値が True のとき、 e2 の値を返し、e1False のとき e3 を返す。それ以外 の場合には _|_ を返す。

変換:

以下の同一性が保存される
if e1 then e2 else e3 = case e1 of { True -> e2 ; False -> e3 }
ここで、True および False はプレリュードで定義さ れている Bool 型の無引数データ構成子である。 e1 の型は Bool でなければならず、 e2 および e3 は同 じ型で、当該の条件式全体の型でなければならない。

3.7  リスト

exp -> exp1 qop exp2
aexp -> [ exp1 , ... , expk ] (k>=1)
| gcon
gcon -> []
| qcon
qcon -> ( gconsym )
qop -> qconop
qconop -> gconsym
gconsym -> :

リスト[e1,..., ek] のように書く。ここで k>=1 である。リスト構成子は : であり、空リストは [] と書きあらわす。リスト上の標準的な演算はプレリュードであ たえられている(6.1.3 節をみよ。 また、8 章の特に、 8.1 節を見よ)。

変換:

次の同一性が保存される:
[e1, ..., ek] = e1 : (e2 : ( ... (ek : [])))
ここで、 : and [] プレリュードに定義されているよ うに、リストの構成子である。 (6.1.3 節を見よ。) e1 から、ek の型 はすべて同じ(これを t としよう)でなければならない。そして式 全体の型は [t] である。 (4.1.2 節を見よ。)

構成子の「:」は、[] も同様で、リストの構築専用に 予約されている。これはこの言語の構文の一部と考えられ、隠蔽や再定義は できない。: は右結合性をもつ演算子で、その優先レベルは 5 (4.4.2) 節を見よ)である。

3.8  タプル

aexp -> ( exp1 , ... , expk ) (k>=2)
| qcon
qcon -> (,{,})

タプル(e1,..., ek) と書き、任意の長さ k>=2 をとりうる。n-タプルの構成子は (,...,) と書 き表わす。ここで、コンマは n-1 個である。したがって、 (a,b,c) および (,,) a b c は同じ値を あらわす。タプル上の標準演算はプレリュードで定義されている (6.1.4 節および 8 章を見よ)。

変換:

k>=2 に対して (e1, ..., ek) は、プレリュードの定義により k-タプルのインスタンスであり、 変換を必要としない。もし、t1 から tk までが、それぞれ e1 から ek までの型 をもつならタプル全体の型は (t1, ..., tk) である(4.1.2 節を見よ)。

3.9  ユニット式と括弧でくくられた式

aexp -> gcon
| ( exp )
gcon -> ()

(e) という形式は単なる 括弧でくくられた式であり、e と同等である。 ユニット式 ()() 型 (4.1.2 節を見よ)の、 _|_ 以外の唯一の要素である。これは無引数タプルとみなすことができる。 (6.1.5 節を見よ。)

変換:

(e)e と同等である。

3.10  数列

aexp -> [ exp1 [, exp2] .. [exp3] ]

数列[e1, e2 ..e3] は型 t の値のリストを表す。ここで、各 ei の型は t であり、tEnum クラスのインスタンスである。

変換:

数列は以下の同一性を満す。
e1.. ] = enumFrom e1
e1,e2.. ] = enumFromThen e1 e2
e1..e3 ] = enumFromTo e1 e3
e1,e2..e3 ] = enumFromThenTo e1 e2 e3
ここで enumFromenumFromThenenumFromTo および、enumFromThenToEnum クラスのクラスメソッドであり、プレリュードで定義され ている(図 6.1 を見よ)。

これ故、数列のセマンティクスは型 t の対するインスタンス宣言 に全面的に依存する。 どの Prelude 型が Enum クラスのインスタンスであるかの 詳細は 図 6.3.4 節を見よ。

3.11  リスト内包表記

aexp -> [ exp | qual1 , ... , qualn ] (リスト内包表記, n>=1)
qual -> pat <- exp (生成器)
| let decls (局所宣言)
| exp

リストの内包表記[ e | q1, ..., qn ],n>=1, という形式を 持つ。ここでは、qi という限定子は以下のいずれか である。

このような、リストの内包表記は、限定子リストのなかの入れ子になった、 深さ優先評価によって作られた一連の環境のなかで e を評価するこ とで作りだされた要素のリストを返す。変数の束縛は通常のパターン照合の ルール(3.17 節を見よ)にした がって起こり、もし、照合が失敗すればそのリストの要素は単にスキップさ れる。したがって、

[ x |  xs   <- [ [(1,2),(3,4)], [(5,4),(3,2)] ], 
      (3,x) <- xs ]

[4,2] というリストになる。もし、限定子がガードなら、先行する パターン照合が成功するためには、そのガードが評価されて True にならねばならない。通常とおなじようにリストの内包表記中の束縛は外側 の束縛を覆い隠す。たとえば、

[ x | x <- x, x <- x ] = [ z | y <- x, z <- y]

変換:

リストの内包表記は以下の同一性を満す。これはカーネルへの変換時にも用 いられる。
e | True ] = [e]
e | q ] = [ e | q, True ]
e | b, Q ] = if b then e | Q ] else []
e | p <- l, Q ] = let ok p = e | Q ]
    ok _ = []
in concatMap ok l
e | let decls, Q ] = let decls in e | Q ]
ここで e のとりうる範囲は式、p のとりうる範囲はパター ン、l のとりうる範囲はリスト値の式、b のとりうる範囲 はブール式、decls は宣言リスト、q は限定子の、 Q は限定子のリストである。 ok は新しい変数である。関数 concatMap および 真理値 True はプレリュードで定義されている。

リスト内包表記の変換に示されているように let によって束 縛された変数は完全な多相型になる。一方で、<- で定義された 変数はラムダ束縛であるので単相型になる。 (4.5.4 節を見よ。)

3.12  let 式

exp -> let decls in exp

Let 式let { d1 ; ... ; dn } in e という一般形式を持ち、入れ子でレキシカルスコープで相互再帰的な宣言リスト (このような let は他の言語ではよく letrec と呼ばれる) を持つ。宣言のスコープ(有効範囲)は、式 e および宣言の右辺である。 宣言については 4 章を参照のこと。 パターン束縛は遅延照合となる。すなわち暗黙の ~ がパターンを反駁 不可にする。たとえば、

let (x,y) = undefined in 
e

x あるいは y が評価されるまでは実行時エラーを起こさ ない。

変換:

let { d1 ; ... ; dn } in e0 の動的セマンティクスは次の変換により捕捉される。すべての型シグネチャー を除いた後、各宣言 dipi = ei という形式の等式に変換される。ここで、 pi および ei はパ ターンおよび再帰的に 4.4.3 節の変換を使う式であ る。一旦変換が行われると以下の同等性が保持さる。これはカーネルへの 変換として用いられる。
内で自由変数としてあらわれない。
let {p1=e1 ... pn=en} in e0 = let (~p1, ... ,~pn) = (e1, ... ,en) in e0
let p = e1  in  e0 = case e1 of ~p -> e0
ここでは 内の変数が e1
let p = e1  in  e0 = let p = fix ( \ ~p -> e1) in e0
ここで fix は最小不動点演算子である。反駁不可パターン ~p の使い方に注意すること。この変換は静的セマンティ クスを保存しない、なぜなら、case の使用が束縛変数の完全な 多相型付けをはばんでいるからである。let 式での束縛の静的セ マンティクスは 4.4.3 節で 解説する。

3.13  case 式

exp -> case exp of { alts }
alts -> alt1 ; ... ; altn (n>=1)
alt -> pat -> exp [where decls]
| pat gdpat [where decls]
| (empty alternative)
gdpat -> gd -> exp [ gdpat ]
gd -> | exp0

case 式は一般的には以下の形式を持つ。

case e of { p1 match1 ; ... ; pn matchn }

ここで、各 matchi は以下の一般的形式をもつ。

| gi1 -> ei1
...
| gimi -> eimi
where declsi

( gd に対する構文ルールでは、"|" は終端シンボルであり、 選択肢のためのメタシンボルではないことに注意 ) 各選択肢 pi matchi はパター ン部 pi および照合部 matchi から構成される。各照合部はさらに ガード部 gij とボディ部 eij (expressions) の対のならびから構成される。 同様に、当該ガード部および当該選択肢の式を 有効範囲とする付加的な束縛 (declsi) が続く。 以下の形式

pat -> exp where decls

は次のものの省略形として扱う。

pat | True -> exp
where decls

case 式は少くとも 1 つの選択肢を持たねばならない。また、各選択肢は 少くとも 1 つのボディ部をもたなければならない。各ボディ部は同じ型 でなければならず、この型が当該 case 式全体の型である。

case 式は、式 e を個別の選択肢にパターン照合することによっ て評価される。選択肢は上から下へ順に試される。e が選択肢最初に 成功した照合により対応するボディ部の評価がおこなわれる。 このとき、当該の case 式の環境はその選択肢を照合するときに作られた束 縛と、その選択肢に対応する declsi とによって 拡張される。もし、照合がすべて失敗すると結果は _|_ になる。パ ターン照合については 3.17 節 で解説し、3.17.3 節で、case 式 の形式的セマンティクスをについても解説する。

構文解析に関するノート 次の式

  case x of { (a,_) | let b = not a in b :: Bool -> a }

は正しく構文解析できる巧妙な例である。曖昧でない単一の構文解析、すなわち、

  case x of { (a,_) | (let b = not a in b :: Bool) -> a }

を持つ。 しかしながら、Bool -> a 句は型の構文としては 正当であり、先読みが制限された構文解析器では誤ってこの選択にたどりつ くことがありえる。それゆえ、このプログラム拒否れる。それ故、プログラ マは、型シグネチャーでおわるガードは避け べきである。実際それが、 gdexp ではなく exp0 を を含む理由である

3.14   do 式

exp -> do { stmts } (do expression)
stmts -> stmt1 ... stmtn exp [;] (n>=0)
stmt -> exp ;
| pat <- exp ;
| let decls ;
| ; (empty statement)
do 式はモナドプログラミングの習慣的な構文である。次のような式

  putStr "x: "    >> 
  getLine         >>= \l ->
  return (words l)

を以下のような古典的な書き方にすることができる。

  do putStr "x: "
     l <- getLine
     return (words l)

となる。

変換:

do 式は以下の同一性を満し、これらは、空の stmtsを除去した後、 カーネルへの変換に用いることができる。
do {e} = e
do {e;stmts} = e >> do {stmts}
do {p <- estmts} = let ok p = do {stmts}
    ok _ = fail "..."
  in e >>= ok
do {let declsstmts} = let decls in do {stmts}
"..." はコンパイラのエラーメッセージをあらわしている。これ は fail に渡される。パターン照合失敗の個所を示すようにする ことが多い。関数 >>>>=、および、 failMonad クラスの演算でありプレリュードで定義さ れている。また、ok は初出の識別子である。

do の変換で示されているように、let で束縛された変 数は完全な多相型である。一方、<- で定義されている変数は ラムダ束縛であるので、単相型である。

3.15  フィールドラベルをもつデータ型

データ型宣言は、その型の構成要素のいくつかあるいはすべてにフィール ドラベルを定義することができる( 4.2.1 節を見よ)。これらのフィールドラベルは、データ型全体の構造 とは独立に、構築、選択、更新することが可能である。

同じスコープで、異るデータ型が同じフィールド名を共有することはでき ない。ひとつのフィールドラベルはひとつの構成子中に高々1度しか使えない。 しかしながら、同じフィールド名はひとつ のデータ型の中で、すべての構築 子のなかで、同じ型付けのフィールドに対して、一度以上使うことができる。 最後の要点を説明すると、

  data S = S1 { x :: Int } | S2 { x :: Int }   -- OK
  data T = T1 { y :: Int } | T2 { y :: Bool }  -- NG

ここで、S は正しいが、T は正しくない、それは y は後者では型付けの整合性がとれていないからである。

3.15.1  フィールドの選択

aexp -> qvar

フィールド名は選択子関数として使用する。変数として使用するときは、 フィールド名はオブジェクトからそのフィールドを取り出す関数として働く。 選択子はトップレベルの束縛なので局所変数によって覆い隠される。しかし、 同じ名前の他のトップレベルの束縛とは衝突することは出来ない。局所変数 による隠蔽は選択子関数にのみ効果があり、レコード構築 (3.15.2 節)や更新 (3.15.3 節)では、フィールド ドラベルを普通の変数と混同してはならない。

変換:

フィールドラベル f は以下のような定義の選択子関数を導入する。
f x = case x of { C1 p11 ...p1k  ->  e1 ; ... ; Cn pn1 ...pnk  ->  en }
ここで C1 ...Cnf というラベルをもつフィールド含むすべての構成子で、 pijfCij 番目のフィールドのラベルであ るときはy、さもなければ _、そして、 eiCi のいくつ かのフィールドのラベルが f のとき y となり、さもなけ れば、undefined となる。

3.15.2  フィールドラベルを用いた構築

aexp -> qcon { fbind1 , ... , fbindn } (labeled construction, n>=0)
fbind -> qvar = exp

ラベルの付いたフィールドをもつ構成子は構成要素が位置ではなく名前で 指定される値を構成するのに使用できる。宣言リストで用いるブレースとは 違い、これらはレイアウトの支配を受けない。{ および } は明示的に書かねばならない。(これはフィールドパターンおよ びフィールド更新のときにも真である。) フィールド名を用いた構築は以下 の制約にしたがう:

F {}F がデータコンストラクタであるな ら、Fレコード構文 (この場合、F は正格フィールドをもたない -- 上の三番目 の項目をみよ)で定義されいるかどうかにかかわらずF _|_1 ... _|_n を表わす。 なお、nF の引数の数である。

変換:

束縛 f = v において、フィールド fv のラベルである。
C { bs } = C (pickC1 bs undefined) ...(pickCk bs undefined)
ここで kC の引数の数。

補助関数 pickCi bs d は以下のように定義される。

もし、構成子 Ci番目の構成要素のフィールド名が f であり、f=v が束縛リスト bs 中に出現するな ら、pickCi bs dv である。さもなければ、 pickCi bs d はデ フォルト値 d である。

3.15.3  フィールドラベルを用いた更新

aexp -> aexp<qcon> { fbind1 , ... , fbindn } (labeled update, n>=1)

フィールドラベルを持つ、データ型に属する値は非破壊的に更新すること ができる。これにより、指定したフィールドの値がそれまでの値と置き換え た新しい値がつくられる。更新は次のような方法に限られる。

変換:

前述の pick を用いて、
e { bs } = case e of
        C1 v1 ... vk1 -> C1 (pickC11 bs v1) ... (pickC1k1 bs vk1)
             ...
        Cj v1 ... vkj -> Cj (pickCj1 bs v1) ... (pickCjkj bs vkj)
        _ -> error "Update error"
ここで、 {C1,...,Cj}b に現れるすべてのラベルを含む構成子の集合であり、 kiCiの引数の数 である。

以下はラベル付きフィールドを使った例である。

data T    = C1 {f1,f2 :: Int}
          | C2 {f1 :: Int,
                f3,f4 :: Char}

変換
C1 {f1 = 3} C1 3 undefined
C2 {f1 = 1, f4 = 'A', f3 = 'B'} C2 1 'B' 'A'
x {f1 = 1} case x of C1 _ f2    -> C1 1 f2
          C2 _ f3 f4 -> C2 1 f3 f4

フィールド f1 は T の二つの構成子に共通している。この例は、フィール ドラベル記法による構成子を使った式を同等のフィールドラベルのない構築 子を使った式へ変換する。もし、更新のなかで使用するフィールド名の集合、 たとえば、x {f2 = 1, f3 = 'x'} を定義する単一構成子がなければ、コンパイル時エラーとなる。

3.16  式の型シグネチャ

exp -> exp :: [context =>] type

式の型シグネチャe :: t という形 式をもつ。ここで、e は式、t は型 (4.1.2節)である。式の型シグネチャは 式を明示的に型付けするのに用い、多重定義 (4.3.4 節を見よ)によっておこる型の 曖昧さを解決するために用いることができる。当該の式の値はまさに exp の値である。一般の型シグネチャ (4.4.1 節を見よ)と同様に、式 exp から導出される主型よりもより特殊な型を宣言することができる。 しかし、主型より一般的なものや主型と比較できないような型を指定すると エラーとなる。

変換:

e :: t = let { v :: t v = e } in v

3.17  パターン照合

パターンは、ラムダ抽象、関数定義、パターン束縛、リスト内包 表記、do 式、case 式に出現する。しかしながら、これらのうち、最初の5つ は最終的には、case 式に変換される。それゆえ、パターン照合のセマンティ クスは case 式対するもので十分である。

3.17.1  パターン

パターンの構文は以下のとおり:

pat -> var + integer (successor pattern)
| pat0
pati -> pati+1 [qconop(n,i) pati+1]
| lpati
| rpati
lpati -> (lpati | pati+1) qconop(l,i) pati+1
lpat6 -> - (integer | float) (negative literal)
rpati -> pati+1 qconop(r,i) (rpati | pati+1)
pat10 -> apat
| gcon apat1 ... apatk (arity gcon = k, k>=1)
apat -> var [@ apat] (as pattern)
| gcon (arity gcon = 0)
| qcon { fpat1 , ... , fpatk } (labeled pattern, k>=0)
| literal
| _ (wildcard)
| ( pat ) (parenthesized pattern)
| ( pat1 , ... , patk ) (tuple pattern, k>=2)
| [ pat1 , ... , patk ] (list pattern, k>=1)
| ~ apat (irrefutable pattern)
fpat -> qvar = pat

構成子の引数の数は、それに対応するサブパターンの数と一致しなければ ならない。部分適用された構成子に対して一致することはできない。

すべてのパターンは線型でなければならない。すなわち、一つの 変数は 2 度以上出現してはならない。例えば:
  f (x,x) = x -- ILLEGAL; x が 2度 パターンのなかで使われている

var@pat という形式のパターンはアズパター ンとよばれ、varpat でマッチした値に対する名前 として使用することができる。例えば、

case e of { xs@(x:rest) -> if x==0 then rest else xs }

は以下と同等である。

let { xs = e } in
  case xs of { (x:rest) -> if x==0 then rest else xs }

_ という形式のパターンはワイルドカードであり、パ ターンの一部が右辺で参照されないような場合に便利である。その場所を示 す以外では使われない認識子のようなものである。たとえば、

case e of { [x,_,_]  ->  if x==0 then True else False }

は以下と同等である。

case e of { [x,y,z]  ->  if x==0 then True else False }

3.17.2  パターン照合の非形式的セマンティクス

パターンは値に対して照合される。パターンを照合しようする場合、つぎ の 3 つのうちの一つが起こる。失敗成功して当該パター ンの各変数の束縛を返す、発散(すなわち、_|_ が返る)。 パターン照合は以下のルールに従い、左から右へ、外から内へと進む。

  1. v に対するパターン var の照合は常に成功し、 varv に束縛する。

  2. v に対するパターン ~apat の照合は 常に成功する。vapat への照合が成功すれば、 apat 中の自由変数は対応する値に束縛される。もし、vapat への照合が失敗するか、発散すれば、apat 中の自由 変数は _|_ に束縛される。(束縛は評価を強制しない)。

    操作的にいえば、パターン ~apat 上の照合は、パターン apat 中の変数のひとつが使用されるまでは起こらないということ である。使用の時点でパターン全体がその値に照合され、もし、照合が失 敗あるいは発散すれば、計算全体が失敗あるいは発散する。

  3. 値のワイルドカードパターン _ への照合は常に成功するが、 束縛は起こらない。

  4. ある値へのパターン con pat の照合は、connewtype で定義されたものであれば、その値が、

    すなわち、newtype に対応する構成子は値の型の変更をのみ提供 する。

  5. condata により定義された構成子でるとすると、 パターン con pat1...patn のある 値への照合は、その値に依存する:

  6. ラベル付フィールドをもちいた構成子に対する照合は、フィールドが フィールドリストで名前付けられた順番に照合されるということを除けば、 通常の構成子パターンの照合と同じである。リストアップされているすべ てのフィールドはその構成子によって宣言されていなければならない。フィー ルドは 2度以上名付けられてはいけない。パターンによって名付けられて いないフィールドは( _ と照合され)無視される。

  7. 数値、文字あるいは文字列リテラルのパターン k の値 v への照合は、v == k であれば成功する。ここで、 == はそのパターンの型で多重定義されているものとする。もしこ のテストが発散すれば照合は発散する。

    数値リテラルの解釈は 3.2 節 で解説したとおりである。すなわち、多重定義された fromInteger あるいは fromRationalInteger 型あるいは Rational 型のリテラル (resp) に 適用して、適切な型に変換する。

  8. パターン n+k (ここで n は変数、 k は正の整数リテラル) の値 v への照合は、x >= k であるときに成功し、結果として、nx - k に束縛する。また、それ以外の場合には照 合は失敗する。さらに関数 >= および - は多重定義 される。これは、当該パターンの型に依存する。もし、比較が発散すれば、 照合は発散する。

    リテラル k の解釈は整数のリテラルのみが許されることを除けば、 数値リテラルの解釈と同じである。

  9. アズパターン var @ apat の値 v への照合は、varv への束縛をともなった上で、 apatv への照合の結果となる。apatv への照合が失敗または発散した場合、全体のマッチングも同様に 失敗または発散する。

自明な静的型制約(たとえば、文字の真理値への照合はエラーになるなど) 以外に、次のような静的なクラス制約が保存される。

多くのひとが n+k パターンは使うべきではないと 感じている。これらのパターンは Haskell の将来のバージョンでは変更され るか取り除かれる可能性がある。

2種類のパターンを分けたほうよいばあいある。反駁不可能パターン の照合は非正格である。当該パターンは、対象となる値が _|_ であっても照合する。反駁可能パターン の照合は 正格である。対象になる値が _|_ である場合には、その照合は発散 する。反駁不可能パターンは次のようなものである。変数、ワイルドカード、 Nnewtype で定義された構成子であり、apat が 反駁不可能(4.2.3 節をみよ) である場合の N patapat が反駁不可能であるか または(apat が反駁不可能であるかどうかにかかわらず) ~apat という形式をもつもの。

いくつか例をあげよう

  1. パターン ['a','b']['x',_|_] に照合しようとすれば、'a''x' への照合に失敗し、結果は失敗照合となる。しかし、 パターン ['a','b'][_|_,'x'] に 照合しようとすれば、'a'_|_ への照合が、全体の照合 を発散させる。

  2. 以下の例は、反駁可能照合 vs. 反駁不可能照合の例示である。

    (\ ~(x,y) -> 0) 
    _|_    =>    0
    (\  (x,y) -> 0) 
    _|_    =>    _|_



    (\ ~[x] -> 0) []    
    =>    0
    (\ ~[x] -> x) []    
    =>    _|_



    (\ ~[x,~(a,b)] -> x) [(0,1),
    _|_]    =>    (0,1)
    (\ ~[x, (a,b)] -> x) [(0,1),
    _|_]    =>    _|_



    (\  (x:xs) -> x:x:xs) 
    _|_   =>   _|_
    (\ ~(x:xs) -> x:x:xs) 
    _|_   =>   _|_:_|_:_|_

  3. 以下のような宣言を考える。

      newtype N = N Bool
      data    D = D !Bool

    次の例は、datanewtype の型宣言によるパターン照 合の違いを示したものである。

    (\  (N True) -> True) 
    _|_     =>    _|_
    (\  (D True) -> True) 
    _|_     =>    _|_
    (\ ~(D True) -> True) 
    _|_     =>    True

    その他の例は 4.2.3 節にある。

case 式のトップレベルでのパターンと、関数あるはパターン束縛でのトッ プレベルパターンは 0 ないしそれ以上の対応するガード部を持つ ことができる。ガード部は、すべての引数のパターン照合が成功したあとに のみ評価される真理値式であり、パターン照合全体が成功したときには必ず 真となる。ガード部の環境は、case 式選択肢、関数定義、あるいはそれがむ すびつけているパターン束縛と同じ環境である。

ガード部のセマンティクスは明らかに関数あるいは case 式の正格性とい うような性質に影響をあたえる。特に反駁不可能パターン以外ではガード部 があれば評価される。たとえば、

f :: (Int,Int,Int) -> [Int] -> Int
f ~(x,y,z) [a] | (a == y) = 1

では ay の両方がガード部の == に よって評価される。

3.17.3  パターン照合の形式的セマンティクス

case 式以外のすべてのパターン照合構成のセマンティクスは、 それら構成に case 式を関連づける同等性を与えることで定義する。 case 式そのもののセマンティクスは、図3--4 中の一連の同等性を与えるこ とにより定義される。どの実装もこの同等性を保持するようにしなければな らない。効率のよくないコード生成につながるので、この同等性は直接用い ることが期待されているわけではない。

(a) case e of { alts } = (\v -> case v of { alts }) e
v は新しい変数
(b) case v of { p1 match1;  ... ; pn matchn }
=  case v of { p1 match1 ;
                _  -> ... case v of {
                           pn matchn ;
                           _  -> error "No match" }...}
  各 matchi は以下の形式をもつ。
  | gi,1  -> ei,1 ; ... ; | gi,mi -> ei,mi where { declsi }
(c) case v of { p | g1 -> e1 ; ...
             | gn -> en where { decls }
            _     -> e' }
= case e' of
  {y ->  (y は新しい変数)
   case v of {
         p -> let { decls } in
                if g1 then e1 ... else if gn then en else y ;
         _ -> y }}
(d) case v of { ~p -> e; _ -> e' }
= (\x1 ... xn -> e ) (case v of { p-> x1 }) ... (case v of { p -> xn})
x1, ..., xn はすべて p 内の変数
(e) case v of { x@p -> e; _ -> e' }
=  case v of { p -> ( \ x -> e ) v ; _ -> e' }
(f) case v of { _ -> e; _ -> e' } = e

図 3

case 式のセマンティクス(その1)

(g) case v of { K p1 ...pn -> e; _ -> e' }
= case v of {
     K x1 ...xn -> case x1 of {
                    p1 -> ... case xn of { pn -> e ; _ -> e' } ...
                    _  -> e' }
     _ -> e' }
p1, ..., pn のうち、少くともひとつは変 数ではなく、x1, ..., xn は新しい変数
(h) case v of { k -> e; _ -> e' } = if (v==k) then e else e'
k は数値リテラル、文字リテラル、あるいは、文字列リテラル
(i) case v of { x -> e; _ -> e' } = case v of { x -> e }
(j) case v of { x -> e } = ( \ x -> e ) v
(k) case N v of { N p -> e; _ -> e' }
= case v of { p -> e; _ -> e' }
N は newtype の構成子
(l) case _|_ of { N p -> e; _ -> e' } = case _|_ of { p -> e }
N は newtype の構成子
(m) case  v  of {  K  { f1  =  p1  ,  f2  =  p2  ,  ... } ->  e ; _ ->  e'  }
=  case e' of {
   y ->
    case  v  of { 
      K  {  f1  =  p1  } ->
            case  v  of { K  { f2  =  p2  ,  ...  } ->  e ; _ ->  y  };
            _ ->  y  }}
f1, f2, ... は構成子 K のフィールド。 y は新しい変数
(n) case  v  of {  K  { f  =  p } ->  e ; _ ->  e'  }
= case  v  of {
     K p1 ... pn  ->  e ; _ ->  e'  }
pi は、もし、K の i 番目の構成要素のラベルが f で あるならば、p、そうでなければ、_
(o) case  v  of {  K  {} ->  e ; _ ->  e'  }
= case  v  of {
     K _ ... _ ->  e ; _ ->  e'  }
(p) case (K' e1 ... em) of { K x1 ... xn -> e; _ -> e' } = e'
K と K' はそれぞれ n 引数と m 引数の別の data 構成子
(q) case (K e1 ... en) of { K x1 ... xn -> e; _ -> e' }
= (\x1 ... xn -> ee1 ... en
K は n 引数の data 構成子

(r)

case _|_ of { K x1 ... xn -> e; _ -> e' } = _|_
K は n 引数の data 構成子

(s)

case v of { x+k -> e; _ -> e' }
= if v >= k then (\x -> e) (v-k) else e'
k は数値リテラル

図 4

case 式のセマンティクス(その2)

3.1-- 3.2 では ee' および ei は式、 g および gi は真理値式、 p および pi はパターン vx および xi は変数、 K および K' は代数的データ型 (data) 構成子(タプル コンストラクタを含む)、Nnewtype 構成子、k は 文字、文字列、あるいは数値のリテラルである。

規則 (b) は、ガード部を実際に含むかどうかにかかわらず、一般のソース 言語の case 式に対応する。もしガード部が書かれていなければ、 Truematchi 形式のガード部 gi,j を置き換える。そのあとに続く、同等性は、 case 式の結果をより単純な、簡単な形式にするものである。

4 の規則 (h) は多重定 義された == を含む。多重定義された定数に対するパターン照合の 意味を定義するのはこの規則である。

これらの同等性すべて静的セマンティクスを保存するものである。規則 (d)、(e)、(j)、(q) そして (s) は let ではなくλを用いている。 このことは、case によって束縛される変数は、単相的に型付けされ ることを示している(4.1.4 節を 見よ)


The Haskell 98 Report
top | back | next | contents | function index
December 2002