Haskell勉強会

関数型プログラミングの学習日記

プログラミングの基礎

OCaml関数型プログラミングを学ぶ教科書がありました。

「プログラミングの基礎」という本です。

本書も読んで、関数型プログラミングの基礎を学んでみようと思います。

 

 

目次

(via プログラミングの基礎 株式会社サイエンス社

 

第1章 はじめに

  1.1 デザインレシピ
  1.2 使用する言語
  1.3 準備
  1.4 参考となる資料

 

第2章 基本的なデータ

  2.1 整数
  2.2 実数
  2.3 文字列
  2.4 真偽値
  2.5 そのほかのデータ

 

第3章 変数の定義

  3.1 変数の必要性
  3.2 変数定義の構文
  3.3 変数の実行方法
  3.4 ほかの言語の変数との違い

 

第4章 関数の定義

  4.1 関数定義の必要性
  4.2 関数定義の構文
  4.3 関数の型
  4.4 型推論と型チェック
  4.5 関数の実行方法
  4.6 関数定義に対するデザインレシピ

 

第5章 条件分岐

  5.1 条件分岐の必要性
  5.2 条件分岐の構文
  5.3 kyuyoの例
  5.4 式としてのif文
  5.5 条件分岐に対するデザインレシピ
  5.6 真偽値を返す関数
  5.7 条件分岐の実行方法

 

第6章 さまざまなエラー

  6.1 構文エラー
  6.2 未定義の変数
  6.3 型エラー
  6.4 実行時のエラー
  6.5 論理的なエラー

 

第7章 組とパターンマッチ

  7.1 組の構文
  7.2 パターンマッチ
  7.3 構造データに対するデザインレシピ
  7.4 パターンマッチの実行方法

 

第8章 レコード

  8.1 レコードの必要性
  8.2 レコードの構文
  8.3 レコードとパターンマッチ
  8.4 そのほかの記法
  8.5 ユーザによる型定義
  8.6 データ定義に対するデザインレシピ
  8.7 駅名と駅間の情報の定義

 

第9章 リスト

  9.1 リストの構造
  9.2 リストの構文と型
  9.3 リストとパターンマッチ
  9.4 再帰関数
  9.5 再帰関数に対するデザインレシピ
  9.6 テンプレートの複合
  9.7 駅名リストと駅間リストの整備

 

第10章 再帰関数を使ったプログラミング

  10.1 関数のネスト
  10.2 リストの中の最小値を求める関数
  10.3 局所変数定義
  10.4 パターンマッチつき局所変数定義
  10.5 ふたつのリストを結合する関数
  10.6 ふたつの昇順に並んだリストをマージする関数
  10.7 駅名・駅間リストからの情報の取得

 

第11章 自然数再帰

  11.1 自然数の構造
  11.2 自然数に基づいた再帰関数
  11.3 ベキ乗を求める関数
  11.4 リスト上の再帰との違い

 

第12章 ダイクストラアルゴリズム

  12.1 グラフ上の最短路問題
  12.2 ダイクストラアルゴリズム
  12.3 アルゴリズムの正当性
  12.4 プログラムにおける頂点と辺の定義
  12.5 駅名の重複の除去

 

第13章 一般化と高階関数

  13.1 データの一般化
  13.2 関数の一般化とmap
  13.3 多相型と多相関数
  13.4 値としての関数
  13.5 関数を返す関数
  13.6 確定点に隣接する点の最短距離の更新

 

第14章 高階関数を使ったリスト処理

  14.1 条件を満たす要素を取り出す関数
  14.2 各要素をまとめあげる関数
  14.3 局所関数定義
  14.4 名前のない関数
  14.5 infix関数とprefix関数
  14.6 完全数を求める関数

 

第15章 新しい形の再帰

  15.1 再帰関数の構造
  15.2 部分問題の生成
  15.3 補助関数の作成
  15.4 停止性の判定
  15.5 一般の再帰に対するデザインレシピ
  15.6 最短距離最小の点の分離
  15.7 例の作成とデバッグについて

 

第16章 情報の蓄積

  16.1 情報の欠落
  16.2 アキュムレータ
  16.3 アキュムレータの活用
  16.4 最初の完動プログラム
  16.5 プログラム作成のプロセス

 

第17章 再帰的なデータ構造

  17.1 バリアント型
  17.2 木
  17.3 再帰的なデータ構造に対するデザインレシピ
  17.4 2分探索木
  17.5 多相型の宣言
  17.6 停止性
  17.7 get_ekikan_kyoriの高速化
  17.8 全通りを尽くしていない場合の対処

 

第18章 例外と例外処理

  18.1 オプション型
  18.2 オプション型を使った例外処理
  18.3 オプション型を使った例外処理の問題点
  18.4 例外処理専用の構文
  18.5 例外処理の実際
  18.6 例外処理を使ったプログラミング
  18.7 最短路問題における例外処理

 

第19章 モジュール

  19.1 モジュールの構文
  19.2 2分探索木のモジュール
  19.3 モジュールインタフェース:シグネチャ
  19.4 抽象データ型
  19.5 そのほかのシグネチャの宣言法
  19.6 ファイルの分割と分割コンパイル
  19.7 2分探索木モジュールの使用

 

第20章 モジュールの開発

  20.1 赤黒木
  20.2 赤黒木への挿入
  20.3 赤黒木の再構成
  20.4 「または」のパターン
  20.5 赤黒木のモジュール化
  20.6 open文

 

第21章 逐次実行

  21.1 副作用を持つ関数
  21.2 unit型
  21.3 逐次実行の構文
  21.4 実行中の変数の表示
  21.5 実行の順序
  21.6 スタンドアローンのプログラム
  21.7 引数の渡し方

 

第22章 値の書き換えと参照透過性

  22.1 参照透過性
  22.2 呼び出し回数のカウント
  22.3 参照型と値の書き換え
  22.4 参照透過性の喪失
  22.5 変更可能なレコード
  22.6 配列
  22.7 配列の変更

 

第23章 副作用命令を使ったプログラミング

  23.1 ダイクストラ法におけるデータアクセス
  23.2 ヒープ
  23.3 ヒープへの挿入
  23.4 そのほかの操作
  23.5 ヒープのインタフェース
  23.6 副作用命令の影響について
  23.7 ヒープ実装の概要

 

第24章 まとめ―プログラミングとは―

  24.1 OCamlを習得して
  24.2 この先の道

 

索引

 

出版社情報

プログラミングの基礎 - 株式会社サイエンス社

デザインレシピを用いてプログラミングに必要な思考法を学び,メトロネットワーク最短路問題を解きながらデータ構造とアルゴリズムを身につける,関数型言語OCamlによる入門者のための教科・参考書.

 

「プログラミングの基礎」

サポート情報

(1)OCaml のインストールと日本語の表示法

(2)メトロネットワークデータ

(3)演習問題解答例、ほか

(4)参考となる資料

(5)改訂履歴(正誤表

(6)著者による授業紹介

 

「プログラミングの基礎」を使った授業紹介

お茶の水女子大学、理学部、情報科学の2年生を 対象とした授業「関数型言語」のビデオほかを公開しています。

この授業は反転授業 (flipped class) を行っており、 受講生は授業前に以下の予習を求められます。

  • 毎回の授業用に用意されたビデオを見て、 予習クイズに答えること。
  • 教科書の該当部分を読んで、 教科書問題に答えること。

授業時間中は特に内容の説明はせず、 受講生は別途、示される練習問題レポート問題を各自、解きます。

その際に生じた疑問点等について授業で個別に対応しています。

 

著者紹介

浅井 健一(あさい けんいち)

1992年 東京大学大学院理学系研究科修士課程修了

    東京大学助手を経て、

現在 お茶の水女子大学理学部情報科学科准教授

   博士(理学)

   専門:プログラミング言語

 

書評

著者のサポートページで、大学の授業で使う予習用の動画が用意されています。

動画を見ると、大変参考になります。

 

OCaml関数型プログラミングの基本を学ぶことができます。

構造化プログラミングの基本3要素を

  1. 順次 → (関数の)合成
  2. 分岐 → パターンマッチ
  3. 反復 → 再帰

という対応関係で学ぶ際に、(3)の再帰について

アキュームレーター」(状態を保持するための引数)の解説があったので、分かりやすいと思いました。

 

(参考)アキュームレーターとは?

「すごいErlangゆかいに学ぼう!」4章〜5章の途中 - 虎塚

f:id:hamamuratakuo:20171023142354p:plain

 

また、「デザインレシピ」と呼ぶデザインパターンの提示によって、学習を補佐してくれています。

 

本書を通じて、

を学んでみたいと思います。