open netshop

Chapter 1. 関数の基本

Table of Contents

1. 関数の基礎
1.1. 関数の定義
1.2. 部分適用
1.3. 再帰関数
1.4. 識別子のスコープ
1.5. 練習問題
2. 関数の応用
2.1. ループと再帰関数
2.2. 末尾再帰
2.3. 関数式(ラムダ式)
2.4. カリー化
2.5. 演算子
2.6. 練習問題

1. 関数の基礎

関数型言語はその名のとおり関数の扱いに特化しています。たとえば、ローカル変数を宣言する感覚で簡単に関数を宣言したり、普通の数値や文字列と同じように変数に代入(識別子に束縛)したり、関数呼び出し時に引数として渡したりすることができます。このように関数型言語では数値などの値と関数は同列に扱うことができる、すなわち関数を第一級オブジェクトとして扱うことができます。

1.1. 関数の定義

関数とは、1つ以上の引数をとって1つの値を返すものです。まず一番単純な例として、数値を2乗する関数squareを定義して使ってみます。

> let square x = x * x;;
val square : int -> int

> square 3;;
val it : int = 9      

関数の定義方法については「基本的な型と演算」の章の最後で少し説明しましたが、関数の場合もintstringなどの値と同じようにlet束縛を使います。値への束縛と関数の束縛で異なる点は、識別子名のあとに引数が並んでいるかの違いです。上の例では、squareという関数名を表す識別子のあとに、xという引数を表す識別子が1つ並んでいます。関数型言語では、intstringなどの値と同様、関数もひとつの値であると考えます。そのため、F#では関数を表す値のことを関数値(function value)と呼びます。

=の右側には関数の本体を記述します。この関数の本体では、引数として定義した識別子(この場合はx)を使用することができます。ここではxの値を2乗しています。

2番目の入力では、実際にsquareに対して引数として3を与えて呼び出しています。F#では、関数に引数を渡して呼び出すことを、引数に関数を「適用する(apply)」といいます。ただし、「関数を適用する」という表現は冗長になる場合があるため、本サイトでは場合に応じて単に「関数を呼び出す」という表現をします。

Note

「適用する」という言葉の使い方に注意してください。これはもともとラムダ計算論の用語であり、「引数に関数を適用する」といういいかたが正しい表現です。「関数に引数を適用する」という言い方は、厳密には正しくありません。

ところが、日本語のさまざまな文献ではこれらの誤用が目立ちます。プログラミング言語の世界では、よく「関数に引数を与える」といった表現があるために、この誤用が広がったのではないかと個人的には思います。

次に戻り値の返し方ですが、C#では関数の戻り値は必ずreturn文によって返すのに対して、F#ではその方法が大きく異なります。前の章において、F#のプログラムは小さな式を組み合わせた、巨大な式のかたまりだと述べたことを思い出してください。F#の関数の本体も結局は1個の式に過ぎず、関数を実行することは、その巨大な1個の式が最終的にひとつの値になるまで評価を繰り返すのと同じことです。そして、関数の実行(評価)が完了すると、最終的に1つの値が出来上がります。F#では、この最終的に出来上がった1つの値が戻り値として返されることになります。

例として、上のsquareが評価されて1つの値になり、それが戻り値となる様子を詳しく見てみましょう。⇒という記号は式が1つずつ評価されることを意味しています。

square 3
⇒ 3 * 3
⇒ 3
// 1つの値になったのでここで評価完了

この例は非常に単純ですが、乗算が1回おこなわれて1つの値になり、最終的にそれが式全体の値として返されます。次に、もう少し複雑な例を示します。

"10 is " + if 10 % 2 = 0 then "even value" else "odd value"
⇒ "10 is " + if 0 = 0 then "even value" else "odd value" // 10 % 2を評価
⇒ "10 is " + if true then "even value" else "odd value" // 0 = 0を評価
⇒ "10 is " + "even value" // if true then "even value" else "odd value"を評価
⇒ "10 is even value" // "10 is " + "even value"を評価
// 1つの値になったのでここで評価完了

さらに別の例を見てみましょう。

if 3 > 0 then printf "positive value" else printf "negative value"
⇒ if true then printf "positive value" else printf "negative value" // 3 > 0を評価
⇒ printf "positive value" // if true then printf "positive value" else printf "negative value"を評価
⇒ () // printf "positive value"を評価(副作用として画面にpositive valueという文字列を出力)
// 1つの値になったのでここで評価完了

この例は、最終的にunit型の値()へ評価されますが、printf式の実行時に副作用として画面に文字列を出力しています。

では、次に関数の型名について説明します。squareの型名に注目してください。intからintへ右向きの矢印が書かれています。これは「intを受け取りintを返す関数」をあらわす型です。次に2つ以上の引数をとる関数の定義をみてみましょう。

> let plus2 x y = x + y;;
val plus2 : int -> int -> int

> plus2 2 3;;
val it : int = 5

> let plus3 x y z = x + y + z;;
val plus3 : int -> int -> int -> int

> plus3 2 3 4;;
val it : int = 9      

ここでは加算を行うplus2plus3という2つの関数を定義したあとに、それぞれを呼び出しています。plus2は2つの引数をとる関数で、plus3は3つの引数をとる関数です。これらの関数の型は、それぞれint -> int -> intint -> int -> int -> intです。以上の例からわかるように、F#におけるn引数の関数の型は第1引数の型 -> 第2引数の型 -> ... -> 第n引数の型 -> 戻り値の型と表現します。

さて、ここでちょっと問題です。以下の関数の型を答えてください。上のplus2とは何が違うのでしょうか。

let plus2_ (x,y) = x + y

答えを知るために、実際にこの関数を定義してみましょう。

> let plus2_ (x,y) = x + y;;
val plus2_ : int * int -> int

> plus2_ (2,3);;
val it : int = 5      

正解はint * int -> intです。

この違いを理解するために、plus2_plus2を比べて考えてみましょう。先ほど述べた第1引数の型 -> 第2引数の型 -> ... -> 第n引数の型 -> 戻り値の型という形に当てはめてみると、「第1引数の型がint * intで戻り値の型がintの関数」という意味になります。int * intとはint型とint型の2つ組のタプルでしたね。すなわち、この関数plus2_は1つの引数(int * intのタプル)をとって戻り値を返す関数です。

以上のように、plus2plus2_はそれぞれ関数の型は違いますが、両方とも同じように加算を行います。では、これらはどう使い分ければよいのでしょうか。それについては節で説明します。

Note

このような関数の型の表記方法は、見慣れないと非常に奇妙な記法に見えますが、もともとは数学における写像の記法に由来しています。数学では、関数はしばしば写像ともよばれます。関数と写像は同じものを表現する言葉ですが、写像という言葉はどちらかというと集合(定義域)から集合(値域)への対応づけに注目する場合によく用いられます。

集合Aから集合Bへの写像fは、数学的には以下のように表現します。

プログラミングにおける関数も、基本的にはこの考えに基づいています。たとえば、ある整数(uint16)を受け取って、それが素数ならtrueを返す関数is_primeを考えてみましょう。F#ではこの関数の型は以下のように表現します。

is_prime : uint16 -> bool

この表現を数学的にとらえると、「uint16という集合からboolという集合への写像is_prime」と解釈することができます。またuint16は0~65535という元をもつ集合で、booltruefalseという元をもつ集合です。このようにプログラミングにおける関数は、数学的にとらえてもきちんとした意味をもちます。

1.2. 部分適用

一般的な命令型言語における関数の呼び出しは、その関数の引数として必ず何かしらの値を渡さなくてはなりません。たとえば、2引数の関数ならば、必ず2つの実引数を渡さなければコンパイルエラーになります。

ところが、F#では引数を中途半端に与えることができます。たとえば、2引数の関数なのに先頭の第1引数しか与えないというようなことができます。実際に例を見てみましょう。

> let plus2 x y = x + y;; // plus2を定義する
val plus2 : int -> int -> int

> plus2 10;; // 第1引数のみ与える
val it : (int -> int) = <fun:clo@0>

> plus2;; // 何も与えない
val it : (int -> int -> int) = <fun:clo@20>

> plus2 10 5;; // 第1、第2引数の両方を与える(通常の呼び出し)
val it : int = 15     

非常に興味深い結果です。まず最初にplus2を定義すると、その応答としてplus2の(型推論された結果の)型が表示されます。この型はint -> int -> int、すなわちintを2引数受け取りintを返す関数を表します。

次に2番目の入力を見てください。ここでは、中途半端に第1引数のみを与えています。さらに3番目の入力では引数を一切与えていません。ここで、この2番目と3番目の入力に対する応答に注目してください。それぞれ、<fun:clo@0>、<fun::clo@20>といったものが返ってきています。これらはクロージャ(closure)と呼ばれるもので、部分適用した関数値に「それまでに与えられた引数の情報と、呼び出しに必要な残りの引数は何か」という情報が付加したものです。例えば<fun:clo@0>というクロージャは「これまでに第1引数に10が与えられたが、plus2の呼び出しにはintの引数がもう1つ必要である」といった情報を保持しており、<fun:clo@20>というクロージャは「これまでにまだ引数は1つも与えられておらず、plus2の呼び出しにはintの引数があと2つ必要である」といった情報を保持しています。

Note

クロージャは他の言語にも存在する一般的な概念で、ご存知の方もいると思います。しかしF#におけるクロージャは、一般的な概念よりも少し広い意味で使われています。詳しくは次の章で解説します。

さらに、これらのクロージャの型に注目してください。まず、<fun:clo@20>の型を見るとint -> intとなっています。<fun:clo@0>と比べると、ちょうど引数の数が1つ減っていることがわかります。このことからも予想できるとおり、<fun:clo@0>の第1引数を10に固定したバージョンが<fun:clo@20>です。

このように、F#では関数の引数を部分的に固定して新たな関数を作り出すことができます。このように引数を部分的に固定して新たな関数を作り出すことを、部分適用(partial application)と呼びます。

Note

クロージャは静的なものではなく、実行時に生成され、実行時に与えられた引数の情報をようにメモリに保持する動的なものです。

1.3. 再帰関数

関数定義の中で自分自身を呼び出す関数を再帰関数とよびます。F#で再帰関数を定義するには、recというキーワードを使う必要があります。再帰関数の例として、階乗(factorial)を計算する関数factを定義してみます。

> let rec fact n =
    if n <= 0 then 1
    else (fact (n-1) * n);;

val fact : int -> int

> fact 5;;
val it : int = 120

関数定義の最初の行ではrecが指定されており、最後の行ではfact自身を呼び出していることがわかります。再帰関数を定義する際にrecキーワードは必須です。recキーワードを指定しないバージョンのfact_errorを定義してみましょう。

> let fact_error n =
  if n <= 0 then 1
  else (fact_error (n-1) * n);;

    else (fact_error (n-1) * n);;
  --------^^^^^^^^^^^

stdin(12,9): error FS0039: The value or constructor 'fact_error' is not defined.

このようにエラーになりました。エラーの内容を読んでみると、fact_errorというものは定義されていないとのことです。recキーワードをつけた場合はきちんと認識されました。つまりrecをつけるつけないの違いは、関数定義内から自分自身の関数名が見えるか見えないかの違いです。

1.4. 識別子のスコープ

すべての識別子はスコープをもちます。スコープとは、その識別子にアクセスできる範囲のことで、C#などのほとんどの言語がもつ概念です。まずは復習も兼ねて、C#でのスコープについておさらいしてみましょう。

 1: class ValuePrinter
 2: {
 3:    public static void printXValue()
 4:    {
 5:        int X1 = 10;
 6:        int X2 = 15;
 7:        Console.WriteLine("X1={0}, X2={1}, Z1={2}, Z2={3}", X1, X2, Z1, Z2);
 8:    }
 9:
10:    public static void printYValue()
11:    {
12:        int Y1 = 10;
13:        int Y2 = 15;
14:        Console.WriteLine("Y1={0}, Y2={1}, Z1={2}, Z2={3}", Y1, Y2, Z1, Z2);
15:    }
16:
17:    private static int Z1 = 30;
18:    public static int Z2 = 40;
19: }

上のプログラムの中で現れる変数のスコープについて考えてみましょう。まず、printXValueメソッド内の変数に注目してください。この関数内ではX1X2という2つのローカル変数を定義しています。ローカル変数の場合は、定義された地点からアクセスが可能となります。たとえば、4行目の地点ではX1もX2も定義されていないので、どちらにもアクセスすることはできません。次の5行目では、X1にはアクセスできますが、X2はまだ定義されていなのでアクセスできません。そして、6行目でようやくX1X2にアクセスできるようになります。

ローカル変数は、ブロックの中で定義することができ、定義された直後からアクセス可能となります。そして、そのブロックが終了するとともにアクセス不可能となります。したがって、上のプログラムの場合、X1X2printXValueのブロックが終了するとともにアクセスできなくなります。したがって、printYValueの中からアクセスすることはできません。逆にprintXValueのブロック内では、Y1Y2はまだ定義すらされていないためアクセスすることはできません。以上をまとめると、ローカル変数のスコープは、定義された直後からブロックの終了位置までということがわかります。

次に、変数Z1Z2に注目してください。これはクラスValuePrinterのクラス変数(静的変数)です。クラス変数の場合はローカル変数とは異なり、同一クラス内ならばどこからでもアクセスでき、何行目で定義されているかは関係しません。したがって、Z1Z2の定義位置はprintXValueprintYValueよりも後の行であるにもかかわらず、printXValueからもprintYValueからもアクセスすることができます。以上をまとめると、クラス変数のスコープは、クラス全体ということがわかります。

さらに、Z1Z2はそれぞれアクセス修飾子が異なります。アクセス修飾子はクラスの外部からのアクセスの可否、つまりスコープを制御することができます。例えば、Z1privateが指定されているため、クラスの外部からアクセスすることはできませんが、Z2publicが指定されているため、クラスの外部から直接アクセスすることができます。すなわち、private属性のスコープはクラスの内部のみで、public属性のスコープはクラスの内部と外部の両方ということがわかります。

Note

スコープにもさまざまな種類が存在し、以上のようなC#のスコープの概念はレキシカルスコープ(lexical scope)と呼ばれます。

では、おさらいはここまでにして、ここからはF#の識別子とスコープの関係について説明します。まずは以下の単純なプログラムのスコープを詳しく観察してみましょう。

軽量構文では、改行やインデントが重要な意味を持ちます。let束縛の場合、値および関数の束縛が終了した次の行からスコープが始まります。たとえば上のプログラムの場合、aのスコープは2行目、bのスコープは3行目、plusのスコープは4行目から始まります。そして、これらのスコープはすべてトップレベルから始まっているため、スコープの終了位置はソースコードの終端になります。ちなみに、詳しくは「モジュール」の章で説明しますが、トップレベルにおけるlet束縛は静的メンバとして外部に公開されます。では、次に関数定義内に改行を含む例を見てみましょう。

このプログラムは、signという関数を定義してそれを呼び出しています。このsignの関数定義は、ソースコードの1行目から開始し、次のトップレベルの式が始まる直前の4行目で終了します。したがって、この場合のsignのスコープは5行目からソースコードの終端までになります。では、さらに別の例として、関数定義内にlet束縛が存在する例を見てみましょう。

このプログラムでは、distという関数の内部でlet束縛によりdxdyという2つの新たな識別子を導入しています。この2つのlet束縛は、トップレベルのインデント上で定義されてない、関数内だけの局所的な束縛になります。したがって、関数定義のブロックが終了する5行目以降では、これらの識別子にアクセスすることはできません。最後に再帰を含む例を見てみましょう。

このプログラムでは、再帰関数factを定義しています。再帰関数を定義するときは、recキーワードを指定する必要があります。このrecキーワードを指定すると、関数の識別子のスコープが、上の図のように関数定義内にまで広がります。もし、recキーワードを指定しないと、スコープは以下の図のようになり、factを再帰的に呼び出すことができないためにコンパイルエラーになります。

1.5. 練習問題

  1. 与えられた引数に対して1を加算する関数inc : int -> intと減算する関数dec : int -> intを定義してください。ただし、この節のはじめで定義したplus2を使い、部分適用を利用して定義してください。

  2. 排他的論理和を計算する関数xor : bool -> bool -> boolを定義してください。条件式やmatch式を使って定義してもかまいませんが、できれば論理積演算子&&と論理和演算子||と論理否定関数notのみを使って定義してください。(排他的論理和は、与えられた2つの値が両方ともtrueのとき、または両方ともfalseのときにfalseを返し、その他のときはtrueを返す論理演算です。)

  3. 再帰関数の説明で使ったfactを参考にして、1からnまでの整数の和を計算を行う関数sum : int -> intを再帰を使って定義してください。

2. 関数の応用

2.1. ループと再帰関数

一般的に、ループを行うにはループ変数が必要です。forループではループのたびに変数を書き換えて、ある値に達するまで処理を繰り返します。ところが関数型プログラミングのスタイルでは、基本的に一度定義した変数(識別子)は書き換えられません。そこで関数型言語では、ループ変数を使う代わりに再帰を使ってループを行います。再帰を使うループは、命令型言語のforループの考え方になれた方には非常に奇妙にうつるかもしれません。しかしこれは慣れの問題にすぎず、再帰を使うほうが簡潔に表現できる場合が多々あります。

Note

ループ変数を使うループと再帰を使うループは、一概にどちらが優れているというわけではありません。それぞれに適した使い方があります。

Note

(注)ここはちょっとマニアックなNoteです。理解できなければ適当に読み飛ばしてください。

先ほど、関数型プログラミングでは変数(識別子)の内容は書き換えられないといいましたが、実はF#では書き換え可能な変数を扱うこともできます。これについては命令型プログラミングの章で詳しく説明します。

ところが「純粋」関数型言語Haskellでは、識別子の内容は一切書き換えることができません。すべてが定数の世界で、関数は常に同じ値しか返すことができません。しかし現実世界では、時刻・ファイル・入出力など、時々刻々と変化する対象が数多くあるため、定数のみの世界ではそれらを扱うことはできません。そこでHaskellでは、IOモナド(IO Monad)というものを概念を導入することでそれらを扱います。

IOモナドの考え方はユニークで、入出力というものを非常に壮大なレベルでとらえます。その考え方は次のとおりです。まず、ある瞬間の世界の状態(この世に存在するあらゆる物質の位置やエネルギーの状態)のもとで、何らかの入出力(世界への干渉)を行うと、世界の状態はそれに応じて変化します。

そして、いちど入出力を行ってしまうと、前の世界と完全に同じ状態を再現することは2度とできません。この世は時々刻々と新しい状態に変化しており、過去のある瞬間とまったく同じ世界の状態は、未来永劫現れることはありません。すなわち、世界のある瞬間瞬間は、それぞれが唯一無二のものであると考えることができます。もし、ある瞬間が完全に復元できるならば、その時点での入力は常に同じになるはずです。

Haskellの中では、ファイル入出力やユーザーからの入力などのように、毎回違う結果が反映される可能性のある処理おこなう関数には、必ず「現在の世界の状態」を与える必要があります。このように世界の瞬間を扱うことで、時々刻々と変化する対象でも矛盾なく扱うことができます。たとえば、ネットワーク上からデータを読み込む関数get_data_from_networkがあるとすると、この関数は引数に現在のこの世の状態を受け取り、その状態のもとで入力が行われます。そして、その結果として、読み取ったデータと変化した世界の状態が生み出されます。

Haskellにはモナド(Monad)という情報隠蔽(information hiding)の枠組みがあり、これを使うと単調な繰り返しをきれいに隠蔽することができます。Haskellではこのモナドを利用して、変化する世界を裏側に隠しています。それがIOモナドなのです。

ここで勘違いしないでほしいのですが、モナドはこの世の状態や副作用をあらわすものではありません。モナド自体は、オブジェクト指向や構造化プログラミングなどのように単に余計なものを裏側に隠しながら一連の処理をきれい扱う、あくまで情報隠蔽のための仕組みです。Haskellでは、変化する世界をプログラマから隠蔽してしまう手段として、モナドを利用したに過ぎません。

モナドは非常に高度な抽象化能力を持つ仕組みで、関数型プログラミングではIOモナド以外にも数多くの応用例があります。実際、F#ではモナド的構文であるワークフローというものが活用されています。たとえば、後で説明するシーケンス式、非同期ワークフロー、構文解析などはすべてワークフローによって実現されています。

forループと再帰によるループを比較するために、階乗を計算する関数をそれぞれの方法で定義してみましょう。ただし、F#におけるforループの書き方についてはまだ触れていないので、ここではなじみのあるC#で表現します。

public static int fact(int n)
{
    int result = 1;
    for (int i = 1; i < n; i++)
        result *= i;
    return result;
}

public static int fact_rec(int n)
{
    if (n == 1)
        return 1;
    else
        return n * fact_rec(n - 1);
}

forループバージョンは「ある条件を満たすまで処理を繰り返す」というプログラムの内部処理を意識した関数となっています。しかし、それに対して再帰バージョンは漸化式による定義でより数学的な関数となっています。また、forループバージョンでは表現合計を記憶する変数とループ変数の宣言と初期化、停止条件、インクリメントなど、階乗の数学的に本質的でない要素がいくつか含まれていますが、再帰バージョンではforループに比べると非本質的な要素は省かれています。

このように、再帰を使う場合には漸化式的な表現をする必要があるため、forループから再帰に書き換える際には、発想の転換をする必要があります。この発想の転換は慣れないと混乱してしまいますが、いくつか考え方のコツを抑えればあまり難しいことではありません。

再帰を考えるための基本となるのは、高校数学で出てくる数学的帰納法です。といっても、とくに難しく考える必要はありません。ここでは数学的知識は必要ではないので安心してください。数学的帰納法で基本となるのは、base case、induction stepとよばれる2つの場合分けを考えることです。base caseとは再帰が停止するときに実行される式で、induction stepとは再帰のたびに実行される式です。

上記の例では、n == 1のときがbase caseで、それ以外のときがinduction stepです。base caseでは単に1を返し、induction stepでは現在のnの値とn-1までの階乗の値との積を返しています。再帰関数を定義するときは、このbase caseとinduction stepを意識するのがコツです。例としてツリーを探索するプログラムを以下に示します。

> type Tree = // ツリーをあらわすdiscriminated unionを定義
  | Node of Tree * Tree
  | Leaf of int;;
type Tree =
  | Node of Tree * Tree
  | Leaf of int

> let rec fold_tree t = // ツリーのすべての葉の値を合計する再帰関数
  match t with
  | Leaf x -> x                               // base case
  | Node (x,y) -> fold_tree x + fold_tree y;; // induction step
val fold_tree : Tree -> int

> fold_tree (Leaf 5);;
val it : int = 5

> fold_tree (Node (Leaf 1, Leaf 2));;
val it : int = 3

> fold_tree (Node (Node (Leaf 1, Node (Leaf 2, Leaf 3)), Leaf 4));;
val it : int = 10

このfold_tree関数もbase caseとinduction stepにより定義しています。induction stepでは自分の2つの子の合計を足すということを表現しており、base caseでは単に値を取り出すということを表現しています。

このように再帰関数は再帰的なデータ構造の探索に向いています。さらに、F#のmatch式とパターンマッチのおかげで非常にすっきりとした定義を書くことができます。fold_treeもたったの4行で定義できましたし、fact_recもC#よりもすっきりと記述することができます。

let rec fact_rec n =
  match n with
  | 1 -> 1 // base case
  | n -> n * fact_rec (n-1) // induction step

Note

近代的なC++プログラミングの世界は、関数型言語の考え方なしには成立しません。それは、C++におけるテンプレートメタプログラミング(Template Metaprogramming)というものが、まさに純粋関数型言語だからです。

C# 2.0ではジェネリックが導入されましたが、これはC++のテンプレートという機能がルーツとなっています。テンプレートもジェネリックと同じように、型名をいろいろ取り替えて、再利用性を高めるための仕組みです。ジェネリックに関する情報はコンパイル後にも残り、実行時にもその情報を保持しますが、テンプレートによって記述されたものは、すべてコンパイラによって処理され、実行時にはその情報はもちません。

テンプレートは、もともとは型名をいろいろ取り替える程度の仕組みに過ぎず、C++を作ったBjarne Stroustrupもそれを意図していました。ところが1994年、Erwin Unruhが驚くべきプログラムを書いて見せました。それは、テンプレートのみを使ってコンパイラに素数を計算させるプログラムでした。これは当時のC++プログラマを驚愕させ、C++を新たな世界へと導きました。

そして、当時は単なるコーディング上のハックに過ぎなかったこのプログラムが研究され、チューリング完全であることが示され、現在ではテンプレートメタプログラミングという名の立派な手法にまで確立されました。次世代のC++の標準ライブラリ候補が数多く入っているBoostライブラリは、この手法抜きには語れません。

テンプレートメタプログラミングの強力さは、Expression Templateの例Boost::Spiritの例を見てもらえればわかるはずです。このテクニックを学ぶには、書籍C++ Templatesが非常におすすめです。

2.2. 末尾再帰

ここまで見てきたように、再帰は高い表現力をもちます。しかし再帰を使う際には、実装上の都合から気をつけなければならないことがあります。これに気をつけないと、不必要にメモリを圧迫してしまったり、最悪の場合は実行時エラーが発生してプログラムが停止したりします。

このことを説明するために、F#の式が評価される様子を詳しく見てみましょう。

fact_rec 3
⇒ match 3 with | 1 -> 1 | n -> n * (fact_rec (n-1))
⇒ 3 * (fact_rec (3-1)) // induction stepの適用
⇒ 3 * (fact_rec 2)
⇒ 3 * (match 2 with | 1 -> 1 | n -> n * fact_rec (n-1))
⇒ 3 * (2 * fact_rec (2-1)) // induction stepの適用
⇒ 3 * (2 * fact_rec 1)
⇒ 3 * (2 * (match 3 with | 1 -> 1 | n -> n * fact_rec (n-1)))
⇒ 3 * (2 * 1) // base caseの適用
⇒ 3 * 2
⇒ 6

F#における式は、単純な関数適用がひとつひとつ順番に行われることで、最終的な値へと評価されます。上の例では、という記号が単純な1つの関数適用をあらわしています。このように、複雑な式をひとつひとつ関数適用し、単純な式へ導くことを簡約(reduction)といいます。

上のfact_recの例ではinduction stepが何回か適用され、最後にbase caseが適用されています。base caseが適用されることで、はじめて式が単純な積の形になり、最後にその積が計算されます。この例では3の階乗を求めているので最終的な積の形は3 * (2 * 1)という形ですが、もしこれが1000000のような巨大な値だったらどうなるでしょうか。

その式は、まず1000000 * (999999 * … * (2 * 1)…)という式に簡約され、そこから積の計算が始まります。したがって、式の形を記憶するためだけに大量のメモリが消費されてしまいます。そのメモリはスタックから確保されますが、スタック領域のサイズはあまり大きくないので、すぐにスタックオーバーフローが発生してプログラムが停止するかもしれません。

では、どのように対処すればよいのでしょうか。解決策のひとつは、ループをforループに書き換える方法(命令型プログラミングのところで解説)で、もうひとつは末尾再帰(tail recursion)という形に書き換えるという方法です。関数型言語では、その簡潔さから末尾再帰による方法が一般的に用いられます。

末尾再帰とは、induction step全体が自分自身への再帰呼び出しになっているような再帰関数のことをいいます。言葉ではわかりにくいので、末尾再帰に書き換えたバージョンを見てみましょう。

// 末尾再帰でないオリジナルバージョン
let rec fact_rec n =
  match n with
  | 1 -> 1 // base case
  | n -> n * fact_rec (n-1) // induction step

// 末尾再帰に書き換えたバージョン
let rec fact_tail_rec n result =
  match n with
  | 1 -> result // base case
  | n -> fact_tail_rec (n-1) (n*result) // induction step

関数の中身の説明に入る前に、まずは末尾再帰かどうかを簡単に見分ける方法を説明します。ある関数が末尾再帰であるかは、基本的にinduction stepに注目すればすぐに見分けることができます。わかりやすくするために、上のふたつの関数のinduction stepを、以下に書き出してみます。

  • n * fact_rec (n-1)

  • fact_tail_rec (n-1) (n*result)

前者が非末尾再帰で、後者が末尾再帰です。よく見てみると、後者はinduction step全体がfact_tail_rec自身への呼び出しとなっていますが、前者は自身の呼び出しの前に「n *」という余計なものがついています。このように余計なものがついていると、再帰呼び出しのたびに、この余計なものがどんどん蓄積していってメモリを圧迫してしまいます。ところが、末尾再帰では余計なものによってメモリが圧迫されることはありません。

では、関数の中身について詳しく見ていきましょう。末尾再帰バージョンは、少し複雑に見えるかもしれませんが、非末尾再帰バージョンとの2つの違いが重要です。

まず1つ目は、先ほど説明したようにinduction step全体が自分自身への再帰呼び出しとなっていることです。このような形になっていることで、まず引数が先に評価され、一番末尾で再帰呼び出しがおこなわれる(すなわち末尾再帰)ようになります。

2つ目は、その末尾再帰を実現するために計算結果を第2引数に記録・蓄積するように書き換えたことです。このように記録用の新たな引数を導入することで、非末尾再帰関数を末尾再帰関数へ書き換えるのはよく使われるテクニックです。

では、この末尾再帰バージョンがどのように簡約されるのかを見てみましょう。

fact_tail_rec 3 1 // 蓄積用引数の初期値を1にする
⇒ match 3 with | 1 -> 1 | n -> fact_tail_rec (n-1) (n*1)
⇒ fact_tail_rec (3-1) (3*1) // induction stepの適用
⇒ fact_tail_rec 2 (3*1)
⇒ fact_tail_rec 2 3 // 引数へ蓄積
⇒ match 2 with | 1 -> 3 | n -> fact_tail_rec (n-1) (n*3)
⇒ fact_tail_rec (2-1) (2*3) // induction stepの適用
⇒ fact_tail_rec 1 (2*3)
⇒ fact_tail_rec 1 6 // 引数へ蓄積
⇒ match 1 with | 1 -> 6 | n -> fact_tail_rec (n-1) (n*6)
⇒ 6 // base caseの適用、蓄積された値をそのまま返す

この末尾再帰バージョンでは、一番最後にまとめて積が求められるのではなく、再帰呼び出しのたびに少しずつ積が計算され、逐次蓄積用引数に蓄積していきます。したがって非再帰バージョンとは違い、長い式を記憶する必要がないため、余計なメモリは必要とせず、スタックオーバーフローの心配もありません。

末尾再帰のもうひとつの特徴として、末尾呼び出し最適化(tail call optimizatioin)が期待できることがあげられます。再帰呼び出しは表現力が高い反面、それを愚直にコンパイルすると効率の悪いコードが生成されてしまいます。そこで、コンパイル時に末尾再帰を(forループなどの)単純なループに置き換えることで、効率のよいコードを生成することを末尾呼び出し最適化とよびます。末尾再帰ならばかならずこの最適化が行われるという保証はありませんが、たいていの場合は最適化されるはずです。

ちなみに、ある関数同士が相互に相手を呼び出しあっているような再帰呼び出しも存在し、これは相互再帰(mutually recursion)とよびます。さらに、相互再帰におけるinduction step全体で相手を呼び出しているようなものは、相互末尾再帰とよびます。

2.3. 関数式(ラムダ式)

関数式(function expression)またはラムダ式(lambda expression)を使うと、ローカル変数のような感覚で簡単に関数をつくることができます。ラムダ式の構文は以下のとおりです。

fun [pat]+ -> expr

まず一番簡単な例を見てみましょう。

> (fun x -> x + 10);; // ラムダ式で1引数の関数を作る
val it : int -> int = <fun:clo@0>

> (fun x -> x + 10) 5;; // 同じように関数を作り、5という引数を渡す
val it : int = 15

> (fun x y z -> x + y + z) 1 2 3;; // 3引数の関数を作り、1、2、3という引数を渡す
val it : int = 6

> let plus10 = fun x -> x + 10;; // 作り出した関数に名前をつける
val plus10 : int -> int

> plus10 5;; // 5という引数を渡す
val it : int = 15

1番目の入力は、ラムダ式で1引数の関数を作り出しています。2番目の入力では同じように関数を作り出し、すぐにその関数に5という引数を与えて呼び出しています。3番目は複数の引数を持つラムダ式の例です。

4番目と5番目では、ラムダ式で作り出した関数値にplus10という名前をつけ、普通の関数のように呼び出しをしています。

ラムダ式は、次章で説明する高階関数と組み合わせることで非常に強力な表現力をもちます。

2.4. カリー化

関数型言語における関数呼び出しの考え方は、命令型言語における考え方とは大きく異なります。命令型言語において関数を呼び出すときは、必ず全ての引数をそろえて呼び出すのが常識です。ところが関数型言語では、前節の部分適用のところで説明したように、引数を途中まで渡しておいて後で全ての引数がそろった時点で呼び出しを行うといった、命令型言語から見ると非常に奇妙なことができます。

このような奇妙なことが当たり前にできるのは、実は関数型言語の背景に隠れているカリー化(currying)という概念によるものです。ここでは、その仕組みについて詳しく見ていきましょう。まずは、以下の単純な関数を見てください。

> let add10 x = x + 10;; // 10を加算する関数add10を定義
val add10 : int -> int

この関数は、前節で紹介したラムダ式を使って書くこともできます。

> let add10 = fun x -> x + 10;; // 10を加算するラムダ式にadd10という識別子を束縛
val add10 : int -> int

実はF#では、この2つの関数定義は「等価」なのです。どちらの方法で関数を定義しても、プログラム上はまったく同じ意味になります。さらに引数が複数の場合でも同様です。

> let plus3 x y z = x + y + z;; // 3引数の関数を定義
val plus3 : int -> int -> int -> int

> let plus3 = fun x y z -> x + y + z;; // 上と等価な定義
val plus3 : int -> int -> int -> int

ここでは3引数のラムダ式を使っていますが、このような複数の引数をとるラムダ式は、さらに1引数をとるラムダ式の連鎖で書くことができます。

> let plus3 = fun x -> (fun y -> (fun z -> x + y + z));; // 1引数のラムダ式の連鎖で定義
val plus3 : int -> int -> int -> int

これらの3つの定義もすべて等価です。このように、F#の関数はすべて1引数のラムダ式による定義に書き換えることができます。

このラムダ式による定義の書き換えは非常に冗長ですが、ここでそれを紹介したのには大きな意味があります。実は、関数型言語の背景理論であるラムダ計算論の観点から見ると、驚くべきことに1引数のラムダ式の連鎖よる定義のほうが本質的な定義なのです。すなわち、ラムダ計算論的にはラムダ式による関数定義が本質であり、関数の名前はあくまでおまけなのです。

では、ここで複数の引数を持つ以下の関数の呼び出しが理論的にはどのように処理されるかを見てみましょう。

> let plus = fun x -> (fun y -> x + y);; // let plus x y = x + yと等価
val plus : int -> int -> int

まず、この関数の引数として3と2を与えると、以下のように処理されます。(「⇒」という記号は関数が評価されてゆく過程の1ステップを意味しますが、この評価過程はあくまで理論的なもので、実際のものとは異なる可能性があります。)

plus 3 2
⇒ (fun x -> (fun y -> x + y)) 3 2 // plusの関数定義
⇒ (fun y -> 3 + y) 2 // xに3を入れる
⇒ 3 + 2 // yに2を入れる
⇒ 5 // 3+2を行う

このように、引数が1つずつ置き換えられる様子がわかります。では、引数を中途半端に与えた場合はどうなるでしょうか。

plus 3 // 1つしか引数を与えない
⇒ (fun x -> (fun y -> x + y)) 3 // plusの関数定義
⇒ (fun y -> 3 + y) // xに3を入れる

引数が足りないのでこれ以上処理することはできず、最終的に1引数の関数となりました。この最終的にできた関数は、plusの片方の引数が3に固定されたバージョン、すなわち部分適用により作り出されたバージョンです。このように、関数がラムダ式の連鎖で構成されていると考えると、部分適用という仕組みがごく自然に出てくることがわかります。

コンピュータサイエンスでは、このようなラムダ式の連鎖で構成された関数のことを、カリー化関数(curried function)と呼びます。関数型言語の関数は、基本的にカリー化関数として構成されています。

ところで上の関数plusは、以下のようにタプルを使って定義することもできます。

> let plus (x,y) = x + y;; // タプルを使って定義
val plus : int * int -> int

この関数をラムダ式を使って書き換えてみましょう。

> let plus = fun (x,y) -> x + y;; // タプルを使って定義
val plus : int * int -> int

このラムダ式は何引数のラムダ式でしょうか。これは2つ組タプルを引数にとる「1引数」のラムダ式です。したがって、これ以上細かいラムダ式に分けることはできません。つまり、タプルを使って引数を受け取ってしまうと、部分適用の恩恵を受けることができません。このように、n個の引数を1つのn組タプルで受け取っている関数のことを、非カリー化関数(uncurried function)と呼びます。

基本的に命令型言語の関数は、非カリー化関数として構成されています。実際、.NET Frameworkは命令型言語の上で設計されており、F#はそこに含まれるメソッドを非カリー化関数として扱います。たとえば、累乗を計算するSystem.MathクラスのPowメソッドの型を見てみましょう。

> System.Math.Pow(2.0,3.0);; // 2の3乗を計算
val it : float = 8.0

> System.Math.Pow;; // 型を確認
val it : float * float -> float = <fun:clo@0_5>

C#から見るとSystem.Math.Powは2引数のメソッドですが、F#では2つ組タプルを受け取る1引数の関数として扱われていることがわかります。

このような理由から、.NET Framework上のメソッドは、そのままでは部分適用をすることができません。そこで必要に応じてカリー化関数バージョンを定義しておくと便利です。たとえば以下のようにな使い方をします。

> open System.Windows.Forms;; // 名前空間を開く
> let message_box (text:string) (caption:string) (button:MessageBoxButtons) = MessageBox.Show(text,caption,button);; // MessageBox.Showのカリー化バージョンを定義
val message_box : string -> string -> MessageBoxButtons -> DialogResult

> let button_tester = message_box "hello,world!" "title";; // 第2引数まで部分適用することで、1引数関数button_testerを作り出す
val button_tester : MessageBoxButtons -> DialogResult

> button_tester MessageBoxButtons.OKCancel;; // OK/Cancelボタンつきのメッセージボックスを表示
val it : DialogResult = OK

> button_tester MessageBoxButtons.AbortRetryIgnore;; // Abort/Retry/Ignoreボタンつきのメッセージボックスを表示
val it : DialogResult = Abort

ここでは、おなじみのMessageBoxクラスのShowメソッドのカリー化バージョンであるmessage_boxという関数を定義しています。

Note

ご存知のとおり、MessageBox.Showメソッドには複数のオーバーロードが存在しますが、ここではそのひとつであるMessageBox.Show(String, String, MessageBoxButton)のカリー化関数バージョンを定義しました。実際に関数の定義時(2番目の入力)には、各引数に対して明示的に型アノテーションをつけることで、オーバーロードのあいまいさを無くしています。ここで型アノテーションをつけないと、どのオーバーロードメソッドを採用すればよいか判別できずにエラーが発生します。

そして、message_boxを部分適用することによりbutton_testerという関数を作り出しています。このbutton_testerを使うことで、さまざまなボタンをF# Interactive上から簡単にテストできます。

ここで紹介したのは部分適用の簡単な応用例に過ぎませんが、必要に応じてカリー化関数バージョンを作るとよいことがわかったと思います。このように、非カリー化関数からカリー化関数を作り出すことをカリー化(currying)といい、その反対を非カリー化(uncurrying)といいます。したがってこの例の場合は、「MessageBox.Show(非カリー化関数)をカリー化してmessage_box(カリー化関数)を作った」または「MessageBox.Showmessage_boxを非カリー化したものである」といった表現ができます。

Warning

カリー化や部分適用という用語は非常によく誤用されます。特に多いのが、「部分適用」と「カリー化」という用語を混同しているケースで、「部分適用」と書くべきところを「カリー化」と書く人が後を絶ちません。そこで、もう一度簡単にその用語をまとめてみましょう。

カリー化(currying)

非カリー化関数をカリー化関数に変換すること

非カリー化(uncurrying)

カリー化関数を非カリー化関数に変換すること

カリー化関数(curryed function)

1引数ラムダ式のn重の連鎖で構成された関数

非カリー化関数(uncurryed function)

引数としてn組タプルを受け取る関数

部分適用(partial application)

n引数のカリー化関数に対してm個の引数(m < n)を与えて、n-m引数のカリー化関数を作り出すこと

Note

カリー化はもともと数学の概念です。たとえば「

という関数をカリー化してという関数を作る」というように表現します。F#においてタプルを集合の直積だと考えると、この数式はF#のカリー化と同じ意味になります。

ちなみにカリー化という名前は、アメリカの論理学者Haskell Curry(1900-1982)に由来しています。

2.5. 演算子

ここまでに、加算演算子+や論理和演算子||などのいくつかの演算子が出てきましたが、これらも実は関数のひとつに過ぎません。

たとえば加算演算子はexpr1 + expr2という形で使いますが、これは+という名前の2引数関数と考えることが出来ます。ただ呼び出す際に、関数名を第1引数と第2引数の間に配置しなければならないという違いがあるだけです。また符号反転演算子-は、-xと呼び出すとxの符号を反転する1引数の関数です。

このように、第1引数と第2引数の間に配置して使う特別な関数を中置演算子(infix operator)といい、先頭に置いて1引数をとる特別な関数を前置演算子(prefix operator)といいます。

今見たように前置演算子と中置演算子は特殊な呼び出し方をしますが、通常の関数と同じように呼び出すこともできます。中置演算子は(infix-op)、前置演算子は(~infix-op)とすることで、通常の2引数関数および1引数関数として扱うことができます。

> let x,y = 3,2;;
val y : int
val x : int

> x + y;; // 中置演算子として呼び出す
val it : int = 5

> (+) x y;; // 通常の2引数関数として呼び出す
val it : int = 5

> -x;; // 前置演算子として呼び出す
val it : int = -3

> (~-) x;; // 通常の1引数関数として呼び出す
val it : int = -3

同様にして、独自の演算子を定義することができます。

> let (@) x y = (x && not y) || (not x && y);; // 排他的論理和の演算子を定義
val ( @ ) : bool -> bool -> bool

> false @ true;;
val it : bool = true

> false @ false;;
val it : bool = false

> let rec (<+>) (x:int list) (y:int list) = // 2つの配列の各要素を加算する演算子
  match (x,y) with
  | (x'::xs,y'::ys) -> (x' + y') :: (xs <+> ys) // 2つの配列が両方とも1要素以上存在する場合にマッチ
  | _ -> [];; // どちらか一方が空の場合にマッチ
val ( <+> ) : int list -> int list -> int list

> [1;2;3] <+> [0;1;2];; // 2つの配列を加算
val it : int list = [1; 3; 5]

演算子名には以下の記号を使用できます。ただし、:だけは演算子名の先頭の文字としては使えません。

!$%&*+-./<=>?@^|~:

2.6. 練習問題

  1. 末尾最適化のところ定義したfact_tail_recを参考にして、1からnまでの整数の和を計算を行う関数sum_tail : int -> intを、末尾再帰を使って定義してください。

  2. 以下の関数make_pairは通常の2引数の関数ですが、この関数を1引数のラムダ式のみを使った等価な定義に書き換えてください。

    例) let inc x = x + 1let inc = fun x -> x + 1

    let make_pair (name:string) (value:int) = (name,value)
  3. 以下に示すプログラムの中では再帰関数が使われています。その再帰関数が末尾再帰か非末尾再帰かを判定してください。また、非末尾再帰だった場合は、末尾再帰に書き換えてください。

    1. let rec sum n = // 0からnまでの和を求める関数
        if n <= 0 then 0
        else n + sum (n-1)
      
    2. let power x n = // xのn乗を求める関数
        let rec power_helper x n accum = // power内だけで使う補助関数を定義
          if n <= 1 then x
          else power_helper x (n-1) (x*accum)
        power_helper x n 1 // accumに初期値1を与えて補助関数を呼び出す
    3. // ディレクトリ内の指定日以降に更新されたファイルのリストを作る関数
      // 使用例) enum_updated_files @"C:\" (System.DateTime.Parse("2009/04/10"))
      let enum_updated_files dir date =
        let dir_files = Array.to_list (System.IO.Directory.GetFiles(dir))
        let rec enum_helper files = // 補助関数を定義
          if List.is_empty files then
            [] // ファイルリストが空ならば何も一致しないので空のリストを返す
          else
            let file = List.hd files // ファイルリストの先頭から1つ取り出す
            let fullpath = System.IO.Path.Combine(dir, file) // フルパス名を生成する
            let lastupdate = System.IO.Directory.GetLastWriteTime(fullpath) // 最終更新日を取得
            // 最終更新日に応じて結果を返す
            if lastupdate > date then
              file :: enum_helper (List.tl files)
            else
              enum_helper (List.tl files)
        enum_helper dir_files // 補助関数を呼び出す
      
  4. 以下の関数が、カリー化関数の場合は非カリー化し、非カリー化関数の場合はカリー化してください。

    1. let area (x,y) = x + y

    2. let rect x y w h = (x,y,w,h)

    3. let circle (x:int) (y:int) (r:float) = (x,y,r)

  5. 2つのfloat値を比較し、2つの値の差が0.001以下の場合にtrue、そうでない場合にfalseを返す比較演算子=~を定義してください。

inserted by FC2 system