月: 2008年3月

unfold を覚えたので，こないだの1から10までのリストを unfold を使ってやってみる。

と思ったら unfold が見つからないのでまずはその定義から。

# let rec unfold f init =
match f init with
Some (a, b) -> a :: unfold f b
| None        -> []
;;
val unfold : ('a -> ('b * 'a) option) -> 'a -> 'b list = <fun>

で，リストを作る関数。

# let list_of_int i j =
unfold (fun x -> if x + 1 = j then None else Some (x, x+1)) i
;;
val list_of_int : int -> int -> int list = <fun>
# list_of_int 1 10;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

コマンドライン引数は Sys.argv に配列として格納される。インデックス0がプログラム名で，以下引数の数だけ続く。

インデックス0を出力する例：

let () = print_endline Sys.argv.(0)

^o^ >ocamlc -o argv.exe argv.ml
^o^ >argv
argv

インデックス1を出力する例：

let () = print_endline Sys.argv.(1)

^o^ >ocamlc -o argv.exe argv.ml
^o^ >argv foo
foo

引数を与えないとエラーになる。

^o^ >argv
Fatal error: exception Invalid_argument("index out of bounds")

Array.iter は配列に対して ‘a -> unit 型の関数を順に適用する関数。List.iter の配列版。これを使えばコマンドライン引数の数だけ繰り返せる。

let () = Array.iter (fun s -> print_endline s) Sys.argv

^o^ >argv2 foo bar buz
argv2
foo
bar
buz

ソースファイル（=モジュール）と同名で拡張子が .mli のファイルを用意しておくことで，モジュールにシグネチャを与えることができる。

前にも例に挙げた Table モジュールを例にとると，

table.mli

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

table.ml

type ('a, 'b) t = Empty | Entry of 'a * 'b * ('a, 'b) t
let empty = Empty
let add key content table = Entry (key, content, table)
let rec retrieve key = function
Empty -> None
| Entry (key', content, rest) ->
if key = key' then Some content else retrieve key rest
let rec delete key = function
Empty -> Empty
| Entry (key', content, rest) ->
if key = key' then delete key rest
else Entry (key', content, delete key rest)
let rec dump = function
Empty -> []
| Entry (key, content, rest) ->
(key, content) :: (dump (delete key rest))

こういう風にtable.mliとtable.mlを書く。これで

module type TABLE =
sig
...
end
module Table : TABLE =
struct
...
end

と書いたのと同じになる。

コンパイルするときは，インターフェイス(mli)ファイルを先にコンパイルする。手順としては

1. 各mliファイルを ocamlc でコンパイル（cmiファイルができる）
2. 各mlファイルを ocamlc -c でコンパイル（cmoファイルができる）
3. 全cmoファイルを ocamlc でリンク

となる。mlファイルよりもmliファイルを先にコンパイルしておくことに注意。でないとcmiファイルがないので，コンパイラが推論して勝手にcmiファイルを作り，意図したのと違うことになる。

次のディレクトリを順に検索する。

1. ocamlc コマンドを起動したディレクトリ
2. ocamlc コマンドの -I オプションで指定したディレクトリ
3. 標準ライブラリのディレクトリ

今日は Problem 2。フィボナッチ数列のうち4,000,000以下で偶数のみを合計せよ，という問題。

cf. http://projecteuler.net/index.php?section=problems&id=2

Haskell ではやってる人がいるので，OCaml でやってみた。

let fibs_under_n n =
let rec fibs a b x =
let c = a + b in
if c > x then [] else c :: fibs b c x
in
1 :: 2 :: fibs 1 2 n
let even n = if n mod 2 = 0 then true else false
let sum lis = List.fold_left (+) 0 lis
let euler002 n = sum (List.filter even (fibs_under_n n))
let () = print_int (euler002 4000000)

even とか sum とかありそうな関数なんだけど，マニュアル見ても見つからなかったから自分で定義した。

コンパイルして実行：

^o^ >ocamlc -o euler002.exe euler002.ml
^o^ >euler002
4613732

追記：

_さんに教えてもらった方法で。

# let fibs_under_n2 n =
let rec fibs a b x =
let c = 4 * b + a in
if c > x then [] else c :: fibs b c x
in
2 :: 8 :: fibs 2 8 n
;;
# fibs_under_n2 5000;;
- : int list = [2; 8; 34; 144; 610; 2584]

元の関数を使うと

# List.filter even (fibs_under_n 5000);;
- : int list = [2; 8; 34; 144; 610; 2584]

って OCaml ではどう書けばいいんだろう。

Haskell では簡単に [1..10] と書ける。

Prelude> [1..10]
[1,2,3,4,5,6,7,8,9,10]

これなら10といわずいくつまででも簡単だ。だけど OCaml こういう書き方はできないらしい。

# [1..10];;
Characters 4-6:
[1..10];;
^^
Syntax error
# [1;;10];;
Characters 2-4:
[1;;10];;
^^
Syntax error

ともかく関数を書いてみた。

# let rec list_of_int f t =
if f > t then [] else f :: list_of_int (f+1) t
;;
# list_of_int 1 10;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

ソースファイルは1つじゃなくてもいい。次の例では，fact関数を定義している fact.ml と，それを呼び出す main.ml に分けている。

fact.ml

let rec fact n = if n = 0 then 1 else n * fact (n-1)

main.ml

let () = print_int (Fact.fact 5)

OCamlではファイル＝モジュール（ストラクチャ）なので，fact.mlに定義されているfact関数は，Fact.fact として呼び出すか，open Fact してから使う。

さて，それぞれを（リンクせずに）コンパイルするには -c オプションを使う。

^o^ >ocamlc -c fact.ml
^o^ >ocamlc -c main.ml
^o^ >ls
fact.cmi  fact.cmo  fact.ml  main.cmi  main.cmo  main.ml

.cmo と .cmi という2種類のファイルができている。 .cmo がオブジェクトファイルだ。

これらをリンクして実行形式のファイルを作るには，ソースファイルから直接コンパイルするときと同じようにすればいい。

^o^ >ocamlc -o fact5.exe fact.cmo main.cmo
^o^ >ls *.exe
fact5.exe

単にリンクする.cmoファイルを並べるだけだけど，参照される側（ここではfact.cmo）を先に書くことに注意。逆にするとエラーになる。

^o^ >ocamlc -o fact5.exe main.cmo fact.cmo
Error while linking main.cmo: Reference to undefined global `Fact'

さて，うまくいってるだろうか。

^o^ >fact5
120