5

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

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

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

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

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

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

4 件の回答 4

6

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 (xs@[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) などです。

2

示唆されたところによると、OCamlにおいてリストは単一連結リスト(?)という形になっているため、最後に要素を追加するときにはコストがかかり、非推奨であるようです。実際にIdeonで検証コードを書いて頂いたところ、パフォーマンスの違いが明確になっています。

同様に、海外のStackOverflowでも同様の示唆があります。従って、リストの最後に要素を追加したい場合は、上の方法を取るしかなさそうです。

3
  • 1
    OCamlでもリストは不変なのではないでしょうか。そうであれば、どちらの端にであれ、要素を追加する事は出来ません。新しいリストを作る際に先頭へ追加するのであれば、元のリストと要素たちを共有出来る、リスト末尾まで辿らなくてよい、という2点で効率的だという事でしょう。
    – mjy
    Commented 2016年5月9日 23:55
  • 確かにご指摘通りだと思います。正確には「要素をリストに追加する」ではなく、「要素を追加したリストを作成する」になりますね。修正しておきます。ありがとうございます。
    – esehara
    Commented 2016年5月9日 23:57
  • MLではリストは不変ですので「リストの先頭に要素を追加した新しいリストを作成する」という意味としての「リストの先頭に要素を追加する」という表現は普通に英語日本語でも使われます。特に混乱はありません。 Commented 2016年5月10日 2:01
1

データ構造からするとなさそう。
http://www.atmarkit.co.jp/fdotnet/special/introfs_01/introfs_01_03.html

F# のマニュアルにも新しく後ろに要素を追加するときは新しいリストを生成する例しか載ってませんでした。
https://msdn.microsoft.com/ja-jp/library/dd233224.aspx

0

ocaml-3.12.1-print/pervasives.ml

let rec (@) l1 l2 =
  match l1 with
    [] -> l2
  | hd :: tl -> hd :: (tl @ l2)

と定義されているので、これを少し変更して @@ として定義してみます。

let rec (@@) l1 l2 =
  match l1 with
    [] -> [l2]   (* return list *)
  | hd :: tl -> hd :: (tl @@ l2);;


# [1;2;3;] @@ 4;;
- : int list = [1; 2; 3; 4]

まぁ、この様なやり方が OCaml らしいのかどうかは分かりませんが…

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。