Mergesort在F#中遇到错误

问题描述

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问题中获取了这段代码，但是当我运行带有列表的mergesort时我收到一个错误:

I took this code from here StackOverflow Question but when I run the mergesort with a list I get an error:

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

我该如何解决此问题?问题是什么?信息越多越好(所以我可以学习:))

How would I fix this problem? What is the problem? The more information, the better (so I can learn :) )

推荐答案

您的mergesort函数缺少一种情况，导致编译器推断出的签名为'a list -> 'b list而不是应为的'a list -> 'a list.应该为'a list -> 'a list的原因是您不希望更改mergesort中的列表类型.

Your mergesort function is missing a case causing the signature to be inferred by the compiler to be 'a list -> 'b list instead of 'a list -> 'a list which it should be. The reason it should be 'a list -> 'a list is that you're not looking to changing the type of the list in mergesort.

尝试将您的mergesort函数更改为此，这应该可以解决问题:

Try changing your mergesort function to this, that should fix the problem:

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]调用更正的mergesort).

Another problem with your code however is that neither merge nor split is tail recursive and you will therefore get stack overflow exceptions on large lists (try to call the corrected mergesort like this mergesort [for i in 1000000..-1..1 -> i]).

您可以使用累加器模式使split和merge函数尾部递归

You can make your split and merge functions tail recursive by using the accumulator pattern

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 [])

您可以在此处了解更多有关累加器模式的信息. ;例子虽然有些虚假，但它是一种通用模式，可以在提供尾调用优化的任何语言中使用.

You can read more about the accumulator pattern here; the examples are in lisp but it's a general pattern that works in any language that provides tail call optimization.

这篇关于Mergesort在F#中遇到错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！