I've posted a similar question to this before, but I think I need to rephrase what I am asking about. I got some great help earlier with what I want to accomplish.
So, what I am currently wondering right now is how can I pass down the comp function in my code so that it can be customizable.
I would like to be able to run
insertSorted(5, fn(a, b) => a > b, [8, 6, 3, 1];
Which would return
val it = [8, 6, 5, 3, 1]
While also being able to flip a sign and be able to run
insertSorted(5, fn(a, b) => a < b, [8, 6, 3, 1];
Which would return
val it = [1, 3, 5, 6, 8]
Heres What I have so far:
* insertSorted *
fun insertSorted (x, comp, nil) = [x]
| insertSorted (x, comp, y::ys) = if x comp y then y::x::ys else y :: insertSorted (x,ys);
This is the "comp" that is in question: Line 2: if x comp y then y::x::ys else y :: insertSorted (x,ys);
In my mind, insertSorted could be two things: Either (a) a function that assumes that its input list is sorted with the same relation as the one given, so that insertion is O(n), or (b) a function that first sorts the input list according to the relation, and then inserts the element.
I will argue that (a) makes sense, even though it is a little fragile, and that (b) is a little bad:
If you are allowed to assume that your input is already sorted, your function is O(n) rather than O(n log n). You could call this data structure a pre-sorted list. Now, nothing prevents you from feeding an unsorted list to insertSorted, so that could result in bugs. There are ways you can overcome this. But that is another topic.
If that's what you want, then this is how to do that:
fun insertSorted (x, comp, y::ys) =
if comp (x, y)
then y :: insertSorted (x, comp, ys)
else x :: y :: ys
| insertSorted (x, _, []) = [x]
Testing this:
- insertSorted (5, op <, [8,7,6,4,3,2]);
val it = [8,7,6,5,4,3,2] : int list
- insertSorted (5, op >, [2,3,4,6,7,8]);
val it = [2,3,4,5,6,7,8] : int list
If you do not assume that your input is already sorted, then insertSorted is a really bad name: We're not inserting into something that is sorted. Additionally, since we need to sort the entire input anyway, being O(n log n), there is no real point in then inserting for an additional O(n), unless we're allowed to assume that the input is "nearly" sorted, in which case some sorting algorithms are better than others.
Assuming that "unsorted" is the opposite of "sorted", and since you use SML/NJ which comes with a sorting function, what you can do is:
fun insertUnsorted (x, comp, ys) =
ListMergeSort.sort comp (x::ys)
Testing this:
- insertUnsorted (5, op <, [1,9,3,4,6,2]);
val it = [9,6,5,4,3,2,1] : int list
- insertUnsorted (5, op >, [1,9,3,4,6,2]);
val it = [1,2,3,4,5,6,9] : int list
I don't think this function is very useful compared to sort.
For sorting functions in other SML compilers than SML/NJ, see this answer.