プログラミングの基礎

[[ OCaml ]]でプログラミングを学ぶ本。HtDPのDesign Recipeという方法論を踏襲している。 [[ Modern Compiler Implementation in ML ]]でOCamlを使うので読んでみた。

構造に従う [[ 再帰 ]]：データ構造が決まれば、プログラムの形も概ね決まってしまう

[[ Polymorphism ]]の定義がOOPと異なる？

このようにどのような型でもよいという性質のことを多相性 (polymorphism) と呼びます。また、型変数を含むような型のことを多相型、多相型をもつ関数のことを多相関数 (polymorphic function) と呼びます。

リストの各要素をばらばらにとらえるのではなく一括してとらえると、そのリストをひとつのデータとして扱うことができるようになります。そうすると、例えばリストの各要素をどの順序で処理するかなどという非本質的な部分に頭を悩ませることなくプログラムを作ることができるようになります。そして、次第にリストをひとまとめに捉えた、より抽象度の高い思考ができるようになっていきます。

一般の再帰

(15章 新しい形の再帰)

一般の再帰を行う関数をつくるときに気をつけること

• 自明に答えがでるケースは何？その答えは？
• より小さな部分問題はどうやって作る？
• 再帰の結果から全体の結果を得るにはどうする？
• 停止するか？： [[ 停止性問題 ]]はまだ解けていない。次を満たしていれば、まあだいたい停止する：
  • 部分問題が、もとの問題よりも簡単になっていること
  • それを繰り返すと、有限回で自明なケースに帰着すること

例： [[ クイックソート ]]

• []のソート結果は自明
• 分割統治法：基準 $k$ より大きい要素 $K_+$ と小さい要素 $K_-$ に分ける
• 再帰でソートされた結果から、 $K_, \; k, \; K_+$ の順に並べれば全体の結果になる

ふつうにアニメーションとかを活用して習うよりもわかりやすい気がする。なんで？ left, rightとかポインタがあっちこっちに動いて… ループと再帰の対応 ループ変数　再帰の深さ

ひとつの関数に複数の仕事をさせると、間違いが増えるばかりでなく、見通しも悪くなり、信頼性が落ちます。そういうときには補助関数を使って見通しのよいプログラムを作りましょう。なお、補助関数はヘッダさえできていれば、定義はまだ作らなくても構いません。ヘッダさえあればそのままプログラミングを続行できるからです。（p154）