読者です 読者をやめる 読者になる 読者になる

akimachoのはてなブログ

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

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

読書 関数プログラミング プログラム

はじめに

前回の続きです.今回は再帰についてみていきます.

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

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

再帰関数

再帰関数(recursive function)とは,関数内で自分自身の呼び出し(再帰呼び出し)を行う関数のことを指します.ところで,大川徳之『関数プログラミング実践入門』p.170で,構造化プログラミングの制御構造「連接」・「分岐」・「反復」と命令型言語とHaskell関数型言語)の対応関係を次のようにまとめています.これはOCamlにも当てはまると思います.

制御構造 命令型言語 Haskell
連接 文を並べること 関数合成
分岐 if文 パターンマッチやガード
反復 for文やwhile文 再帰関数

余談ですが,構造化プログラミングを提唱したダイクストラは,他にも構造化定理により任意のプログラムは「連接」・「分岐」・「反復」で構成できることを証明しました.これは,制御構造と関数型言語の概念の対応関係が成り立つならば,関数型言語も任意のプログラムを作ることが可能であるという証明になるのではないでしょうかね?


構造化プログラミングとは 【 structured programming 】 - 意味/解説/説明/定義 : IT用語辞典

構造化プログラミング - Wikipedia

構造再帰

再帰関数と再帰的なデータについて述べます.自己参照を含む部分で,再帰関数は再帰呼び出しを行っています.一方で,自己参照を含まない無条件で使える部分で再帰関数は再帰呼び出しを行いません.このように再帰的なデータを分解しながら,再び分解した自己参照を含む部分に再帰呼び出しを行っていきます.つまり,再帰的データの構造と再帰呼び出しが1対1対応したカタチになっています.以上のような再帰のことを,構造にしたがった再帰と呼びます.(『関数プログラミング実践入門』p.p172-173では,構造再帰(structual recursion)という用語が用いられてました)

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

著者は,以下に示すもの(私が意訳してますが)がデザインレシピの決定版であるとしています.

  1. データ定義 ・・・ 入力出力に用いるデータ型の選択
  2. 目的 ・・・ 関数の仕様の決定
  3. 例 ・・・ テストケースの作成
  4. テンプレート ・・・ 構造データに応じたmatch文の作成
  5. 本体 ・・・ 関数の実装
  6. テスト ・・・ プログラムの動作確認

また,特に再帰関数に関する注意として,データ定義の際にはデータ型のどこに再帰が含まれるのか確認すること,例では簡単に答えが出るケースと再帰によるケースの例を用意すること,テンプレートでは,どのパターン変数について再帰呼び出しが行えるのかを確認,本体では再帰呼び出しの意味するところを目的を使って理解した上で作成することが述べられていました.

おわりに

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

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