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

プログラミングの基礎、読み終わり

技術

プログラミングの基礎と言う本を読み終わった。

OCamlを勉強しつつも、プログラミングの基本のところをもう一度キチンと押さえてみるかなという感じで、読み始めた。

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

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

内容は、まさに基礎でそれほど深いところまでやっているわけではないのだけど、終章から引用するところによると、

… その過程でデータ構造が効率に与える影響, 特に木を使うことでプログラムが高速化されることを体感してきました。また, それ以外にも線形探索や2分探索, 基本的な整列法やクイックソート, 分割統治法, 再帰など, データ構造とアルゴリズムの基礎をほとんど扱っています。…

とあるように、基本的な部分がけっこう網羅されている。もともと情報系の大学の教科書としてかかれたものなので、うちの一回生のころの授業内容ともかぶる。

基本を確認するという点でもなかなか良い本だったのだけれど、やはり、うちには関数型言語のOCamlでそれらが説明されているのを読み解くのがおもしろかった。

普通なら手続き型ではなく関数型言語を使うことを、あらかじめひとこと断っておくようなものだけど、そういったこともない。どんどん関数型言語を使って説明がされていって、とまどうかと思いきや、この本に沿ってプログラムによる問題解決の手法を段階的に見ていくうちに、関数型言語によるプログラミングが合理的ですごく自然に思えてくるから不思議。

実際、文字を標準出力に表示するHello, Worldがかなり最後の方に例として出てくるのだけれど、そのころにはOCamlで副作用があるのが、きもちわるくてしかたなくなっていた。ある意味洗脳本やも。

また、この本では「デザインレシピ」と名付けられたプロセスにそってプログラムを書くことを奨励している。どういった順番でプログラムを書いていくべきかの指針で、例えば、プログラムの目的、例およびテストをきちんと書いてからプログラム本体を書くように言っている。まさにTDD。

思いつきでコードを書き進めていくんじゃなくて、目的をはっきりさせてからテストを書いて、コードを書かないといけない。これは、わかってはいても、なかなか実践できてなかったので、この機に徹底したいところであるな。

読みながらちょろっとOCamlのコードも書いたのでせっかくだから、すこしはりつけておく。

(* 目的: リストを左から畳み込む *)
(* fold_left: ('a -> 'b -> 'b) -> 'b -> 'a list -> b *)

let rec fold_left f init lst = match lst with
    [] -> init
  | first::rest -> fold_left f (f first init) rest

(* テスト *)
let l_test1 = fold_left (^) "" ["a"; "b"; "c"; "d"] = "dcba"
let l_test2 = fold_left (+) 0 [1; 2; 3; 4] = 10

(* 目的: リストを右から畳み込む *)
(* fold_left: ('a -> 'b -> 'b) -> 'a list -> 'b -> b *)

let rec fold_right f lst init = match lst with
    [] -> init
  | first::rest -> f first (fold_right f rest init)

(* テスト *)
let r_test1 = fold_right (^) ["a"; "b"; "c"; "d"] "" = "abcd"
let r_test2 = fold_right (+) [1; 2; 3; 4] 0 = 10

テストケース少なめだけどゆるして><。このプログラムをfold.mlとかいう名前にして、ocamlのプロンプトから読み込むと以下のように表示されます。

# #use "fold.ml";;
val fold_left : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>
val l_test1 : bool = true
val l_test2 : bool = true
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
val r_test1 : bool = true
val r_test2 : bool = true
# 

ほかにも、あまり使うことがなくて忘れそうになってた、バランス木とかヒープを復習できてよかった。

関数型言語とか、アルゴリズムとか、そういうあたりの潤いがたりていない人には、なかなかおすすめ。