-1 を 10 で割ったあまりは?

どう書く?org のこのお題,はじめはHaskellで書いた。

modular n l h = l + n mod (h - l + 1)

すでに投稿があったのでOCamlで書き直したんだけど,そのまま移植したんではうまくいかない。

# let modular n l h = l + n mod (h - l + 1);;
val modular : int -> int -> int -> int = <fun>
# modular (-1) 100 200;;
- : int = 99

しばらく悩んだけど,要するに mod の引数に負数が現れた場合の振る舞いが Haskell と OCaml で違う。思わぬ盲点だよな。

Haskellの場合:

Prelude> mod (-1) 10
9
Prelude> mod 1 (-10)
-9

OCamlの場合:

# (-1) mod 10;;
- : int = -1
# 1 mod (-10);;
- : int = 1

さて,算術的にはどっちが正しいんだろうか。

練習問題 10.3 fold コマンド

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~のp.215より。

wc コマンドはなんか難しいのでこっちを先に。

UNIX の fold コマンドは,ファイル名の列を引数として,その内容を,長い行を複数の短い 行(デフォルトでは80文字)に分割しながら表示します。これを OCaml で実装し,実行可能 ファイルを作成しなさい。オプションとしては,行の長さを整数で指定する –width を実装 しなさい。

let version = "0.1"
let filenames = ref []
let width = ref 80
let spec = [("--width",
Arg.Int (fun n -> width := n),
"Set line width");
("--version",
Arg.Unit (fun () -> Printf.printf "fold in OCaml ver.%s\n" version),
"Display version")]
let rec fold_line n str =
let len = String.length str in
if len > n then
( print_endline (String.sub str 0 n);
fold_line n (String.sub str n (len - n)))
else
print_endline str
let rec each_line ic =
fold_line !width (input_line ic);
each_line ic
let fold_file filename =
let infile = open_in filename in
try
each_line infile
with
End_of_file -> close_in infile
let () =
Arg.parse spec
(fun s -> filenames := s :: !filenames)
"Usage: fold [--width width] [--help] [--version] filename ...";
List.iter fold_file (List.rev !filenames)
^o^ >ocamlc -o fold.exe fold.ml
^o^ >fold --width 40 fold.ml
let version = "0.1"
let filenames = ref []
let width = ref 80
let spec = [("--width",
Arg.Int (fun n -> width :=
n),
"Set line width");
("--version",
Arg.Unit (fun () -> Printf
.printf "fold in OCaml ver.%s\n" version
),
"Display version")]
let rec fold_line n str =
let len = String.length str in
if len > n then
( print_endline (String.sub str 0 n)
;
(以下略)

練習問題 10.1

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~のp.215より。

UNIXの cat コマンドは,ファイル名の列を引数として,その内容を順次表示する(標準出力 に書き込む)ものです。これを OCaml で実装し,実行可能ファイルを作成しなさい。オプシ ョンに関しては少なくとも行番号を表示するための -n オプションを実装すること。

let version = "0.1"
let display_linenum = ref false
let filenames = ref []
let spec = [("-n",
Arg.Set display_linenum,
"Display line number.");
("-version",
Arg.Unit (fun () -> Printf.printf "cat in OCaml ver.%s\n" version),
"Display version.")]
(* print each lines *)
let rec output_file ic =
print_endline (input_line ic);
output_file ic
(* print each lines with line number *)
let rec output_file_n n ic =
Printf.printf "%5d %s\n" n (input_line ic);
output_file_n (n+1) ic
let cat_file filename =
let infile = open_in filename in
try
if !display_linenum then
output_file_n 1 infile
else
output_file infile;
with
End_of_file -> close_in infile
let () =
Arg.parse spec
(fun s -> filenames := s :: !filenames)
"Usage: cat [-n] [-help] [-version] filename ...";
List.iter cat_file (List.rev !filenames)

^o^ >ocamlc -o cat.exe cat.ml
^o^ >cat -n cat.ml
1 let version = "0.1"
2
3 let display_linenum = ref false
4
5 let filenames = ref []
6
7 let spec = [("-n",
8              Arg.Set display_linenum,
9              "Display line number.");
10             ("-version",
11              Arg.Unit (fun () -> Printf.printf "cat in OCaml ver.%s\n" ve
sion),
12              "Display version.")]
13
(以下略)

unfold で1から10までのリスト

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]

Array.iter

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

Sys.argv

コマンドライン引数は 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")

インターフェイスファイル

ソースファイル(=モジュール)と同名で拡張子が .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から10までのリスト

って 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]

Problem 2

今日は 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]