プログラミングの基礎を読んだ

プログラミングの基礎を読んだのでまとめ

はじめに

関数型言語を仕事でも個人でも使ったことがなかったので何かしら触ってみたいと思っていたところ知人に進められたのがきっかけで読み始めた。
情報系出身ではなくコンピュータサイエンスの基礎にあやふやな部分が少なくない自分にはとても良かった。

学んだこととプラスアルファ

この本から学んだことのまとめ
自分が学びになったことのまとめなので網羅的な要約ではないことに注意

変数

Ocamlの変数は基本的には一度定義すると後から変更することができない
- 他言語でいうところのconstのようなものだろうか
- 参照透過性という性質(後述)

型推論と型チェック

型を定義するとその型が何の型を受け取って何の型を返すのかを、関数内部の演算子などから推測することを型推論という
また定義された関数への引数の型が推論した型と合致しているかをチェックすることを型チェックという

# let add a b = a + b ;;
(* int2つを受け取り、int1つを受け取る関数であると推論している *)
val add : int -> int -> int = <fun>
# add "a" "b" ;;
(* int型が期待されているのにstring型が渡されたというエラーを発生させている *)
Error: This expression has type string but an expression was expected of type
         int

パターンマッチ

組(複数の値をひとまとめにしたもの)やレコード(ハッシュのようなもの)、型といった構造データからデータの中身を取り出す方法
- 入力が構造データの場合は行う
下記が典型的な形で、matchとwithに挟まれた式を実行し、その結果をパターンと比較する
- パターンは復数列挙できる

match 式 with
    パターン -> 式
  | パターン -> 式

レコード

定義された型のフィールドを省略して、レコードを作ることはできない
- パターンマッチでパターン変数に束縛する時は省略できる
型同士でフィールドの重複は許可されない
- 型推論と関係しているんじゃないかなと思う
  - パターンマッチの際にはフィールドを省略することができ、フィールドが1つでも成り立つが，複数の型で同一フィールドが使われていたら型推論できないはず。
意味のあるかたまりに対して一つの型を定義するのが望ましいプログラミングスタイル
- 他言語でも同様だと思う。

リスト定義

2つの定義によって帰納的に定められている。
自分自身を使って定義されたデータ型を再帰的なデータ型、あるいは自己参照をするデータ型と呼ぶ

空リスト[]はリストである
firstが要素、restがリストならfirst::restもリストである(自分自身を定義に使っている)

上記の定義よりリストのパターンマッチは空かそれ以外のケースの2通りで表すことができるようだ

match リスト with
    [] -> 式
  | first :: rest -> 式

またリストは内部的にはLinked Listになっているらしい
なので、リストを再帰的にパターンマッチしていくことは連結リストをheadから次のnodeを見ていくことに等しい

自然数定義

リストと同じように2つの定義かつ帰納的に定めることができる

0は自然数である
nが自然数ならn+1も自然数である

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

アルゴリズム関連はプログラミングコンテスト攻略のためのアルゴリズムとデータ構造でまとめてやった
- 関数型でもう一度やり直したら楽しそうだと思った(TODO)

高階関数

Ocaml の関数はfirst-classの値 -> 他の値と同じように扱うことができる
- 関数が引数にも返り値にもなることができる
関数を引数として受け取る関数のことを高階関数と呼ぶ
- OcamlのList.map、List.filterなどはそれにあたる

多相型と多相関数

'a, 'b といった型は型変数と呼ばれ、どのような型でもよいことを表す
- プログラム実行時に具体的な型に置き換わる
どのような型でもよいという性質のことを多相性(polymorphism)と呼ぶ
型変数を含むような型のことを多相型、多相型を持つ関数のことを多相関数と呼ぶ <-> 単相関数

infix関数とprefix関数

prefix関数
- 関数を引数の先頭に書き、引数を後に並べる関数。普通の関数
infix関数
- +演算子など。関数を引数の間に置く
- このinfix関数の中にはprefix関数に変換できるものがあり、それを使うと下記のようにプログラムを簡潔にできるかも

(* リスト lst の関数の和を求める関数 *)
(* sum : int list -> int *)
let sum lst = List.fold_right (+) lst 0

リストの性質

似たような性質のデータの集めたもの
- mapやfilter、fold_rightなどはそのような同種のデータを一括して扱うという意味で、リスト処理の本質を捉えていると言える
  - map : リストの全要素に対して同じ処理を施す
  - filter : リストの中から特定の要件を満たす要素を抽出する
  - fold_right : リストの各要素をまとめあげる
- 再帰的にプログラムすることで関数名を使わずに実行できるが、リストの各要素をバラバラではなく1つのデータとして扱いたい
  - 例えば下記の場合、 (enumerate n) は 1~nまでのリスト、(divisor n) は nの約数 という同種のデータの集まりになる

lee rec enumerate n =
  if n = 0 then []
  else n :: enumerate (n - 1)
let divisor n = List.filter (fun x -> n mod x = 0) (enumerate n)

再帰関数

データ構造にしたがった再帰 [] | first :: rest で分けられるようなデータ構造
- メリット
  - 簡単に関数を作ることができる
  - 停止性が明らか
一般的な再帰(データ構造に従わない再帰)
- 下記を考慮する必要がある
  - 自明に答えが出るのはどのようなケースか
  - より小さな部分問題はどのようにしたら作れるか
  - 再帰呼出しの結果から全体の結果がどのように得られるか

停止性の判定

一般の再帰は構造に従った再帰と違って、再帰呼出しの停止性が自明ではないので下記2点を確認する

再帰呼び出しを行う際の部分問題が何らかの意味でもとの問題よりも簡単になっていること
それを繰り返すと有限回で自明なケースに帰着されること

一般的な再帰

自明に答えが出るケースとそれ以外のケースについて考える
その上で下記４つのことを考える
1. 自明に答えが出るケースはどのような場合か
2. その場合の答えはなにか
3. 部分問題はどのように作ることができるか(1つとは限らない)
4. 部分問題の結果から全体の結果を得るにはどのようにすればよいか

情報の蓄積

欠落している情報を補うための引数アキュムレータ
- ex) 距離とそれまでの距離の合計を持つ型のリストを受け取り、距離の合計を埋めたリストを返す時、再帰的にリストを受け取ってもそれまでの距離という情報が欠落しているため解くことができないこのような時に、アキュムレータを使う。ただし、元の関数はリストだけを受け取って、リストだけを返したいのでその場合局所変数定義など内部的に用いる

バリアント型

まずは下記の例を参照

# type color_t = Blue | Red | Black ;;
- : type color_t = Blue | Red | Black
# Black ;;
- : color_t = Black

Blue、 Red、Black を構成子として、color_t という型を宣言している
このcolor_tがバリアント型

木構造

自己参照できるので下記のような木構造を作るのに使うことができる
- ex) 各ノード、リーフが整数を持つ木構造

type tree_t =
    Empty
  | Leaf of int
  | Node of tree_t * int * tree_t

# 使う時はこんな感じ
# tree1 = Empty
# tree2 = Leaf (1)
# tree3 = Node (Empty, 2, Node (Emply, 5, Leaf(9)))

多相型を使うとより汎用的な木構造の定義をできる
- ex) 各リーフ、ノードが連想(ハッシュと思ってよい)を持つ木構造

type ('a * 'b) association_tree_t =
    Empty
  | Leaf of 'a * 'b
  | Node of ('a * 'b) association_tree_t * 'a * 'b * ('a * 'b) association_tree_t

# 使う時
# tree1 = Empty
# tree2 = Leaf ("nekootoko3", 100)
# tree3 = Node (Empty, ("nekootoko3", 100), Node (Leaf ("pokemon", 100), ("occhan", 1500), Empty))

全通りを尽くしていない場合の対処

例外の場合にinfinityを返さなければならないケースなどが存在すると思う
- 例えばそれが空のリストを渡された場合に発生するとしたら、そもそも引数を2つ受け取るようにすることで解決できる
  - 引数の1つ目はリストには本来リストに含まれる値を渡し、その値とリストとで処理を行う。空のリストの場合には1つ目の値をそのまま返す
プログラムの構造を見直すことで網羅性高くうまい具合に例外も処理できる場合がある

オプション型

Ocamlに下記のような定義で組み込まれている
値が存在しない場合のNoneと何かしらが存在しているSome ('a)を区別することができる
- これによって該当値が見つからない場合は0を返すなど、特殊な返り値を使う必要が明確に存在しないことを表すことができる

type 'a option =
    None
  | Some of 'a

例外と例外処理

他言語でもよくあるような形だと思う
raise 定義されたエラー型で例外を発生させられる
exception 定義したいエラー型 (of int)でエラー型の定義もできる
下記のように例外の補足・処理を記述できる

try 式 with
    エラー型 -> 処理
  | エラー型 -> 処理

モジュール

通常のモジュールと変わらない
- 意味的にまとまりのある定義を1つにまとめる
外部に公開するインターフェースはシグネチャ(signature)と呼ばれる
シグネチャとモジュールの実体は例えば下記のように宣言できる

module モジュールの名前 : sig
  シグネチャの本体
  ex) type ('a, 'b) t
  ex) val empty : ('a, 'b) t
  ex) val search : ('a, 'b) t -> 'a -> 'b
end = struct
  モジュールの本体
  ex) ここでは上で外部宣言されている3つを実装する必要がある
    1. 連想を持つ`t`という型
    2. `t`という型の構成子からなるemptyという変数
    3. `t`という型、とtのキーとなっている型を受け取りtの値を返すsearchという関数
end

他言語のインターフェースと同じようなものだと思う
- モジュールがシグネチャを満たしていなければ、Error: Signature mismatch:というエラーが発生する
- シグネチャ、モジュールは別ファイルに分割もできるので、シグネチャは同じで内部実装を変えることもできる

副作用と参照透過性

値の受け渡し以外を行っている関数を副作用を持つ関数と呼ぶ
- 例えば文字の表示や渡された変数に代入して値を書き換えることがなどがそれにあたる
参照透過性とは一度定義された変数がその後変更されないという性質のことを指す
- この性質によりプログラムの途中や関数内で変数が書き換えられないことが保証された上で処理を書くことができるのが嬉しい
- Ocamlのint型やリストなどは参照透過性を持っている
- 参照型(ref)や配列(array)は参照透過性(referrence tranceparrency)を持たない型であり、データが不変であることが保証されない

参照透過性の喪失が問題を引き起こすのはモジュールのシグネチャ(インターフェース)だけが公開されており、破壊的変更を行うように見えない時など
下記例は極端だが、関数の利用者は配列要素の合計値を知りたいだけだが、実際には配列の各要素にそれまでの合計値を入れてしまっている
この配列を関数に渡す前の状態と思って利用すると思わぬ結果を引き起こす

(* 何の型を受け取って何を返すかだけが公開されている)
val add : int array -> int

(* 実際の実装 *)
let add arr =
  let sum = ref 0 in
  for i = 0 to (Array.length arr) - 1 do
    sum := !sum + arr.(i);
    arr.(i) <- !sum
  done;
  !sum

(* 実際に配列を定義して渡してみると、、、)
# let arr = [|1; 2; 3; 4; 5|] ;;
val arr : int array = [|1; 2; 3; 4; 5|]
# add arr ;;
- : int 15
# arr ;;
- : int array = [|1; 3; 6; 10; 15|]
(* 中身が書き換わっている *)

感想

非常によい本だと思った。
プログラミング初学者向けかと言われると怪しいが、少しプログラミングに慣れてきてプログラミングの新たなパラダイムを学びたい、
基礎的な概念をちゃんと身につけたいといったニーズには応えられる本なのではないかと思う。
丁寧に解説されているし、練習問題も多く入っているので身につけられることは少なくない。
オプション型って素晴らしいなぁと思ったり、よいコードを書くために必要なことも学べたんじゃないかと思う。
ただ関数型言語について分かったかと言われるとどうだろう。
それに関しては実際に自分でより多くのプログララムを関数型言語で書くことでその良し悪しを実感したり、
同じく関数型言語の別言語を学んでみることで関数型言語というパラダイムを共通項をまとめてみたりする経験が必要な気がする。
というわけで関数型言語を巡る冒険はしばらく続けていきたい。
さしあたり次はoz/mozartやる