月: 2008年2月

どう書く？.orgに投稿した。

cf. データの整列

sort_by_dic が辞書順に整列する関数，sort_by_dis が距離の昇順に整列する関数。

type point = Point of float * float
let compare_point a b =
match (a, b) with
(Point (x1, y1), Point (x2, y2)) -> if x1 = x2 then compare y1 y2
else compare x1 x2
let distance = function
Point (x, y) -> sqrt (x *. x +. y *. y)
let sort_by_dic = List.sort compare_point
let sort_by_dis = List.sort (fun a b -> compare (distance a) (distance b))

実行結果，辞書順：

# sort_by_dic [Point (3.2, 1.9); Point (3.2, 0.3); Point (1.2, 3.5)];;
- : point list = [Point (1.2, 3.5); Point (3.2, 0.3); Point (3.2, 1.9)]

距離の昇順：

# sort_by_dis [Point (3.2, 1.9); Point (3.2, 0.3); Point (1.2, 3.5)];;
- : point list = [Point (3.2, 0.3); Point (1.2, 3.5); Point (3.2, 1.9)]

モジュール（正確にはストラクチャ）の定義は次のようにして，struct と endo のあいだに各種定義の書く。

# module Tree =
struct
type 'a t = Lf | Br of 'a * 'a t * 'a t
let rec size = function
Lf -> 0
| Br (_, left, right) -> 1 + size left + size right
let rec depth = function
Lf -> 0
| Br (_, left, right) -> 1 + max (depth left) (depth right)
end
;;

モジュールの中に書けるのは：

• 変数束縛
• 関数宣言
• type による型宣言
• exception宣言
• open宣言
• module定義（入れ子）

さて，対話環境で上のようにモジュール定義をすると次のような応答が返ってくる。

module Tree :
sig
type 'a t = Lf | Br of 'a * 'a t * 'a t
val size : 'a t -> int
val depth : 'a t -> int
end

これはシグネチャといって，いってみればモジュールの型というべきもの。これについてはまた後で書く。

前のエントリの例のようにシグネチャをコンパイラに推論させるのではなく，自分で書くこともできる。そのとき，モジュールの外部には公開したくない関数や，定義した型の詳細を隠蔽することもできる。一般には：

• シグネチャを定義する
• そのシグネチャをモジュールに与える

という手順を踏む。

たとえば次のようにモジュールを定義したとする。

# module Table =
struct
type ('a, 'b) t = Empty | Entry of 'a * 'b * ('a, 'b) t
let empty = Empty
let add key datum table = Entry (key, datum, table)
let rec retrieve key = function
Empty -> None
| Entry (key', datum, rest) ->
if key = key' then Some datum else retrieve key rest
let rec delete key = function
Empty -> Empty
| Entry (key', datum, rest) ->
if key = key' then delete key rest
else Entry (key', datum, delete key rest)
let rec dump = function
Empty -> []
| Entry (key, datum, rest) ->
(key, datum) :: (dump (delete key rest))
end;;
module Table :
sig
type ('a, 'b) t = Empty | Entry of 'a * 'b * ('a, 'b) t
val empty : ('a, 'b) t
val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
val retrieve : 'a -> ('a, 'b) t -> 'b option
val delete : 'a -> ('a, 'b) t -> ('a, 'b) t
val dump : ('a, 'b) t -> ('a * 'b) list
end

見てわかるとおり，データ型ひとつと関数を4つ定義している。

さて，ここで Table.t型の詳細とdelete関数を隠すことにする（ついでに書いておくとこのように詳細の隠されたデータ型を抽象データ型という）。隠すには単にシグネチャに書かなければいい。具体的にはデータ型定義の = 以降の部分と，delete関数の定義部分だ。

シグネチャを定義するには module type宣言を使う。

# module type TABLE1 =
sig
type ('a, 'b) t
val empty : ('a, 'b) t
val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
val retrieve : 'a -> ('a, 'b) t -> 'b option
val dump : ('a, 'b) t -> ('a * 'b) list
end;;
module type TABLE1 =
sig
type ('a, 'b) t
val empty : ('a, 'b) t
val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
val retrieve : 'a -> ('a, 'b) t -> 'b option
val dump : ('a, 'b) t -> ('a * 'b) list
end

このシグネチャを与えて新しい Table1モジュールを定義する。といっても実態はTableモジュールとおなじだ。

# module Table1 : TABLE1 = Table;;
module Table1 : TABLE1

これで実体は同じだけどシグネチャの違うモジュールができた。2つを比べてみよう。

# Table.empty;;
- : ('a, 'b) Table.t = Table.Empty
# Table1.empty;;
- : ('a, 'b) Table1.t = <abstr>

Table1の方はデータ型か <abstr> になっている。これは抽象データ型を表している。

# Table.retrieve;;
- : 'a -> ('a, 'b) Table.t -> 'b option = <fun>
# Table1.retrieve;;
- : 'a -> ('a, 'b) Table1.t -> 'b option = <fun>

retrieve関数には両方ともアクセスできる。

# Table.delete;;
- : 'a -> ('a, 'b) Table.t -> ('a, 'b) Table.t = <fun>
# Table1.delete;;
Characters 0-13:
Table1.delete;;
^^^^^^^^^^^^^
Unbound value Table1.delete

Table1.delete はダメ。

前エントリではモジュールの定義とシグネチャを与えるのを別にしたけど，いっぺんにすることもできる。というかその方が一般的なのかな。こんな感じ。

module Table1 : TABLE1 =
struct
...
end;;

モジュールの関数を使うときには[モジュール名].[関数名]とするけど，open宣言をすればモジュール名をつけなくても使えるようになる。

# map (fun x -> x * x) [1;2;3;4];;
Characters 0-3:
map (fun x -> x * x) [1;2;3;4];;
^^^
Unbound value map
# open List;;
# map (fun x -> x * x) [1;2;3;4];;
- : int list = [1; 4; 9; 16]

複数のモジュールをopenしたとき，同じ名前の関数がある場合には後からopenしたモジュールの関数だけが使えるようになる。たとえば，map関数は ListモジュールにもArrayモジュールにもあるけど，次のようにするとArrayモジュールのほうだけが使える。

# open List;;
# open Array;;
# map (fun x -> x * 10) [|1;2;3;4|];;
- : int array = [|10; 20; 30; 40|]

↑Arrayのmapは使える。↓Listのmapは使えない。

# map (fun x -> x * 10) [1;2;3;4];;
Characters 22-31:
map (fun x -> x * 10) [1;2;3;4];;
^^^^^^^^^
This expression has type 'a list but is here used with type int array

モジュール名をつけてやれば使える。

# List.map (fun x -> x * 10) [1;2;3;4];;
- : int list = [10; 20; 30; 40]

出力も覚えたし書いてみた。

let fizzbuzz x =
let f = if x mod 3 = 0 then "Fizz" else "" in
let b = if x mod 5 = 0 then "Buzz" else "" in
let fb = f ^ b in
if fb = "" then string_of_int x else fb
;;
let () = for i = 1 to 100 do
print_endline (fizzbuzz i)
done
;;

実行結果は省略するけど，うまくいったとだけ書いておく。

本文中の関数 whle を参考にして，for式相当の機能を実現する再帰関数を定義しなさい。

こんなんでいいのかな。

# let rec fr frm t body =
if frm <= t then
begin body frm; fr (frm + 1) t body end
;;
val fr : int -> int -> (int -> 'a) -> unit = <fun>

# fr 1 5 (fun x -> print_endline ( string_of_int x));;
1
2
3
4
5
- : unit = ()

本文中でもふれたように，ref型は以下のように定義された，1フィールドの書き換え可能な レコードです。

type 'a ref = { mutable contents : 'a };; 

関数 ref，前置演算子 !，中置演算子 := の定義をレコードに関連した操作で書きなさい。

こうかな。

let ref x = { contents = x };;

let (!) x = x.contents;;

let (:=) x v = x.contents <- v;;

与えられた参照の指す先の整数を1増やす関数 incr を定義しなさい。

# let incr x = x := !x + 1;;
val incr : int ref -> unit = <fun>

# let x = ref 3;;
val x : int ref = {contents = 3}
# incr x;;
- : unit = ()
# !x;;
- : int = 4