sorting - 昇順のリストに要素を挿入する [ocaml]

Question

次のコードは、昇順で並べ替えられたリストに要素を挿入します。

let rec insert x l =
  match l with
    | [] -> [x]
    | y::ys -> if x < y then x::y::ys else y::insert x ys

ただし、List.fold_right を使用して再帰を使用せずに上記の関数を実装するにはどうすればよいですか?

Answer 1

の最も単純な実装を見てくださいList.fold_right:

let rec fold_right f li init = match li with
  | [] -> init
  | y::ys -> f y (fold_right f ys init)

次のようなものを試すことができます

let insert x li =
  let add_x y inserted_ys =
    if x < y then x::y::inserted_ys
    else y::inserted_ys
  in
  List.fold_right add_x li [x]

問題は、then分岐が正しくないことです。xリストの先頭とinserted_ys. ただし、のすべての要素が よりも大きいためx、リストのどの位置にあるかはわかっています。したがって、で削除できます。inserted_ysysxxList.tl

let insert x li =
  let add_x y inserted_ys =
    if x < y then x::y::(List.tl inserted_ys)
    else y::inserted_ys
  in
  List.fold_right add_x li [x]

これは複雑な書き方であることに注意してinsertください。より良い手法はadd_x、リストとブール値のペアを返すことです。ブール値は、x既に追加されているかどうかを示します。

Answer 2

ソリューションのスキームは次のようなものだと思います。

fun insert x l =
    List.fold_right (fun a b -> if <test> then a :: x :: b else a :: b) l []

関数が呼び出されるたびに、最終的なリストの最後と、通常はリストの前に次に移動する新しい要素が表示されます。xこの情報に基づいて、現在の位置に値を挿入するかどうかを決定できるようです。

このスキームの単純な実装では、結果に x が何度も挿入されます。<test>しかし、十分に具体的にすればうまくいくように思えます。

このスキームは、x がリストの先頭にある場合にも機能しません。その場合は個別に処理する必要があります。

Gasche が言うように、これは昇順リストを作成する効果的な方法ではありません。(FWIW ガッシェは私よりはるかに知識豊富な OCaml エキスパートです :-)