Bubblesort 实现中的无限循环

Question

我正在尝试使用 'let in end' 在 SML 中创建递归冒泡排序以包含辅助函数。

当谈到为什么它不打印任何东西时，我很困惑。

main.sml:

val master = [1,2,3,1,4,2,8,3,2,1]: int list;

fun bubblesort ( x : int list) : int list = 
    let
        fun sort [] = []
          | sort [a] = [a]
          | sort (a::b::c) = if (a < b) then [a]@sort(b::c) else [b]@sort(a::c)

        fun issorted [] = true  
          | issorted [x] = true 
          | issorted (x::y::t) = x <= y andalso issorted(y::t)
    in
        sort x;
        if issorted x then x else bubblesort x;
        x
    end;

val result = bubblesort master

结果：

Standard ML of New Jersey v110.78 [built: Thu Aug 31 03:45:42 2017]
val master = [1,2,3,1,4,2,8,3,2,1] : int list 
val bubblesort = fn :int list -> int list
=

Answer 1

问题是你在用命令式思考，好像sort x 突变x。在您当前的代码中，在 if issorted x ... 开头的行中使用的是原始的、未排序的 x。如果那个 x 是未排序的，那么你将永远在那个原始值上调用 bubblesort。事实上，由于该代码试图 return x 本身（通过 x 在 in 块的最后一行）你将永远调用 bubblesort 相同的值，即使 x 已排序。相反，您需要在比较中使用 value sort x，最好先在 val 绑定中捕获它，然后 return 的值if，而不是 x 本身。以下作品：

fun bubblesort ( x : int list) : int list = 

    let
        fun sort [] = []
                |sort [a] = [a]
                |sort(a::b::c) = if (a < b) then a::sort(b::c) else b::sort(a::c);

        fun issorted [] = true  
          | issorted [x] = true 
          | issorted (x::y::t) = x <= y andalso issorted(y::t);

        val y = sort x;
    in
       if issorted y then y else bubblesort y
    end;

然后：

- bubblesort master;
val it = [1,1,1,2,2,2,3,3,4,8] : int list

请注意，我用更惯用的 a::sort(b::c) 替换了 [a]@sort(b::c)。

Bubblesort 实现中的无限循环

Infinite loop in Bubblesort implementation

sml