magazine.gif関数プログラミング実践入門

本書について
本書の構成
本書で必要となる前提知識
謝辞

第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について
    • 型システムについて