akimachoのはてなブログ

ICTとデザインのためのブログ

『プログラミングの基礎』読書日誌-14日目-

はじめに

今日は,第9〜11章で主役だった再帰をやり直したいと思います.

再帰関数に対するデザインレシピ

設計の指針を振り返ってみます.

データ定義

入力・出力のデータ型を考えます.もしそのデータ型が構造データならば,意味のあるまとまりに対してひとつの型を与えます.さらに,再帰的なデータ型ならば,そのデータ型の自己参照を行う部分と自己参照を行わない部分を確認します.自己参照を行わない部分は無条件に使うことができます.以下のようにコード上にデータ構造についてコメントしておきましょう.

(* int list は
  - []			空リスト,あるいは
  - first :: rest	最初の要素がfirstで残りのリストがrest(restが自己参照のケース)
  という形*)

関数の目的と例

作成の関数が何をするのか,入力と出力を考え,関数の型を決定します.また,関数の動きをより理解するために作成する関数に理想的な入力とそれに対する出力を作成します(=テストケースの作成).境界や簡単に答えが出る場合,再帰が必要になる場合の例を必ず含めるようにします.この段階では,関数の処理内容には立ち入りません.

テンプレート

構造データや再帰的なデータが関数の入力の場合は,その構造に応じたパターンマッチを作成します.再帰的なデータの場合は,どのパターン変数について再帰呼び出しが行えるをチェックします.この変数は,構造データにおいて自己参照を行う部分になります.

本体

関数の本体を作成するために,アルゴリズムを考えます.再帰関数では,再帰呼び出しの意味するところを目的を使い実装します.

テスト

テストプログラムを走らせ,望む動作が行われているか確認します.期待する挙動をしていない場合は,デザインレシピに沿って,誤りを訂正します.

再帰的な考え方のコツ

川徳之『関数プログラミング実践入門』p.p.175-176に再帰的な考え方のコツが書いてあったので,メモしておきます.

  1. 構造再帰で対象(=引数)を構造的に分解していく
  2. ベースケースを考える
  3. 結果として守られる性質に着目する

構造再帰で対象(=引数)を構造的に分解していく

再帰で反復的に行いたい計算は,実は,データ構造的に分解したより小さいデータ構造に対して行う形になることが多いのです。

ベースケースを考える

ベースケースは再帰を扱う上で場合分けしていったときに,それ以上再帰的な定義が必要ない最もシンプルなケースです。(略)ベースケースがどうなるのかを正しく与えられることは,再帰関数全体の正しさに直結します。

結果として守られる性質に着目する

再帰的定義を行うということは,再起して得られた結果がある声質を満たしているという材料から,それと同じ声質を満たすより大きな結果をどうやったら作れるかを宣言するということです。

おわりに

googleで「再帰」と検索すると,「もしかして:再帰」と表示されるんですね(Recursionでも同様でした).知りませんでした.遊び心に溢れてますね.

プログラミングの基礎 (Computer Science Library)

プログラミングの基礎 (Computer Science Library)