任意の要素をリストの最後に追加したリストを作成する方法

投稿者: Anonymous

OCamlでコードを書いているときに、リスト操作をすることがあるのですが、

4 :: [1; 2; 3];;

みたいに、 リストの先頭に対して要素を追加したリストを作成する方法はわかるのですが、リストの最後に対して追加したリストを作る方法がわかりません。とりあえずの方法として:

[1; 2; 3;] @ [4];;

という風にしているのですが、たかだか要素を後ろに追加するだけのために、リストを作っているのは、変な印象を受けます。

もし直接、リストの最後に要素を追加する方法があれば教えていただければと思います。

解決

Listのappend (xs @ ys) はxsの各要素を ::ys に追加していくので、ysの長さと関係なく、xs の長さに比例した時間がかかります。(なお :: は引数に関係なく定数時間で処理が終了します。)

ですから、 y :: xs:: 一回の操作ですみますが、 xs @ [y]xs の長さに比例した時間がかかります。これが xs @ [y] という式を書いてはいけないといわれる理由です。

ですが、

[1; 2; 3;] @ [4];;

というコードが単体である場合は、それ以外にリストの最後に要素を追加する合法(違法な方法があります。後述)な手はありませんから、それで構わないです。

xs @ [y] は避けよと言われるのはライブラリ関数や再帰関数中などで、 xs の長さがいくらでも長くなる可能性がある場合です。たとえば:

let rec wrong_append xs ys = match ys with
  | [] -> xs
  | y::ys' -> wrong_append ([email protected][y]) ys'

このような関数は書いてはいけません。これはxsの長さをm、ysの長さをnとすると、m + m+1 + … + m+n-1 回の :: を呼び出すことになり、普通に xs @ ys を使った場合(m) と比べると非常に遅くなります。

再帰関数中でリストを状態として持ちまわしつつ、その最後尾に要素を足したい場合は、そうせず、その状態を逆順のリストとして持つコードを書き :: で先頭に付け足していきながら、最後に逆転させることが多いです:

(* リストの先頭 n 個の要素からなるリストを返す関数 take *)

(* 補助関数 *)
let rec take_aux n st xs =
  if n <= 0 then List.rev st
  else match xs with
    | [] -> List.rev st
    | x::xs -> take_aux (n-1) (x::st) xs

let take n xs = take_aux n [] xs

この例でだと :: の呼び出し回数は 2n くらいになります。これは末尾再帰関数を書く事とも関係しているので是非理解しておきたいポイントです。

なお、大昔のExtlibに破壊的にリストの最後尾に要素を追加する関数がありましたが今は無いようです。これはOCamlの内部値表現をいじる「違法な」方法で実現されていていて、当時(もしくは現在)のOCamlコンパイラの実装でたまたまうまく動くといったもので、全く推奨される方法ではありません。

最後に、もしリストの先頭にも末尾にも要素を頻繁に付け加えたい場合はリストではなく別のデータ型を使うという選択も考えるべきです。たとえばキュー (Queue.t) などです。

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *