プログラミングの基礎
情報
関数型プログラミング言語であるOCamlを用いた教本 関数型言語を何でもいいからやってみたい!という人にオススメとのこと(@bleisさん) まえがき
本書の目的
プログラムを作る際に踏むべきステップをひと通り定めたもの
最終目標: メトロネットワーク最短路問題を解くプログラム
第1章 はじめに
1.2 使用する言語
記述量の少なさ
複雑な制御構造を自然な形で書くことのできる記述力の高さ
低レベルの操作を気にせずアルゴリズムの記述が可能
強力な型システム
強力なコンパイラによりCと遜色のないスピード
第2章 基本的なデータ
2.2 実数
OCamlでは整数と実数を厳格に区別する
実数専用の計算用演算子を使う
tnagatomi.iconこれは面倒くさそうだけどどうなんだろ
ベキ乗 (**) は実数のみに用意されている
infinityで無限大を表す
普通の実数と一緒に使える
neg_infinityでマイナス無限大を表す
2. 3 文字列
^で文字列連結
2.4 真偽値
trueはfalseより大きい
true > falseはtrue
違う型のデータは比較できない
2 < 3.0はエラーとなる
第3章 変数の定義
3.2 変数定義の構文
let 変数名 = 式で変数を定義
先頭の文字がアルファベットの小文字でなくてはならない
3.4 ほかの言語の変数との違い
基本的に書き換えることのできない定数である
第4章 関数の定義
4.2 関数定義の構文
let 関数名 引数 ... = 式
変数と同様にアルファベットの小文字で始まらなければならない
4. 3 関数の型
A -> B -> Cは右に結合する
つまりA -> (B -> C)
4.4 型推論と型チェック
型推論
型チェック
4.5 関数の実行方法
OCamlにおける関数は数学の関数と非常に近い
4.6 関数定義に対するデザインレシピ
目的、例、本体、テストの4つで構成されるデザインレシピ
(* ... *)でコメント
式末の;;はファイルに書くときは不要
tnagatomi.icon テスト駆動で書いていく感じいいな
第5章 条件分岐
5.2 条件分岐の構文
OCamlのif文の要件
条件はbool式である
then部分とelse部分のふたつの式は同じ型である
tnagatomi.icon 重複を無くすリファクタリングもテストが通ることを確認しながら行う。良い。
第7章 組とパターンマッチ
7.2 パターンマッチ
パターンマッチの最も簡単な構文の形
code:ocaml
match 式 with
パターン -> 式
7.3 構造データに対するデザインレシピ
テンプレート
入力データの方が定まるとそこから必然的に決まってくる関数本体の形のこと
tnagatomi.icon 問題 7.4のテストが模範解答でもコケるけど飛ばす
第8章 レコード
8.5 ユーザによる型定義
OCamlでは、あるレコードのフィールド名が他のレコードのフィールド名と重なってはいけない
第9章 リスト
9.1 リストの構造
リストの定義
空リスト [] はリストである。
firstが要素、restがリストならfirst :: restもリストである
自分自身を使って定義されたデータ型を再帰的なデータ型、あるいは自己参照をするデータ型と呼ぶ
:: の左右は対称でなく、常に左側には要素、右側にはリストがくる
9.2 リストの構文と型
OCamlではリスト中の要素は皆、同じ型を持たなくてはならない
一般的なパターンマッチの構文
code:ocaml
match 式 with
パターン1 -> 式1
| パターン2 -> 式2
| ...
| パターンn -> 式n
入力データ型がリストだった場合のmatch文のテンプレート
code:ocaml
match リスト with
[] -> リストが空だった場合の式
| first :: rest -> そうでなかった場合の式
一般的に警告には必ず対処
再帰関数にはlet recと書く
再帰的データの構造と1対1に対応した再帰のことを構造にしたがった再帰と呼ぶ
p.82 デザインレシピの決定版
第10章 再帰関数を使ったプログラミング
10.3 局所変数定義
局所変数を定義するには以下のような構文を使う
code:ocaml
let 変数名 = 式1 in 式2
第11章 自然数と再帰
11.4 リスト上の再帰との違い
自然数の構造にしたがった再帰をするときはn - 1以外に対しては再帰をしないよう注意
第12章 ダイクストラのアルゴリズム
12.5 駅名の重複の除去
tnagatomi.icon 問題 12.4で、駅が重複した場合にどちらを取り除くか書かかれてないから違う実装してたので解答に合わせた
第13章 一般化と高階関数
さまざまな一般化
データの一般化
似た関数の異なる部分を引数として受け取る関数を定義
関数の一般化
関数を引数として受け取る関数を定義
型の一般化
13.2 関数の一般化とmap
tnagatomi.icon 関数型言語に慣れていないと理解しにくいfirst-class (第一級) 関数、高階関数を実例を通して学べる非常にいい節
13. 5 関数を返す関数
tnagatomi.icon 関数の型を考える問13.3と問13.4に相当苦戦して時間をかなり使ってしまった。実用的には関数の型を答えられなくてもあまり問題ないかもしれないけど、パズルとして難しかった。
tnagatomi.icon 以下、関数の型の読み解き方を自分なりに理解した結果
考え方ひとつめ
例えばlet x f = f xの場合、
まずは右辺から考えて、左辺に適用する型を推測
f x は 'a -> 'b
次に左辺を考える
x fは上で推測した型を代入して'a -> ('a -> 'b)
ここで右辺に戻ると、f xが戻すのは'bであるので、結果は'a -> ('a -> 'b) -> 'b
もうひとつの考え方で、関数の型は右結合なので、'a -> ('a -> 'b) -> 'bは'a -> (('a -> 'b) -> 'b)である
これはどういうことかというと、引数xにaを与えると、引数fに('a -> 'b)をとって'bを返す関数を返すということ
こっちの考え方は上手く整理できてないけど、カリー化とかをもっと使いこなせるとより理解が進みそう
第14章 高階関数を使ったリスト処理
リストをひとつのデータとして扱うことで、より抽象度の高い思考ができるようになる
第15章 新しい形の再帰
一般の再帰を行う関数を作る際に注意すること
自明に答えが出るのはどのようなケースか
より小さな部分問題はどのようにしたら作れるか
再帰呼び出しの結果から全体の結果がどのように得られるか
停止性を示すには次の2つを示す
再帰呼び出しを行う際の部分問題が、何らかの意味でもとの問題よりも簡単になっていること
それを繰り返すと、有限回で自明なケースに帰着されること
第18章 例外と例外処理
オプション型を使った例外処理
tnagatomi.icon このへんはSwiftで触れてるのですんなり入ってくる 例外的な場合はあくまで例外として例外的に記述すべきで、本来の計算の記述が乱されては見通しが悪くなり、信頼の低下に繋がる
第19章 モジュール
モジュール
モジュールの宣言の構文
module モジュールの名前 = struct 本体 end
モジュールはオブジェクト指向言語におけるオブジェクトに近いもの
データとそれに対する操作をひとまとめに扱う
OCamlではモジュールを代表するような型にtという名前をよく使う シグネチャ
公開してもよいもののみをシグネチャに書いて外部に公開すべきでないものをモジュール内に隠蔽する
シグネチャの宣言の構文
module type シグネチャの名前 = sig 本体 end
外部インタフェースを規定するものととらえられる
抽象データ型 (Abstract Data Type)
データ構造の実現方法については言及せず、使い方のみ規定されるデータのこと
利点
モジュール性を高める
シグネチャがモジュールのとてもよい説明書になる
モジュールの入れ替えを容易にする
第20章 モジュールの開発
20.1 赤黒木への挿入
tnagatomi.icon 挿入の詳細が/icons/わからん.icon
1項目目
木が空なのにこの頂点の親が赤ってどういうこと?
次に挿入する時の話?
2項目目
「現在の頂点」って何を指している?
挿入する頂点とは別だよな?
「得られた木」ってのもわからん
「"プログラミングの基礎" 赤黒木」で検索したらnumb86さんもよくわからんって書いてた
赤黒木の挿入の説明がよく分からなかったのと、最後のヒープについては飽きてしまったので、やってない。
アルゴリズムとデータ構造ではなく、あくまでモジュールを使うことでインタフェースを変えずに実装を入れ替えられるという利点の勉強なので僕も飛ばそう
第21章 逐次実行
tnagatomi.icon ここでprint_stringが登場してようやく副作用のある関数が出てきた
ここまで純粋な関数だけ使って逐次実行も行わずプログラムを書いてきたんだな
だから書き慣れなかったのかも
当たり前に副作用があるプログラムばっかり書いてきたからなぁ
unit 型
「何も返さない」ことを示すための型
値は () だけで、ユニットと読む
21.5 実行の順序
インタプリタ、コンパイラの実装上の都合
このようにした方が引数をたくさん持つ関数を早く実行する方法がある
実行順序を意識しなくてはならないようなプログラムはあまりよいプログラムとはいえない
副作用のない純粋な関数を使っている場合は意識しなくてよい
第22章 値の書き変えと参照透過性
参照透過性を持つと、データの「現在の値」を気にする必要がない
変更可能なデータ(本書ではセルと呼ぶ)の構文
ref 初期値でデータを作成
!セルでセルの中身を取り出す
セル := 値でセルの中身を変更する
第23章 副作用命令を使ったプログラミング
副作用命令をうまく使う心がけ
副作用命令はモジュール内に隠蔽する
関数は「どこかを書き変える」という形にするのではなく「書き変えたものを返す」という形にする
プログラムを書くときには常に最新のデータのみを手元におき、古いものを再利用したりはしない
全体の感想
型が厳格なのでエラーを見つけやすい
レコードのフィールドの値を取り出すのに他の言語だと一般的なレコード.フィールドという表記を使わず、必ずmatch文を使うという方針なのでなかなか書き慣れなかった。パターンマッチが基本ということなのだろうけど。
相変わらず再帰関数が苦手で、第9章、第10章に手こずった
アルゴリズムが難しくて実装できないというよりは、この本でその時点で習った制限のあるOCamlの知識で問題を解く、ということに苦戦した感がある
若者のforループ離れが進む中、forが使えない縛りというのはタメになった
「プログラミングの基礎」というタイトルを見るとプログラミング初心者に向けた本のようにも思えるけど、関数型言語の考え方が色んな言語に取り入られる中、初心者でない人が改めて関数型プログラミングの考えを学ぶのにいい教材だと思った
テストプログラムの重要性を説いていて良いと思った