2

私はOCamlを学ぼうとしていますが、まだfold関数に少し苦労しています。少し調べてみたところ、foldleftを使用して挿入ソートを実装している次のコードスニペット（Scalaで記述）が見つかりました。私はその考えを理解したと思いますが、Scalaについてはまったく何も知らないので、まだ少し説明が必要です。だから、私の質問は2つあると思います（ha、わかりますか？）、この関数はOcamlでどのように記述され、実際にはどのように機能しますか？ 

def insertionSort[A <% Ordered[A]](list: List[A]): List[A] =
  list.foldLeft(List[A]()) { (r,c) =>
    val (front, back) = r.span(_ < c)
    front ::: c :: back
  }

助けてくれてありがとう！

4

2 に答える 2

2

上でコメントしたように、これは特に良い並べ替え方法ではありません (Scala コードを理解していると仮定しますが、理解していない可能性があります)。これは、何をしているように見えるかを OCaml に翻訳したものです。

let insertion_sort l =
    let add1 sortedl x =
        let le, gt = List.partition ((>=) x) sortedl
        in
            le @ [x] @ gt
    in      
        List.fold_left add1 [] l

FP コードをしばらく書くと、折り畳みが非常に自然になります。目的は、データ構造 (リストなど) の一連の要素を既知の順序 (左端など) で処理しながら、処理中に渡される状態を維持することです。最も単純なケース (ここのように) では、状態が最終的な答えでもあります。それ以外の場合は、最終的な回答とともに追加の状態を保持する必要があります。そのような場合、最後に最終的な答えを抽出します。

これを言うべきではないかもしれませんが、折り畳みはfor(;;)、ループで変更する予定のすべての状態をカプセル化することを除いて、C ファミリーのステートメントに似ています。このように、これは適切に制御された形式の反復です。

対応は次のようになります。

for(state = S, x = first(D); more(D); x = next(D)) { state = E(state, x) }

fold_left (fun state x -> E state x) S D

変更された状態をカプセル化する規則は、通常、慣れると非常に役立つことがわかります。折りたたんだ関数 (上記の add1 など) は、他の多くの状況で役立つことがよくあります。これは、折りたたみの構造がその場所で一般的に役立つ関数を必要とするためです。

特に、fold 関数には、データ構造をトラバースする方法に関するすべての知識が含まれていることに注意してください。折りたたまれた関数は、各要素をどう処理するかを知る必要があるだけです。したがって、他のコードを変更することなく、データ構造 (およびフォールド) を自由に変更できます。また、同じ関数 (add1上記) を異なるデータ構造で使用することもできます。

于 2012-09-08T20:24:27.973 に答える
0 
let insertion_sort (l: int list) : int list = 
  let rec insert (e: int) (a: int list) =
    match a with
    | [] -> e::a 
    | h::t -> if (e > h) then e::a else h::(insert e t)
  in 
  List.rev (List.fold_left (fun a e -> insert e a) [] l)

List.fold_left は、関数、アキュムレータ、およびリストを受け取ります。アキュムレータは空のリスト [] として初期化する必要があります。これにより、List.fold_left が「l」引数として空のリストを受け取ると、ソートするものが何もないため、空のリストが返されます。

(fun ae -> insert ea) アキュムレータを更新します。List.fold_left がリストを折りたたむと、各要素が取得され、並べ替えられたリストの正しい位置に挿入されます。ヘルパー関数 let rec insert がこのジョブを実行します。

let rec insert (e: int) (a: int list) =
  match a with
  | [] -> e::a 
  | h::t -> if (e > h) then e::a else h::(insert e t)

まず、ソートされたリストが空かどうかを確認します。そうであれば、その要素を空のリストに挿入します。それ以外の場合 (ソート済みリストが空でない場合)、挿入する要素をソート済みリストの先頭と比較し、再帰的にチェックして、ソート済みリスト内の要素のソート済み位置を見つけます。

最後に List.rev が呼び出されます。これは、insert 関数がリストの前に要素を追加するコンス演算子 (::) を使用しているためです。したがって、最終的なリストを逆にする必要があります。

于 2014-10-09T07:03:29.053 に答える