为什么MergeSort函数会发生值限制? [英] Why does value restriction happen with MergeSort function?
问题描述
我在List上有一个非常简单的 MergeSort 实现.
I have a very simple MergeSort implementation on List.
/// Divide the list into (almost) equal halves
let rec split = function
| [] -> [], []
| [x] -> [x], []
| x1::x2::xs -> let xs1, xs2 = split xs
x1::xs1, x2::xs2
/// Merge two sorted lists
let rec merge xs ys =
match xs, ys with
| [], _ -> ys
| _, [] -> xs
| x::xs', y::ys' when x <= y -> x::merge xs' ys
| _, y::ys' -> y::merge xs ys'
let rec mergeSort = function
| [] -> []
| xs -> let xs1, xs2 = split xs
merge (mergeSort xs1) (mergeSort xs2)
但是只要我尝试使用F#Interactive中的任何输入进行测试:
But whenever I tried to test with any input in F# Interactive:
let xs = mergeSort [1;4;3;2];;
我遇到了值限制错误:
错误FS0030:值限制.值"xs"已推断为 具有通用类型 val xs:'_a列出'_a:比较时要么将'xs'定义为一个简单的数据项,使其成为具有显式参数的函数,或者如果 您不希望它具有通用性,请添加类型注释.
error FS0030: Value restriction. The value 'xs' has been inferred to have generic type val xs : '_a list when '_a : comparison Either define 'xs' as a simple data term, make it a function with explicit arguments or, if you do not intend for it to be generic, add a type annotation.
为什么会发生?修复它的简单方法是什么?
推荐答案
您没有处理mergeSort
中1元素列表的特殊情况.
一般情况是太笼统",无法推断出正确的类型.因此,编译器会为函数推断出过于通用的类型('a列表->'b列表),结果始终是通用列表(由于值限制而被禁止).
You are not handling the special case of 1-element lists in mergeSort
.
The general case is "too general" to infer the right type. As a consequence, the compiler infers a too generic type for the function ('a list -> 'b list) and the result is always a generic list (which is not allowed due to value restriction).
如果您这样修复它,则该类型将正确地推断为列表->列表".
If you fix it like this, the type will be correctly inferred as 'a list -> 'a list.
let rec mergeSort = function
| [] -> []
| [x] -> [x]
| xs -> let xs1, xs2 = split xs
merge (mergeSort xs1) (mergeSort xs2)
这篇关于为什么MergeSort函数会发生值限制?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!