その他の便利な機能

Leanにはプログラムをより簡潔にする便利な機能がたくさんあります。

自動的な暗黙引数

Leanで多相関数を書く場合、基本的にすべての暗黙引数を列挙する必要はありません。その代わりに、単にそれらを参照するだけでよいのです。Leanが引数に現れなかった変数の型を決定できる場合、それらは自動的に暗黙の引数として挿入されます。例えば、先ほどの length の定義について:

def length {α : Type} (xs : List α) : Nat :=
  match xs with
  | [] => 0
  | y :: ys => Nat.succ (length ys)

{α : Type} を書かずに定義できます:

def length (xs : List α) : Nat :=
  match xs with
  | [] => 0
  | y :: ys => Nat.succ (length ys)

これにより、多くの暗黙引数をとるような高度に多相的な定義を大幅に簡略化することができます。

パターンマッチによる定義

def で関数を定義するとき、引数に名前をつけてもすぐにパターンマッチに適用してしまうケースはよくあります。例えば、length では引数 xsmatch でのみ使用されます。このような状況では、引数に名前を付けずに match 式のケースを直接書くことができます。

最初のステップは、引数の型をコロンの右側に移動させることです。例えば length の型は List α → Nat となります。次に、:= をパターンマッチの各ケースで置き換えます:

def length : List α → Nat
  | [] => 0
  | y :: ys => Nat.succ (length ys)

この構文は複数の引数を取る関数を定義するのにも使えます。この場合、パターンはカンマで区切られます。例えば、drop は整数値 \( n \) とリストを受け取り、先頭から \( n \) 個の要素を取り除いたリストを返します。

def drop : Nat → List α → List α
  | Nat.zero, xs => xs
  | _, [] => []
  | Nat.succ n, x :: xs => drop n xs

名前の付いた引数とパターンを同じ定義で使用することもできます。例えば、デフォルト値とオプション値を受け取り、オプション値が none の場合はデフォルト値を返す関数を書くことができます:

def fromOption (default : α) : Option α → α
  | none => default
  | some x => x

この関数は標準ライブラリに Option.getD という名前で定義されており、ドット記法で呼び出すことができます:

#eval (some "salmonberry").getD ""
"salmonberry"
#eval none.getD ""
""

ローカル定義

計算の途中のステップに名前を付けると便利なことが多いものです。多くの場合、こうした中間値はそれだけで有用な概念を表しており、明示的に名前をつけることでプログラムを読みやすくすることができます。また中間値が複数回使われる場合もあります。ほかの多くの言語と同じように、Leanにて同じコードを2回書くと2回計算されることになる一方で、結果を変数に保存すると計算結果が保存されて再利用されることになります。

例えば、unzip はペアからなるリストをリストのペアに変換する関数です。ペアのリストが空の場合、unzip の結果は空のリストのペアになります。ペアのリストの先頭にペアがある場合、そのペアの2つのフィールドが残りのリストを unzip した結果に追加されます。この unzip の定義を完全に起こすと以下のようになります:

def unzip : List (α × β) → List α × List β
  | [] => ([], [])
  | (x, y) :: xys =>
    (x :: (unzip xys).fst, y :: (unzip xys).snd)

残念ながら、このコードには問題があります: これは必要以上に遅いのです。ペアのリストの各要素が2回の再帰呼び出しを行うため、この関数には指数関数的な時間がかかります。しかし、どちらの再帰呼び出しも結果は同じであるため、再帰呼び出しを2回行う必要はありません。

Leanでは再帰呼び出しの結果を let を使って名前を付け、保存することができます。let によるローカル定義は def によるトップレベル定義と似ています:この構文ではローカル定義する名前、必要であれば引数、型シグネチャ、そして := に続く本体を取ります。ローカル定義の後、この定義が使用可能な式( let 式の 本体 (body)と呼ばれます)は次の行からかつ let キーワードが定義された列と同じかそれよりも後ろから始まる必要があります。例えば letunzip で次のように使用することができます:

def unzip : List (α × β) → List α × List β
  | [] => ([], [])
  | (x, y) :: xys =>
    let unzipped : List α × List β := unzip xys
    (x :: unzipped.fst, y :: unzipped.snd)

let を1行で使用するには、ローカル定義と本体をセミコロンで区切ります。

let を使用したローカル定義では、1つのパターンでデータ型のすべてのケースにマッチする場合であればパターンマッチを使うこともできます。unzip の場合、再帰呼び出しの結果はペアになります。ペアは単一のコンストラクタしか持たないので、unzipped という名前をペアのパターンに置き換えることができます:

def unzip : List (α × β) → List α × List β
  | [] => ([], [])
  | (x, y) :: xys =>
    let (xs, ys) : List α × List β := unzip xys
    (x :: xs, y :: ys)

let を使ったパターンをうまく使えば、手作業でアクセサの呼び出しを書くよりもコードを読みやすくすることができます。

letdef の最大の違いは再帰的な let 定義は let rec と書いて明示的に示さなければならない点です。例えば、リストを反転させる方法の1つに、以下の定義のような再帰的な補助関数を用いるものがあります:

def reverse (xs : List α) : List α :=
  let rec helper : List α → List α → List α
    | [], soFar => soFar
    | y :: ys, soFar => helper ys (y :: soFar)
  helper xs []

補助関数は入力リストを下向きに進み、そのたびに1つの要素を soFar に移動していきます。入力リストの最後に到達すると、soFar には入力されたリストの逆順が格納されます。

型推論

多くの場合、Leanは式の型を自動的に決定することができます。このような場合、( def による)トップレベルの定義と( let による)ローカル定義のどちらでも明示的な型の省略ができます。例えば、再帰的に呼び出される unzip には注釈は不要です:

def unzip : List (α × β) → List α × List β
  | [] => ([], [])
  | (x, y) :: xys =>
    let unzipped := unzip xys
    (x :: unzipped.fst, y :: unzipped.snd)

経験則として、(文字列や数値のような)リテラル値の型を省略することは通常うまくいきますが、Leanはリテラルの数値に対して意図した型よりも特殊な型を選ぶことがあります。Leanは関数適用の型を決定することができます、というのもすでに引数の型と戻り値の型を知っているからです。関数の定義で戻り値の型を省略することはよくありますが、引数には通常注釈が必要です。先ほどの unzipped のような関数ではない定義においては、その本体が型注釈を必要とせず、かつ定義の本体が関数適用である場合は型注釈を必要としません。

明示的な match 式を使用する場合、unzip の戻り値の型を省略することができます:

def unzip (pairs : List (α × β)) :=
  match pairs with
  | [] => ([], [])
  | (x, y) :: xys =>
    let unzipped := unzip xys
    (x :: unzipped.fst, y :: unzipped.snd)

一般論として、型注釈は少なすぎるよりは多すぎる方が良いです。まず、明示的な型は読み手にコードの前提を伝えます。たとえLeanによって型が決定できるものでも、Leanに型情報をいちいち問い合わせることなくコードを読むことができます。第二に、明示的な型はエラーの特定に役立ちます。プログラムが型について明示的であればあるほど、エラーメッセージはより有益なものになります。これはLeanに限らず非常に表現力豊かな型システムを持つ言語では特に重要です。第三に、型が明示されていることによって、そもそもプログラムを書くのが簡単になります。型は仕様であり、コンパイラのフィードバックは仕様を満たすプログラムを書くのに役立つツールになります。最後に、Leanの型推論はベストエフォートなシステムです。Leanの型システムは非常に表現力が豊かであるため、すべての式に対して「最良」な型や最も一般的な型を見つけることができません。つまり、型が得られたとしても、それが与えられたアプリケーションにとって「正しい」型であるという保証はないということです。例えば、14Nat にも Int にもなり得ます:

#check 14
14 : Nat
#check (14 : Int)
14 : Int

型注釈が欠落すると、エラーメッセージがわかりづらくなります。unzip の定義からすべての型を省略すると:

def unzip pairs :=
  match pairs with
  | [] => ([], [])
  | (x, y) :: xys =>
    let unzipped := unzip xys
    (x :: unzipped.fst, y :: unzipped.snd)

match 式について以下のようなメッセージが出力されます:

invalid match-expression, pattern contains metavariables
  []

これは match が受け取った検査対象の値の型を知る必要がありますが、その型が利用できなかったためです。「metavariable(メタ変数)」とはプログラムの未知の部分のことで、エラーメッセージでは ?m.XYZ と書かれます。これについては 「多相性」節 で解説しています。このプログラムでは、引数の型注釈が必要です。

非常に単純なプログラムであっても、型注釈を必要とするものがあります。例えば、恒等関数は渡された引数をそのまま返すだけの関数です。引数と型注釈を使うと次のようになります:

def id (x : α) : α := x

Leanはこの戻り値の型を自力で決定できます:

def id (x : α) := x

ここで引数の型を削除すると、以下のエラーを引き起こします:

def id x := x
failed to infer binder type

一般的に、「failed to infer(推論に失敗)」のようなメッセージやメタ変数に言及したメッセージは型注釈が足りていないというサインであることが多いです。特にLeanを学習している段階においては、ほとんどの型を明示的に提供することが有用です。

一斉パターンマッチ

パターンマッチング式は、パターンマッチング定義と同様に、一度に複数の値にマッチすることができます。検査する式とマッチするパターンは、定義に使われる構文と同じようにカンマで区切って記述します。以下は一斉パターンマッチを使用するバージョンの drop です:

def drop (n : Nat) (xs : List α) : List α :=
  match n, xs with
  | Nat.zero, ys => ys
  | _, [] => []
  | Nat.succ n , y :: ys => drop n ys

整数のパターンマッチ

「データ型・パターン・再帰」の節において、even は次のように定義されていました:

def even (n : Nat) : Bool :=
  match n with
  | Nat.zero => true
  | Nat.succ k => not (even k)

リストのパターンマッチを List.consList.nil を使うよりも読みやすくするための特別な構文があるように、自然数もリテラル数値と + を使ってマッチさせることができます。例えば、even は以下のように定義することもできます:

def even : Nat → Bool
  | 0 => true
  | n + 1 => not (even n)

この記法では、+ パターンの引数は異なる役割を果たします。裏側では、左の引数(上の n )は何かしらの数値の Nat.succ パターンの引数になり、右の引数(上の 1 )はパターンにラップする Nat.succ の数を決定します。さて、次に halve 関数の明示的なパターンでは Nat を2で割って余りを落とします:

def halve : Nat → Nat
  | Nat.zero => 0
  | Nat.succ Nat.zero => 0
  | Nat.succ (Nat.succ n) => halve n + 1

このパターンマッチは数値リテラルと + で置き換えることができます:

def halve : Nat → Nat
  | 0 => 0
  | 1 => 0
  | n + 2 => halve n + 1

この裏側では、上記二つの定義はどちらも完全に等価です。ここで覚えておいてほしいこととして、halve n + 1(halve n) + 1 と等価であり、halve (n + 1) とは等価ではありません。

この構文を使う場合、+ の第二引数は常に Nat のリテラルでなければなりません。また加算は可換であるにもかかわらず、パターン内の引数を反転させると次のようなエラーになることがあります:

def halve : Nat → Nat
  | 0 => 0
  | 1 => 0
  | 2 + n => halve n + 1
invalid patterns, `n` is an explicit pattern variable, but it only occurs in positions that are inaccessible to pattern matching
  .(Nat.add 2 n)

この制限により、Leanはパターン内で + 表記を使用する場合はすべて、その基礎となる Nat.succ 表記に変換することができます。

無名関数

Leanの関数はトップレベルで定義する必要はありません。式としての関数は fun 構文で生成されます。関数式はキーワード fun で始まり、1つ以上の引数が続き、その後に => を挟んで返される式が続きます。例えば、ある数値に1を足す関数は次のように書くことができます:

#check fun x => x + 1
fun x => x + 1 : Nat → Nat

型注釈は def と同じように括弧とコロンを使って記述します:

#check fun (x : Int) => x + 1
fun x => x + 1 : Int → Int

同じように、暗黙引数は波括弧を使って記述します:

#check fun {α : Type} (x : α) => x
fun {α} x => x : {α : Type} → α → α

この無名関数式のスタイルはしばしば ラムダ式 (lambda expression)と呼ばれます、というのもLeanではキーワード fun に対応するプログラミング言語の数学的な記述で使われる典型的な表記法はギリシャ文字のλ(ラムダ)だからです。Leanでも fun の代わりに λ を使うことができますが、fun と書く方が一般的です。

無名関数は def で使われる複数パターンのスタイルもサポートしています。例えば、ある自然数に対して、もし存在するならそのひとつ前を返す関数は以下のように書けます:

#check fun
  | 0 => none
  | n + 1 => some n
fun x =>
  match x with
  | 0 => none
  | Nat.succ n => some n : Nat → Option Nat

この関数に対してLeanから実際に付けられる情報には、名前付き引数と match 式があることに注意してください。Leanの便利な構文の短縮形の多くは、裏ではより単純な構文に拡張されており、抽象化が漏れることもあります。

def を使った定義で引数を取るものは、関数式に置き換えることができます。例えば、引数を2倍にする関数は以下のように書けます:

def double : Nat → Nat := fun
  | 0 => 0
  | k + 1 => double k + 2

無名関数が、fun x => x + 1 のように非常に単純な場合、関数を作成する構文はかなり冗長になります。この例では、6つの非空白文字が関数の導入に使用され、本体は3つの非空白文字で構成されています。このような単純なケースのために、Leanは省略記法を用意しています。括弧で囲まれた式の中で、中黒点 · が引数を表し、括弧の中の式が関数の本体になります。この関数は (· + 1) と書くこともできます。

中黒点は常に最も近い括弧から関数を生成します。例えば、(· + 5, 3) は数字のペアを返す関数で、((· + 5), 3) は関数と数字のペアです。複数の点が使用された場合、それらは左から右の順に複数の引数になります:

(· , ·) 1 2
===>
(1, ·) 2
===>
(1, 2)

無名関数は deflet で定義された関数とまったく同じように適用することができます。コマンド #eval (fun x => x + x) 5 の結果は以下のようになります:

10

一方で #eval (· * 2) 5 の結果は以下のようになります:

10

名前空間

Leanの各名前は名前の集まりである 名前空間 (namespace)の中に存在します。名前は . を使って名前空間に配置されるので、List.mapList 名前空間の map という名前になります。名前空間が異なる名前同士は、たとえ同じ名前であっても衝突することはありません。つまり、List.mapArray.map は異なる名前です。名前空間は入れ子にすることができるので、Project.Frontend.User.loginTime は入れ子の名前空間 Project.Frontend.User 内の loginTime という名前になります。

名前は名前空間内で直接定義することができます。例えば、double という名前は Nat 名前空間で定義することができます:

def Nat.double (x : Nat) : Nat := x + x

Nat は型の名前でもあるので、ドット記法を使えば Nat 型の式で Nat.double を呼び出すことができる:

#eval (4 : Nat).double
8

名前空間内で直接名前を定義するだけでなく、namespace コマンドと end コマンドを使用して一連の宣言を名前空間内に配置することができます。例えば、以下では名前空間 NewNamespacetriplequadruple を定義しています:

namespace NewNamespace
def triple (x : Nat) : Nat := 3 * x
def quadruple (x : Nat) : Nat := 2 * x + 2 * x
end NewNamespace

これらを参照するには、それらの名前に接頭辞 NewNamespace. を付けます:

#check NewNamespace.triple
NewNamespace.triple (x : Nat) : Nat
#check NewNamespace.quadruple
NewNamespace.quadruple (x : Nat) : Nat

名前空間は 開く (open)ことができます。これによって名前空間内の名前を明示的に指定することなく使うことができるようになります。式の前に open MyNamespace in と書くと、その式で MyNamespace の内容が使用できるようになります。以下の例で、timesTwelveNewNamespace を開いた後に quadrupletriple の両方を使用しています:

def timesTwelve (x : Nat) :=
  open NewNamespace in
  quadruple (triple x)

名前空間はコマンドの前に開くこともできます。これにより単一の式内ではなく、コマンドのすべての部分で名前空間の内容を参照できるようになります。これを行うには、コマンドの前に open ... in を置きます:

open NewNamespace in
#check quadruple
NewNamespace.quadruple (x : Nat) : Nat

関数のシグネチャは、名前の完全な名前空間を示します。名前空間はさらに、ファイルの残りの部分 すべて のコマンドのために開くこともできます。これを行うには open のトップレベルの使用法から in を省略するだけです。

if let

直和型を持つ値を計算する場合、複数のコンストラクタの中のどれか一つだけが注目されることがよくあります。例えば、Markdownのインライン要素のサブセットを表す以下の型を考えます:

inductive Inline : Type where
  | lineBreak
  | string : String → Inline
  | emph : Inline → Inline
  | strong : Inline → Inline

ここで文字列要素を認識してその内容を抽出する関数を書くことができます:

def Inline.string? (inline : Inline) : Option String :=
  match inline with
  | Inline.string s => some s
  | _ => none

この関数の本体部分は、iflet と一緒に使うことでも記述できます:

def Inline.string? (inline : Inline) : Option String :=
  if let Inline.string s := inline then
    some s
  else none

これはパターンマッチの let 構文によく似ています。違いは、else の場合にフォールバックするようになるため、直和型で使用できる点です。文脈によっては、match の代わりに if let を使うとコードが読みやすくなることがあります。

構造体の位置引数

「構造体」の節 では構造体の構築の仕方について2つの方法を紹介しました:

  1. Point.mk 1 2 のようにコンストラクタを直接呼ぶ。
  1. { x := 1, y := 2 } のように括弧記法を使う。

文脈によっては、コンストラクタに直接名前を付けずに、名前ではなく位置で引数を渡すと便利な場合があります。例えば、様々な似たような構造体タイプを定義することで、ドメイン概念を分離しておくことができますが、コードを読む際にはそれらを実質的にタプルとして扱う方が自然です。このような文脈では、引数を角括弧 で囲むことができます。Point⟨1, 2⟩ と書くことができます。ここで注意点です!この括弧は小なり記号 < と大なり記号 > のように見えますが、これらの括弧は違うものです。それぞれ \<\> で入力できます。

名前付きコンストラクタ引数の波括弧表記と同様に、この位置指定構文は、型注釈やプログラム内の他の型情報から、Leanが構造体の型を決定できるコンテキストでのみ使用できます。例えば、#eval ⟨1, 2⟩ は以下のエラーを返します:

invalid constructor ⟨...⟩, expected type must be an inductive type 
  ?m.34991

エラーのメタ変数は、利用可能な型情報が無いためです。例えば、#eval (⟨1, 2⟩ : Point) のような注釈を追加することで問題は解決します:

{ x := 1.000000, y := 2.000000 }

文字列への内挿

Leanでは、文字列の先頭に s! を付けると 内挿 が発動し、文字列内の波括弧に含まれる式がその値に置き換えられます。これはPythonの f 文字列や、C#の $ 接頭辞付き文字列に似ています。例えば、

#eval s!"three fives is {NewNamespace.triple 5}"

は以下を出力します

"three fives is 15"

すべての式を文字列に内挿できるわけではありません。例えば、関数を内挿しようとするとエラーになります。

#check s!"three fives is {NewNamespace.triple}"

上記は以下を出力します

failed to synthesize instance
  ToString (Nat → Nat)

これは、関数を文字列に変換する標準的な方法がないからです。Leanコンパイラはさまざまな型の値を文字列に変換する方法を記述したテーブルを保持しており、failed to synthesize instance というメッセージはLeanコンパイラがこのテーブルの中から指定された型の要素を見つけられなかったことを意味します。これは「構造体」の節 で説明した deriving Repr 構文と同じ言語機能を使用しています。