デザインレシピ

データ定義

  • 入力データの型、出力データの型を考える
    • もしそれらの型が構造を持つのであれば、その型も定義する
      • 意味のある塊に対して一つの型を定義する
    • 再帰的なデータ型を持つ場合は、自己参照を行わないケースがあることを確認する

目的

  • 作成する関数が何を行うものかを考える
  • どの様なものを受け取り、どの様なものを返すのかを考え、関数の型を決定する
    • ヘッダを作成する

例

  • 関数を使用した具体的な入力と出力の例を作成する
    • ある境界によって場合分けが必要になる場合は、それらについての例を必ず用意する
      • テストケースとなる
    • 再帰的なデータの場合、全ての場合の例を用意する

テンプレート

  • 入力が構造を持つデータや再帰的なデータを保つ場合、その構造に応じたmatch 構文を作成する
    • 使用できるパターン変数を確認する
    • どの部分について再帰呼び出しを行えるか確認する

本体

  • 関数がどのようにして目的を実現するかを考え実装する
  • アキュムレータを用いる場合は、それが何を意味するのかを明確にする

テスト

  • 望む動作を行っているか、例で作成したテストプログラムを用いて確認する
    • 行っていない場合、原因をデザインレシピに沿って修正する

第1章 はじめに

  • デザインレシピ
    • プログラムを上手く作るためのレシピ

第2章 基本的なデータ

第3章 変数の定義

  • OCamlは適用順序評価である

第4章 関数の定義

  • A -> B -> C は右に結合するA -> (B -> C)
  • 関数作成のデザインレシピ
    • 目的
      • 作成する関数が何をするものか考える
      • 関数が何を受け取り、何を返すのかを考え、関数の型を決定する
    • 例
      • 関数の動きを明確にするため、入力と出力の例を作成する
        • テストになる
    • 本体
      • 関数の動作を再現するため、どの様に処理するかの具体を考える
    • テスト
      • 例で作った入力と出力の例からテストを実行する

第5章 条件分岐

  • OCamlにおけるif 式ではconsequentとalternativeが同じ型を持たなくてはならない
  • 条件分岐のデザインレシピ
    • 様々な条件についても考慮し、それに伴う結果の分岐に対してのテストを作成する
      • 値が変化する境界などに対して作成すると良い

第6章 さまざまなエラー

第7章 組とパターンマッチ

  • 構造データに対するデザインレシピ
    • 入力の一部が構造データの場合は、その中身を取り出すmatch 構文を作り、必ず取り出せることを確かめる

第8章 レコード

  • データ定義に対するデザインレシピ
    • 入力データ、出力データの型について定義する
      • もし階層構造を持つならそれらも定義する
    • 意味のある塊に対して一つの型を定義する

第9章 リスト

  • 再帰的データ型
    • 自身の型を構成要素として用いているデータ型
      • 自己参照している
  • 入力データの型が定まるとプログラムの大枠は自然に定まる

第10章 再帰関数を使ったプログラミング

第11章 自然数と再帰

第12章 ダイクストラのアルゴリズム

第13章 一般化と高階関数

  • 多相（polymorphic）
    • どの様な型でもよいという性質
      • 型の一般化
    • 実際に具体的な型を使用して呼び出した際に置き換えられる
  • 関数を作成する際に型を限定する必要がない場合、多相関数にしておいた方が便利

第14章 高階関数を使ったリスト処理

  • map, filter, fold
    • 高階関数三銃士

第15章 新しい形の再帰

  • 再帰関数のパターン
    • 自明に答えが出るケース
      • 手元にある情報から答えが計算できる
    • そうでないケース
      • 小さな部分問題（自明になりそうな方向）に対して再帰呼び出しを行う
  • 再帰を行う関数の考慮点
    • 自明に答えが出るパターンを考える
    • 部分問題にどう分割するか考える
    • 再帰呼び出しの結果から全体の結果をどう導出するか考える
  • よく用いられる停止性の確認方法
    • 再帰呼び出しを行う際の部分問題が、何らかの意味で元の問題よりも簡単になっていること
    • それを繰り返すと有限回で自明なケースに帰着させられること

第16章 情報の蓄積

  • アキュムレータ（accumulator）
    • 欠落している情報を補うために導入される引数
    • 再帰中においてアキュムレータが意味するものは変わらない

第17章 再帰的なデータ構造

  • バリアント型
    • 複数種類ある型のうち、どれか一つとなる型
  • 構成子（constructor）
    • データ型（バリアント型など）を構成している型

第18章 例外と例外処理

  • 意味的に異なるものには別の表現を与えるのが正しいプログラミングスタイル

第19章 モジュール

第20章 モジュールの開発

  • 赤黒木ﾜｶﾗﾝ

第21章 逐次実行

第22章 値の書き換えと参照透過性

  • 参照透過性（referential transparency）
    • 一度作成されたデータが変わること無く、未来永劫その値であり続けること
      • いつ参照しても同じ値になるため、A -> 1 である場合、式の中でA が登場している箇所を1 としても問題ないという性質がある
  • セル
    • OCamlにおける変更可能なデータのこと
      • ref 初期値 で作成、! セル で取り出し、セル := 値 で変更・代入

第23章 副作用命令を使ったプログラミング

  • 副作用命令をうまく使う方法
    • 副作用命令はモジュール内に隠蔽する
    • 関数を「書き換えたものを返す」形にする
      • 変更したデータの参照を同じ変数に代入することで、古い参照にアクセスさせないようにする
    • 常に最新のデータのみを手元に置き、古いものを再利用しない

第14章 まとめ-プログラミングとは-

  • いい事を言っている