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
) などです。