8

OCamlで末尾再帰のリストソート関数を実装しようとしていますが、次のコードを思いつきました。

let tailrec_merge_sort l =
  let split l = 
    let rec _split source left right =
      match source with
        | [] -> (left, right)
        | head :: tail -> _split tail right (head :: left) 
    in _split l [] []
  in

  let merge l1 l2 = 
    let rec _merge l1 l2 result =
      match l1, l2 with
        | [], [] -> result
        | [], h :: t | h :: t, [] -> _merge [] t (h :: result)
        | h1 :: t1, h2 :: t2 ->
            if h1 < h2 then _merge t1 l2 (h1 :: result)
            else            _merge l1 t2 (h2 :: result)
    in List.rev (_merge l1 l2 [])
  in

  let rec sort = function
    | [] -> []
    | [a] -> [a]
    | list -> let left, right = split list in merge (sort left) (sort right)
  in sort l
;;

しかし、「評価中のスタックオーバーフロー（ループ再帰？）」エラーが発生したため、実際には末尾再帰ではないようです。

このコードで末尾再帰ではない呼び出しを見つけるのを手伝っていただけませんか。私はそれを見つけることなく、かなりたくさん検索しました。sortそれは関数のletバインディングですか？

4

2 に答える 2

9

マージソートは、本質的に末尾再帰ではありません。 並べ替えには2 つの再帰呼び出しが必要であり、任意の関数の任意の実行で、最大1 つの動的呼び出しを末尾位置にすることができます。(splitはテール以外の位置からも呼び出されますが、一定のスタック スペースを使用する必要があるため、問題ありません)。

OCaml の最新バージョンを使用していることを確認してください。 バージョン 3.08 以前でList.revは、スタックが壊れる可能性がありました。この問題は、バージョン 3.10 で修正されています。バージョン 3.10.2 を使用すると、コードを使用して1,000 万個の要素のリストを並べ替えることができます。数分かかりますが、スタックを吹き飛ばしません。だから私はあなたの問題が古いバージョンのOCamlを持っているという単純なものであることを願っています.

そうでない場合、適切な次のステップは環境変数を設定することです

OCAMLRUNPARAM=b=1

スタックを吹き飛ばすとスタックトレースが得られます。

また、並べ替えている配列の長さも知りたいです。マージソートは末尾再帰にすることはできませんが、その非末尾の性質により、対数のスタックスペースが必要になります。

1,000 万を超える要素を並べ替える必要がある場合は、別のアルゴリズムを検討する必要があるのではないでしょうか? または、必要に応じて、mergesort を手動で CPS 変換することもできます。これにより、ヒープに継続を割り当てる代わりに末尾再帰バージョンが生成されます。しかし、私の推測では、それは必要ないでしょう。

于 2010-03-27T22:12:06.917 に答える
7

表現

merge (sort left) (sort right)

末尾再帰ではありません。呼び出し（マージ）に残りの作業がある間、（左にソート）と（右にソート）の両方を再帰的に呼び出します。

追加の継続パラメータで修正できると思います。

  let rec sort l k =
    match l with
    | [] -> k [] 
    | [a] -> k [a] 
    | list -> let left, right = split list in sort left (fun leftR -> sort right (fun rightR -> k (merge leftR rightR)))
  in sort l (fun x -> x)
于 2010-03-27T14:33:06.657 に答える