letを用いた関数定義
関数(ラムダ式)も値であるので
letを用いて識別子を関数に束縛することができます。
この構文を簡略化したものは次のようになります。
(正確な構文は値の束縛：letのページ末尾参照)
- letを用いた関数定義
- let ident pat1 ... patn return-typeopt = bodyexpr //構文A
let ident pat1 ... patn return-typeopt = bodyexpr in expr //構文B
identは、定義する関数の名前です。演算子も定義出来ます
pat1 ... patnは、引数で、匿名関数のところで説明したものと全く同じです
return-typeoptは、定義する関数の型の注釈で、省略可能です
bodyexprは関数本体に相当する式です。
構文Aはモジュールに値を定義する形式で
構文Bはモジュールに値は定義せずに、in exprの中でだけ使える
関数を識別子へ束縛する形式になります。
また、関数の適用法は匿名関数の章で説明したものと全く同様ですが
全体を括弧でくくらなくて済む分すっきりします。
letによる関数の定義
> let inc x = x + 1;; //入力を1増やしたものを返す関数
val inc : int -> int
> let add x y = x + y;; //2つの入力をとり、それらを加算する関数
val add : int -> int -> int
> inc 10;;
val it : int = 11
> add 10 20;;
val it : int = 30
実は、これは次のような形の式として評価されると以前のF#入門では記載していたのですが、
(F#4.1 spec 6.6.1,14.6.4)には該当箇所を見つけることができませんでした。
ただ、一つの理解の仕方としてはありだと思うので残しておきます。
↓↓
ラムダ式が理解出来ていれば
letでの関数定義は理解しやすいと思います。
上の式の評価
let ident = (fun pat1 ... patn return-typeopt -> bodyexpr)
let ident = (fun pat1 ... patn return-typeopt -> bodyexpr) in expr
上の例は、次のような関数と実質同じです。
上の例を書き換えたもの
> let inc2 = fun x -> x + 1;;
val inc2 : int -> int
> let add2 = fun x y -> x + y;;
val add2 : int -> int -> int
> inc2 10;;
val it : int = 11
> add2 10 20;;
val it : int = 30
let recを用いた関数定義
また、let recを使えば再帰的(recursive)な関数も定義することができます。
再帰的な関数、とは関数定義の中で自分自身を呼び出す関数のことです。
構文的には、単にrecというキーワードが増えただけです。
(正確な構文は値の束縛：letのページ末尾参照)
- let recを用いた関数定義
- let rec ident pat1 ... patn return-typeopt = bodyexpr
let rec ident pat1 ... patn return-typeopt = bodyexpr in expr
再帰関数は最初は理解しにくいと思うので
出来るだけ簡単な例から挙げてみます。
おそらく、最も単純な再帰関数はこんな感じです。
与えられた自然数の数だけ1を足す
let rec add1loop n =
if n<=0 then
0
else
1 + add1loop(n-1);;
これは、自然数が入力されたときはその自然数を返し
負の数が入力されたときは0を返す関数です。
add1loop(n-1)の部分が自分自身を呼び出している箇所です。
ここで新しく出てきたifは条件分岐のための構文で
if 条件 then 真の時評価 else 偽の時評価
のような動作をします。
詳細は基礎編のifの章を参照してください。
add1loop 3と呼び出したときの動作について考えてみます。
まず、各数値に対応した呼び出しを具体的に書き出すと
add1loop 3 : if n<=0 then 0 else 1 + add1loop 2
add1loop 2 : if n<=0 then 0 else 1 + add1loop 1
add1loop 1 : if n<=0 then 0 else 1 + add1loop 0
add1loop 0 : if n<=0 then 0 else 1 + add1loop (-1)
こんな感じになります。
add1loop 0の時は0が評価され、
それ以外はelseの箇所が評価されることに注意して
if文を取り除いてみると
add1loop 3 : 1 + add1loop 2
add1loop 2 : 1 + add1loop 1
add1loop 1 : 1 + add1loop 0
add1loop 0 : 0
こうなります。
つまり、add1loop 3という呼び出しは
add1loop 3
→1 + (add1loop 2)
→1 + (1 + (add1loop 1))
→1 + (1 + (1 + (add1loop 0)))
→1 + (1 + (1 + 0))
→1 + (1 + 1)
→1 + 2
→3
のような計算がなされます。
上の例をもう少し複雑にしたのが次の例です。
与えられた自然数までの和を求める関数
let rec sum n =
if n<=0 then
0
else
n + sum(n-1);;
これを実行すると、与えられた自然数までの和が求まります。
sumの実行例
> sum 1;;
val it : int = 1
> sum 2;;
val it : int = 3
> sum 3;;
val it : int = 6
> sum 4;;
val it : int = 10
> sum 10;;
val it : int = 55
なんとなく雰囲気がつかめたでしょうか。
ちょっとした修正で、階乗を求めるコードが作れます。
階乗関数の定義
let rec fact n =
if n=1 then
1
else
n * fact(n-1);;
階乗関数の実行例
> fact 5;;
val it : int = 120
> fact 10;;
val it : int = 3628800
再帰関数はある意味では、漸化式と似ています。
実際、漸化式はそのまま再帰関数に書き直すことが出来ます。
nの階乗を表す数列A(n)を考えると
(X).初項は1
(Y).A(n)=n*A(n-1)
となりますが、これは上のプログラムほぼそのままなのがわかります。
それから、再帰関数であるにもかかわらず
let recを使わずにletを使って関数を定義しようとするとエラーになってしまいます。
プログラミングしていて、一度は見ることになるエラーです。
recを忘れエラー発生
> let fact n = if n=1 then 1 else n * fact (n-1) in fact 5;;
let fact n = if n=1 then 1 else n * fact (n-1) in fact 5;;
------------------------------------^^^^
stdin(1,37): error FS0039: The value or constructor 'fact' is not defined
相互再帰関数
let recを使った再帰には、相互再帰(mutual recursion)というテクニックもあります。
これは、2つ以上の関数がお互いに呼び出し合うような再帰的定義のことで
よくある簡単な例としては偶数奇数の判定があります。
F#で相互再帰な関数を定義するには、
andキーワードを使って
複数の関数定義を並べます。
相互再帰関数(mutually recursive function)の例
let rec even x =
if x=0 then true else odd (x-1)
and odd x = if x=0 then false else even(x-1);;
let isEven x = if (x < 0) then even (-x) else even x;;
printfn "9 is even? %A" (isEven 9);;
printfn "10 is even? %A" (isEven 10);;
再帰関数とスタック
関数呼び出しを行う際、関数の引数や、関数からの返り値を格納するために
メモリのスタックという領域を使うのですが
この
スタック領域というのは、比較的使える量が少ない領域であるため
再帰関数をよく使う、関数型のプログラミングスタイルでは
スタックを使いすぎないように注意する必要があります。
もし、使いすぎてしまうと、
スタックオーバーフローという例外が発生してしまいます。
(例外については後で説明します)
次の例では、わざとスタックオーバーフローを発生させているのですが
スタックは使える量が少ないということが実感出来ると思います。
環境によっては発生しなかったり、もっと小さい値で発生したりするので
その場合は数値を変えてみてください
(add1loopは一番最初の再帰関数の例と同じものです)
簡単にスタックオーバーフローは起こる
let rec add1loop x = if x=0 then 0 else 1+add1loop(x-1);;
printf "%A" (add1loop 40000);; //大丈夫
//printf "%A" (add1loop 60000);; //オーバーフロー
です。
(コンパイラの/Fオプションでスタックのサイズは変更出来ます)
大体5万回のループでスタックオーバーフローが発生しているので
5万×20=1M(100万バイト)となり
上コードは、おおよそ1回の再帰呼び出しごとに
20バイト程度スタックを消費している計算になります。
この程度の回数しかループ出来ないのであれば
あまり実用的ではなくなってしまいますが
ある形(末尾再帰)で関数を書けば
コンパイラが再帰関数をループに展開してくれます。
これを末尾再帰呼び出しの最適化といい、
そういった最適化が仕様で保証されている言語もあります(Scheme(R6RS 5.11))
F#4.1の仕様書を見た限りでは
末尾再帰呼び出しの最適化を保証している箇所は見つけられないのですが
実際の処理系では、末尾再帰呼び出しは最適化されるようです。
StackOverflowのこちらのスレッドにはCLRに.tail命令があって、F#は末尾再帰呼び出しの
最適化の問題はないと書いてあります。
末尾再帰な形に書き換えたコード
let rec add1looptailrec x n= if x=0 then n else add1looptailrec (x-1) (n+1);;
printf "%A" (add1looptailrec 10000000 0);; //例外がでなくなった
先のコードはこのように変更すると、
大きな数を入力しても動くコードになります。
末尾再帰呼び出しについては、関数型偏で取り上げる予定です。
letとfunの違い
-ここは、最初はとばしても問題無いです-
F#の型システム的な面からみると
letでの関数定義とfunによるラムダ式では
少し違いがあります。
これは、lispなどの言語で
letを使った式がlambda式に変換可能(※2)であるのと比べると
異なった点だと言えると思います。
letとfunでの動作の違い
> let id x = x in (id 10,id true);;
val it : int * bool = (10, true)
> (fun id -> (id 10,id true)) (fun x -> x);;
(fun id -> (id 10,id true)) (fun x -> x);;
---------------------^^^^
stdin(3,22): error FS0001: This expression was expected to have type
int
but here has type
bool
これは、ML系の言語の型システムの特徴で
letで定義した識別子は、
その本体部では毎回異なった型として
インスタンス化できるが
funの引数は、同じ型としてしかインスタンス化出来ない
という違いに由来するそうです。
(ここでのインスタンス化という用語は
型変数を別の型(型変数を含む型でも良い)に置き換えるといった意味で使っており
オブジェクト指向の用語とは違う意味です)
次に引用する用語に従うと
letを使って定義した識別子の型変数はgenericになるが
funの引数の型に型変数があれば、
それはnon-genericになります。
このletが導入する多相性のことを
let多相(let polymorphism)とも呼ぶそうです。
参考文献(※1)から型変数がgenericになる際のルールを引用すると
- generic
-
式eに出現する型の型変数がgenericであるのは
その型変数がeを囲むfun式の束縛部分の型に出現しない時であり、
またその時に限る
A type variable occurring in the type of an expression e is generic (with
respect to e) iff it does not occur in the type of the binder of any fun
expression enclosing e.
また、型変数がnon-genericであるとは
一度しか特定の型にインスタンス化できないものを言います。
その他注意点として、fun式の中で型チェックの結果non-genericになった型変数でも
その外側ではgenericになる、とあります。
a type variable which is found to be non-generic while typechecking within a fun
expression may become generic outside it
具体的な(参考文献のものと同じ)例は次のようになります。
これは上の方で見たとおり
letが実際に展開される形と一緒ですね。
funの外側ではgeneric
> let f = fun x -> x in (f 3,f true);;
val it : int * bool = (3, true)
F#の場合、genericな型は'a、non-genericな型は'_aのような表記がなされますが
'_aのほうは、実質エラーメッセージでしか見ることはないと思います。
また、用語的には、仕様書では特に統一されていないようで
genericな型変数のことを
type variable(f#4.1 spec 1.1.3)
type inference variable(f#4.1 spec 5.1)
compiler-inferred generic parameters(f#4.1 spec 5.1.2)
non-genericな型変数のことを
type inference variable that is yet to be resolved(f#4.1 spec 14.6.7)
unsolved inference variables(f#4.1 spec 14.6.8)
などと呼んでいます。
※1 Luca Cardelli, Basic Polymorphic Typechecking, Science of Computer Programming, 8,2 (April 1987).
※2 例えばlisp方言の一つであるschemeのR6RS仕様書の1.9によると let expression can be translated into a procedure call and a lambda expressionとある