0 
let rec merge = function
| ([], ys) -> ys
| (xs, []) -> xs
| (x::xs, y::ys) -> if x < y then x :: merge (xs, y::ys)
                    else y :: merge (x::xs, ys)

let rec split = function
| [] -> ([], [])
| [a] -> ([a], [])
| a::b::cs -> let (M,N) = split cs
              (a::M, b::N)

let rec mergesort = function
| [] -> []
| L -> let (M, N) = split L
       merge (mergesort M, mergesort N)


mergesort [5;3;2;1]  // Will throw an error.

ここからこのコードを取得しましたStackOverflow Questionしかし、リストを使用してマージソートを実行すると、エラーが発生します:

stdin(192,1): error FS0030: Value restriction. The value 'it' has been inferred to have generic type
    val it : '_a list when '_a : comparison

この問題を解決するにはどうすればよいですか? 何が問題ですか？情報が多ければ多いほど良いです（だから私は学ぶことができます:)）

4

1 に答える 1

3

マージソート関数にケースが欠落しているため、署名が本来あるべきでは'a list -> 'b listなくコンパイラによって推測され'a list -> 'a listます。そうあるべき理由'a list -> 'a listは、マージソートでリストのタイプを変更しようとしていないからです。

mergesort 関数をこれに変更してみてください。これで問題が解決するはずです。

let rec mergesort = function
 | [] -> []
 | [a] -> [a]
 | L -> let (M, N) = split L
        merge (mergesort M, mergesort N)

ただし、コードの別の問題は、マージも分割も末尾再帰的ではないため、大きなリストでスタック オーバーフロー例外が発生することです (このように修正されたマージソートを呼び出してみてくださいmergesort [for i in 1000000..-1..1 -> i])。

アキュムレータ パターンを使用して、分割およびマージ関数を末尾再帰にすることができます。

let split list =
  let rec aux l acc1 acc2 =
    match l with
        | [] -> (acc1,acc2)
        | [x] -> (x::acc1,acc2)
        | x::y::tail ->
            aux tail (x::acc1) (y::acc2)
  aux list [] []

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

アキュムレータ パターンの詳細については、こちらを参照してください。例は Lisp で書かれていますが、テール コールの最適化を提供する任意の言語で機能する一般的なパターンです。

于 2013-05-30T06:23:34.923 に答える