Ocaml插入排序

Question

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

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

(如果我可以将第一个元素插入到排序的尾部,我可以对列表进行排序.)

我使用了"insert",这是helper的功能.

然而,它会溢出.Couuld有谁告诉我这是什么问题？

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

我再次提出了风格建议:

• 您应该将这两个函数分开sort,insert因为它会使它更具可读性,并且因为该insert函数本身也很有用.
• 为什么你给一个元组作为函数的参数insert？在OCaml中,人们会使用currying而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)