関数

関数型言語の主役である関数について見てきましょう。この節は長くなりそうです。

関数の定義

MLには手続き型言語における while ループのような便利な制御構造は存在しません!しますが,普通は使いません。 MLでは反復処理を再帰関数によって記述します。

以下のプログラムは自然数のべき乗(xy乗)を返す関数 power を定義したものです。

(* file: power1.sml *)

fun power x 0 = 1                    (* y = 0 のとき *)
  | power x y = x * power x (y - 1)  (* y > 0 のとき *)

関数の宣言はキーワード fun で始まり,= の左に関数名と引数,右に式を記述します。 複数のケースを書きたい場合,上記の例のように縦棒 | を使って関数の記述を続けることができます。

これを対話環境で読み込むと,次のようになります。

- use "power1.sml";
[opening power1.sml]
val power = fn : int -> int -> int
val it = () : unit

- power 2 8;
val it = 256 : int

- power 2 0;
val it = 1 : int

関数定義の順番には意味があります。 例えば今回の power 関数の宣言の 1行目と2行目を入れ替えてしまうと,power x y がすべてのケースにマッチしてしまうため,関数は終了しません。

fun power x y = x * power x (y - 1)
  | power x 0 = 1            (* こちらの定義には到達しない *)

パターンマッチング

もう既に使用していますが,関数の引数にはパターン (pattern) を使うことができます。 パターンには,変数や整数リテラルの他に,タプルもリストもレコードも書くことができます。

以下の例は,リストの長さを返す関数 length を,引数にリストパターンを用いて記述したものです。

- fun length nil  = 0
    | length (x::xs) = 1 + length xs;
val length = fn : 'a list -> int

- length [1,2,3,4,5];
val it = 5 : int

次の例のように,興味のない部分にはワイルドカードと呼ばれるパターン _ を使うこともあります。

- fun second (_, y) = y;
val second = fn : 'a * 'b -> 'a

- second (123, "abc");
val it = "abc" : string

パターンは val 宣言の左辺に使うこともできます。

- val (a, b) = (123, "abc");
val a = 123 : int
val b = "abc" : string

case 式を使って,式の中でパターンマッチを行うこともできます。

- fun length xs =
    case xs of nil => 0
             | x::xs => 1 + length xs;
val length = fn : 'a list -> int

if 式

パターンではなく論理式によって場合分けを行うには,if 式を使います。

- fun abs x = if x < 0 then ~x else x;
val abs = fn : int -> int

- abs ~5;
val it = 5 : int

if 式はあくまでも式なので値を持ちます。 そのため,then 以下を省略することはできません。

相互再帰関数

次のプログラムは,引数が偶数のときに真を返す関数 even と,引数が奇数のときに真を返す関数 odd を定義したものです。

- fun even 0 = true
    | even n = odd (n - 1)
  and odd 0 = false
    | odd n = even (n - 1);
val even = fn : int -> bool
val odd = fn : int -> bool

- even 2;
val it = true : bool

相互再帰的な関数は,互いが互いを参照しあえるように,1つの fun宣言の中に記述する必要があります。 そのために,この例のように and キーワードを使用します。

高階関数

関数型言語では,関数は第一級オブジェクト (first-class object) です。 つまり,関数は他の普通の値と同様に,変数に格納したり,関数の引数に指定したりすることができます。

関数を引数や返り値に持つ関数は高階関数 (higher-order function) と呼ばれます。 以下に示す map 関数は,標準で定義されている高階関数の代表的な例です。 map 関数は関数とリストを引数に持ち,リストの各要素に関数を適用した結果を返します。

- fun square x = x * x;
val square = fn : int -> int

- map square [1,2,3,4,5];
val it = [1,4,9,16,25] : int list

関数 map の定義は,例えば以下のように書くことができます。

fun map f nil     = nil
  | map f (x::xs) = f x :: map f xs

関数式

関数型言語の関数は第一級オブジェクトであるため,当然関数を式として記述することもできます。 関数を表す式は関数式と呼ばれ,しばしばラムダ式 (lambda expression),匿名関数 (anonymous function) とも呼ばれます。

以下の例は,関数式を使って square 関数を定義したものです。

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

- square 5;
val it = 25 : int

関数式を用いると,map square [1,2,3,4,5] と等価な式を次のように書くこともできます。

- map (fn x => x * x) [1,2,3,4,5];
val it = [1,4,9,16,25] : int list

階乗を求める関数 fact は,関数式を使うと次のように書けます。 再帰関数は関数式の中で左辺の名前を参照するため,次のように rec キーワードが必要です (rec は "recursive" の意)。

- val rec fact = fn 0 => 1 | n => n * fact (n - 1);
val fact = fn : int -> int

- fact 5;
val it = 120 : int

部分適用

次のプログラムは,2つの関数 addaddtwo を定義したものです。

- fun add x y = x + y;
val add = fn : int -> int -> int

- val addtwo = add 2;
val addtwo = fn : int -> int

- addtwo 3;
val it = 5 : int

関数適用は左結合であるため,例えば式 add 2 3(add 2) 3 と評価されます。 ここで add 2 は関数 add部分適用 (partial appication) と呼ばれ,int -> int 型を持ちます。 関数 addtwo は,関数 add の部分適用を利用して定義されています。

関数の部分適用を考慮すると,関数 add の型は int -> (int -> int),すなわち,引数が int 型で返り値が int -> int 型である関数の型と見ることができます。 一般に,1 -> ... -> 型n-1 -> 型n という関数の型があれば,これは 1 -> (... -> (型n-1 -> 型n)...) と同じ意味です。

今回の関数 add のように部分適用の可能な関数は,カリー化された関数 (curried function) といいます。 逆に,次に示す add' のような関数は,非カリー化された関数といいます。

- fun add' (x, y) = x + y;
val add' = fn : int * int -> int

- add' (2, 3);
val it = 5 : int

中置演算子

ここでは pl という中置演算子を宣言してみます。 演算子名は,関数名として使えるものなら何でも構いません。 次のように書くと,名前 pl が優先順位 6 の(左結合の)中置演算子として宣言されます。

- infix 6 pl;
infix 6 pl

右結合の中置演算子を宣言するには,infix の代わりに infixr キーワードを使います。

中置演算子の定義は,普通の関数と同様に fun 宣言により記述します。 例えば,中置演算子 pl の定義を次のように与えることができます。

- fun x pl y = x + y;
val pl = fn : int * int -> int

- 2 pl 3;
val it = 5 : int

中置演算子の直前にキーワード op を置くと,中置演算子を一時的に普通の関数として扱えます。

- op pl (2, 3);
val it = 5 : int

中置演算子の結合の優先順位は 0 から 9 までの数字をとります(9が最も強い)。 参考までに,トップレベルでは以下のように演算子が宣言されています。

infix  0 before
infix  3 o :=
infix  4 = <> > < >= <=
infixr 5 :: @
infix  6 + - ^
infix  7 * / div mod