Loading [MathJax]/jax/output/CommonHTML/jax.js

SML#プロジェクト

プログラミング言語SML#解説 4.0.0版
III 参照マニュアル

Chapter 20 パターンとパターンマッチング

値束縛宣言（valBind）(23.1)の束縛対象および 関数宣言（funDecl）(23.2)， case式 (19.18)， fn式 (19.19)， handle式 (19.14) の引数には，パターンを記述する． 変数はパターンの特殊な場合である．

パターンは，値が持つべき構造を記述する． 記述されたパターンは，対応する値とマッチングが試みられ，マッチす れば，パターンに含まれる変数が，その現れる位置に対応する値に束縛される． パターンマッチングは，各パターンのスコープにある式を評価のた めの束縛環境にパターンに含まれる変数の束縛環境を追加する効果を持つ． 従って，各パターンは，静的な評価の場合，追加すべき型環境を，実行 時の動的な評価の場合，型環境に対応した値の環境を生成する．

⟨pat⟩構文は以下の文法で与えられる．

  • •

    パターン（トップレベル）

    ⟨pat⟩ ::= ⟨atpat⟩
     | (op)? ⟨longVid⟩ ⟨atpat⟩ データ構造
     | ⟨pat⟩ ⟨vid⟩ ⟨pat⟩ データ構造（演算子表現）
     | ⟨pat⟩ : ⟨ty⟩ 型制約パターン
     | ⟨vid⟩ (: ⟨ty⟩)? as ⟨pat⟩ 多層パターン
  • •

    原子パターン

    ⟨atpat⟩ ::= ⟨scon⟩ 定数
     | _ 匿名パターン
     | ⟨vid⟩ 変数及びコンストラクタ
     | ⟨longVid⟩ コンストラクタ
     | {(⟨patrow⟩)? } レコードパターン
     | () unit 型定数
     | (⟨pat1⟩,⋯,⟨patn⟩) 組 (n≥2)
     | [⟨pat1⟩,⋯,⟨patn⟩] リスト (n≥0)
     | (⟨pat⟩)
    ⟨patrow⟩ ::= ... 匿名フィールド
     | ⟨lab⟩ = ⟨pat⟩ (, ⟨patrow⟩)? レコードフィールド
     | vid(:⟨ty⟩)? (as ⟨pat⟩)? (,⟨patrow⟩)? 変数兼ラベル

以下，各パターン⟨pat⟩について，その型⟨ty⟩と 生成される型環境Γおよびマッチする値を定義する． 実行時の動的な評価時に生成される環境は，生成される型環境に対応す るマッチした値の束縛環境である．

定数パターン:⟨scon⟩

19.2で定義された定数式同一であり，対応する型を持ち，空 の型環境∅を生成する． 同一の定数値にマッチする．

匿名パターン:_

文脈に従って決まる任意の型を持ち，空の型環境∅を生成する． パターンの型を持つ任意の値にマッチする．

識別子パターン:⟨vid⟩

この識別子名が，このパターンが現れる位置をスコープとして含むコン ストラクタとして定義されていれば，そのコンストラクタの型を持ち，空の型環 境を生成する． そのコンストラクタにマッチする．

識別子が定義されていないか，または，変数属性を持つ名前として定義 されていれば，この名前は文脈によって定まる任意の型⟨ty⟩を持ち， 型環境{⟨vid⟩:⟨ty⟩}を生成する． 型⟨ty⟩を持つ任意の値にマッチする． このパターンは，パターンを含む構文が定めるスコープ規則に従い，名 前⟨vid⟩が再定義される．

以下に簡単な例を示す．

SML# 4.0.0 (2021-04-06) for x86_64-pc-linux-gnu with LLVM 11.1.0
# val A = 1
val A = 1 : int
# fn A => 1;
val it = fn : [’a. ’a -> int]
# datatype foo = A;
datatype foo = A
# fn A => 1;
val it = fn : foo -> int
# datatype foo = A of int;
datatype foo = x of int
# fn A => 1;
(interactive):12.3-12.3 Error:
    (type inference 039) data constructor A used without argument in pattern

long識別子パターン:⟨longVid⟩

このlong識別子名が，このパターンが現れる位置をスコープとして含む 引数を持たないコンストラクタ⟨vid⟩として定義されていれば， 空の型環境が生成されれ，コンストラクタ⟨vid⟩にマッチする． 現在の環境にlong識別子がコンストラクタとして定義されていないか， または，引数を持つコンストラクタとして定義されていれば，エラーとなる． 以下に簡単な例を示す．

# structure A = struct datatype foo = A | B of int val C = 1 end;
structure A =
  struct
    datatype foo = A | B of int
    val C = 1 : int
  end
# val f = fn A.A => 1;
val f = fn : A.foo -> int
# val g = fn A.B => 1;
(interactive):3.11-3.13 Error:
  (type inference 046) data constructor A.B used without argument in pattern
# val h = fn A.C => 1;
(interactive):4.11-4.13 Error: (name evaluation "020") unbound constructor: A.C

A.Bは引数を持つコンストラクタであり，A.Cは変数であるため， 関数宣言gとhはエラーとなる．

レコードパターン:⟨{(⟨patrow⟩)? }⟩

レコードフィールドパターン⟨patrow⟩が指定されない {}の形のパターンの場合，空のレコード{}にマッチする． 変数の型環境は生成されない．

レコードフィールドパターン⟨patrow⟩が指定されている場合， そのフィールド型を ⟨lab1⟩:⟨ty1⟩,…, ⟨labn⟩:⟨tyn⟩， 生成される変数の型環境をΓとす る． レコードフィールドパターン⟨patrow⟩の形に応じて以下の2通 りの場合がある．

  1. 1.

    匿名フィールド...を含まない固定レコードパターンの場合． フィールド型からなる単相レコード型 {⟨lab1⟩:⟨ty1⟩,…, ⟨labn⟩:⟨tyn⟩} を持ち，型環境Γを生成する．

    このパターンは，レコードフィールドパターン⟨patrow⟩にマッ チするレコードフィールドを含む上記の型のレコードにマッチする．

  2. 2.

    多相レコードパターン． レコードフィールドパターン⟨patrow⟩が，匿名フィールド ...を含む場合． ⟨patrow⟩のフィルド型をレコードカインドとしてもつ多相レコード型 ’a#{⟨lab1⟩:⟨ty1⟩,…, ⟨labn⟩:⟨tyn⟩} を持ち，レコードフィールドパターン⟨patrow⟩が生成する変数束縛を生 成する． この多相型は，文脈の型制約により，種々の多相レコード型または単相 レコード型にインスタンス化されうる．

    このパターンは，レコードフィールドパターン⟨patrow⟩にマッ チするレコードフィールドを含む上記の型のレコードにマッチする．

レコードフィールドパターン:⟨patrow⟩

  • •

    匿名フィールドパターン：...． 指定されたフィールド集合が，レコードの一部であることの指定である．

  • •

    フィールドパターン：⟨lab⟩ = ⟨pat⟩ (, ⟨patrow⟩)?． (, ⟨patrow⟩)?のフィールド型を ⟨lab1⟩:⟨ty1⟩,…, ⟨labn⟩:⟨tyn⟩， 型環境をΓ， パターン⟨pat⟩の型を⟨ty⟩，生成する型環境をΓ0とする．

    ラベル⟨lab⟩が ⟨lab1⟩,…,⟨labn⟩とすべて異なる場合， フィールド型 ⟨lab⟩:⟨ty⟩,⟨lab1⟩:⟨ty1⟩,…, ⟨labn⟩:⟨tyn⟩， を持ち，型環境Γ0∪Γが生成される． ラベル⟨lab⟩が ⟨lab1⟩,…,⟨labn⟩の何れかと一致する場合は型エラーである．

  • •

    変数兼ラベルパターン： vid(:⟨ty⟩)? (as ⟨pat⟩)?  (, ⟨patrow⟩)?．

    以下のフィールドパターンに変換された後評価される．

    vid = vid(:⟨ty⟩)? (as ⟨pat⟩)?  (, ⟨patrow⟩)?．

    生成される型環境，マッチする値は，対応するレコードパターンの場合と同一である． 以下に簡単な例を示す．

# val f = fn {x:int as 1, y} => x + y;
(interactive):33.8-33.34 Warning: match nonexhaustive
  {x = x as 1, y = y} => ...
val f = fn : {x: int, y: int} -> int
# val g = fn {x = x:int as 1, y = y} => x + y;
(interactive):34.8-34.37 Warning: match nonexhaustive
  {x = x as 1, y = y} => ...
val g = fn : {x: int, y: int} -> int
# f {x = 1, y = 2};
val it = 3 : int
# g {x = 1, y = 2};
val it = 3 : int

組パターン:(⟨pat1⟩,⋯,⟨patn⟩)

レコードパターン

{1 = ⟨pat1⟩, ⋯, n = ⟨patn⟩}

に変換され，評価される． 生成される型環境，マッチする値は，対応するレコードパターンの場合と同一である． 以下に簡単な例を示す．

# val f = fn (x,y) => 2 * x + y;
val f = fn : int * int -> int
# val g = fn {1=x, 2=y} => 2 * x + y;
val g = fn : int * int -> int
# f 1=1, 2=2;
val it = 4 : int
# g (1,2);
val it = 4 : int

リストパターン:[⟨pat1⟩,⋯,⟨patn⟩]

ネストしたリストデータ構造パターン

⟨pat1⟩ :: ⋯ :: ⟨patn⟩ :: nil

に変換され，評価される． 生成される型環境，マッチする値は，対応するコンストラクタアプリケー ションパターンの場合と同一である． 以下に簡単な例を示す．

# val f = fn [x,y] => 2 * x + y;
(interactive):24.8-24.26 Warning: match nonexhaustive
  :: (x, :: (y, nil )) => ...
val f = fn : int list -> int
# val g = fn (x::y::nil) => 2 * x + y;
(interactive):25.8-25.32 Warning: match nonexhaustive
  :: (x, :: (y, nil )) => ...
val g = fn : int list -> int
# f (1::2::nil);
val it = 4 : int
# g [1,2];
val it = 4 : int

データ構造パターン:(op)? ⟨longVid⟩ ⟨atpat⟩

⟨longVid⟩が型⟨ty1⟩ -> ⟨ty2⟩を持 つコンストラクタCに束縛されている時，型⟨ty2⟩を持ち，⟨atpat⟩が生成する型環境を生成する． このパターンは，⟨atpat⟩のマッチするデータvを部分構造としてもつデータ構造C(v)にマッチする．

演算子表現のデータ構造パターン ⟨pat1⟩ ⟨vid⟩ ⟨pat2⟩は， op ⟨vid⟩(⟨pat1⟩,⟨pat2⟩)に変換された後評価される． その型と生成される型環境，マッチする動的値は，変換後のパターンと同一である．

型制約パターン: ⟨pat⟩:⟨ty⟩

パターン⟨pat⟩が型⟨ty1⟩と型環境Γ0を持ちかつ ⟨ty1⟩と⟨ty⟩が型代入Sのもとで単一化できる場合， 型S(⟨ty⟩)を持ち，型環境S(Γ0)をもつ． 型制約の下で，パターン⟨pat⟩にマッチする値にマッチする．

多層パターン: ⟨vid⟩ (: ⟨ty⟩)? as ⟨pat⟩

パターン⟨pat⟩:⟨ty⟩が型⟨ty′⟩と型環境Γをもてば， このパターンは型⟨ty′⟩と型環境Γ∪{x:⟨ty′⟩}をもつ． このパターンは，⟨pat⟩:⟨ty⟩ にマッチする動的値にマッチする．