関数

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

1. 関数の定義

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

以下のプログラムは自然数のべき乗（x の y乗）を返す関数 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            (* こちらの定義には到達しない *)

2. パターンマッチング

もう既に使用していますが，関数の引数にはパターン（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

3. 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 以下を省略することはできません．

4. 相互再帰関数

次のプログラムは，引数が偶数のときに真を返す関数 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 キーワードを使用します．

5. 高階関数

関数型言語では，関数は第一級オブジェクト（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

6. 関数式

関数型言語の関数は第一級オブジェクトであるため，当然関数を式として記述することもできます． 関数を表す式は関数式と呼ばれ，しばしばラムダ抽象（lambda abstraction），匿名関数（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

7. 部分適用

次のプログラムは，2つの関数 add と addtwo を定義したものです．

- 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

8. 中置演算子

ここでは 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