[OCaml]#7 List.map List.fold_right List.fold_leftを使ってみる

デフォルトで定義されている、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
;;

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