リスト
次は「リスト (list)」というデータ構造を説明します。OCaml のリストは「連結リスト (Linked List)」のことです。リストを扱うプログラミング言語といえば Lisp が有名です。SML/NJ や Haskell などの関数型言語や論理型言語の Prolog も、組み込みのデータ構造として連結リストを装備しています。
連結リストは単純なデータ構造ですが、他のデータ構造を実装するときに用いられることがあります。連結リストは基本的で重要なデータ構造の一つなのです。OCaml のリストは Lisp のリストと同じで、複数のデータを格納することができます。ただし、Lisp のリストとは違って、リストの要素は同じデータ型でなければいけません。
●リストの構造
リストの構造を図で表すと次のようになります。
リストは貨物列車にたとえるとわかりやすいでしょう。車両に相当するものを「コンスセル (cons cell)」といいます。貨物列車には多数の車両が接続されて運行されるように、リストは複数のコンスセルを接続して構成されます。1 つのコンスセルには、貨物 (データ) を格納する場所と、連結器に相当する場所があります。
上図では、コンスセルを箱で表しています。コンスセルの左側がデータを格納する場所で、右側が次のコンスセルと連結しています。この例では、3 つのコンスセルが接続されています。それから、最後尾のコンスセルには、リストの終わりを示す特別なデータが格納されます。OCaml の場合、要素が一つもないリスト (空リスト) を表すデータ [ ] でリストの終端を表します。
●リストの構成法
OCaml のリストは、要素をセミコロン ( ; ) で区切り、角カッコ [ ] で囲んで表します。次の例を見てください。
# let a = [1; 2; 3; 4];; val a : int list = [1; 2; 3; 4] # let b = ["abc"; "def"; "ghi"];; val b : string list ["abc"; "def"; "ghi"] # let c = [(1, 2); (3, 4); (5, 6)];; val c : (int * int) list= [(1, 2), (3, 4), (5, 6)] # let d = [[1]; [2; 3]; [4; 5; 6]];; val d : int list list = [[1]; [2; 3]; [4; 5; 6]] # let e = [1 + 2 + 3; 4 * 5 * 6];; val e : int list = [6; 120]
変数 a のリストは要素が int なので型は int list になります。[1] や [2; 3] も型は int list になります。リストに格納された要素の個数を「リストの長さ」といいます。リストの型はリストの長さとは関係なく、格納する要素の型によって決まります。変数 b のリストは要素が文字列なので型は string list になります。
組をリストに入れてもかまいません。変数 c は組 int * int を格納するリストなので、型は (int * int) list になります。このリストに (1, 2, 3) という組を入れることはできません。(1, 2, 3) の型は int * int * int で、int * int とは型が異なるからです。
リストは入れ子にすることができます。変数 d のリストは [1], [2; 3], [4; 5; 6] という int list を格納しています。したがって、型は int list list になります。このリストに [[7]] を入れることはできません。[[7]] の型は int list list になるので、要素の型 int list とは異なるからです。また、最後の例のように角カッコの中に式を書くと、それを評価した値がリストの要素になります。
●リストの合成と分解
リストは関数 hd, tl を使って分解し、演算子 :: (コンス演算子) で合成することができます。また、演算子 @ でリストを連結することができます。次の例を見てください。
# let a = [1; 2; 3; 4];; val a : int list = [1; 2; 3; 4] # List.hd a;; - : int = 1 # List.tl a;; - : int list = [2; 3; 4] # let b = 0 :: a;; val b = [0; 1; 2; 3; 4] # let c = [1; 2; 3] @ [4; 5; 6];; val c : int list = [1; 2; 3; 4; 5; 6]
OCaml の場合、リストを操作する関数は標準ライブラリ List に定義されています。OCaml は「モジュール」という機能を使ってライブラリを構成しています。モジュール内の関数は "モジュール名 + ドット ( . ) + 関数名" という形式で呼び出します。関数 hd を呼び出すときは List.hd とし、関数 tl を呼び出すときは List.tl とします。
hd a は Lisp の関数 car と同じで、リスト a の先頭要素を取り出します。リスト [1; 2; 3; 4] の先頭要素は 1 なので、hd a は 1 を返します。tl a は Lisp の関数 cdr と同じで、リスト a から先頭要素を取り除いたリストを返します。tl a は [1; 2; 3; 4] から 1 を取り除いた [2; 3; 4] を返します。演算子 :: は Lisp の関数 cons と同じで、リストの先頭にデータを付け加えます。演算子 @ は Lisp の関数 append と同じで、2 つのリストをつないだリストを返します。
hd, tl, コンス演算子の関係を図に表すと次のようになります。
この関係はリストを操作する関数を作る場合の基本になります。
要素のないリストを「空リスト」といい、OCaml では [ ] で表します。次の例を見てください。
# [];; - : 'a list = [] # List.tl [1];; - : int list = [] # List.tl ["abc"];; - : string list = []
[ ] はどのようなリスト型にもあてはまります。[ ] だけを入力すると型は 'a list と表示されます。要素が一つしかないリストに tl を適用すると空リストになります。次の例は int list に tl を適用したので、[ ] を int list と表示しました。3 番目の例のように、string list の空リスト [ ] は string list と表示されます。リスト自身は多相的なデータ型で、格納する要素のデータ型によってリストのデータ型が決まることに注意してください。
コンス演算子を続ける場合は結合規則に注意してください。次の例を見てください。
1::2::3::[] => (1::(2::(3::[]))) => [1; 2; 3]
このように、コンス演算子は四則演算とは違って「右結合」になります。また、コンス演算子の右辺はリストでなければいけません。1::2 はエラーになります。ご注意くださいませ。
実際のプログラムでは、hd や tl でリストを分解するよりも「パターンマッチング」を使った方が簡単です。リストのパターンマッチングはあとで詳しく説明します。
●再帰定義によるリスト操作
リストを操作する関数は再帰定義を使うと簡単に作ることができます。実は、リスト操作と再帰定義はとても相性が良いのです。まずは、リストの長さを求める関数 length を作りましょう。 OCaml には List.length という同等の機能を持つ関数が用意されていますが、再帰定義を使えば簡単に作ることができます。
まず、いちばん簡単な場合を考えます。引数が空リストであれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト ls の長さを求めるには、リスト ls に tl を適用したリストの長さがわかればいい、と考えるのです。それに 1 を足せば、リストの長さを求めることができます。これをプログラムすると、次のようになります。
リスト 5 : リストの長さを求める let rec length ls = if ls = [] then 0 else 1 + length (List.tl ls)
引数 ls が空リストであれば 0 を返します。そうでなければ、引数 ls に関数 tl を適用して length を再帰呼び出しします。リストに tl を繰り返し適用していくと最後は空リストになります。ここで再帰呼び出しが止まって 0 を返します。そうすると、1 + length によって length の返り値に 1 を足した値を返していきます。すなわち tl した回数だけ 1 が足されるわけです。
実際に length を定義すると次のように表示されます。
val length : 'a list -> int = <fun>
length の場合、任意の型 'a を格納するリストを引数に取り、int を返すことが示されています。つまり、引数が int list でも string list でも、リストであればその長さを返すことができます。このように、length は多相型関数として定義されます。OCaml の関数 hd, tl も多相型関数です。
# List.hd;; - : 'a list -> 'a = <fun> # List.tl;; - : 'a list -> 'a list = <fun>
それでは実際に試してみましょう。
# length [1; 2; 3; 4; 5; 6];; - : int = 6 # length ["ab", "cd", "ef"];; - : int = 3
正常に動作していますね。なお、length を末尾再帰で直すと次のようになります。
リスト 6 : 末尾再帰版
let length ls =
let rec iter ls a =
if ls = [] then a
else iter (List.tl ls) (a + 1)
in
iter ls 0
●リストの連結
次はリストを連結する演算子 @ と同じ動作をする関数 append を作ってみましょう。引数としてリスト xs と ys を渡して、それを連結したリストを返します。
処理手順ですが、簡単な場合から考えていきましょう。まず、リスト xs が空リストならば、リスト ys を返すだけでいいですね。次に、リスト xs に要素が 1 つしかない場合を考えてみます。これは、リスト xs に hd を適用して要素を取り出し、それをコンス演算子でリスト ys の先頭に追加すればいいでしょう。
それでは、リスト xs に要素が複数ある場合を考えてください。リスト xs を hd と tl で分解します。そして、tl xs と ys を連結したリストを求め、そのリストの先頭に hd xs を追加すれば xs と ys を連結することができます。tl xs と ys の連結は再帰呼び出しで実現することができます。これを図に示すと次のようになります。
これをプログラムすると次のようになります。
リスト 7 : リストの結合 let rec append xs ys = if xs = [] then ys else List.hd xs :: append (List.tl xs) ys
引数 xs が空リストであればリスト ys をそのまま返します。これが再帰呼び出しの停止条件になります。そうでなければ、tl xs を append に渡して再帰呼び出しします。そして、その返り値と hd xs をコンス演算子で接続します。これでリストを連結することができます。
実際に append を定義すると、次のように表示されます。
val append = 'a list -> 'a list -> 'a list
このように、append も多相型関数になります。簡単な実行例を示します。
# append [1; 2; 3] [4; 5; 6];; - : int list = [1; 2; 3; 4; 5; 6] # append ["ab"; "cd"] ["ef"; "gh"];; - : string list = ["ab"; "cd"; "ef"; "gh"]
●リストの反転
今度はリストの要素を反転する関数 reverse を作ってみましょう。OCaml には List.rev という同等の機能を持つ関数が用意されていますが、私達でも簡単に作ることができます。reverse は引数のリスト xs を hd と tl で分解し、tl xs を反転させてから hd xs を最後尾に追加することで実現できます。次の図を見てください。
これをプログラムすると、次のようになります。
リスト 8 : リストの反転 let rec reverse xs = if xs = [] then [] else reverse (List.tl xs) @ [List.hd xs]
引数 xs が空リストの場合は [ ] を返します。そうでなければ、reverse を再帰呼び出しして tl xs を反転し、演算子 @ で反転したリストの最後尾に先頭の要素を追加します。
実際に reverse を定義すると、次のように表示されます。
val reverse : 'a list -> 'a list = <fun>
reverse も多相型関数になります。簡単な実行例を示します。
# reverse [1; 2; 3];; - : int list = [3; 2; 1] # reverse ["ab"; "cd"; "ef"];; - : string list = ["ef";"cd";"ab"]
正常に動作していますね。なお、このプログラムはリストを連結する @ 演算子を使っているので効率的ではありません。末尾再帰で書き直すと次のようになります。
リスト 9 : 末尾再帰版
let reverse ls =
let rec iter ls a =
if ls = [] then a
else iter (List.tl ls) (List.hd ls :: a)
in
iter ls []
リスト ls の先頭要素を取り出し、コンス演算子で累積変数 a の先頭に追加していけば、ls の逆順のリストを得ることができます。
●リストの探索
最後に、リストからデータを探索する関数 member を作ってみましょう。OCaml にはデータを見つけたら true を返し、見つからない場合は false を返す関数 List.mem がありますが、ここでは Common Lisp の関数 member と同等の動作をする関数を作ります。
member はリストの中にデータがなければ空リストを返します。データを見つけた場合は、そのリストの残りを返します。つまり、返り値のリストの先頭要素が見つけたデータになります。
プログラムは次のようになります。
リスト 10 : リストの探索 let rec member x ys = if ys = [] then [] else if x = List.hd ys then ys else member x (List.tl ys)
関数 member はリスト ys の中から x と等しい要素を探します。これは member を再帰呼び出ししてリストを分解し、リストの先頭要素をチェックしていくことで実現できます。
ys が空リストの場合は x を見つけることができなかったので [ ] を返します。これが再帰の停止条件になります。次に、リスト ys の先頭の要素 hd ys が x と等しいかチェックします。等しい場合は、リスト ys をそのまま返します。そうでなければ、member を再帰呼び出しして次の要素を調べます。
実際に member を定義すると、次のように表示されます。
val member : 'a -> 'a list -> 'a list
それでは、簡単な実行例を示します。
# member 3 [1; 2; 3; 4; 5];; - : int list = [3; 4; 5] # member 5 [1; 2; 3; 4; 5];; - : int list = [5] # member 0 [1; 2; 3; 4; 5];; - : int list = [] # member "ab" ["ab"; "cd"; "ef"];; - : string list = ["ab";"cd";"ef"] # member "ac" ["ab"; "cd"; "ef"];; - : string list = []
データが見つからない場合、空リストが返されますが、そのデータ型は引数のリストと同じデータ型であることに注意してください。OCaml の関数は、異なるデータ型を返すことができません。たとえば、見つけた場合はその要素を返し、見つからない場合は false を返す、ということはできないのです。要素を返したい場合は option というデータ型を使うと簡単です。これは後で詳しく説明します。
●問題
次の関数を定義してください。
- 要素 x を n 個持つリストを生成する関数 make_list x n
- 整数 n から m までを格納したリストを作る関数 iota n m
- リスト xs の先頭から n 個の要素を取り出す関数 take xs n
- リストの先頭から n 個の要素を取り除く関数 drop xs n
- 2 つのリスト xs, ys の要素をタプルにまとめたリストを返す関数 zip xs ys
- zip の逆変換を行う関数 unzip
なお、OCaml には zip, unzip と同様の関数 List.combine, List.split が用意されています。
●解答
# let rec make_list x n =
if n = 0 then []
else x :: make_list x (n - 1);;
val make_list : 'a -> int -> 'a list = <fun>
# make_list 0 10;;
- : int list = [0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
# make_list "foo" 5;;
- : string list = ["foo"; "foo"; "foo"; "foo"; "foo"]
# make_list (1, "foo") 3;;
- : (int * string) list = [(1, "foo"); (1, "foo"); (1, "foo")]
# let rec iota n m =
if n > m then []
else n :: iota (n + 1) m;;
val iota : int -> int -> int list = <fun>
# iota 1 10;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
# iota 1 1;;
- : int list = [1]
# iota 1 0;;
- : int list = []
# let rec take xs n =
if xs = [] || n = 0 then []
else List.hd xs :: take (List.tl xs) (n - 1);;
val take : 'a list -> int -> 'a list = <fun>
# take [1;2;3;4;5] 0;;
- : int list = []
# take [1;2;3;4;5] 3;;
- : int list = [1; 2; 3]
# take [1;2;3;4;5] 5;;
- : int list = [1; 2; 3; 4; 5]
# let rec drop xs n =
if xs = [] || n = 0 then xs
else drop (List.tl xs) (n - 1);;
val drop : 'a list -> int -> 'a list = <fun>
# drop [1;2;3;4;5] 0;;
- : int list = [1; 2; 3; 4; 5]
# drop [1;2;3;4;5] 3;;
- : int list = [4; 5]
# drop [1;2;3;4;5] 5;;
- : int list = []
# let rec zip xs ys =
if xs = [] || ys = [] then []
else (List.hd xs, List.hd ys) :: zip (List.tl xs) (List.tl ys);;
val zip : 'a list -> 'b list -> ('a * 'b) list = <fun>
# zip [1; 2; 3] [4; 5; 6];;
- : (int * int) list = [(1, 4); (2, 5); (3, 6)]
# zip ["foo"; "bar"; "baz"] [1; 2; 3];;
- : (string * int) list = [("foo", 1); ("bar", 2); ("baz", 3)]
# let rec unzip xs =
if xs = [] then ([], [])
else let (y, z) = List.hd xs in
let (ys, zs) = unzip (List.tl xs) in (y :: ys, z ::zs);;
val unzip : ('a * 'b) list -> 'a list * 'b list = <fun>
# unzip [(1, 2); (3, 4); (5, 6)];;
- : int list * int list = ([1; 3; 5], [2; 4; 6])
# unzip [('a', 2); ('b', 4); ('c', 6)];;
- : char list * int list = (['a'; 'b'; 'c'], [2; 4; 6])
改訂 2020 年 6 月 21 日