ocaml冒泡排序

Question

我的基本想法是实现('a list -> 'a list)类型的冒泡排序。我使用的变量是sorted和result。如果我更改了列表中的某些元素，sorted将变为1。否则，sorted将保持为0。Result是比较的一个周期。

我想我的sorted变量有问题。有人能想出问题出在哪里吗？

let rec sort (l: int list) : int list =
    let sorted=0 in
    let result = match l with
           | []->[]
           | x::xs-> if xs=[] then x
                     else let y::ys = xs in
                          if x<y then x::sort(xs)
                          else let sorted=1 in
                               y::sort(x::ys)
    in
    if sorted=0 then result
    else sort(result)

Answer 1

在我看来，您正在尝试将sorted用作可变变量。OCaml变量是不可变的。一旦将变量绑定到值，绑定就不能更改。每个let sorted =语句都定义一个名为sorted的新变量。因此，您的最后一个测试将始终显示排序为等于0。它正在测试排序的第一个定义，它永远不能有除0以外的任何其他值。

Answer 2

正如Jeffrey所说，OCaml值是不可变的。这就是为什么你的程序不能像预期的那样工作。

但是你的代码还有其他的问题：

• sorted的类型应为bool，而不是int。OCaml的优点之一是它有一个强类型系统，所以使用它。
• 要解构列表，你应该使用模式匹配只使用if xs=[] then x else let y::ys = xs in不是做这件事的好方法( OCaml应该警告你你的模式匹配不是详尽的)。您应该将其他案例添加到您的模式匹配中。

如下所示：

| [] -> []
| x::[] -> x
| x::y::ys -> ...