本書について

本書の構成

増補改訂における，おもな変更点

本書で必要となる前提知識

謝辞

第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が持つ特徴的な機能

Column　世界で一番美しい？ クイックソート？

• Haskellの実装
• Haskell環境の構築
  • 対話的インタープリタGHCiの基本的な使い方
  • コンパイラGHCの基本的な使い方

0.11　まとめ

Column　現在関数型言語が採用されている分野/プロダクト

第1章　［比較で見えてくる］関数プログラミング ——C/C++，Java，JavaScript，Ruby，Python，そしてHaskell

1.1　部品を組み合わせる ——合う部品のみ合わせられる力

• 同じものから同じものへの変換を組み合わせる
• 2次元の座標変換
• C言語の場合 ——合わない部品
• JavaScriptの場合 ——合うかもしれない部品を作り/合わせる力
  • 組み合わせやすさは部品化の大前提
  • さらなる部品化
• Haskellの場合 ——合う部品を作り/合う部品のみ合わせる力

1.2　文脈をプログラミングする ——NULL considered harmful

• NULLが示すもの
• NULLの危険性
• 値がないことを扱う方法
  • C++（boost::optional）の場合 ——強力過ぎる例外処理のボイラープレート
  • Javaの場合 ——ネストしていくメソッドチェイン
  • Haskellの場合 ——行間に処理を発生させることのできる力

1.3　正しい並列計算パターン ——計算パターンの変化と影響

• C（OpenMP）の場合 ——アノテーションによる並列化
  • 要件追加に対応するための不用意な変更
  • 失敗の原因と正しい変更
• Haskellの場合 ——危険な並列化の排除
  • 要件追加に対応する変更
  • 純粋であることによって守られたもの

Column　それでも並列化は難しい

1.4　構造化データの取り扱い ——Visitorパターン

• Java（Visitorパターン）の場合 ——肥大化と引き換えの柔軟性
• Haskellの場合 ——型の定義/利用のしさすさ
  • コード量の差が生じる要因
  • 型を簡単に定義できる
  • パターンマッチがある

1.5　型に性質を持たせる ——文字列のエスケープ

• HTMLの文字列エスケープ
• Rubyの場合 ——性質の改変は利用者の権利
  • 「エスケープ済みである」という性質をクラスで保護/保証する
  • 保証を破れる言語機能の存在
• Haskellの場合 ——性質の保証は提供者の義務
  • 「エスケープ済みである」という性質を型で保護/保証する
  • 保証した性質を破らせない
• 「型システムが強力である」ことが意味するもの
  • 　——その場所場所で，適切な型付けの度合いを選択する余地がある

1.6　文書をルール通りに生成する ——安全なDSL

• 構造を持つ文書とルール
• プログラムから文書を生成する方法
• Pythonの場合 ——Jinja2で生成してみる
• Haskellの場合 ——言語内DSL
• 文脈にまで性質を持たせる

1.7　まとめ

第2章　型と値 ——「型」は，すべての基本である

2.1　Prelude ——基本のモジュール

• 基本のPreludeモジュール ——モジュールのimportの基本

2.2　値 ——操作の対象

• 値の基本
• リテラル ——値の表現，およびその方法
  • 数値リテラル
  • 文字リテラル
  • 文字列リテラル
  • ラムダ式 ——関数のリテラル
• 値コンストラクタ ——Haskellの真偽値True/Falseは値コンストラクタ

2.3　変数 ——値の抽象化

• 変数
• 定数
• 束縛

2.4　型 ——値の性質

• 型の基本
• 型の確認と型注釈
• 関数の型
  • カリー化
• 意図的に避けた型の確認
• 型検査
• 多相型と型変数
  • リスト
  • タプル
  • Either
  • Maybe
• 型推論

2.5　型を定義する ——扱う性質の決定

• 既存の型に別名を付ける ——type宣言
• 既存の型をベースにした新しい型を作る ——newtype宣言
• 完全に新しい型を作る ——代数データ型
  • 代数データ型の定義の基本 ——HTTPステータス
  • レコードを使う ——色空間RGBA
  • 多相型に定義し直してみる ——2次元の座標空間
  • 再帰型の定義 ——自然数
  • 多相型と再帰型 ——2分木
• 代数データ型と直積/直和

2.6　型クラス ——型に共通した性質

• 型クラスとは何か？
• 型クラスを調べる
• いろいろな型クラス
  • Show
  • Read
  • Num
  • Fractional
  • Floating
  • Integral
  • Eq
  • Ord
  • Enum
  • Bounded

2.7　よくある誤解 ——実行時型情報を利用したい

• 型を見て分岐したい
• 実行時型情報と型検査の相性

2.8　まとめ

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　まとめ

第4章　評価戦略 ——遅延評価と積極評価

4.1　遅延評価を見てみよう ——有効利用した例から，しっかり学ぶ

• たらい回し関数（竹内関数）
  • たらい回し関数の定義
  • たらい回し関数の実行——C++版
  • たらい回し関数の実行——Haskell版
  • たらい回しの省略
• 無限のデータ
  • レンジによる無限列
  • 再帰的定義による無限列
  • フィボナッチ数列，再び
  • 無限に広がる2分木
• 省略によるエラー耐性
  • 実行時のエラー
  • 最高の実行時エラー対策 ——それは，実行しないこと
• 平均値
  • 通常の平均値の計算
  • ちょっと変わった平均値の計算

4.2　評価戦略 ——遅延評価と積極評価のしくみ，メリット/デメリット

• 評価戦略と遅延評価
• 簡約
  • 正規形
  • 簡約の順番
  • 順番による結果の違い
• 積極評価
  • C言語
• 遅延評価
  • 最左最外簡約
  • WHNF（弱冠頭正規形）
  • サンク
  • グラフ簡約
• 積極評価と遅延評価の，利点と欠点
  • 積極評価の利点，遅延評価の欠点
  • 遅延評価の利点，積極評価の欠点

4.3　評価を制御する ——パフォーマンスチューニングのために

• 評価の進む様子を観察する
• サンクを潰す
  • コンストラクト時に潰す
  • 束縛時に潰す ——BangPatterns
  • モジュール単位で潰す ——積極評価のHaskell
  • サンクを潰したいケース ——スペースリークの恐怖
• Haskell版たらい回し関数を遅くする
• C++版たらい回し関数を速くする

4.4　まとめ

Column　パフォーマンスチューニングの第一歩 ——プロファイルを取る

第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）
  • 関数の型を決める
  • テストを書く
  • 「らしからぬ」コード
  • 「らしい」コード
  • トップダウンに設計/実装する
  • 型から関数を検索する ——型情報で検索できる「hoogle」
  • 設計/実装を進める
  • hlintで仕上げる ——よりHaskellらしいコードにするために
  • さらなる仕上げ ——もっとシンプルに
  • 今回の例から学ぶ，設計/実装，考え方の勘所
• 数独
  • ソルバの型を考える
  • 盤面状況を扱うデータ構造を決める
  • 何をすると数独が解けるか
  • まだ数値が埋まっていないマスの候補を選ぶ
  • マスに入れることのできる数値の候補を選ぶ
  • 入れることのできる数値の候補が最も少ないマスを選ぶ

6.3　制約を設ける ——型に制約を持たせる

• 制約をどのように表現するか
• 2の冪乗を要求するインタフェース
• 2の冪乗という制約を持った数の型
• 可視性を制御して性質を保護する
  • 命令型言語で型に制約を持たせる ——C++の例

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　依存パッケージのバージョンコントロール ——パッケージごとにどのバージョンを選択するか

• バージョンの選定および固定について
  • 1 各OSのパッケージシステムに用意されているものを使う
• 1 Cabalでローリングアップデートポリシーを定めて
• 　逐次更新していく
  • 3 Stackageに用意されているものを使う

7.6　バージョン間差の吸収 ——バージョン間の差分の検出から

• 複数開発環境の共存
  • Dockerを使う
  • Stackを使う
  • CIサービスを使う
• インタフェースが安定しないパッケージの扱い方

Column　Stackage/Stackを使う上での注意

7.7　まとめ

Column　HaskellでのWebアプリケーション作成 ——より一層，複雑な文脈を表現するモナドの必要性

第8章　各言語に見られる関数プログラミングの影響 ——Ruby，Python，Java，JavaScript，Go，Swift，Rust，C#，C++

8.1　変数を定数化できるか ——変更を抑止する

• 変数を定数修飾する
• メソッドを定数修飾する

8.2　関数の扱いやすさ ——関数/ラムダ式，変数への代入，関数合成，部分適用，演算子

• 各言語における関数/ラムダ式
• 変数への代入
  • 呼び出し方の差異 ——Rubyの例
  • ［関数ではない点1］Pythonのラムダ式 ——参照する環境の影響
  • ［関数ではない点2］Javaのラムダ式 ——定数制約の検査
  • ［関数ではない点3］C++のラムダ式 ——キャプチャ
• 「関数」を定義するポイント
• 関数合成
• 部分適用
  • Rubyの部分適用
  • C++，Pythonの部分適用
  • Goの部分適用
• 演算子
  • Swiftの演算子定義 ——オペレータ関数
  • Rubyの演算子定義

8.3　データ型定義とパターンマッチ ——Rust，Swift

• データ型定義とパターンマッチの例
• 網羅性検査
• 再帰的な構造

8.4　型システムの強化 ——静的型付けと型検査，型推論

• 静的型付けの導入
• 型推論の採用

8.5　リスト内包表記 ——Python，C#のLINQ

• Pythonのリスト内包表記
• C#のリスト内包表記 ——LINQ

8.6　モナド ——Java 8，Swift

• Swiftのモナド相当のインタフェース

Column　Python関数プログラミングHOWTO

• Stateモナド相当の実装例

8.7　コンパイル時計算 ——C++テンプレート

• C++テンプレートによる関数プログラミング
• C++テンプレートによるデータ型定義
  • 自然数
  • リスト
• C++テンプレートによる関数定義
• C++テンプレートの評価戦略
• C++テンプレートの限界

8.8　まとめ

Column　Safe navigation operator

Appendix

A.1　関数型言語が使えるプログラミングコンテストサイト ——ゲーム感覚で挑戦

• ［入門］プログラミングコンテスト
• Anarchy Golf
• AtCoder
• CodeChef
• Codeforces
• SPOJ

A.2　押さえておきたい参考文献＆参考情報 ——次の1手。さらに深い世界へ...

• 関数プログラミングについて
• Haskellについて
• 型システムについて
• 圏論について