OCamlの最近のブログ記事

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)の実装について考える