24691


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

[code]

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

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

[code]

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

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

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


CC BY-SA 3.0
2016-05-09T22:50:33.687
24684
2016-05-10T04:58:07.763
2016-05-09T23:58:54.797
939
939
question
ocaml
任意の要素をリストの最後に追加したリストを作成する方法


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

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


CC BY-SA 3.0
2016-05-09T23:38:22.823
24685
2016-05-09T23:38:22.823
982
24684
answer


示唆されたところによると、OCamlにおいてリストは[単一連結リスト(？)](https://realworldocaml.org/v1/en/html/lists-
and-
patterns.html)という形になっているため、最後に要素を追加するときにはコストがかかり、非推奨であるようです。実際に[Ideon](https://ideone.com/gdq4Bp)で検証コードを書いて頂いたところ、パフォーマンスの違いが明確になっています。

同様に、[海外のStackOverflow](https://ideone.com/gdq4Bp)でも[同様の示唆があります](http://www.joelonsoftware.com/articles/fog0000000319.html)。従って、リストの最後に要素を追加したい場合は、上の方法を取るしかなさそうです。


CC BY-SA 3.0
2016-05-09T23:49:12.773
24687
2016-05-09T23:49:12.773
939
24684
answer


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

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

ですが、

[code]

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

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

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

[code]

    let rec wrong_append xs ys = match ys with
      | [] -> xs
      | y::ys' -> wrong_append (xs@[y]) ys'
    
[/code]

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

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

[code]

    (* リストの先頭 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
    
[/code]

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

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

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


CC BY-SA 3.0
2016-05-10T02:35:54.687
24691
2016-05-10T04:58:07.763
2016-05-10T04:58:07.763
898
898
24684
answer


**[ocaml-3.12.1-print/pervasives.ml](https://github.com/diml/ocaml-3.12.1-print/blob/master/stdlib/pervasives.ml#L202)**

[code]

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

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

[code]

    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]
    
[/code]

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


CC BY-SA 3.0
2016-05-10T02:37:22.927
24692
2016-05-10T02:37:22.927
24684
answer