Custom comparator sort in SML?

Question

I am a bit stuck with this problem in SML / SMLNJ and I would love some guidance. So I have a problem where I need to make a function called insertSorted, where it takes a number, a comparison statement, and an (assumed sorted) list that it needs to insert into. I'm not sure how to start approaching this so any help would be amazing.

My thought is to split the two lists up where the number would be, insert the number, and then concatenate both lists.

fun insertSorted (x, comp, []) = [x] 
  |  insertSorted (x, comp, a::rest) = ...

Update: I got a bit farther now I just need to know how to debug this, any guidance?

fun insertSorted (x, []) = [x]
 |  insertSorted (x, y::ys) = 
    if (x < y)
        then x::y::ys
    else if (x > y) 
        then y::x::ys
    else y::insertSorted (x, ys);

Update 2: My new goal is to figure out how to merge these two functions into one. Ultimately named insertSorted.

fun insertSorted (x, nil) = [x]
 |  insertSorted (x,y::ys) = if x<y then x::y::ys else y :: insertSorted (x,ys);

fun insertSorted (x, nil) = [x]
 |  insertSorted (x,y::ys) = if x>y then y::x::ys else y :: insertSorted (x,ys);

ruakh ruakh · Accepted Answer · 2020-12-12T00:06:05

There are three cases:

The list is nil.
- You've already covered this. :-)
The list is not nil, and its first element is less than x, so we need to keep searching for where to insert x.
- In this case, the result should be the first element, followed by the result of inserting x into the rest of the list.
The list is not nil, and its first element is greater than or equal to x, so we can insert x right here.
- In this case, the result should be x, followed by the entire list.

Distinguishing cases #2 and #3 involves if/then/else; implementing case #2 involves recursion.

Custom comparator sort in SML?

1 Answers