时间戳

首页 > 解决方案 > Custom comparator sort in SML?

sml - Custom comparator sort in SML?

问题描述

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);

标签： smlsmlnj

解决方案

有以下三种情况：

  1. 名单是nil。
    • 你已经涵盖了这一点。:-)
  2. 列表不是nil，它的第一个元素是小于x，所以我们需要不断寻找插入的位置x。
    • 在这种情况下，结果应该是第一个元素，然后是插入x到列表其余部分的结果。
  3. 列表不是nil，并且它的第一个元素大于或等于，所以我们可以在这里 x插入。x
    • 在这种情况下，结果应该是x，后跟整个列表。

区分案例#2 和# 3涉及if// then; else实施案例#2 涉及递归。

推荐阅读