プログラミングCの最近のブログ記事

OCamlで再帰関数や、他の関数を呼び出す関数などをデバッグする時に、
traceを使えば、何回くらい再帰が起こってるのかとか、引数が正しく渡されてるかを確認できる

関数hogeについてtraceしたければ

# #trace hoge;;

と打ち、関数を実行すればよい
また、traceを辞めたい時は

# #untrace hoge;;

と打てばよい。

長めの関数を書く時や、試行錯誤しながらコーディングする時は意外に便利だ

デフォルトで定義されている、Listの中のmap, fold_right, fold_leftという関数を使ってみる


まず、List.mapとは、以下のような関数であり、リストの要素1つ1つに対して引数の関数を実行し、その結果をリストで返してくれるものである。

# let rec map f = function
[] -> []
| h::t -> (f h) :: map f t;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun> 

このmapを使って、
[1;2;3] と["a";"b"] を受け取ると両者の「直積」、つまり[(1,"a");(1,"b");(2,"a"); (2,"b");(3,"a");(3,"b")] を返すような関数productを書くと

let rec product a b = 
  match a with
    [] -> []
  | h::t -> (List.map (fun x->(h,x)) b) @ product t b
;;

のようになる。これは、リストaの要素を順番に、リストbのすべての要素とのtuple(組)を作っていけばよい。
また、前回[OCaml]#6 今までの改良＆powerset(べき集合)のpowersetをmapを用いて書き直すと、

let rec powerset a =
  match a with
    [] -> [[]]
  | h::t -> (List.map (fun x -> h::x) (powerset t))@(powerset t)
;;

のように簡単に書ける。だが、powerset tの部分で同じ計算を2度やるなど非効率なので、この結果を変数に保持しておいて、次のように改良できる。

let rec powerset a =
  match a with
    [] -> [[]]
  | h::t -> let p = powerset t in (List.map (fun x -> h::x) p)@p
;;

次に、fold_rightを使ってみる。
fold_rightの定義は以下のようになっている。

# let rec fold_right f a unit =
match a with
[] -> unit
| h::t -> f h (fold_right f t unit);;

fold_right、fold_leftは、畳込み関数と呼ばれ、unitとリストの最後の項との演算、その結果と最後から2番目との演算、その結果と最後から３番目との演算、その結果と・・・というように、引数を2つとり、１つ返す関数を右から順に行っていく。例えば、リストの和を計算したければ、

let sum a =
  List.fold_right (+) 0 a
;;

のように簡単に定義できる。
ここで、(+)は(fun x y -> x+y) のことである。
他にも、リストの最大値を求める関数listMaxや

let listMax a = 
  List.fold_right max a min_int
;;

unitにbを指定することで、リストとリストの連結を行う関数appendや、

let append a b =
  List.fold_right (fun x y -> x::y) a b

リストの長さを求める関数length

let length a =
  List.fold_right (fun x y -> 1 + y) a 0
;;

が簡単に定義できる。
また、先ほどのmapも

let map f a =
  List.fold_right (fun x y -> (f x) :: y) a []
;;

のように定義できる。これは、１つ１つの要素に対し、fを実行し、今までの結果と繋げていけばよい

同様にfold_leftという関数も存在し、これはfold_rightとは逆にリストの左の要素から順に演算を行うものである。左から順に行ってくれることで、リストを逆順にするreverseが次のように実装できる。

let reverse a =
  List.fold_left (fun x y -> y::x) [] a
;;

このリストの反転は、fold_leftだからこそ出来ることで、積み上げられたプリントの一番上を取って、別のところに重ねていくのと同じである。
最後に、二つのリストa,bに対しその内積(a[0]*b[0] + a[1]*b[1] + a[2]*b[2] + a[3]*b[3] + a[4]*b[4] +・・・+ a[length-1]*b[length-1])を計算する関数inner_productを考える。
これはまず、関数combineによって、2つのリストの第n項同士をtupleにし、それをfold_rightを用いて掛けて足していくだけである。 funを定義する時に、(x,y) z つまり、掛け算をすべき組と今までの和を引数にとることに気がつけば簡単である。

let rec combine a1 a2 = 
  match (a1,a2) with
    ([],_) -> []
  | (_,[]) -> []
  | (h1::t1, h2::t2) -> (h1,h2) :: combine t1 t2
;;

let inner_product a b =
  List.fold_right (fun (x,y) z -> x*y + z) (combine a b) 0
;;

以上、まだ提出してない人はお早めに（笑）

さっき書いた、 [OCaml]#5 和集合　積集合　差集合　対称差集合のunion、intersectionについて、このプログラムはO(n)であるcontainをn回再帰しているのでO(n^2)の手間がかかる。
ここで、引数として与えるリストがソート済みならば、O(n)でもっと早く実行できる。


引数のリストは昇順にソートされているので、２つのリストの先頭の要素つまり最小値を取り出し、値が違えば小さい方と同じ値はもう１つのリストには含まれていないことがわかる。intersectionも同様にして求めると、

let rec union l1 l2 =
  match (l1,l2) with
    (_,[]) -> l1
  | ([],_) -> l2
  | (h1::t1,h2::t2) -> if(h1=h2) then h1::(union t1 t2)
                  else if(h1<h2) then h1::(union t1 l2)
                  else h2::(union l1 t2)
;;

let rec intersection l1 l2 =
  match (l1,l2) with
    ((_,[]) | ([],_)) -> [] (* 片方のリストが空なら空リストを返す *)
  | (h1::t1,h2::t2) -> if(h1<h2) then intersection t1 l2
                  else if(h1>h2) then intersection l1 t2
                  else h1::(intersection t1 t2)
;;

最後に、あるリストを与えた時にそのリストのべき集合を返すpowersetを考える。
例えば、powerset [1;2;3;]と実行すると、[[]; [1]; [2]; [3]; [1; 2]; [1; 3]; [2; 3]; [1; 2; 3]]を返すという具合である。

これは再帰的に考えると、n個の要素からなる集合のべき集合は、n-1個の要素からなる集合のべき集合を求め、それとそれの各要素にn個目を加えたものの和集合である。 この、べき集合の各要素（要素といってもリストだが）にn個目を加える作業は別メソッドで定義した。powerset2は、リストのリストと、追加する要素を受け取り、リストのリストから先頭のリストを取り出し、要素を加えたものと加えないものを計算し、残りは再帰的に求める。

let rec powerset2 element listInList =
  match listInList with
    [] -> []
  | h::t -> h :: (element::h) :: (powerset2 element t)
;;

let rec powerset list = 
  match list with 
    [] -> [[]]
  | h::[] -> [[];[h]]
  | h::t -> powerset2 h (powerset t)
;;

ちなみに、実行すると、

# powerset [1;2;3];;
- : int list list = [[]; [1]; [2]; [1; 2]; [3]; [1; 3]; [2; 3]; [1; 2; 3]]
# powerset ["egg"; "sausage"; "spam"];;
- : string list list =
[[]; ["egg"]; ["sausage"]; ["egg"; "sausage"]; ["spam"]; ["egg"; "spam"];
 ["sausage"; "spam"]; ["egg"; "sausage"; "spam"]]

となって、確かにべき集合を求めることが出来た

数学の集合、つまり重複を許さないリストについて考えてみる。リストの結合演算子"@"では、結合するリストに同じ要素があれば、結合後のリストにはそれが２個でてくる。これを、要素が重複しない、和集合(A∪B)を返してくれるメソッドunionを定義したい。
重複しないようにするには、先頭から順に結合するリストにも同じものが入っているかを調べればよい。同じものが入っているかどうかは、[OCaml]#4 リストとmatch文のcontainを使えばよく

# let rec contain list n =
  match list with
    [] -> false
  | h::t -> if h=n then true
            else contain t n
  ;;

# let rec union a b = 
  match a with
    [] -> b
    | h::t -> if(contain b h) then union t b
                else h::union t b
  ;;

となり、同様に、積集合(A∩B)intersection、差集合(A-B)defference、対称差(A∪B-A∩B)symmetric differenceを定義する。

# let rec intersection a b = 
  match a with
    [] -> []
    | h::t -> if(contain b h) then h :: intersection t b
                else intersection t b
  ;;

# let rec defference a b = 
  match a with
    [] -> []
    | h::t -> if(contain b h) then defference t b
                else h::defference t b
  ;;

# let rec symmetric_defference a b = 
    defference a b @ defference b a
  ;;

となる。

OCamlでは、配列ではなくリストが使われる。
リストの宣言＆初期化の仕方は、

# let array = [1; 2; 3; 4];;
val array : int list = [1; 2; 3; 4]
# let charArray = ['a'; 'b'; 'c'];;
val charArray : char list = ['a'; 'b'; 'c']

のようにやる。

また、リストの要素は同じ型でないといけないので、char型とint型、float型とint型を混ぜて使おうとするとエラーになる。

 # let array = [1; 2; 'a'];;
This expression has type char but is here used with type int
# let array = [1.0; 2];;
This expression has type int but is here used with type float

リストとリストの結合は、演算子"@"を使う。

# let a = [1;2;3];;
val a : int list = [1; 2; 3]
# let b = [2;4;5];;
val b : int list = [2; 4; 5]
# let c = a @ b;;
val c : int list = [1; 2; 3; 2; 4; 5]

これはあくまでリストの結合なので、前のリストに続いて後ろをくっつけただけである。

同じように、ある要素をリストの先頭に挿入する場合は、"::"を用いて

# let d = 0::a;;
val d : int list = [0; 1; 2; 3]

のようにする。


ある要素がリストに含まれているかを調べるには、containメソッドを次のように定義すればよい。

# let rec contain list n =
  match list with
    [] -> false
  | h::t -> if h=n then true
            else contain t n
  ;;
val contain : 'a list -> 'a -> bool = <fun>

これは、まず、match文で仮引数のlistについて比較し、
listの要素が無ければnが含まれているわけないのでfalseを返し、
そうでない時、listを最初の要素h(head)と残りのリスト(tail)に分割し、hがnと等しかったらtrueを返し、そうでない時、残りの部分tとnを比較する。

"|"と"||"は"または"の意味で、前者は、比較最中にtrueが決まると残りの部分は検討せずにtrueを返し、後者は最後まで計算をする。"&"と"&&"も同様である。
実行結果は、先ほどのリストa( = [1; 2;3])を使うと、

# contain a 1;;
- : bool = true
# contain a 4;;
- : bool = false

となる。


次回は、集合(map)の実装について考える

長い処理を書く時や書いた処理を保存したい時など、やはりエディタでソースを書き、それを読み込むようにしたい。

外部ファイル、sorce.txtを読み込む場合は、

# #use "sorce.txt";;

とすればよい。

また、ソースないにコメントを書きたい場合は、
(* コメント*)
のように、(*と*)でくくる。

CやJAVAでいう、/* ～～～ */と同じように使う。

[OCaml]#1 OCamlで関数や変数を定義するでは関数をlet　変数（関数）名　引数1　引数2・・・のように定義したが、再帰関数を定義する場合にはrecというオプションが必要となる。

例を挙げて説明すると、
n xの2引数をとり、xのn乗を計算する再帰関数powerは、

# let rec power n x =
  if(n=0) then 1
  else if(n mod 2 = 0) then power (n/2) (x*x)
  else x * power (n/2) (x*x)
;;
val power : int -> int -> int = <fun>

のようにletと関数名の間にrecを入れる。そして、単にxをn回掛けるとO(n)の手間になってしまうので、再帰をうまく使いO(logn)で出来るようにした。
これは、例えば、x^10はx^10 = (x^5)^2 = (x*(x^2)^2)^2 とすると、掛け算の処理は4回で済む。
このようにx^2を(x^(n/2))^2とする時に、nが偶数か奇数かで分類している。


もうひとつ例を挙げると、フィボナッチ数列の第n項を求める関数を考える。

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

とやってしまうと、fib (n-1) + fib (n-2)を求める過程で同じ計算を何度もしてしまうことになり効率が悪い。 これをO(n)で計算するためには、第n項から第1項に向かって順に求めていくのはなく、
実際にあなたがフィボナッチ数列を求めるように、第1項から第n項に向かって計算していけばよい。
つまり、

# let rec fib2 a b n cnt =
 if(n=cnt) then b
   else fib2 b (a+b) n (cnt+1)
;;
val fib2 : int -> int -> int -> int -> int = <fun>
# let fib n =
    fib2 1 1 n 2
;;
val fib : int -> int = <fun>

とすればよい。fib2でのcntはbが第何項かを保持している
ここで、recオプションを用いた再帰関数や、そのうち書くつもりだがandを用いて関数を同時に宣言する以外では、関数内で用いる関数は、その関数の定義時には既に定義されていなければならない。なので、補助関数fib2はfib内で使われているので、fib以前に定義しなければならない。

OCaml入門の第一歩として、変数や関数の定義をしてみる。
まずOCamlは、CやJAVAのようにソースコードを何行も書いてそれを一気にコンパイルすると言った形を取らず、 命令を書いたらそれが一行一行実行される。（正確には;;と打つたびに実行される）

なので、関数名や変数名が重複すると、2回目以降で定義した時に上書きされてしまう。だが、これはデバッグなんかを簡単に出来るので慣れてしまえば逆に便利だ

まずは変数の定義と四則演算

# let a = 7;;
val a : int = 7
# let b = 5;;
val b : int = 5
# a + b;;
- : int = 12
# a - b;;
- : int = 2
# a * b;;
- : int = 35
# a / b;;
- : int = 1
# a mod b;;
- : int = 2

浮動小数点を扱いたい時は

# let c = 2.5;;
val c : float = 2.5
# let d = 0.2;;
val d : float = 0.2
# c +. d;;
- : float = 2.7
# c -. d;;
- : float = 2.3
# c *. d;;
- : float = 0.5
# c /. d;;
- : float = 12.5

のように演算子にも.をつける必要がある。もし、それを書き忘れたら

# c + d;;
This expression has type float but is here used with type int

と即座にエラーが出て、コンパイルエラーで何行目が・・・のようにならずに違えた瞬間に教えてくれる。
また、円周率の計算は次の式でできる。

# let pi = 4.0 *. atan(1.0);;
val pi : float = 3.14159265358979312

関数の定義も同じletを使って行える。

# let f a b x =
  a*x + b
;;
val f : int -> int -> int -> int = <fun>
# f 3 4 5;;
- : int = 19

と書くと、3つの整数を引数にとって、a*x +bを返す関数が定義できる。
また、

# let f2 = f 2 3;;
val f2 : int -> int = <fun>
# f2 2;;
- : int = 7

のように、関数を使って関数を定義することも出来る。f2は、ひとつの整数を引数にとり、2*x+3を返す関数である。

関数型言語であるOCaml(Objective Caml)を使ってみる。OCamlは、実行速度がJavaなどよりはるかに速く、Cにかなり近いスピードが出る。そして、使用言語が自由なICFP（International Conference on Functional Programming，国際関数型プログラミング学会）のプログラミングコンテストの上位者の多くがOCamlを使っているらしい。

今回は、その動作環境のインストールについて
マシンはWindowsPCを想定している。
WindowsでOCamlをインストールする場合、CygwinとMinGWの２種類の方法があるが、今回はCygwinで入れることにする。

①まず、http://www.cygwin.com/からCygwinをインストールするためのsetupファイルをダウンロードする。Cygwin自体はインストールされているが、OCamlは入ってないという人もこちらから

②ダウンロードできたらsetup.exeを実行し、『次へ』→『次へ』→Default Text File TypeをDOS / textにして『次へ』→『次へ』
→『次へ』ダウンロードサーバーの一覧が出るが下のほうのftp://～～～.jpを選び『次へ』→DevelからOcamlを選んでinstallに、後は『次へ』を選んでいくとインストールできる。

インストールが完了したら、Cygwinを起動し、OCamlと打てばOCamlが実行できる。終了する時は、#quit;;
注意しないといけないのが、画面にはすでに#が出ているが、それとは別に#quit;;を打つ必要があること

だが、このままでは、OCaml実行中にキーボードの→や←を押すと、表示はされないがそのキーコードが入力されてしまい、実行時にエラーとなる。

これはかなり不便なので、leditというソフトを入れる。

③ここからledit-1.11.tar.gzをダウンロード

④解凍ツールを持っている場合は解凍し、なければCygwinのtar xzvf ledit-1.11.tar.gzコマンドで解凍する

⑤解凍したら、Cgwinで出来たフォルダの中に移動し、makeコマンドを実行

⑥その後、make installコマンドを実行

これでleditがインストールされる。起動は、Cgwinでledit OCamlと打てば実行でき、今度は→とか←とかを打ってもへんなことにはならない