再帰関数

与えられたリストに0があるかどうかを調べる関数を作ってみる。

(* リスト内に0が含まれているかを調べる *)
(* contain_zero : int list -> bool *)
let contain_zero lst = match lst with
        [] -> false
        | first :: rest -> if first = 0 then true
                                        else false

(* テスト *)
let test1 = contain_zero [] = false
let test2 = contain_zero [0; 2] = true
let test3 = contain_zero [1; 2] = false
let test4 = contain_zero [1; 2; 3; 0; 5; 6; 7] = true
let test5 = contain_zero [1; 2; 3; 4; 5; 6; 7] = false

ただしこの関数contain_zeroの実行結果は以下の様になる。

# #use "recursive.ml" ;;
val contain_zero : int list -> bool = <fun>
val test1 : bool = true
val test2 : bool = true
val test3 : bool = true
val test4 : bool = false
val test5 : bool = true

contain_zero [0; 2]は正しく0を検索できているが
contain_zero [1; 2; 3; 0; 5; 6; 7]がfalseで返ってきてしまっている。

これは、関数contain_zeroがfirstが0かどうかを調べている関数なので
restに0があっても探すことはできない。

# contain_zero [1; 0];;
- : bool = false

この場合、以下の様にすることで[1; 0]というリストに対応することが出来る。
ただし、リストの要素分処理をしないといけないし
そもそも、リストは要素数が決まっていないデータである。

(* リスト内に0が含まれているかを調べる *)
(* contain_zero : int list -> bool *)
let contain_zero lst = match lst with
        [] -> false
        | first :: rest -> if first = 0 then true
                                        else match rest with
                                                [] -> false
                                                | first :: rest -> if first = 0 then true
                                                                                else false

ここで、この関数を再帰関数という形にしてみる。

(* リスト内に0が含まれているかを調べる *)
(* contain_zero : int list -> bool *)
let rec contain_zero lst = match lst with
        [] -> false
        | first :: rest -> if first = 0 then true
                                        else contain_zero rest

最後の行で

else contain_zero rest

の様に、関数contain_zeroの中で、関数contain_zeroを呼んでいる。
この様な、自分自身を呼ぶことを再帰呼び出しといい
再帰呼び出しを含む関数を再帰関数と言う。
※Ocamlでは、再帰関数を定義する際には"let rec 関数名"のように書く。

関数contain_zeroの処理の流れ

contain_zeroにリストが渡される。
先頭の要素が0でなければ、自分自身にrestを渡す。
restの先頭が0でなければ、自分自身にrestを渡す。
2.3を繰り返す。
restの先頭が0なら、trueを返す。

再帰関数で気を付けなければいけない点は
無限ループに陥らない=必ず停止することが分かっていなければならないと言う点。

上の関数contain_zeroでは、firstが0でなければ、残りのリストであるrestを渡すため
リストの要素は自分自身が呼び出される毎に減り
0がリスト内に含まれていない場合にも、いつかは、パターンマッチで"[] -> false"にひっかかり止まる。

再帰関数のポイント

入出力データの検討

データは意味のあるかたまりに対して１つの型を定義することが望ましい。
もし、再帰的なデータ型であるなら、どこに再帰が含まれているのかも確認しておく。

作成する関数の目的を考える

何を受取り、何を返すのか、そして関数の型を検討する。

入出力の例を作成する。

作成する関数に望まれる入出力例を作成し、テストプログラムにする。
色々な入力によって場合分けが必要になってくる時は、全てのケースを考える。

テンプレート

データの構造に応じたmatch文を作成する。
その際に、どの様なパターン変数が使用できるのかを確認しておく。
再帰的なデータであれば、どのパターン変数について再帰呼び出しを行えるかもチェックする。

本体の作成

作成する関数の目的に対して、どうやって実現するかを考える。
必要に応じて、作成した例を参照しながら行う。

テスト

作成したテストプログラムを使って、関数の動作を確認する。

複雑な入力データの処理

今までの入力データは単純なリストだったが、実際はもっと複雑なものになる。

(* 学生1人分のデータを表す型 *)
type student ={
  name   : string;  (* 名前 *)
  score  : int;     (* 点数 *)
  result : string;  (* 成績 *)
}

学生のデータのリストを受けとったら、成績が"A"の生徒の数を返す関数を
デザインレシピに従って考えてみる。

データ定義

(* 学生1人分のデータを表す型 *)
type student = {
  name   : string;  (* 名前 *)
  score  : int;     (* 点数 *)
  result : string;  (* 成績 *)
}

(* student list : 
   - [] 空のリスト
   | - first :: rest firstはstudent型のリスト、restは自己参照
*)

データ例

データ例は先に作っておくと、後でテストプログラムを作りやすい。

(* student list型のデータ例 *)
let lst1 = []

let lst2 = [{name = "sDaigo" ; score = 10 ; result = "E"}]

let lst3 = [{name = "sDaigo" ; score = 10 ; result = "E"} ;
            {name = "sHiromi" ; score = 85 ; result = "A"}]

let lst4 = [{name = "sDaigo" ; score = 10 ; result = "E"} ;
            {name = "sHiromi" ; score = 90 ; result = "A"} ;
            {name = "nNobita" ; score = 100 ; result = "A"}]

目的と例

(* 学生リスト lstのうち、成績がAの人数を返す *)
(* count_A : student list -> int *)
let count_A lst = 0

(* テスト *)
let test1 = count_A lst1 = 0
let test2 = count_A lst2 = 0
let test3 = count_A lst3 = 1
let test4 = count_A lst4 = 2

テンプレート

(* 学生リスト lstのうち、成績がAの人数を返す *)
(* count_A : student list -> int *)
let count_A lst = match lst with
    [] -> 0
    | first :: rest -> 0 (* count_A rest *)

成績がAかどうかの判定が必要なので、学生リスト内のレコードの中身にアクセスする必要がある。

(* 学生リスト lstのうち、成績がAの人数を返す *)
(* count_A : student list -> int *)
let count_A lst = match lst with
    [] -> 0
    | first :: rest -> (match first with
                         {name = n ; score = s ; result = r} 
                         -> 0(* count_A rest *)

の様に、match文の中に別のmatch文を書くか

(* 学生リスト lstのうち、成績がAの人数を返す *)
(* count_A : student list -> int *)
let count_A lst = match lst with
    [] -> 0
    | {name = n ; score = s ; result = r} :: rest
      -> 0 (* count_A rest *)

の様に、パターンの中にパターンを埋め込む。

プログラムの大枠が出来たので、成績の判定ロジックを作る。

(* 学生リスト lstのうち、成績がAの人数を返す *)
(* count_A : student list -> int *)
let count_A lst = match lst with
    [] -> 0
    | {name = n ; score = s ; result = r} :: rest
      -> if s = "A" then 0 (* count_A rest *)
                    else 0 (* count_A rest *)

本体

(* 学生リスト lstのうち、成績がAの人数を返す *)
(* count_A : student list -> int *)
let rec count_A lst = match lst with
    [] -> 0
    | {name = n ; score = s ; result = r} :: rest
      -> if s = "A" then 1 + count_A rest
                    else count_A rest