プログラミング言語: OCaml演習
田浦健次朗

Programming Languages: OCaml Excercise
Kenjiro Taura

(the page is encoded in UTF-8)

演習環境 (Jupyter)

Exercise Environment (Jupyter)

本演習ではブラウザだけあれば演習が実行できる, Jupyterを利用する.自分のマシンにOCamlをインストールする必要はない. 授業で指示したURLにブラウザでアクセスし, 解答もそこに入力して保存すること.

This exercise uses Jupyter environment, for which you only need a browser. You don't have to install OCaml on your machine. Access the URL told in the class and write/save your answer there.

OCaml環境を 自分のマシンにインストールする方法 は後述します.

If you want to install OCaml in your machine, the instructions are below in How to Install OCaml in Your Machine

有用リンク

Useful Links

Jupyter環境でOCamlと対話する

Interacting with OCaml in Jupyter Environment

Jupyter環境ではセルにOCamlのプログラムを入力し,SHIFT + ENTERを押すことで出力を得る.

In Jupyter environment, you input OCaml code in a cell and press SHIFT + ENTER to obtain the output.

なお,定義のあとの;;は必須ではないが, 処理系が入力を処理する際の切れ目になる. 一つのセルにいくつもの定義を並べる場合, 適宜;;で区切ったほうが文法間違いなどの時に, わかりやすくなるかも知れない.

The ;; after a definition are not mandatory, but server as a delimiter when the interpreter processes the inputs. When you write several definitions in a cell, delimiting definitions with ;; may make error messages easier to understand.

以下では,太字 が入力セルに入力すべき文字列, 斜体が,それに対する出力を示す.

Below, bold faces are your inputs and italic faces their corresponding outputs.

まずは簡単な変数の定義から.

 (* 変数定義 *)
# let x = 1;;
val x : int = 1
# x;;
- : int = 1
# x+1;;
- : int = 2

Here are how you define variables.

 (* variable definitions *)
# let x = 1;;
val x : int = 1
# x;;
- : int = 1
# x+1;;
- : int = 2

見ての通り変数の定義には,

let 変数 = 式

を使う.対話的処理系は,定義に使われた値や, 入力された式の型を表示してくれる.

As you can see, use the syntax:

let variable = expression

to define a variable. The interpreter shows you the value and its type.

関数の定義にも同じ文法(let)を使う. 変数名の後に,受け取りたい引数を書けば, ひとりでに関数の定義になる. 実際の所, 関数定義と変数定義は同じもので, たまたま値が関数であるものが関数定義であるに過ぎない.

 (* 関数の定義 *)
# let f x y = x + y;;
val f : int -> int -> int = <fun>
# f;;
- : int -> int -> int = <fun>
# f 3 4;;
- : int = 7
# f 3;;
- : int -> int = <fun>

1行目の入力の結果,fint -> int -> intという型を持つことが示されている. fの定義からは「整数を2個受け取って整数を返す」ように見えるかもしれないし, そう思っておいて大きな間違いはないのだが,より正確には, fは,整数を1つ受取り,「整数を一つ受取り整数を返す」ような関数である. だから,4行目のように整数をひとつだけ渡すことが可能になる.

 (* 部分適用 *)
# let plus5 = f 5;;
val plus5 : int -> int = <fun>
# let plus6 = f 6;;
val plus6 : int -> int = <fun>
# plus5 10;;
- : int = 15
# plus6 10;;
- : int = 16

Use the same keyword (let) to define functions too. Simply add a list of input parameters after the function name. As a matter of fact, a function definition and a variable definition are the same thing; a function definition is merely a variable definition whose value happens to be a function.

 (* function definition *)
# let f x y = x + y;;
val f : int -> int -> int = <fun>
# f;;
- : int -> int -> int = <fun>
# f 3 4;;
- : int = 7
# f 3;;
- : int -> int = <fun>

The ouput of the first input shows f has a type int -> int -> int. The definition of f looks as though f "takes two parameters and return an int" and it is not a huge misunderstanding; to be precise, f is a function that takes an int and returns "a function that takes an int (int -> int)". Therefore, it is allowed to pass only a single integer as you saw in the line 4 of the above.

 (* partial application *)
# let plus5 = f 5;;
val plus5 : int -> int = <fun>
# let plus6 = f 6;;
val plus6 : int -> int = <fun>
# plus5 10;;
- : int = 15
# plus6 10;;
- : int = 16

普通の変数も関数も同じ文法(let)で定義するのだが, 再帰的な関数は少し違う文法(let rec)を用いる.

You have now learned OCaml uses the same syntax (let) to define both variables and functions. OCaml uses a slightly different syntax (let rec) to define a recursive function, however.

# let rec fib n = if n < 2 then 1 else fib (n - 1) + fib (n - 2);;
val fib : int -> int = <fun>
# fib 10;;
- : int = 89

recを忘れると,本体中の参照が未定義であるといって,エラーになる.

If you forget to put rec, an error is raised saying the reference to the symbol in the righthand side is undefined.

 (* rec を忘れた例 *)
# let gib n = if n < 2 then 1 else gib (n - 1) + gib (n - 2);;

Characters 33-36:
  let gib n = if n < 2 then 1 else gib (n - 1) + gib (n - 2);;
                                   ^^^
Error: Unbound value gib

 (* if you forget rec ... *)
# let gib n = if n < 2 then 1 else gib (n - 1) + gib (n - 2);;

Characters 33-36:
  let gib n = if n < 2 then 1 else gib (n - 1) + gib (n - 2);;
                                   ^^^
Error: Unbound value gib

演習問題集

Exercise Problems

OCamlの Core Languageのマニュアルの1.1-1.4までを読み,以下の演習問題に取り組みなさい.
また,OCamlにもともと備わっているライブラリについては, このページのPart IVを見ると良い.

Read OCaml Core Language manual section 1.1-1.4 and solve the following problems.
Consult the part IV of this page for libraries built into OCaml.

[a,b)に含まれる整数の和

Sum of integers in [a,b)

2つの整数a bに対し,a以上b未満の整数(a <= x < b) の和を計算する関数を書け.

Write a function sum that takes two integers a and b and calculate summation of integers from a (inclusive) to b (exclusive) (a <= x < b).

let rec sum a b = ...

実行例

Example:

# sum 0 10 ;;
- : int = 45
# sum 5 10 ;;
- : int = 35

[a,b)に含まれる整数のリスト

List of integers in [a,b)

2つの整数a bに対し,aからb-1まで(a以上b未満)の整数をこの順に要素とするような,リストを計算する関数rangeを書け.

Write a function range that takes two integers a and b and returns a list of integers from a (inclusive) to b (exclusive) in this order.

let rec range a b = ...

実行例

Example:

# range 0 10;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
# range 5 10;;
- : int list = [5; 6; 7; 8; 9]

リストの全要素に1ずつ足す

Add one to each element in a list

リストを受け取り,すべての要素に1ずつ足したリストを返すような関数inclistを書け.実行例:

Write a function inclist that takes a list and builds another list by adding one to each element of the input list. Example:

# inclist (range 0 10);;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

リストの全要素にfを施す

Apply f to each element of a list

上記を少し一般化して,関数fとリストlを受取り, lの各要素xにfを適用したリストを返す関数 apply_list を書け. 例えば,

Slighly generalize the last problem and write a function apply_list that takes a function f and a list l and builds a list by applying f to each element of l. For example:

let inc x = x + 1;;

とした上で,

and

apply_list inc (range 0 10);;

とすると,上と同じ答えになってほしい. なお,incという関数をわざわざ定義しなくても, (fun x -> x + 1)という式で,「1をたす関数」が作れる(無名関数).

should return the same result as the last problem. By the way, you do not have to define inc and can use an expression (fun x -> x + 1) to represent a function that "adds one to its input" (anonymous functions).

# apply_list (fun x -> x + 1) (range 0 10);;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

最後にうれしい(残念な?)お知らせ. このような計算(リストの各要素に関数を適用する) は非常によく出てくるので,実は最初から備わっている. Listモジュールのmapという関数がそれ.つまり,

A good (or bad?) news for you; this pattern (applying a function to each element of a list) occurs so frequently that it is already built into OCaml. The map function in the List module is it. That is,

# List.map (fun x -> x + 1) (range 0 10);;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

乱数のリスト

List of Random Numbers

後々テストに使うために,乱数の生成方法を覚えておく. マニュアルから,乱数の発生のさせ方を見つけよ.そして, 各要素が0以上a未満の整数であるような,長さnの乱数のリスト を返す関数 random_ints (引数はa, nの順)を書け. これまでに定義した関数やmapを用いてなるべく短く書いてみよ.
実行例:

Master how to generate random numbers for later experiments. Find how to do it in the manual. Define a function random_ints that takes two parameters a and n and returns a list of n elements each of which is between 0 (inclusive) and a (exclusive). Try to write it as concisely as possible by utilizing functions you defined so far and/or the map function.
Example:

# random_ints 1000 5;;
- : int list = [615; 678; 949; 885; 217]

リストから偶数だけを取り出す

Extract even numbers from a list

与えられた整数のリストから偶数だけを取り出す関数 evens を書いてみよ.
実行例:

Write a function evens that extracts even numbers of a given list.
Example:

# evens [ 3; 9; 8; 6; 4; 7 ];;
- : int list = [8; 6; 4]

リストから(p x)を満たすxだけを取り出す

Extract elements x of a list satisfying (p x)

同じようにこのような処理の一般形を書いてみよう. 関数pとリストlを受取り, lから(p x)を満たす要素だけを取り出してこの順にリストにする関数 filter_list を書け.その上で例えば以下のように確認せよ.

Let's similarly generalize the above function. Write a function filter_list that takes a function p and a list l and extracts only elements x of l satisfying (p x). Check the function, for example, as follows.

# filter_list (fun x -> x mod 2 = 0)  [ 3; 9; 8; 6; 4; 7 ];;
- : int list = [8; 6; 4]

またしてもうれしく残念なお知らせ. リストからある条件を満たす要素だけを取り出す計算も 非常によく出てくるので,やはり最初から備わっている. List.filterという関数がそれである.つまり,

Another good (or bad) news for you; extracting elements from a list satisfying a certain function also occurs so frequently that it is built into OCaml. List.filter is it. That is,

# List.filter (fun x -> x mod 2 = 0) [ 3; 9; 8; 6; 4; 7 ];;
- : int list = [8; 6; 4]

クイックソート

Quicksort

リストlを受取り,クイックソートを使って整列したリストを返す関数 qs を書け. 実行例としては

Write a function qs that takes a list l and sorts it by the quicksort. For example,

# qs [ 8; 5; 7; 2 ];;
- : int list = [2; 5; 7; 8]

長いリストのソート

Sort a large list

リストが昇順に整列されているかを判定する関数 check_sorted を書け. そして,n要素のランダムな整数のリストを生成し,それをクイックソートで整列し, 整列されているかを判定する関数 test_qs を書け. それによって,クイックソートをテストせよ.
実行例:

Write a function check_sorted that checks if a given list is sorted in the ascending order. Using this function, write a function test_qs that generates a random list of n elements, sorts it by the quicksort, and checks if the result is in fact sorted. Test your quicksort implementation with it.
Example:

# check_sorted [3; 1; 2];;
- : bool = false
# check_sorted [1; 2; 4];;
- : bool = true
# test_qs 100000;;
- : bool = true

実行時間測定

Measure Execution Time

Unixモジュールのgettimeofday関数を用いると, 現在時刻を得ることができる. これを利用して,関数の実行時間を測定できる.

You can obtain the current time via gettimeofday function in Unix module. You can measure an execution time of a function with it.

# Unix.gettimeofday ();;
- : float = 1396802697.034235

前問の test_qs を変更し,クイックソートにかかった時刻を表示する関数 measure_qs を作れ.表示には,Printfモジュールの,printf関数を使うと良い.

Modify the test_qs in the last problem to define a function measure_qs that reports the time quicksort took to sort a list like this. Use printf function in Printf module to print a message.

# measure_qs 1000000;;
OK 1000000 elems in 7.976 sec
- : unit = ()

2分探索木

Binary Search Tree

2分探索木は探索のためのデータ構造で, 各ノード(葉も内部ノードも)ひとつの値を持ち, すべてのノードにおいて,

A binary search tree is a data structure for searching, in which each node (an internal node or a leaf node) has a value so that it holds everywhere that:

左の子供の値 < あるノードの値 < 右の子供の値
the value of its left child (if any) < the value of a node < the value of its right child (if any). 

が保たれている.ただし,左の子,右の子供とも,いない場合もある.

A node may or may not have its left/right child.

2分探索木のデータ構造を,type を用いて定義せよ.

Define a type representing a binary search tree, using type syntax of OCaml.

type 'a bs_tree = ...

木が空かもしれない,また, 左右の子供それぞれが, いるかもしれないし, いないかもしれないという状況を正しくモデル化せよ.

Correctly model the fact that a tree may be empty and a node may or may not have its left/right child.

次に,2分探索木への挿入を行う関数bs_tree_insertを書け.具体的には, bs_tree_insert x t は,2分探索木 t に x を追加したような木構造を返す関数とする. ただし,xはtの中のどの要素とも異なるとして良い.

Write a function bs_tree_insert that inserts an element into a binary search tree; specifically, bs_tree_insert x t should return a tree that will result by adding x to t. You may assume x is distinct from any of the elements in t.

let rec bs_tree_insert x t = ...

2分探索木の探索

Search a Binary Search Tree

前問の続きで, 2分探索木の探索を行う関数 (要素xtにあるか否かを返す関数)を書け.

Continue the last problem and write a function that searches a tree for a given element (returns whether the element x in the tree t).

let rec bs_tree_find x t = ...

2分探索木からの削除

Remove an Element of a Binary Search Tree

2分探索木からの削除を行う (削除後の木を返す)関数を書け. その要素が木にない場合, 元と同じ木を返せばよい.

Write a function that removes an element from a binary search tree (returns a tree with the specified element removed). If the specified element is not in the list, simply return the identical tree.

let rec bs_tree_remove x t = ...

2分探索木の計算量

Time Complexity of Operations on Binary Search Trees

復習: 空の木にn個の異なる要素を追加するのにかかるコストは, 平均, 最悪それぞれいくらですか? 最悪となるデータ(挿入される要素の列)の例をあげよ.

A review problem: what is the average and the worst-case time complexity of adding n elements to an empty list? Show a worst-case example (the sequence in which elements are inserted).

2-3木

2-3 Tree

データベースで使われるB木やB+木は, 「平衡木」と呼ばれるデータ構造の一種で, n要素に対して木の深さがO(log n)になるように 工夫された木構造である. B+木の特別簡単な場合である 2-3分木は以下を保ちながら動作する

B tree or B+ tree used in databases are types of data structures broadly called "balanced trees", which are cleverly designed to maintain their depths in O(log n) for n elements. 2-3 tree is a simple special case of B+ tree that maintains the following.

OCamlで2-3木を表すデータ構造, 挿入, 探索を行う関数を作れ.

Write an OCaml data type for 2-3 trees and functions to perform insertion and searching on them.

type 'a tt_tree = ...
let rec tt_tree_insert x t = ...
let rec tt_tree_find x t = ...

2-3木からの削除

Remove an Element of a 2-3 Tree

OCamlで2-3木からの削除を行う関数を作れ.

Write an OCaml function that removes an element from a 2-3 tree.

let rec tt_tree_remove x t = ...

自分のマシンにインストールしたい人は

If you want to install it in your machine

Ubuntu

Windowsその他

Windows and others

インストールのテスト

Test Your Installation

コマンドが動けばとりあえずOK.

OK if ocaml command works.

$ ocaml
      Objective Caml version 3.12.1

# 

また,emacsを起動して,.ml という拡張子のファイルを作成してみよ. 画面下部に,Tuareg Abbrevのようになって, Tuaregモードなるモードに入れば,OCamlのプログラムが快適に編集できる.

Run emacs and create a file with .ml extension. If you see Tuareg Abbrev in the bottom of the window and enter the Tuareg mode, you can comfortably edit OCaml programs.

ファイルに書いたプログラムを実行する

Execute Programs in a File

ocamlコマンドのプロンプトに直接式や定義を打ち込む代わりに, ファイルにプログラムを保存して実行させることができる. .mlという拡張子でファイルを記述し,コマンドocamlにファイル名を与えれば良い.

You can save a program in a file and execute it, rather than entering expressions or definitions to the ocaml command interpreter. Just write a file with .ml extension and give it to the ocaml command line.

以下をfib.mlに保存し

Save the following in fib.ml

let rec fib n = 
  if n < 2 then
    1
  else
    fib (n - 1) + fib (n - 2);;

Printf.printf "%d\n" (fib 10)
         

シェルプロンプトに対して以下を実行する.

and execute the following in the shell.

$ ocaml fib.ml
89

注意としては,対話的実行とはことなり,勝手に定義された変数や評価された式の値が 表示されるわけではないこと.ここで89が表示されたのはあくまで,Printf.printf という式を評価した結果である.

A point to note here is that unlike the interactive environment, values of defined varibles or evaluted expressions are not automatically shown. The 89 printed above is due to the effect of executing Printf.printf.

Emacsから実行

Execute from within Emacs

ocamlコマンドをシェルから立ち上げる代わりに,Emacsの中でocamlを実行することができる. プログラムの開発中に, ファイルの編集 -> 実行 -> 修正 -> 実行 -> ... というループを繰り返したい場合,これを使うと便利である. OCamlプログラムを編集中のバッファ(Tuaregモード)で,

C-c C-b
を押すと,バッファの中身をocamlに放り込んでくれる.

You can run ocaml within Emacs instead of executing it in a shell. Doing so is particularly convenient when you repeat the loop: editing a file -> executing it -> modifying it -> executing it -> ...; simply type

C-c C-b

in a buffer for an OCaml program (in Tuareg mode) and the contents of the buffer is sent to the ocaml interpreter.