(9)[ML] 関数定義

[ トップ | 目次 | 前ページ | 次ページ ]


MLプログラミングの基本は、求めたい値を返す関数を定義することであった。ここでポイントとなるのが再帰の考え方である。再帰関数の基本的考え方は、(今定義している)関数自身を使って部分問題を解きそれを組み合わせて求める値を計算する、というものである。種々の問題は再帰的な構造をしており、再帰関数を使うと自然に解けるものが多い。その例として、Cで解いた階乗を求める問題をMLで解いてみよう。

まず、階乗の定義を振り返ってみよう。nの階乗は以下のような式の値である。

n * (n - 1) * (n - 2) * ... * 2 * 1

この式の値を数学的に定義してみよう。nの階乗をn!と書く。すると以下のように定義できる。

  1. 0! = 1
  2. n! = n * (n - 1)!

この定義は、以下のことを意味している。

  1. 0の階乗は1である。(そう約束する)
  2. Nが1以上の場合、Nの階乗は、N - 1の階乗にNを架けたものである。

この計算を行う関数をMLでは以下のように書く。

fun factorial 0 = 1
  | factorial n = n * factorial (n - 1)

この構文の意味は以下の通りである。

  • funは(再帰的)関数を定義するキーワード、factorialは今定義している関数の名前である.
  • |は場合分けによる関数の定義、
  • fun facrorial 0 = は関数factorialの引数0の時の定義、
  • | factorial n = factorialの0以外の一般の引数nに対する定義、
  • n * factorial (n - 1)はnとfactorial (n - 1)の結果の積を表す式であり、factorialは自分自身の再帰的な利用である。

この定義は以下のように読める。

  1. 0の階乗(factorial 0)は1である。
  2. 0でない数nの階乗(factorial n)はnと(n - 1)の階乗(factorial (n - 1))を架けたものである。

これは、階乗の数学的な定義とほぼ同じ形である。このように、MLの関数定義は、求めたい式の値を関数を再帰的に使いながら、書いていけばよい。

この関数をfactorial.smlに保存し、MLから以下のように使ってみよう。

SML# 0.20 (2007-03-30 10:47:08 JST)
# use "factorial.sml";
val factorial = fn : int  -> int
# factorial 10;
val it = 3628800 : int

対話型処理をサポートするSML#ではmain関数を書くことなく、種々の値にしてfactorial関数を呼び出しテストすることができる。

# factorial 10;
val it = 3628800 : int
# factorial 11;
val it = 39916800 : int
# factorial 12;
val it = 479001600 : int

このような再帰的な定義が,関数型言語の基本である.再帰的な定義をはじめて学ぶものは,補足:再帰的な関数の考え方 を理解しておこう.

Cと同様MLでも種々の定義の仕方がある。次に、MLでのfactorial関数の種々の定義 によってMLの関数定義機構のいくつかを学ぼう。


[ トップ | 目次 | 前ページ | 次ページ ]