SML# - Tutorial/009 Diff

  • Added parts are displayed like this.
  • Deleted parts are displayed like this.

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

まず、階乗の定義を振り返ってみよう。nの階乗は以下のような式の値である。
""n * (n - 1) * (n - 2) * ... * 2 * 1
この式の値を数学的に定義してみよう。nの階乗を'''n!'''と書く。すると
以下のように定義できる。
# 0! = 1
# n! = n * (n - 1)!
この定義は、以下のことを意味している。
# 0の階乗は1である。(そう約束する)
# 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'''は自分自身の再帰的な利用である。
この定義は以下のように読める。
# 0の階乗(factorial 0)は1である。
# 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
このような再帰的な定義が,関数型言語の基本である.
再帰的な定義をはじめて学ぶものは,
[[補足:再帰的な関数の考え方|Tutorial/009-1]]
を理解しておこう.

Cと同様MLでも種々の定義の仕方がある。
次に、[[MLでのfactorial関数の種々の定義|Tutorial/010]]
によってMLの関数定義機構のいくつかを学ぼう。
----
[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/008]] | [[ 次ページ |Tutorial/010]] ]