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