関数プログラミング実践入門
関数プログラミング実践入門 ──簡潔で、正しいコードを書くために (WEB+DB PRESS plus)
技術評論社
著者：大川徳之
本書について
本書の構成
本書で必要となる前提知識
謝辞
目次
第0章 ［入門］関数プログラミング ——「関数」の世界
0.1 関数プログラミング，その前に ——実用のプログラムで活かせる強みを知る
関数プログラミングから得られる改善
0.2 関数とは何か？ ——命令型言語における関数との違い
関数プログラミングにおける関数
副作用
0.3 関数プログミングとは何か？ ——「プログラムとは関数である」という見方
プログラミングのパラダイム
命令型プログラミングのパラダイム
オブジェクト指向プログラミングのパラダイム
関数プログラミングのパラダイム —プログラムとは「関数」である
関数の持つモジュラリティ ──「プログラムを構成する部品」としての独立性
0.4 関数型言語とは？ ——関数が第一級の対象である？ 代入がない？
関数型言語であるための条件
関数のリテラルがある
関数を実行時に生成できる
関数を変数に入れて扱える
関数を手続きや関数に引数として与えることができる
関数を手続きや関数の結果として返すことができる
関数型言語と命令型言語
代入がないことから得られるもの
Column いろいろな関数型言語
0.5 関数型言語の特徴的な機能 ——型の有無，静的/動的，強弱
型付きと型なし
静的型付けと動的型付け
純粋
型検査
強い型付けと弱い型付け
型推論
Column 弱い型付けは何のため？
依存型
評価戦略
おもな関数型言語と命令型言語の機能一覧
0.6 なぜ今関数型言語なのか？ ——抽象化，最適化，並行／並列化
関数型言語の抽象化 ——数学的な抽象化とは？
関数型言語の最適化
関数型言語と並行/並列プログラミング
並行/並列という概念とプログラミングの難しさ
目的から考える並行/並列プログラミング
並行プログラミングの難しさ ——競合状態，デッドロック
並列プログラミングの一助 ——参照等価性の保証
Column 関数型言語と定理証明
0.7 関数型言語と関数プログラミングの関係 ——強力な成果を引き出すために
関数プログラミングの導入——命令型でも活かせる技法
関数型言語による関数プログラミングの導入
0.8 関数型言語の歴史 ——過去を知り，今後を探る
関数型言語のこれまで
関数型言語のこれから
進化の方向
普及可能性
0.9 関数型言語を採用するメリット ——宣言的であること，制約の充足のチェック，型と型検査，型推論
宣言的であることのメリット
制約の充足をチェックしてくれるメリット
型と型検査があることのメリット
型推論のメリット
0.10 本書で取り上げる関数型言語 ——Haskellの特徴，実装，環境構築
Haskellが持つ特徴的な機能
Haskellの実装
Haskell環境の構築
対話的インタープリタGHCiの基本的な使い方
コンパイラGHCの基本的な使い方
0.11 まとめ
Column 現在関数型言語が採用されている分野/プロダクト
第1章 ［比較で見えてくる］関数プログラミング——C/C++，JavaScript，Ruby，そしてHaskell
1.1 座標変換 ——部品を組み合わせる
同じものから同じものへの変換を組み合わせる
2次元の座標変換
C言語の場合 ——合わない部品
JavaScriptの場合 ——合うかもしれない部品を作り/合わせる力
組み合わせやすさは部品化の大前提
さらなる部品化
Haskellの場合 ——合う部品を作り/合う部品のみ合わせる力
1.2 NULL considered harmful ——10億ドル単位の過ち
NULLが示すもの
NULLの危険性
値がないことを扱う方法
C++（boost::optional）の場合 ——強力過ぎる例外処理のボイラープレート
Javaの場合 ——ネストしていくメソッドチェーン
Haskellの場合 ——行間に処理を発生させることのできる力
1.3 素数を数える ——正しい並列化とその仕様変更対応
C（OpenMP）の場合 ——アノテーションによる並列化
要件追加に対応するための不用意な変更
失敗の原因と正しい変更
Haskellの場合 ——危険な並列化の排除
要件追加に対応する変更
純粋であることによって守られたもの
Column それでも並列化は難しい
1.4 構造化データの取り扱い ——Vistorパターン
Java（Visitorパターン）の場合 ——肥大化と引き換えの柔軟性
Haskellの場合 ——型の定義/利用のしさすさ
コード量の差が生じる要因
型を簡単に定義できる
パターンマッチがある
1.5 文字列のエスケープ ——型に性質を持たせる
HTMLの文字列エスケープ
Rubyの場合 ——性質の改変は利用者の権利
「エスケープ済みである」という性質をクラスで保護/保証する
保証を破れる言語機能の存在
Haskellの場合 ——性質の保証は提供者の義務
「エスケープ済みである」という性質を型で保護/保証する
保証した性質を破らせない
「型システムが強力である」ことが意味するもの ——その場所場所で，適切な型付けの度合いを選択する余地がある
1.6 まとめ
第2章 型と値——「型」は，すべての基本である
2.1 Prelude ——基本のモジュール
基本のPreludeモジュール
2.2 値 ——操作の対象
値の基本
リテラル ——値の表現，およびその方法
数値リテラル
文字リテラル
文字列リテラル
ラムダ式 ——関数のリテラル
値コンストラクタ ——Haskellの真偽値True/Falseは値コンストラクタ
2.3 変数 ——値の抽象化
変数
定数
束縛
2.4 型 ——値の性質
型の基本
型の確認と型注釈
関数の型
カリー化
意図的に避けた型の確認
型検査
多相型と型変数
リスト
タプル
Either
Maybe
型推論
2.5 型を定義する ——扱う性質の決定
既存の型に別名を付ける ——type宣言
既存の型をベースにした新しい型を作る ——newtype宣言
完全に新しい型を作る ——代数データ型
HTTPステータス
色空間RGBA ——レコードの使い方
座標 ——多相型に定義し直してみる
自然数 ——再帰型の定義
2分木 ——多相型と再帰型
代数データ型と直積/直和
2.6 型クラス ——型に共通した性質
型クラスとは何か？
型クラスを調べる
いろいろな型クラス
Show
Read
Num
Fractional
Floating
Integral
Eq
Ord
Enum
Bounded
2.7 まとめ
Column コンストラクタ名に惑わされず，データの構造を捉える
第3章 関数——関数適用，関数合成，関数定義，再帰関数，高階関数
3.1 関数を作る ——既存の関数から作る，直接新たな関数の定義する
関数を作る方法
3.2 関数適用 ——既存関数の引数に，値を与える
関数適用のスペース
関数適用の結合優先度
関数の結果としての関数との関数適用
関数の2項演算子化
2項演算子の関数化
セクション
部分適用
3.3 関数合成 ——既存の関数を繋げる
関数合成と，合成関数
3.4 Haskellのソースファイル ——ソースファイルに関数を定義し，GHCi上でそれを読み込む
サンプルファイルの準備とGHCiへの読み込み
ソースファイルへの追加/編集，再読み込み
3.5 関数定義 ——パターンマッチとガード
一般的な関数の定義
パターンマッチ ——データの構造を見る
直接的な値にマッチさせる
コンストラクタにマッチさせる
複合的なパターンマッチ
パターンマッチの網羅性
asパターン
プレースホルダ
ガード ——データの性質を見る
網羅的でないガード条件
パターンマッチとガードを組み合わせる
caseとif
Column 「文」と「式」と，その判別
where/let
Column 場合分けの構文糖衣 ——実は，全部case
let式
where節
3.6 再帰関数 ——反復的な挙動を定義する関数
3つの制御構造と，再帰関数の位置付け ——連結，分岐，反復
再帰的定義
関数の再帰的定義
いろいろな再帰関数
length
take/drop
挿入ソート
再帰的な考え方のコツ
再帰の危険性とその対処
Column そんなに再帰して大丈夫か（!?）
3.7 高階関数 ——結果が関数になる関数，引数として関数を要求する関数
高階関数とは？
結果が関数になる関数
引数として関数を要求する関数
高階関数を定義する
いろいろな高階関数
filter
map
zip（zipWith）
foldl/foldr
scanl/scanr
実際に使ってみる ——部分列の列挙
3.8 まとめ
Column 世界で一番美しい？ クイックソート？
第4章 評価戦略——遅延評価と積極評価
4.1 遅延評価を見てみよう ——有効利用した例から，しっかり学ぶ
たらい回し関数（竹内関数）
たらい回し関数の定義
たらい回し関数の実行——C++版
たらい回し関数の実行——Haskell版
たらい回しの省略
無限のデータ
レンジによる無限列
再帰的定義による無限列
フィボナッチ数列，再び
無限に広がる2分木
省略によるエラー耐性
実行時のエラー
最高の実行時エラー対策 ——それは，実行しないこと
平均値
通常の平均値の計算
ちょっと変わった平均値の計算
4.2 評価戦略 ——遅延評価と積極評価のしくみ，メリット／デメリット
評価戦略と遅延評価
簡約
正規形
簡約の順番
順番による結果の違い
積極評価
C言語
遅延評価
最左最外簡約
弱冠頭正規形（WHNF）
サンク
グラフ簡約
積極評価と遅延評価の，利点と欠点
積極評価の利点，遅延評価の欠点
遅延評価の利点，積極評価の欠点
4.3 評価を制御する ——パフォーマンスチューニングのために
サンクを潰す
Haskell版たらい回し関数を遅くする
C++版たらい回し関数を速くする
4.4 まとめ
第5章 モナド——文脈を持つ計算を扱うための仕掛け
5.1 型クラスをもう一度 ——自分で作るという視点で
型クラスを定義する
型クラスのインスタンスを作る
型クラスインタフェースのデフォルト実装
［比較］他の言語の「あの機能」と「型クラス」
インタフェースの後付け
同じ型であることの保証
5.2 モナドの使い方 ——文脈をうまく扱うための型クラスインタフェース
文脈を持つ計算 ——モナドを使うモチベーション
どこかで失敗するかもしれない計算 ——Maybeモナド
複数の結果を持つ計算 ——リストモナド
同じ環境を参照する計算 ——((->) r)というモナド
型クラスとしてのモナド ——アクション，return（注意！），bind演算子
モナド則 ——インスタンスが満たすべき，3つの性質
「モナド則を満たしていないモナド型クラスのインスタンス」の例，とHaskellでの注意点
do記法
do記法とモナド則
5.3 いろいろなモナド ——Identity，Maybe，リスト，Reader，Writer，State，IO …
Identity ——文脈を持たない
Maybe ——失敗の可能性を持っている
現実世界と理想的な型の世界の接続と失敗
リスト ——複数の可能性を持っている
リスト内包表記
文脈の多相性
Reader ——参照できる環境を共有する
configを参照する処理
Writer ——主要な計算の横で，別の値も一直線に合成する
State ——状態の引き継ぎ
IO ——副作用を伴う
副作用を扱えるのに純粋と言える理由
5.4 他の言語におけるモナド ——モナドや，それに類する機能のサポート状況
他の関数型言語とモナド
命令型言語とモナド ——Javaのモナドとの比較
Optionalクラス
Streamクラス
メソッドチェーンの弊害 ——do記法のありがたみ
副作用による汚染は防げない
5.5 Haskellプログラムのコンパイル ——コンパイルして，Hello, World!
「普通」の実行方法について ——コンパイルして実行する
5.6 まとめ
Column 関数型言語で飯を喰う
第6章 オススメの開発/設計テクニック——「関数型/Haskellっぽい」プログラムの設計/実装，考え方
6.1 動作を決める ——テストを書こう
テスト，その前に
テストのためのライブラリ
doctest/QuickCheckによるテスト
doctestの導入
doctestを使う
QuickCheckを併用する
6.2 トップダウンに考える ——問題を大枠で捉え，小さい問題に分割していく
ランレングス圧縮（RLE）
関数の型を決める
テストを書く
「らしからぬ」コード
「らしい」コード
トップダウンに設計/実装する
型から関数を検索する
hlintで仕上げる
さらなる仕上げ ——もっとシンプルに
今回の例から学ぶ，設計/実装，考え方の勘所
数独
ソルバの型を考える
盤面状況を扱うデータ構造を決める
何をすると数独が解けるか
まだ数値が埋まっていないマスの候補を選ぶ
マスに入れることのできる数値の候補を選ぶ
入れることのできる数値の候補が最も少ないマスを選ぶ
6.3 制約を設ける ——型に制約を持たせる
制約をどのように表現するか
2の冪乗を要求するインタフェース
2の冪乗という制約を持った数の型
可視性を制御して性質を保護する
命令型言語で型に制約を持たせる
6.4 適切な処理を選ばせる ——型と型クラスを適切に利用し，型に制約を記憶させる
複数のエスケープ
変換履歴を持った文字列の型
変換されているかもしれない文字列のクラス
エスケープ方法の持つべき性質
各エスケープを定義する
モジュールを利用してみる
6.5 より複雑な制約を与える ——とても強力なロジックパズルの例
ロジックパズル ——3人の昼食
人間の推論
推論規則を型で表す
推論規則を使って答えを実装する
強力な型がインタフェース設計に与えた力
6.6 まとめ
第7章 Haskellによるプロダクト開発への道——パッケージとの付き合い方
7.1 パッケージの利用 ——パッケージシステムCabal
Haskellのパッケージシステム
公開されているパッケージを探す ——Hackage
公開されているパッケージを利用する ——cabal編
パッケージのインストール
パッケージのアンインストール
パッケージを利用する
公開されているパッケージを利用する ——Cabal sandbox編
sandbox環境を使う
7.2 パッケージの作成 ——とりあえずパッケージングしておこう
cabalize ——パッケージング作業
FizzBuzzライブラリ
cabalizeする
オススメのディレクトリ構成
モジュールの作成と公開
ビルド
パッケージング
バージョニング
パッケージ作成
Column Hackageへ公開しよう
7.3 組織内開発パッケージの扱い ——工夫，あれこれ
Cabalを通した利用 ——一番単純な方法
Cabal sandboxを通した利用
——パッケージデータベースを共有しない方法
組織内Hackageサーバの利用
パッケージを分けない
7.4 利用するパッケージの選定 ——依存関係地獄，選定の指針
依存関係地獄
Haskellにおける依存関係地獄
パッケージ選定上，有望な性質
コアに近いパッケージ
枯れたパッケージ
シンプルなパッケージ
依存関係が少ないパッケージ
Column 「バージョン上限」を設ける利点
依存関係が広いパッケージ
Column Cabal sandboxの光と影
インタフェースが安定しているパッケージ
7.5 依存パッケージのバージョンコントロール ——パッケージごとにどのバージョンを選択するか
バージョンの選定および固定について
各OSのパッケージシステムに用意されているものを使う
Cabalでローリングアップデートポリシーを定めて
逐次更新していく
7.6 バージョン間差の吸収 ——バージョン間の差分の検出から
複数開発環境の共存
Dockerを使う
hsenvを使う
CIサービスを使う
インタフェースが安定しないパッケージの扱い方
7.7 まとめ
Appendix
A.1 関数型言語が使えるプログラミングコンテストサイト ——ゲーム感覚で挑戦
［入門］プログラミングコンテスト
Anarchy Golf
AtCode
CodeChef
Codeforces
SPOJ
A.2 読んだおきたい参考文献 ——次の1手。さらに深い世界へ…
関数プログラミングについて
Haskellについて
型システムについて