Infinite loop in Bubblesort implementation

Question

I'm trying to create a recursive bubble sort in SML using 'let in end' to contain helper functions.

I'm rather lost when it comes to why it won't print anything.

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

Result:

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
=

John Coleman John Coleman · Accepted Answer · 2019-03-03T18:44:37

The problem is that you are thinking imperatively, as if sort x mutates x. In your current code, it is the original, unsorted x which is used in the line which begins if issorted x .... If that x is unsorted, then you are forever calling bubblesort on that original value. In fact, since that code is trying to return x itself (by having x on the final line of the in block) you will be forever calling bubblesort on the same value even if x is sorted. Instead, you need to use the value sort x in the comparison, preferably by first capturing it in a val binding, and return the value of the if, rather than x itself. The following works:

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;

Then:

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

Note that I replaced [a]@sort(b::c) by the more idomatic a::sort(b::c).

Infinite loop in Bubblesort implementation

1 Answers