2

入力: ソートされていないリスト / 出力: ソートされたリスト

私の基本的なアイデアは、ソートされたリストに整数を挿入することです。

(ソートされた末尾に最初の要素を挿入できれば、リストをソートできます。)

ヘルパー関数である「挿入」を使用しました。

ただし、オーバーフローします。誰が問題が何であるか教えてもらえますか?

let rec sort (l: int list) : int list =
    match l with
        []->[]
      | x::[]->[x]
      | x1::x2::xs->let rec insert (n,dest) =
                            match dest with
                                []->[n]
                              | y::[]-> if n<y then [n;y] else [y;n]
                              | y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs)
                    in insert(x1,sort(x2::xs)) ;;
4

3 に答える 3

8

繰り返しますが、スタイルの提案があります。

  • sort2 つの関数を分離する必要があります。insertこれは、読みやすくするためと、insert関数自体が役立つ可能性があるためです。
  • insert関数の引数としてタプルを指定するのはなぜですか? OCaml では、insert x lの代わりにカリー化と書き込みを使用しますinsert(x,l)。これにより、部分的なアプリケーションを実行できます。
  • 関数のタイプを に制限するのはなぜですかint list -> int list。OCaml の関数は多態的である可能性があるため、関数はより一般的な型を持つ必要があります'a ist -> 'a list。

これらすべての修正を行って取得したコードは次のとおりです。

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

let rec sort l =
  match l with
    | [] -> []
    | x::xs -> insert x (sort xs)
于 2013-04-10T10:32:58.243 に答える
4

この行は私にはかなり間違っているように見えます:

| y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs)

ysあなたは自分が（帰納仮説によって）ソートされていることを知っているようです。したがって、互いに比較nするの ysではなく、と比較する必要があります。ysこの線をまっすぐにすると、状況はおそらく改善されます。

価値があるのは、match. 1要素のリストを他のnull以外のリストとは異なる方法で扱う必要がある理由がわかりません。

于 2013-04-10T01:30:46.180 に答える