プログラミングの基礎・学習内容まとめ

「プログラミングの基礎」を1章から17章まで読んで練習問題を解きました。
初学者でも本書を丁寧に読み進めていけば、OCamlを使って東京メトロの最短乗り換え経路を求めるプログラムの作成ができる構成となっています。
下記に、OCamlの型、パターンマッチなどの乗り換えプログラムを作るために必要となる知識をまとめました。
（不適切な内容、誤りなどございましたら指摘をいただけますと幸いです。）

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

作者: 浅井健一
出版社/メーカー: サイエンス社
発売日: 2007/03/01
メディア: 単行本
購入: 17人クリック: 409回
この商品を含むブログ (127件) を見る

基本的なデータ型

int型 ... 整数
float型 ... 実数

ポイント
int型とfloat型は違うデータ型として厳密に区別している
四則演算をする場合
int型 + - * / mod      A mod B = AをBで割ったときの余りを求める(int型のみ使用可能)
float型 +. -. *. /. のように、各演算子の後ろにピリオドが必要 また、**(べき乗)はfloat型のみ使用可能であるため、ピリオド不要

bool型 ... 真偽値 (true false) 　 

ポイント
比較演算子とともに用いられることが多い
not(～ではない) &&(AかつB) ||(AまたはB) 左から優先して実行される　
比較演算子はすべてのデータに対して使用することが可能

string ... 文字列  

ポイント
引用符("")で文字を囲む　^でふたつの文字列をくっつける

変数の定義

let 変数名 = 式
変数の書き換えはできない(他言語の定数に近い！)
変数名は小文字で始まらなくてはならない

関数の定義

①let 関数名 引数 = 式
または
②let 変数名 = fun 引数 -> 式

②はfun 引数 -> 式のみで名前のない関数として使用することができ、
この場合、補助関数などを作るときに、いちいち関数名を考える必要がなくなる、
他の場所で定義した関数名と被る心配がなくなるというメリットがある。
しかし、再帰関数は②の形では定義できないため必ず①の形で定義しなければならない。

条件分岐

if 条件１ then 式１
　　　　else if 条件２ then 式２　
　　　　　　　　　　 else 式３

条件１がなりたつなら式1を実行し、条件1は成り立たないが条件２が成り立つなら式２を実行する
条件１も条件２も成り立たないならば、式３を実行する

ポイント
条件は必ずbool型でなくてはならない
式はすべて同じ型でなくてはならない

内部に構造を持つデータ

組

いくつかのデータを並べてひとつのデータにしたもの
違う型を要素に並べてもよい
,(コンマ)さえあれば()で囲うひつようはないが、可読性が落ちるためしない

例
("oshima", 175.6)
このデータ型はstring * float

レコード

{名前1 = 値１; 名前2 = 値2} のように、名前（フィールドと呼ぶ）と値を紐づけることができる
値に文字列を与える場合は、必ずダブルクォートを使うこと。シングルクォートを使うとSyntax Errorになる
事前に新しい型の定義が必要（下記の型定義を参照）

例
{namae = "hiroki"; tensuu = 75; seiseki = "B"}

型定義

レコードを使う場合は、必ず自分で新しい型を定義し、使いたいフィールド名をOCamlに教えてあげなくてはならない。
まず最初に型を定義し、その後にレコードを扱う関数を定義する
type 新しく定義する型の名前 = その型の定義

例
type gakusei_t = {
  namae : string; (* 名前 *)
  tensuu : int; (* 点数 *)
  seiseki : string; (* 成績 *)
}

リストの定義
1.空リスト[]はリストである
2.firstが要素、restがリストなら、first :: restもリストである　（:: はコンスと読み、常に左側には要素、右側にはリストがくる）

書き方は２パターンあり、下記は両方同じリストを表現している
要素1 :: 要素2 :: 要素3 :: ... :: 要素n :: []
[要素1; 要素2; 要素3 ... 要素n]

パターンマッチ

複数のデータからできているデータの中身を取り出す方法（パターンの照合）

match 式１ with 
　　パターン -> 式２

手順
1.matchとwithに挟まれた式１を実行
2.その結果をパターンと照合
3.照合結果を使って式２を実行する

組の場合

let sum pair = match pair with
  (a, b) -> a + b 

sum (3, 5) = 8

レコードの場合

let tsuuchi gakusei = match gakusei with
  {namae = n; tensuu = t; seiseki = s} -> 
    n ^ "さんは" ^ string_of_int t ^ "点で成績は" ^ s ^ "です"

関数tsuuchiが引数gakuseiを受け取ると、パターンマッチでレコードの中身が取り出され、
それぞれの値がアルファベット（パターン変数）に入る。
関数tsuuchiはこれらパターン変数を使って値を返す。

リストの場合のパターンマッチと、再帰関数（recursion）

リストの要素を全て足した結果を返す関数
let rec sum lst = match lst with
    [] -> 0
  | first :: rest -> first + sum rest

定義しようとしている関数がその関数自身を呼び出す（再帰呼び出し）
再帰呼び出しを含む関数のことを再帰関数という
関数型言語でループを書く強力な手段
（letの後ろにrecをつける必要がある）

局所関数定義

let 変数名 = 式1 in 式2
式２の中でのみ変数名を式１と定義する
変数名には直接パターンを記述することもできる
inを抜けてしまうと変数名で式１を参照できなくなる（局所）

let x = 2 in x + x ;;
- : int = 4

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

OCamlに用意されている３つの高階関数

1.map リストの全要素に同じ処理を施す

map : ('a -> 'b) -> 'a list -> 'b list
let rec map f lst = match lst with
    [] -> []
  | first :: rest -> f first :: map f rest

2.filter 特定の要件を満たす要素を抽出する

filter : ('a - bool) -> 'a list -> 'a list
let rec filter p lst = match lst with
    [] -> []
  | first :: rest -> if p first then first :: filter p rest
                                       else filter p rest

3.fold_right 各要素の値をまとめ上げる（足し合わせたり、一つの文字列にしたり）

fold_right : ('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 )

感想
全体の５分の４ほど読み進め、乗り換え問題を解くプログラムを作成することができ、
初めて使用する言語を１から勉強してプログラムを作成する体験は自分にとって大きな自信となりました。
17章で2分探索木を使用した乗り換えプログラムを作成するまでに合計100時間程度かかりましたので、私と同じ初学者の方はあらかじめ相応の時間を投資する必要があると考えて学習スケジュールを立てたほうが良いかもしれません。
（あくまでプログラミング経験半年程度の私の場合です。要領の良い方はもっと早く終わると思います…！）
説明がわかりやすく、練習問題もおもしろいので、初学者でも本書を読みプログラムを書けば、プログラミングの事がより好きになるのは間違いありません。