Embed Size (px)
Citation preview
ii 編者まえがき
編者まえがき
コンピュータサイエンスはコンピュータに関係するあらゆる学問の中心にある．コ
ンピュータサイエンスを理解せずして，ソフトウェア工学や情報システムを知ること
はできないし，コンピュータ工学を理解することもできないだろう．
では，コンピュータサイエンスとは具体的には何なのか？ この問題に真剣に取り組
んだチームがある．それが米国の情報技術分野の学会であるACM（Association forComputing Machinery）と IEEE Computer Societyの合同作業部会で，2001年 12月 15日にFinal Report of the Joint ACM/IEEE-CS Task Force on ComputingCurricula 2001 for Computer Science（以下，Computing Curriculaと略）をまとめた．これは，その後，同じ委員会がまとめ上げたコンピュータ関連全般に関する
カリキュラムである Computing Curricula 2005でも，その中核となっている．さて，Computing Curriculaとはどのような内容なのであろうか？ これは，コン
ピュータサイエンスを教えようとする大学の学部レベルでどのような科目を展開するべ
きかを体系化したもので，以下のように 14本の柱から成り立っている．ComputingCurriculaでは，これらの柱の中身がより細かく分析され報告されているが，ここではそれに立ち入ることはしない．
Discrete Structures (DS) Human-Computer Interaction (HC)Programming Fundamentals (PF) Graphics and Visual Computing (GV)Algorithms and Complexity (AL) Intelligent Systems (IS)Architecture and Organization (AR) Information Management (IM)Operating Systems (OS) Social and Professional Issues (SP)Net-Centric Computing (NC) Software Engineering (SE)Programming Languages (PL) Computational Science and
Numerical Methods (CN)
一方，我が国の高等教育機関で情報科学科や情報工学科が設立されたのは 1970年代にさかのぼる．それ以来，数多くのコンピュータ関連図書が出版されてきた．しか
しながら，それらの中には，単行本としては良書であるがシリーズ化されていなかっ
たり，あるいはシリーズ化されてはいるが書目が多すぎて総花的であったりと，コン
ピュータサイエンスの全貌を限られた時間割の中で体系的・網羅的に教授できるよう
には構成されていなかった．
編者まえがき iii
そこで，我々は，Computing Curriculaに準拠し，簡にして要を得た教科書シリーズとして「Computer Science Library」の出版を企画した．それは，以下に示す 18巻からなる．読者は，これらが Computing Curriculaの 14本の柱とどのように対応づけられているか，容易に理解することができよう．これは，最近気がついたこと
だが，大学などの高等教育機関で実施されている技術者養成プログラムの認定機関に
JABEE（Japan Accreditation Board for Engineering Education，日本技術者教育認定機構）がある．この認定を“情報および情報関連分野”の CS（ComputerScience）領域で受けようとしたとき，図らずも，その領域で展開することを要求されている科目群が，実はこのライブラリそのものでもあった．これらはこのライブラリ
の普遍性を示すものとなっている．
1© コンピュータサイエンス入門 11© ヒューマンインタフェース入門
2© 情報理論と確率モデルの基礎 12© CGと3© プログラミングの基礎 ビジュアルコンピューティング入門
4© 計算の理論 13© 人工知能の基礎
5© 暗号のための代数入門 14© データベース入門
6© コンピュータアーキテクチャ入門 15© メディアリテラシ
7© オペレーティングシステム入門 16© ソフトウェア工学入門
8© コンピュータネットワーク入門 17© 数値計算入門
9© コンパイラ入門 18© 数値シミュレーション入門
10© システムプログラミング入門
執筆者について書いておく．お茶の水女子大学理学部情報科学科は平成元年に創設
された若い学科であるが，そこに入学してくる一学年 40人の学生は向学心に溢れている．それに応えるために，学科は，教員の選考にあたり，Computing Curriculaが標榜する科目を，それぞれ自信を持って担当できる人材を任用するように努めてきた．
その結果，上記 18巻のうちの多くを本学科の教員に執筆依頼することができた．しかしながら，充足できない部分は，本学科と同じ理念で開かれた奈良女子大学理学部
情報科学科に応援を求めたり，本学科の非常勤講師や斯界の権威に協力を求めた．
このライブラリが，我が国の高等教育機関における情報科学，情報工学，あるいは
情報関連学科での標準的な教科書として採用され，それがこの国の情報科学・技術レ
ベルの向上に寄与することができるとするならば，望外の幸せである．
平成 18年 3月
増永良文
ま え が きプログラミングをする上で最も重要なことは，正しく動作するプログラムを作
ることです。本書は，その方法を基礎からすべて余すところなく説明しています。
これまでにプログラミングの経験がない人は，本書を読むことでプログラミング
の基礎をすべて身につけることができます。また，これまでにプログラミングの
経験はあるもののどうも満足にプログラムを作ることができなかった人は，本書
を読むことでプログラミングに必要な思考法を習得できるでしょう。さらに，こ
れまでに十分なプログラミング経験を持っている人は，本書を読むことでプログ
ラミングに対する新しい考え方を身につけることができると思います。
本書で示すプログラミングの方法は，デザインレシピを使う方法です。デザイ
ンレシピというのは，プログラムを作る，デザインするときに使うレシピです。
プログラムを作るときには，そのプログラムで何をしたいのか，入力は何で出力
は何なのかなど多くのことを考えなくてはなりません。さらに，プログラムがで
きあがったらテストをすることも重要です。これらプログラムを作る際に踏むべ
きステップをひと通り定めたものがデザインレシピです。
デザインレシピは，プログラミングの大雑把なステップを定めたものに過ぎま
せん。しかし，その威力は絶大です。デザインレシピをしっかり習得すると，そ
の考え方はおよそすべてのプログラミングに対して適用できます。プログラミン
グ初心者がうまくプログラムを作れない原因のほとんどは，デザインレシピで考
えるべきステップをきちんと考慮できていないからです。逆に，一度，デザイン
レシピの考え方を習得すると，その後はとても楽にプログラムを作ることができ
るようになります。
デザインレシピの習得に加えて，本書ではさらにふたつのことを目指していま
す。ひとつはリストや木など各種のデータ構造とそれを使ったアルゴリズムを学
習すること，言い換えればコンピュータサイエンスの基礎であるデータ構造とア
ルゴリズムをおさえること，そしてもうひとつはある程度の大きさを持つ意味の
あるプログラムを作成することです。本書ではメトロネットワーク最短路問題を
とりあげ，そのプログラムを実際に作成します。メトロネットワーク最短路問題
のプログラムを作成するという具体的な目標があると，楽しく個々の課題に取り
ま え が き v
組めるとともに，データ構造とアルゴリズムが実際のプログラムの中でどのよう
に効率に影響を与えるかを体感できます。初学者の多くは，そのようなプログラ
ムを本当に自分が作れるのか最初は半信半疑でしょうが，順を追って取り組みさ
えすれば，ほとんどの人がプログラムを完成させることができます。これは大き
な達成感につながるとともに，アルゴリズムの理解にも大きく役に立ちます。
本書で使用する言語は OCaml という関数型言語です。本書で OCaml を採用
しているのは，この言語が簡単で使いやすいため，より大きなプログラムを作り
やすいことに加えて，高階関数など抽象度の高い高度なプログラミングが可能だ
からです。しかし，本書で学習する内容は関数型言語に特有のことではなく，ど
のプログラミング言語を使っていても当てはまることです。実際，本書にあるデ
ザインレシピにしたがった演習を行うと，その後 C によるプログラミングが楽
になったという声を頻繁に聞くようになります。関数型言語の考え方は Java な
どのオブジェクト指向言語にも次々に取り入れられています。今，関数型言語を
しっかり習得しておくことは，プログラミングの基礎を身につける上でも，最先
端のプログラミングを習得する上でも有益なことでしょう。
本書は，お茶の水女子大学 理学部 情報科学科の 2 年生を対象にして半期（1
回 90 分の講義を 14 回，プログラミングは演習課題として各自，授業時間外に行
う）で行っている授業の内容をまとめたものです。受講生は普通，C による 1 年
間のプログラミングの経験がありますが，本書はそれを仮定せずに書かれていま
す。必要なことはすべて丁寧に説明していますので，初学者が独学でプログラミ
ングの基礎を習得することも可能です。
本書を授業で使う場合，受講生がプログラミングの経験者なら本書の内容をす
べて扱うことができるでしょう。一方，プログラミングの初心者に対してより基
礎的な内容に重点をおいた授業を行う場合には，メトロネットワーク最短路問題
の最初のプログラムが完成する 16章と，木を使った高速化（17章）までをひとつ
の目安にするとよいでしょう。その際，難しければ高階関数を扱っている 13章と
14章を省くことも可能です。また，メトロネットワーク最短路問題を使わずにプ
ログラミングの基礎の習得のみを目指すことも可能です。本書はトピックごとに
章を立ててありますので，それぞれの目的に応じて適宜，内容を取捨選択してく
ださい。
本書の内容は，ほとんどがプログラミング一般について成り立つことですが，メ
vi ま え が き
トロネットワーク最短路問題に特有の説明もあちこちに現れます。本書では，メ
トロネットワーク最短路問題に特有の部分を , というマークで明示していま
す。ひとつの章や節全体がメトロネットワーク最短路問題に関連する説明の場合
には，章や節の名前に をつけています。また，大部分は一般的なプログラミン
グについての説明をしている節であっても，メトロネットワーク最短路問題につ
いての問題が含まれている場合には，節の名前に をつけています。あとから
メトロネットワーク最短路問題に関する部分を読み直したくなった場合には，こ
れらのマークを参照するとよいでしょう。
私にとって最初の執筆となる本書は，多くの方の力を借りて書き上げることが
できました。執筆に当たっての心構えを示し，叱咤激励してくださったお茶の水
女子大学 理学部 情報科学科の増永良文教授，執筆当初より種々の細かいアドバイ
スをくださった金子晃教授，共に励ましあって本ライブラリを執筆している情報
科学科内外の先生方，いろいろな演習問題のアイディアを出してくれたお茶の水
女子大学の学生の皆さんなど，多くの方のサポートを頂きました。また，私の大
学時代からの友人である中村紳吾氏，妻恵里には原稿を詳細に読んでもらい，そ
こから多くのコメントやフィードバックを得ることができました。サイエンス社
の田島伸彦，渡辺はるか両氏には，編集においてさまざまなわがままを聞いてい
ただきました。お世話になった全ての方々に，この場を借りて心より感謝申し上
げます。
2007 年 1 月 6 日
浅井 健一
目 次
第 1章 は じ め に 1
1.1 デザインレシピ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 使用する言語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 準 備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 参考となる資料 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
第 2章 基本的なデータ 7
2.1 整 数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 実 数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3 文 字 列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 真 偽 値 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5 そのほかのデータ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
第 3章 変 数 の 定 義 14
3.1 変数の必要性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 変数定義の構文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 変数の実行方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.4 ほかの言語の変数との違い . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
第 4章 関 数 の 定 義 18
4.1 関数定義の必要性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.2 関数定義の構文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.3 関 数 の 型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.4 型推論と型チェック . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.5 関数の実行方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.6 関数定義に対するデザインレシピ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
viii 目 次
第 5章 条 件 分 岐 33
5.1 条件分岐の必要性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.2 条件分岐の構文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.3 kyuyo の 例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.4 式としての if 文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.5 条件分岐に対するデザインレシピ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.6 真偽値を返す関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.7 条件分岐の実行方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
第 6章 さまざまなエラー 45
6.1 構 文 エ ラ ー . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.2 未定義の変数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.3 型 エ ラ ー . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.4 実行時のエラー . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.5 論理的なエラー . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
第 7章 組とパターンマッチ 50
7.1 組 の 構 文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507.2 パターンマッチ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517.3 構造データに対するデザインレシピ . . . . . . . . . . . . . . . . . . . . . . . . . . 547.4 パターンマッチの実行方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
第 8章 レ コ ー ド 58
8.1 レコードの必要性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588.2 レコードの構文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598.3 レコードとパターンマッチ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608.4 そのほかの記法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.5 ユーザによる型定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638.6 データ定義に対するデザインレシピ . . . . . . . . . . . . . . . . . . . . . . . . . . 648.7 駅名と駅間の情報の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
目 次 ix
第 9章 リ ス ト 70
9.1 リストの構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 709.2 リストの構文と型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729.3 リストとパターンマッチ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749.4 再 帰 関 数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789.5 再帰関数に対するデザインレシピ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819.6 テンプレートの複合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859.7 駅名リストと駅間リストの整備 . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
第 10章 再帰関数を使ったプログラミング 91
10.1 関数のネスト . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9110.2 リストの中の最小値を求める関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . 9510.3 局所変数定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9710.4 パターンマッチつき局所変数定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . 9910.5 ふたつのリストを結合する関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10210.6 ふたつの昇順に並んだリストをマージする関数 . . . . . . . . . . . . . . . . . 10310.7 駅名・駅間リストからの情報の取得 . . . . . . . . . . . . . . . . . . . . . . 105
第 11章 自然数と再帰 107
11.1 自然数の構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10711.2 自然数に基づいた再帰関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10811.3 ベキ乗を求める関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11011.4 リスト上の再帰との違い . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
第 12章 ダイクストラのアルゴリズム 112
12.1 グラフ上の最短路問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11212.2 ダイクストラのアルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11312.3 アルゴリズムの正当性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11812.4 プログラムにおける頂点と辺の定義 . . . . . . . . . . . . . . . . . . . . . . . . . 11812.5 駅名の重複の除去 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
x 目 次
第 13章 一般化と高階関数 120
13.1 データの一般化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12013.2 関数の一般化と map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12313.3 多相型と多相関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12613.4 値としての関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12813.5 関数を返す関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13013.6 確定点に隣接する点の最短距離の更新 . . . . . . . . . . . . . . . . . . . . . 133
第 14章 高階関数を使ったリスト処理 135
14.1 条件を満たす要素を取り出す関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . 13514.2 各要素をまとめあげる関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13714.3 局所関数定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14214.4 名前のない関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14314.5 infix 関数と prefix 関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14614.6 完全数を求める関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
第 15章 新しい形の再帰 150
15.1 再帰関数の構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15015.2 部分問題の生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15115.3 補助関数の作成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15515.4 停止性の判定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15815.5 一般の再帰に対するデザインレシピ. . . . . . . . . . . . . . . . . . . . . . . . . . 16115.6 最短距離最小の点の分離 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16315.7 例の作成とデバッグについて. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
第 16章 情 報 の 蓄 積 166
16.1 情 報 の 欠 落 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16616.2 アキュムレータ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16716.3 アキュムレータの活用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17016.4 最初の完動プログラム. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17316.5 プログラム作成のプロセス . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
目 次 xi
第 17章 再帰的なデータ構造 177
17.1 バリアント型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17717.2 木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18017.3 再帰的なデータ構造に対するデザインレシピ . . . . . . . . . . . . . . . . . . . 18317.4 2 分 探 索 木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18517.5 多相型の宣言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18917.6 停 止 性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19117.7 get_ekikan_kyori の高速化 . . . . . . . . . . . . . . . . . . . . . . . . . . 19217.8 全通りを尽くしていない場合の対処 . . . . . . . . . . . . . . . . . . . . . . 194
第 18章 例外と例外処理 197
18.1 オプション型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19718.2 オプション型を使った例外処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19918.3 オプション型を使った例外処理の問題点 . . . . . . . . . . . . . . . . . . . . . . 20018.4 例外処理専用の構文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20318.5 例外処理の実際 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20618.6 例外処理を使ったプログラミング . . . . . . . . . . . . . . . . . . . . . . . . . . . 20818.7 最短路問題における例外処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
第 19章 モ ジ ュ ー ル 211
19.1 モジュールの構文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21119.2 2 分探索木のモジュール . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21319.3 モジュールインタフェース：シグネチャ . . . . . . . . . . . . . . . . . . . . . . 21519.4 抽象データ型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21719.5 そのほかのシグネチャの宣言法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22019.6 ファイルの分割と分割コンパイル . . . . . . . . . . . . . . . . . . . . . . . . . . . 22119.7 2 分探索木モジュールの使用 . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
xii 目 次
第 20章 モジュールの開発 224
20.1 赤 黒 木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22420.2 赤黒木への挿入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22520.3 赤黒木の再構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22620.4 「または」のパターン. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22720.5 赤黒木のモジュール化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22920.6 open 文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
第 21章 逐 次 実 行 232
21.1 副作用を持つ関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23221.2 unit 型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23321.3 逐次実行の構文 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23421.4 実行中の変数の表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23621.5 実 行 の 順 序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23721.6 スタンドアローンのプログラム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23821.7 引数の渡し方 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
第 22章 値の書き変えと参照透過性 243
22.1 参 照 透 過 性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24322.2 呼び出し回数のカウント . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24422.3 参照型と値の書き変え. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24522.4 参照透過性の喪失 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24822.5 変更可能なレコード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25022.6 配 列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25122.7 配 列 の 変 更 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
目 次 xiii
第 23章 副作用命令を使ったプログラミング 254
23.1 ダイクストラ法におけるデータアクセス . . . . . . . . . . . . . . . . . . . . . . 25423.2 ヒ ー プ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25423.3 ヒープへの挿入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25523.4 そのほかの操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25723.5 ヒープのインタフェース . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25823.6 副作用命令の影響について . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26023.7 ヒープの実装の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
第 24章 まとめ ― プログラミングとは ― 263
24.1 OCaml を習得して. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26424.2 こ の 先 の 道 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
索 引 267
第1章は じ め に
ようこそ，プログラミングの世界へ。この本では，プログラミングの基礎，プログラムを作る上で考えなくてはならない
ポイントを余さず解説していきます。ずばり，目標は
メトロネットワーク最短路問題を解くプログラムを作ること
です。東京には多くの地下鉄が走っています。ある駅から別の駅まで，どの路線を使
えばよいのかは必ずしも明らかではありません。この本では，ふたつの駅名を与えら
れたら，そのふたつの駅を結ぶ最も短い経路をみつけるプログラムを作ります。例え
ば，渋谷から護国寺と入力したら半蔵門線を使って永田町で有楽町線に乗り換える経
路が，また茗荷谷から目黒と入力したら丸ノ内線から後楽園で南北線に乗り換える経
路が出力されます。
そんなプログラムを作ることができるだろうか，と不安に思う必要はありません。
対象としている読者は，これまでにプログラミングをしたことがない人たちです。プ
ログラミングに関する前提知識は何も仮定していません。必要なことはすべてひとつ
ひとつ順に説明していきますので，丹念に読み進めていきさえすれば誰でも最短路問
題を解くプログラムを作ることができるようになります。ですから，是非，楽しみに
読み進めてください。
本書に述べられていることは，ほとんどがプログラミング一般について成り立つこ
とばかりですが，メトロネットワーク最短路問題を解くことを目標に掲げている以上，
メトロネットワーク最短路問題に特有の説明もあちこちに現れます。本書では，メト
ロネットワーク最短路問題に特有の部分を , というマークで明示しています。ひ
とつの章や節全体がメトロネットワーク最短路問題に関連する説明の場合には，章や
節の名前に をつけています。また，大部分は一般的なプログラミングについての説
明をしている節であっても，メトロネットワーク最短路問題についての問題が含まれ
ている場合には，節の名前に をつけています。本書を一通り読み終わった後でメト
ロネットワーク最短路問題に関する部分をもう一度，読みたくなった場合には，これ
らのマークを参照するとよいでしょう。
第2章基本的なデータ
この章から，メトロネットワーク最短路問題を解くという目標に向かって一歩一歩，
進んでいきます。この章では，OCaml で使うことのできる基本的なデータを紹介し
ながら，OCaml インタプリタの使い方を覚えます。OCaml は，関数型言語の中でも
特に「強く型付けされた言語」と呼ばれます。これは，プログラム中に現れるすべて
のデータに型が付いている，ということを示しています。この章では，基本的なデー
タとあわせてその型も紹介していきます。
2.1 整 数
OCaml インタプリタに対して 3 ;; と入力してみましょう。これで OCaml インタプリタに対して「3 という式（プログラム）を実行してください」と指示している
ことになります。式の後に付けている ;; というのは，入力の区切りを示しています。
OCaml インタプリタは，この ;; をみて実行を開始します。
# 3 ;;
- : int = 3
#
3 と ;; の間には，スペースが入っても入らなくても構いません。OCaml では，単語の切れ目にスペースや改行を自由に入れることができます。
さて，3 を実行すると - : int = 3 という反応が返ってきます。これは「直前 (-)の結果の型は整数 (int) で，実行した結果の値は 3 である」と読みます。このようにOCaml インタプリタは，結果を表示する際，必ずその結果の型も一緒に表示します。int というのは，OCaml にあらかじめ定義されている型で，整数を表します。整数に対しては，通常の四則演算があらかじめ定義されています。加算は +，減算は -，
乗算は * です。
# 3 + 4 * 2 ;;
- : int = 11
# (3 + 4) * 2 ;;
- : int = 14
第3章変 数 の 定 義
2章では基本的なデータを紹介しました。しかし，基本的なデータだけでは，ほと
んど電卓と変わりません。より複雑なことをしようと思うと変数を使いたくなります。
この章では変数定義の方法を紹介します。
3.1 変数の必要性
前章では整数や実数などのデータをみてきました。いずれも基本的なものばかりで
したが，これらだけでもある程度の計算はできます。例えば，とある会社でアルバイ
トを雇っていたとしましょう。時給が 850 円で，A さんは週に合計 25 時間，B さんは 28 時間，C さんは 31 時間，働いたとすると，この会社は週に合計いくらアルバイト代を出さなくてはいけないでしょうか。それは次のような式を計算すればわか
ります。
# (25 * 850) + (28 * 850) + (31 * 850) ;;
- : int = 71400
#
その昔，電卓しかなかったころはこのような計算をしていたことでしょう。ですが，
この方法には問題点があります。それは，状況の変化に弱いことです。時給が 850 円から 950 円にあがったとしましょう。上のような計算をしていると，式の中に時給の850 という数字が 3 ヶ所に出てくるため，その 3 ヶ所をすべて 950 に書き換えなくてはなりません。3 ヶ所ぐらいなら書き換えてもたいしたことはありませんが，これが何百人もアルバイトを雇っていたのなら，その変更は大変なものになります。
この問題に限っていえば
# (25 + 28 + 31) * 850 ;;
- : int = 71400
#
のように時給をくくり出せば，変更は 1 ヶ所ですむようになります。しかし，給与体系が複雑になってくるといつでもこのようにくくり出せるとは限りません。
第4章関 数 の 定 義
OCaml のプログラムは，3章でみてきた変数定義と，この章で紹介する関数定義
とからなります。OCaml は関数型言語と呼ばれている通り，その中でも特に重要と
なってくるのは関数です。この章では，関数定義の方法を紹介するとともに，間違い
のない関数を作るための指針であるデザインレシピを示します。
4.1 関数定義の必要性
3章では，変数を導入することで同じ情報を何度も書くのではなく 1 ヶ所にまとめることを学びました。そうすることで，その情報が変更されてもその 1 ヶ所のみを書き換えるだけで求める値を得られることをみてきました。しかし，変数だけではすぐ
に不十分になってきます。3章のアルバイトの例をもう一度，考えてみましょう。変数を使うことで時給の変更には対応できるようになりましたが，では，基本給を導入
したらどうなるでしょうか。つまり，週に 100 円の基本給を支給し，それに加えて働いた時間に応じて時給 950 円を支給するように変更したらどうなるでしょうか。まず，変数を使って時給と基本給を表す変数を宣言しましょう。
# let jikyu = 950 ;;
val jikyu : int = 950
# let kihonkyu = 100 ;;
val kihonkyu : int = 100
#
このようにしておくと，将来，時給や基本給が変更になった場合にも，これらの変数
の宣言を書き換えるだけで対応できるようになります。しかし，このようにしても合
計金額の計算部分は書き換えなくてはなりません。以前の
# (25 * jikyu) + (28 * jikyu) + (31 * jikyu) ;;
- : int = 79800
#
では正しくなく
第5章条 件 分 岐
4章では，関数定義の方法と使い方をみてきました。そして，その際に重要となる
デザインレシピを紹介しました。しかし，これまでの関数はいずれも一本道で答えが
出るものばかりでした。これだけではとても単純な関数しか作ることができません。
少しでも複雑な関数を定義しようと思うと，すぐに場合分けが必要になってきます。
この章では，いろいろな条件による場合分け，条件分岐についてみていきます。
5.1 条件分岐の必要性
アルバイトの例を再び考えてみましょう。週に 30 時間以上，働いた人にはより優遇した時給 980 円を使うように給与体系を変更したとします。すでに給与を計算する専用の関数 kyuyo を用意しているので，その定義を変更するだけで対応できるはず
です。では，具体的に関数をどのように書き換えればよいでしょうか。まずは，優遇
時給を表す変数 yugu_jikyu を定義しましょう。
# let yugu_jikyu = 980 ;;
val yugu_jikyu : int = 980
#
そうすると，したいことは以下のように整理することができます。
働いた時間が
• 30 時間未満だったら kihonkyu + x * jikyu で給与を計算する。
• 30 時間以上だったら kihonkyu + x * yugu_jikyu で給与を計算する。
このような場合分けを行うには，まず働いた時間が 30 時間未満であるかどうかを調べなくてはいけません。働いた時間を x としましょう。すると，それが 30 未満であるかどうかを判断する式は x < 30 と書き表せます。x < 30 は全体としては bool
型，つまり真偽値になります。その値は x が 30 未満なら true になり，そうでなけ
れば false になります。これを使って場合分けを行います。
第6章さまざまなエラー
OCaml インタプリタを使ってプログラムを作っていると，途中でいろいろなエラー
に遭遇します。最初はいらいらさせられるエラーメッセージですが，OCaml インタ
プリタのエラーメッセージには間違いを特定するための様々な情報が記されています。
エラーメッセージを丹念に読むことが間違い探しの第一歩です。ここでは，よく起こ
るエラーについて解説します。
6.1 構 文 エ ラ ー
そもそも構文がおかしいときに起こるエラーが，構文エラー Syntax error です。
プログラムの構文に問題があり何を書いてあるのか理解できないときに OCaml はこのエラーを出します。syntax というのは「構文」，「文法」といった意味です。次の例は let 文で変数を宣言しようとしているのに = を書き忘れてしまったものです。
# let x 3 ;;
Syntax error
#
また，次の例は if 文で then 部分を書き忘れてしまったものです。
# if 2 > 3 then else 3 ;;
Syntax error
#
また，括弧の対応が不適切な場合にも構文エラーが出ます。
# 3 + 4) * 2 ;;
Syntax error
#
閉じ括弧を忘れているときには，それを指摘してくれます。
# (3 + 4 ;;
Syntax error: ’)’ expected, the highlighted ’(’ might be unmatched
#
第7章組とパターンマッチ
これまでに扱ってきたデータはいずれも整数や文字列など単純なものばかりでした。
しかし，実際に扱いたいデータがこのように単純な形をしていることはまれです。む
しろ，複数のデータが集まってひとつのデータを形成している方が普通でしょう。7
章から 9章までは，そのような複合データ，内部に構造を持ったデータをみていきま
す。まず最初にこの章では組を扱います。
7.1 組 の 構 文
組というのは，いくつかのデータを並べてひとつのデータにしたものです。一番わ
かりやすい例は，ふたつの実数を並べて作った 2 次元平面上の点でしょう。数学における 2 次元平面上の点は，ふたつの実数 x と y を使って (x, y) と表現されます。内部で x と y というふたつの実数を使ってはいますが，全体としてはひとつの点を表
しています。
OCaml において，組は要素の値をコンマで区切って表現します。
# (3.14, 2.71) ;;
- : float * float = (3.14, 2.71)
#
組の型は要素の型を * でつないだものになります。例えば，上の (3.14, 2.71) と
いう組はどちらの要素も float 型なので全体としては float * float 型になり
ます。
組は違う型の要素を並べても，また 3 つ以上の要素を並べても構いません。次の例は整数と真偽値を組にしたものです。
# (3, true) ;;
- : int * bool = (3, true)
#
また，次の例は整数と文字列と実数の 3 つを組にしたものです。
第8章レ コ ー ド
7章では，内部に構造を持つデータとして組をみてきました。この章では別の構造
データとしてレコードを紹介します。レコードを使うと構造データに含まれる各デー
タに対して意味のある名前をつけることができるようになります。これを使って，い
よいよメトロネットワーク最短路問題における駅の情報および駅のつながり方の情報
を表す方法をみていきます。
8.1 レコードの必要性
組はいろいろな値が単に “ , ” (コンマ) で区切られているだけでした。したがって何をどういう順番で組にしたかを覚えておかないと使うことができません。例えば，
生徒の名前と試験の点数を管理したいとしましょう。組を使って最初に生徒の名前を
文字列で，次に点数を整数で入れると約束しておけば
# ("asai", 70) ;;
- : string * int = ("asai", 70)
#
のように表現することはできます。しかし，これでは常に最初に名前が入っており次
に点数が入っているということを覚えておかなくてはなりません。さらに，将来，試
験の点数だけではなく成績も管理したくなったとしましょう。文字列で表された成績
を加えて 3 つの値の組に変更すると，組の中の名前や点数の位置が変わってしまうかも知れません。しかし，考えてみるとこれらがどういう順番で格納されているかはど
うでもよいことです。重要なのは名前が何であるか，点数はいくらか，成績は何であ
るかという情報です。このような場合には組を使うのではなくレコードを使います。レコードというのは名前のついたデータの集まりのことです。組は単にデータが並
んでいただけでしたが，レコードでは「学生の名前は asai，試験の点数は 70，成績は
B」のように各データに名前がついています。それぞれのデータが何を表しているのか
を明確にしているわけです。各要素に名前がつくと要素の順番には意味がなくなりま
す。上のレコードは，要素の順番を変えて「試験の点数は 70，学生の名前は asai，
第9章リ ス ト
これまでの章では，整数などの基本的なデータ，そして組やレコードといった構造
データをみてきました。学生の成績のデータなど複数の要素からなるデータについて
も，レコードにするとあたかもひとつのデータであるかのように扱うことができるよ
うになります。しかし，これまでにみてきたデータは，組やレコードなどいずれも決
まった大きさのものばかりでした。これくらいのデータなら人手で扱うこともできな
いことはありません。
コンピュータが威力を発揮するのは，似たような作業を大量の対象に対して行う場
合です。ひとりの学生の成績を記入するだけなら我々でも簡単にできます。数十人で
もどうにかなるでしょう。しかし，数百人，数千人になってしまったら，それを手作
業で行うのは大変です。そういうときにこそコンピュータが威力を発揮します。
この章では大量のデータ，任意の大きさのデータを扱うために提供されているリストという構造データをみていきます。
9.1 リストの構造
リストというのは同じ型のデータが任意の個数，並んだデータのことです。組は複
数のデータがあらかじめ決められた個数だけ並んでいました。それに対してリストは
要素がいくつ並んでいても構わない点で組とは大きく異なります。リストはデータを
好きな数だけ並べることができるため，とても柔軟性が高くいろいろな場面で使われ
ます。
しかし，リストは柔軟であるがゆえにその扱いは組よりも複雑になります。そのよ
うな柔軟なデータを系統的に扱うためには，リストの構造をきっちりと把握する必要
がでてきます。この節では，いくつかの例をみながらリストがどのように構成されて
いくかをみていきます。
最も簡単なリストは空のリストです。OCaml では空リストのことを []と書きま
す。これは，中に要素がない，要素が 0 個のリストです。要素がひとつのリストを作るには，空リストにひとつ要素を付け加えます。OCaml ではリストの先頭に要素を付け加えるには ::という命令を使います。この命令はリストを作る，構成するとい
第10章再帰関数を使ったプログラミング
9.5節では，再帰関数を作るときに使うデザインレシピを示すとともに，デザインレ
シピを使ったプログラミングを詳細にみてきました。このデザインレシピを使うと実
にさまざまな再帰関数を定義することができます。そして，作ることのできる関数の
幅がぐっと広がります。この章では，さらにいろいろな再帰関数を紹介しながら，再
帰関数を使ったプログラミングがどのようなものかをみていきます。
10.1 関数のネスト
最初は，接頭語を返す関数 prefix を補助関数 add_to_each を使って作ります。
接頭語というのは，先頭から任意の長さのところで切ったリストのことです。例えば
[1; 2; 3] というリストの接頭語は [1] と [1; 2] と [1; 2; 3] です。ここで
は，空リスト [] は接頭語に含まれないことにしておきます。add_to_each は接頭
語のリストを受け取ったら，各接頭語の先頭にもうひとつ要素を付け加える補助関数
です。
作る関数のイメージがわきにくいでしょうから，ここで例を作っておきましょう。
まずは add_to_each です。
(* テスト *)
let test1 = add_to_each 1 [] = []
let test2 = add_to_each 1 [[2]]
= [[1; 2]]
let test3 = add_to_each 1 [[2]; [2; 3]]
= [[1; 2]; [1; 2; 3]]
let test4 = add_to_each 1 [[2]; [2; 3]; [2; 3; 4]]
= [[1; 2]; [1; 2; 3]; [1; 2; 3; 4]]
add_to_each は整数をひとつと接頭語のリストを受け取ります。そして，各接頭語
の先頭に最初に受け取った整数を付け加えます。一方，prefix の方は，リストをひ
とつ受け取り，その接頭語のリストを返します。
第11章自然数と再帰
前章までに扱った再帰関数は，いずれもリストの構造にしたがった再帰をしていま
した。リストの構造にしたがった再帰は，プログラムの構造がリストの構造と 1 対 1
に対応しているため，比較的，理解するのが簡単です。これと同程度に簡単な再帰と
して，自然数の構造にしたがった再帰があげられます。この章では，自然数に基づい
た再帰関数をみていきます。
11.1 自然数の構造
自然数というのは 0 から始まり，1, 2, 3 と順に増え，これが無限に続いていきます。このような無限に続くデータ構造を扱うときには，まずそれを曖昧性のない形で
定義することが重要です。リストを定義したときと同じようにして自然数を定義して
みましょう。次のようになります。
• 0 は自然数である。• n が自然数なら n + 1 も自然数である。
ここでも自己参照の形が現れています。n + 1 が自然数であることを定義するのにn が自然数であることを使っているわけです。したがって自然数というのも再帰的な
データ型であるととらえることができます。
自然数を再帰的なデータ型ととらえると，その構造にしたがった再帰をする関数を
定義できます。その最初の一歩はデザインレシピのデータ定義です。リストの構造を
書き下したように自然数の構造をここで書き出してみましょう。次のようになります。
(* 自然数は- 0 0，あるいは- n + 1 ひとつ小さい自然数 n に 1 を加えたもの
（n が自己参照のケース）という形 *)
以下ではこの定義に沿って自然数に基づいた再帰関数を作っていきます。
第12章ダイクストラのアルゴリズム
これまでの章では，基本的なデータに始まり，変数，関数，構造データ，リスト，そ
して再帰関数などを学んできました。これだけの道具が揃うとかなりのプログラムを
作ることができます。実際，メトロネットワーク最短路問題に向けて，すでにローマ
字の駅名を漢字の駅名に変換する関数 romaji_to_kanji などいろいろな関数を作っ
てきました。しかし，最短路問題を解くためにはこれだけでは足りません。どうして
も最短路問題そのものを解く方法を知らなくてはなりません。そこで，この章では最
短路問題の解法のひとつであるダイクストラのアルゴリズムを紹介します。
ダイクストラのアルゴリズムをはじめとするグラフアルゴリズムには面白い内容が
たくさんあります。しかし，ここで触れる内容はそのごく一部，メトロネットワーク
最短路問題を解くために必要な最低限の知識のみです。これは，本書の目的がプログ
ラミングの基礎を学ぶことであり，グラフアルゴリズムを学ぶことではないからです。
グラフに関するより深い内容についてはグラフの専門書を参照してください。
12.1 グラフ上の最短路問題
最短路問題を解くときには，まず道がどのようにつながっているかをグラフという構造で表します。グラフというのは頂点が辺でつながっているような構造を抽象化し
たものです。例えば，図１２.１は 5 個の頂点 A, B, C, D, E が 6 本の辺でつながってできたグラフです。グラフの中でも各辺に対して重みが定義されているグラフのこ
とを重みつきグラフといいます。重みというのは頂点間の距離を抽象化したものと思
図１２.１ グラフの例
えばよいでしょう。図１２.１では，辺の重みを辺の近くに書いた数字で表しています。
重みつきグラフと始点，終点が与えられたときに，
始点から終点への最短路を求める問題がグラフ上の最
短路問題です。ここで最短路というのは始点から終点
へ至る道で，途中で通る道の重みの和が最小のものの
ことをいいます。
第13章一般化と高階関数
一般化というのは，同じプログラムをより多くの場面で使えるようにすることです。
3.1節や 4.1節では，変数や関数を使うことで同じ情報を 1 ヶ所にまとめられること
をみてきました。また，それによりプログラムの変更が容易になることを示しました。
これらも一種の一般化とみることができます。時給が 850 円でしか使えなかったプロ
グラムが，変数を使うことでいろいろな時給に対応することができるようになってい
るからです。
この章ではデータの一般化，関数の一般化，型の一般化などさまざまな一般化を紹
介します。一般化することで同じプログラムをより多くの場面で使うことができるよ
うになるとともに，より抽象度の高い思考をすることができるようになります。
13.1 データの一般化
まず最初にデータの一般化をみていきましょう。一般化を考える際に重要となるの
は同じ情報のくくりだしです。一度しか計算をしないなら一般化をする必要はありま
せん。同じような値に対して何度も計算をするからこそ一般化の意味が出てきます。
一般化は，同じようなプログラムの共通部分をくくりだすことから始まります。
例として 9.6節で示した関数 count_A をもう一度，みてみましょう。この関数は
gakusei_t 型のレコードのリストを受け取ってきたら，その中で成績が A の人の数
を返します。以下にもう一度，定義を示します。
(* 目的：学生リスト lst のうち成績が A の人の数を返す *)
(* count_A : gakusei_t list -> int *)
let rec count_A lst = match lst with
[] -> 0
| {namae = n; tensuu = t; seiseki = s} :: rest
-> if s = "A" then 1 + count_A rest
else count_A rest
この関数は成績が A の人の数を返しますが，もし成績が B の人の数が必要になった
らどうすればよいでしょうか。簡単です。count_A のときと同じようにデザインレ
第14章高階関数を使ったリスト処理
これまで，リストを扱う関数を多く紹介してきました。ここで少し振り返ってみま
しょう。そもそもなぜリストを使うのでしょうか。それは似たような性質のデータが
大量にあり，それらを一括して処理したいからです。たとえ型が同じであっても異質
のデータであれば最初からひとつのリストに入れたりはしません。そう考えると，リ
ストの各要素に対して一括して処理をするというのはリストを扱う上で本質的な操作
であるととらえることができます。
13章では，リスト処理を行う関数として map を紹介しました。この章では，リス
ト処理を行うほかの高階関数を紹介します。これらの高階関数を使うと，大量のデー
タを扱う関数をいとも簡単に作ることができるようになります。
14.1 条件を満たす要素を取り出す関数
最初に，リストの中から条件を満たす要素のみを抽出する関数 filterを紹介します。
map のときと同様にして似たような関数を一般化することで filter を定義します。
まず，整数のリストを受け取って，その中から正の要素のみを取り出す関数
filter_positive を考えてみましょう。以下のようなプログラムを書くことができ
ます。
(* 目的：受け取ったリスト lst から正の要素のみを取り出す *)
(* filter_positive : int list -> int list *)
let rec filter_positive lst = match lst with
[] -> []
| first :: rest ->
if first > 0 then first :: filter_positive rest
else filter_positive rest
では，整数のリストを受け取り，その中から 3 で割ったら 1 余る数のみ取り出す関数 filter_mod3_1 ならどうなるでしょうか。とある整数が 3 で割ると 1 余るかは，次の関数で判定することができます。
第15章新しい形の再帰
これまでにみてきたリスト上の再帰関数，自然数上の再帰関数はいずれもデータの
構造にしたがった再帰をしています。構造にしたがった再帰は，デザインレシピにし
たがっていれば簡単に関数を作れること，停止性が明らかなことなど多くの利点があ
ります。ですから，問題を解くにあたって最初に考える解は構造にしたがった解です。
しかし，問題が複雑になってくると構造にしたがった再帰だけでは解けない場合が
出てきます。また，解けたとしても効率が悪く，使い物にならない場合があります。
この章では，構造にはしたがわない再帰，より一般的な再帰をみていきます。
15.1 再帰関数の構造
一般の再帰に入る前に，再帰関数がどのような構造を持っているか，もう一度まと
めておきましょう。構造にしたがった再帰，特にリスト構造の上にできあがっている
再帰の場合，関数の形はほぼ次のような形になります。
(* 目的：受け取ったリスト lst の各要素の和を求める *)
(* sum : int list -> int *)
let rec sum lst = match lst with
[] -> 0
| first :: rest -> first + sum rest
このような再帰関数には，次のような特徴があります。まず第一に「自明に答えが出
るケース」と「そうでないケース」に場合分けをしています。ここで自明に答えが出る
というのは，再帰呼び出しをせずに手元にある情報のみから答えが計算できるという
意味です。上の例では，入力が空リストだった場合のことです。次に自明でないケー
スでは，より小さな部分問題に対して再帰呼び出しを行っています。より小さな部分
問題というのは上の例では単に rest のことです。最後に再帰呼び出しの結果を使っ
て全体の結果を計算しています。上の例では，再帰呼び出しの結果と first を加え
ている部分です。
構造にしたがった再帰を使っている間は，これらのポイントのうち実際に頭を使わ
第16章情 報 の 蓄 積
再帰関数を作成するときには，部分問題が何であるかを特定することがひとつの鍵で
す。構造にしたがった再帰では，部分問題は単にもとのデータよりも小さいデータの問
題を解くことでした。また，一般の再帰ではそう簡単ではなく，自分で新たに部分問題
を作る必要がありました。しかし，いずれの場合にも部分問題を特定できればその部分
問題を独立に解き，その結果を使って全体の結果を得ることができました。ここには，
部分問題は独立に解くことができるという仮定があります。しかし，この仮定は必ずし
も常に成り立つわけではありません。この章ではそのような問題をみていきます。
16.1 情 報 の 欠 落
次のような隣り合う点の距離と先頭からの距離の合計のフィールドを持つレコード
型 distance_t を考えてみます。
(* 距離と距離の合計を持っている型 *)
type distance_t = {
kyori : float; (* 距離 *)
total : float; (* 距離の合計 *)
}
今，この distance_t 型のリストを受け取ったら，先頭から各点までの距離の合計
を計算する関数 total_distance を考えてみましょう。例えば入力として
[{kyori = 0.3; total = 0.}; {kyori = 0.9; total = 0.};
{kyori = 1.4; total = 0.}; {kyori = 0.8; total = 0.}]
が与えられたなら，次のように各 total フィールドにはそれまでの距離の合計を入
れて返します。
[{kyori = 0.3; total = 0.3}; {kyori = 0.9; total = 1.2};
{kyori = 1.4; total = 2.6}; {kyori = 0.8; total = 3.4}]
今まで通りデザインレシピにしたがってこの関数のテンプレートを作ると以下のよう
になります。
第17章再帰的なデータ構造
構造にしたがった再帰は，一般の再帰とは違ってプログラムの構造がデータ構造と
1 対 1 に対応しているので，とてもわかりやすいものです。これまで構造にしたがっ
た再帰をする関数としては，リスト上の再帰関数と自然数上の再帰関数をみてきまし
た。しかし，構造にしたがった再帰の考え方はこれらのデータ構造にしか使えないわ
けではありません。むしろ，どのような再帰的なデータ構造に対しても適用できると
ころが構造にしたがった再帰の強力なところです。
この章では新しい再帰的なデータ構造として木を扱います。そして，木を扱う関数がリストを扱う関数と同様，デザインレシピを使うことで素直に簡単に作ることがで
きることをみていきます。
17.1 バリアント型
木について考える前に，木を定義する際に必要となるバリアント型について述べて
おきましょう。
8章では，レコードを紹介しました。レコードは複数のフィールドの集まりで，いろいろな要素がどれも存在するときに使います。一方，要素がすべて存在するのでは
なく，どれかひとつしか存在しない場合もあります。例えば，運動会で赤組か白組か
を表すデータを考えてみましょう。各選手は赤組か白組のどちらか一方にのみ属しま
す。このようなときには，どれかひとつを表すバリアント型のデータを使います。バリアント型のデータを作るときには，まずその型を宣言しなくてはなりません。赤組
か白組かを表す型 team_t は type 文を使って次のように宣言します。
(* 赤組か白組かを表す型 *)
type team_t = Red | White
ここで宣言した新しい型 team_t は，赤組を示す Red か，白組を示す White のどち
らかを値としてとります。Red あるいは White と書くだけで team_t 型の値になり
ます。
# type team_t = Red | White ;;
type team_t = Red | White
第18章例外と例外処理
ものごとの処理に例外はつきものです。例えば，夕食にカレーライスを作るとしま
しょう。それには八百屋でじゃがいもとにんじんとたまねぎを買ってこなくてはなり
ません。普通は八百屋に出向けばどれも置いてあります。その場合は何の問題も起き
ません。希望の野菜を購入します。しかし，たまたま売り切れということも考えられ
ます。例外的な状況の発生です。この場合はどうすればよいでしょうか。ない野菜を
ほかの野菜で代用することができるかも知れません。代用しにくければほかの八百屋
に買いにいくかも知れません。あるいは，そもそもカレーライスを作るのをあきらめ
て献立を変更するかも知れません。
例外的な状況はプログラムを作っていても起こります。例えば，プログラム中で整数
x を整数 y で割った余りを求めようとして x mod y と書いたとしましょう。これは多
くの場合，正しく動きます。ですが，たまたま y の値が 0 だったらどうなるでしょう
か。その場合は正しく余りを求めることができません。例外的な状況の発生です。
この章では，OCaml における例外処理をみていきます。
18.1 オプション型
最初に，特に例外を扱う特殊な構文を使用しなくても使える方法としてオプション型を使う方法を紹介しましょう。オプション型というのは次のような宣言で定義される型です。
(* ’a 型の値があるか値がないかのどちらかの型 *)
type ’a option = None (* 値なし *)
| Some of ’a (* ’a 型の値 *)
この型はあらかじめ OCaml に定義されているので，改めて宣言する必要はありません。型宣言なしで None と Some という構成子を使うことができます。None という
のは値がないことを示す構成子です。一方，Some というのは ’a 型の値が存在する
ことを示す構成子です。これらを合わせると ’a option 型は「普通は ’a 型の値で
あるけれども値がなくても構わない」ことを示します。
オプション型を使うと例外的な場合を通常の場合から分離することができます。こ
第19章モ ジ ュ ー ル
これまでの章では，プログラムはすべてひとつのファイルに書き込むことを前提に
して進めてきました。しかし，プログラムが次第に大きくなってくると，そのすべて
をひとつのファイルに入れて管理するのは大変になってきます。また，プログラムの
働きを理解する上でも，同じファイルにすべての関数が入っているのは望ましいこと
ではありません。すべての関数を平面的にとらえるのではなく，意味的につながりの
ある関数を機能単位で理解することが，大きなプログラムを作る上では重要になって
きます。そのような考え方をサポートするのがモジュールです。モジュールは意味的につながりのある関数のまとまりです。モジュールはひとつの
思考の単位になるとともに，分割コンパイルの単位，ライブラリの単位などにもなる
重要な概念です。この章ではモジュールについてみていきます。
19.1 モジュールの構文
モジュールの宣言には次のような構文を使います。
module モジュールの名前 = struct 本体 end
OCaml のモジュールの名前は，大文字で始まらなくてはならないという規則があります。本体には変数定義，関数定義，型定義などを自由に書くことができます。例え
ば，次に示すモジュールではふたつの変数を宣言しています。
(* 座標を表すモジュール *)
module Zahyou = struct
let x = 3.0 (* x 座標 *)
let y = 4.0 (* y 座標 *)
end
モジュール Zahyou はふたつの変数 x と y を中で宣言しています。これらの変数が
それぞれ座標平面上の x 座標と y 座標を表していると解釈すると，その意味的につ
ながりのある宣言をまとめているわけです。このモジュールを実際に OCaml インタプリタに入力してみましょう。すると次のようになります。
第20章モジュールの開発
モジュールを使うことの利点は，プログラムを機能単位に分割できること，抽象デー
タ型を実現できること，ほかのプログラムとは独立して開発できること，シグネチャ
さえ同じであればモジュールを入れ替えられることなど，たくさんあげることができ
ます。この章では，モジュールを独立して開発し，既存のモジュールと入れ替える実
例として，バランス木のひとつである赤黒木のモジュールを作成します。
20.1 赤 黒 木
17章で紹介した 2 分探索木は，場合によっては左右のバランスが悪くなり探索の効率が落ちてしまうことがあります。極端な場合として，ふたつの部分木のうち片方
がいつも Empty だったらリストと同じになってしまいます。そこで，バランスが悪
くなったときに木の形を作り替えて，バランスを保つことを考えます。このようにバ
ランスを保つ木のことを総称してバランス木 (balanced tree) と呼びます。ここではバランス木のひとつである赤黒木 (red-black tree) を紹介します。赤黒木というのは，2 分探索木の各節に赤または黒の色がついているもので，さら
に次の 2 条件を満たすような木のことです。
• 木の根から空の木に至るすべてのパスにおいて黒い頂点の数は同じである。• 赤い頂点の子はどちらも必ず黒である。（言い換えれば赤い頂点が連続することはない。）
色は節にのみついているので空の木には色はないのですが，便宜的に黒であると考え
ておくとつじつまが合います。
例えば，図２０.１ のような木を考えてみましょう。黒の頂点は黒い四角で表し，赤の頂点は青い四角で表しています。 は空の木のです。この木は，根である頂点 Aから葉である空の木に至るすべてのパスにおいて途中に現れる黒の頂点の数は（空の
木は数えないことにすると）2 です。さらに，赤い頂点である B, D, F, H の親や子は皆，黒になっています。したがってこの木は上の 2 条件を満たすので赤黒木です。赤黒木は，黒の頂点しか現れていなければ完全にバランスした木になっています。
第21章逐 次 実 行
関数型言語におけるプログラムはいずれも入力を受け取り，何らかの計算を行って
その結果を返す形になっています。これは，プログラムというものが，そもそもいろ
いろな入力に対する計算結果を求めるものであることを考えると自然なことです。入
出力に着目すると，内部でどうやって答えを求めているかを考えることなくその関数
の働きを理解することができます。デザインレシピにおいて目的を考えることが重要
である理由のひとつはここにあります。
しかし，いろいろなプログラムを作っていると，どうしても入力と出力の関係だけ
では書き表しにくいものも出てきます。そのひとつの例は，結果の表示です。複雑な
計算を行ったらその結果をきれいな形に表示したいところです。ダイクストラのアル
ゴリズムを使って最短路問題の結果をレコードの形で得たとしましょう。結果として
は単にレコードをみせるのではなく，最初に起点の駅名を表示し，次に経路を順に表
示し，最後に最短距離を表示して改行せよというような指示を出したいわけです。こ
の章ではそのようなことを行う方法をみていきます。
21.1 副作用を持つ関数
OCaml で文字列を画面に表示するには print_string という命令を使います。
この関数は文字列を受け取ったらそれを画面に表示します。
# print_string "こんにちは" ;;
こんにちは- : unit = ()
#
print_string は文字列を表示するだけで改行はしないので「こんにちは」の後に
直接 OCaml の返答が続いています。OCaml の返答である「- : unit = ()」は
「返ってきたものの型は unit で値は () です」と読みます。unit 型については次節
で触れますので，ここではこういうものだと思っておいてください。
この関数は，これまでにみてきた関数とは大きく違う点がひとつあります。それは
値を受け渡すこと以外の作用を持っている点です。print_string は文字列を受け取
ると () を結果として返します。しかし，その返ってくる値はどうでもよく，この関数
第22章値の書き変えと参照透過性
21章では，副作用を持つ関数として print_string など画面にメッセージを出力
する命令をみてきました。これらの関数は，副作用を持つといっても画面の表示が変
化するだけで，計算した値が変化してしまうことはありません。この章では，実行の
副作用として値が変化してしまうようなものについてみていきます。
22.1 参 照 透 過 性
これまでに紹介してきたプログラムでは，データは一度，作られるとその後で変化
することはありませんでした。例えば
# let a = [1; 2; 3] ;;
val a : int list = [1; 2; 3]
#
のように a という名前のリストを作ったとしましょう。もし，このリストの各要素に
1 を加えたくなったら
# let b = List.map (fun x -> x + 1) a ;;
val b : int list = [2; 3; 4]
#
のように新たに別のリスト b を作ることで対応してきました。ここで b が a とは別
のリストであることは，b を作った後にもう一度 a の値を調べてみればわかります。
# a ;;
- : int list = [1; 2; 3]
#
b を作った後も a は相変わらずもとと同じリストのまま変化していません。このよう
に，関数型言語では基本的に一度，作ったデータは変わることがなく，未来永劫その値
を持ち続けます。この性質を，データが参照透過性 (referential transparency)を持つといいます。データはいつ参照しても濁ることなく同じであるというニュアン
第23章副作用命令を使ったプログラミング
22 章では副作用命令の紹介を行いました。副作用命令を使うと参照透過性が失わ
れるため，うまくプログラムを作らないとプログラムがとてもわかりにくくなるとと
もに，信頼性も低くなってしまいます。副作用命令を使うときでも，ほとんどの部分
を関数型でわかりやすく書き，どうしても必要なときにのみきちんと制御・把握でき
る範囲で副作用命令を使うというのが正しい方針です。この章では，そのような副作
用命令の使い方の例としてヒープというデータ構造を紹介します。
23.1 ダイクストラ法におけるデータアクセス
これまでに作ってきたメトロネットワーク最短路問題のプログラムでは，高速化の
手段として駅間情報の取り出しに木構造を用いました。しかし，ダイクストラのアル
ゴリズムのメインループで使われる未確定の駅の情報については相変わらずリストを
使っています。ですが，この部分もきちんと考察を加えると効率化することができま
す。それにはまず駅の情報がどのように使われるかを考察します。ダイクストラのア
ルゴリズムをみると
• 最短距離最小の駅を取り出す•（確定した駅に接続している駅の）最短距離を更新する
というふたつの操作が必要です。単純に考えると，未確定の駅を最短距離の順に並べ
ておけば最短距離最小の駅を取り出すのは簡単です。しかし，最短距離を更新するた
びに全体を並べ直すのは時間がかかります。そこで，上記ふたつの操作（のみ）に適
したデータ構造であるヒープを使うことを考えます。
23.2 ヒ ー プ
ヒープというのは木構造の一種です。ヒープに入っているデータの数を n としま
しょう。ヒープは，値が最小のものをとってくるのは n に関わらず定数時間，また値
の更新は log n に比例する時間でできるようなデータ構造です。n 個のものを完全に
第24章まとめ―プログラミングとは―本書では，メトロネットワーク最短路問題を題材にしてプログラミングの基礎を扱っ
てきました。最初に掲げた目標は，メトロネットワーク最短路問題を解くプログラム
を作成することに加え，データ構造とアルゴリズムの基礎を身につけること，そして
正しいプログラムを作る方法を身につけることでした。ここまで読み進めてきた今，
皆さんはこれらの目標をほぼ達成しています。実際，メトロネットワーク最短路問題
については，16章で最初のプログラムを作り上げ，その後，さまざまな拡張，高速化を行ってきました。その過程でデータ構造が効率に与える影響，特に木を使うことで
プログラムが高速化されることを体感してきました。また，それ以外にも線形探索や
2 分探索，基本的な整列法やクイックソート，分割統治法，再帰など，データ構造とアルゴリズムの基礎をほとんど扱っています。すでに皆さんは，プログラミングの基
礎，データ構造とアルゴリズムの基礎を両方とも身につけています。
そればかりではありません。皆さんは「正しいプログラムを書く方法」としてデザ
インレシピを習得しました。プログラムを書けといわれると，どうしても思いつきで
「何となく」書いてしまいがちですが，デザインレシピはそれを厳しく戒めています。
問題をきちんと理解し，入出力を把握する，そして入力データから素直に導かれる形
にプログラムを組み，完成したら必ず動作の確認を行う。このようにしてはじめて，
正しく動くプログラムを作れるようになっていきます。プログラムを作るのが上手な
人は，実はデザインレシピに相当することをいつも念頭に置きながらプログラミング
をしているのです。
もちろん，デザインレシピだけですべての問題が解けるようになるわけではありま
せん。デザインレシピは単にプログラミングの方法論を述べているだけですから，問
題を解く具体的な方法，アルゴリズムは自分で考えなくてはなりません。問題解決の
本当の難しさはここにあります。しかし，この段階でもデザインレシピは役に立ちま
す。問題を整理して，入出力を明らかにし，例を考えることは，アルゴリズムを考え
る際にも必須のことです。
このように考えてくると，デザインレシピは問題解決の中でも「プログラミング」の
部分に関する指針を与えていると考えることができます。問題解決をアルゴリズムの
索 引数字・記号
2 分木 181
2 分探索 185
2 分探索木 185
! 246
"" 10
"..." 10
#use 29
&& 11
’a 126
(...) 146
() 233
(*...*) 27
* 7, 50
** 9
*. 8
+ 7
+. 8
, 50
- 7
-. 8, 40
-> 22
. 62, 212
/ 8
/. 8
:: 70, 72
:= 246
; 59, 72, 234, 252
;; 7
< 12
<- 251, 253
<= 12
<> 12
= 12
> 12
>= 12
@ 103, 155
[...] 72
[] 70, 72
[|...|] 252
^ 10
_ 77
{...} 59
| 75, 178, 228
|| 11
欧 字
<abstr> 217
array 252
Array.get 252
Array.length 253
Array.set 253
as 88
assert 229
assoc 193, 207
bool 11
dijkstra 174
dijkstra_main 174
ekikan_t 68
ekimei_t 68
eki_t 118
enumerate 148
exception 204
false 11
268 索 引
filter 136
float 8
float_of_int 159
fold_right 138
<fun> 22
fun 143
get_ekikan_kyori 105, 194, 209
global_ekikan_list 90
global_ekimei_list 89
if 34
Illegal character 46
infinity 9
infix 関数 146
insert_ekikan 193
inserts_ekikan 193
int 7
int_of_string 241
koushin 134, 143, 146, 209
length 84, 126, 137
let 15, 20
let rec 80
let in 97, 142
list 73
List.append 103
List.assoc 207
List.filter 137
List.fold_left 173
List.fold_right 141
List.iter 248
List.length 84
List.map 126
make_eki_list 118, 146
make_initial_eki_list 146
map 124
Match_failure 77
match ... with 51, 75
max 185
max_int 95
min_int 95
mod 8
module 211
module type 215
mutable 250
neg_infinity 10
None 197
No_such_station 210
not 11
OCamlMakefile 5, 221, 238
of 179, 204
open 231
option 197
prefix 関数 146
print_eki 235
print_float 235
print_int 235
print_newline 234
print_string 232
raise 203
rec 80
ref 246
romaji_to_kanji 105, 210
saitan_wo_bunri 163,164,195,196
seiretsu 119
shokika 119, 146
索 引 269
sig 212, 215
Some 197
sqrt 124
string 10
string_of_float 106
string_of_int 60
struct 211
Syntax error 45
Sys.argv 241
true 11
try ... with 205
type 63
Unbound constructor 46
Unbound value 46
unit 233
あ 行
赤黒木 224
アキュムレータ 168
駅間 68
エラトステネスのふるい 163
オプション型 197
重みつきグラフ 112
か 行
階乗 108, 239
型推論 23
型チェック 24
型変数 126
空の木 180
空文字列 10
空リスト 70, 72
完全数 147
木 180
局所関数 142
局所変数 97
クイックソート 151
組 50
グラフ 112
高階関数 126
構成子 178
構造にしたがった再帰 81
コメント 27
コンス 71
さ 行
再帰関数 80
再帰的なデータ型 72
再帰呼び出し 80
参照型 246
参照透過性 243
シグネチャ 212
自己参照 72
実引数 25
純粋な関数 233
スコープ 97
節 180
セル 246
線形探索 192
挿入法 94
た 行
多相型 127, 189
多相関数 127
逐次実行 234
抽象データ型 219
デザインレシピ 2
アキュムレータに対する 170
一般の再帰に対する 162
関数定義に対する 26
構造データに対する 54
再帰関数に対する 82
270 索 引
再帰的なデータ構造に対する 183
条件分岐に対する 37
データ定義に対する 64
テンプレート 54
一般の再帰の 152
組の 55
自然数の 109
リストの 75
レコードの 66
トップレベル 222
な 行
名前のない関数 143
2 分木 181
2 分探索 185
2 分探索木 185
は 行
葉 180
配列 252
パターン変数 52
パターンマッチ 51, 60, 75
バランス木 224
バリアント型 177
ヒープ 254
ヒープソート 262
引数 20, 241
フィールド 59
フィボナッチ数 244
副作用を持つ関数 233
プロンプト 4
分割統治法 151
ベキ乗 9
ま 行
メイン関数 239
メインファイル 238
モジュール 211
や 行
ユークリッドの互除法 162, 236
ユニット 233
ら 行
リスト 72
例外処理 197
レコード 58
連想木 191
連想リスト 193
わ 行
ワイルドカード 77
著 者 略 歴
浅あさ
井い健けん
一いち
1992年 東京大学大学院理学系研究科修士課程修了東京大学助手を経て，
現 在 お茶の水女子大学理学部情報科学科准教授博士（理学）専門：プログラミング言語
サイエンス社のホームページのご案内http://www.saiensu.co.jp
ご意見・ご要望は[email protected] まで．
Computer Science Library-3
プログラミングの基礎（電子版）
2018 年 2 月 25 日 c© 初 版 発 行この電子書籍は 2007 年 2 月 25 日初版発行の同タイトルを底本としています． 著 者 浅 井 健 一 発行者 森 平 敏 孝
発行所 株式会社 サイエンス社〒 151–0051 東京都渋谷区千駄ヶ谷1丁目3番25号営業 ☎（03）5474–8500（代）振替 00170–7–2387編集 ☎（03）5474–8600（代）FAX ☎（03）5474–8900
組版 小宮山印刷工業（株）
≪検印省略≫本書の内容を無断で複写複製することは，著作者および出版社の権利を侵害することがありますので，その場合にはあらかじめ小社あて許諾をお求めください．
ISBN 978-4-7819-9932-6
![rekordbox...モード、およびそれに関連する機能について説明します。rekordbox 全般 に関しては、rekordbox.comの [Support] > [ マニュアル] ページより「rekordbox](https://img.pdfslide.org/doc/110x75/5ff6152c9ccef2576440b62d/rekordbox-fffoeeeeferekordbox.jpg)
