目次
- 本書について
- 本書の構成
- 本書で必要となる前提知識
- 謝辞
- 目次
第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について
- 型システムについて