Ocaml插入排序

Question

输入：未排序列表/输出：排序列表

我的基本想法是在排序列表中插入一个整数。

（I可以对列表进行排序，如果我能插入所述第一元件到排序尾巴。）

我使用的“插入”，这是thehelper功能。

但是，它会溢出。有人告诉我问题是什么？

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)) ;; 

Answer 1

这行看起来相当错误的对我说：

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

在我看来，你知道你的ys排序（由归纳假设）。所以你应该比较n与你的ys，而不是你的ys对方。如果你弄清了这条线，事情可能会改善。

对于它的价值，我怀疑你只需要在你的match有两个案例。我不明白你为什么需要将1元素列表与其他非空列表区分开来。

Answer 2

再有，我有风情的建议：

• 你应该分开两个功能sort和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) 

Answer 3

总是问这样的问题时，很难对人们阅读这样的代码和他们大多会忽略的职位。 就像@Thomash说的，首先尝试分成更小的函数，这样可以更容易地看出它失败的位置。

你可以在 “调试你的眼睛” 这样的：

let rec insertion_sort el = function 
    | [] -> [el] 
    | h::t as ls -> if el > h then h :: insert el t else (el :: ls) 

let sorted_list ls = List.fold_right insertion_sort ls []