Пользовательская сортировка компаратора в SML?
Я немного застрял с этой проблемой в SML / SMLNJ, и мне бы хотелось получить некоторые рекомендации. Итак, у меня есть проблема, когда мне нужно создать функцию с именем insertSorted, где она принимает число, оператор сравнения и (предполагаемый отсортированный) список, в который нужно вставить. Я не уверен, как начать подходить к этому, поэтому любая помощь будет потрясающей.
Моя идея состоит в том, чтобы разделить два списка там, где будет число, вставить число, а затем объединить оба списка.
fun insertSorted (x, comp, []) = [x]
| insertSorted (x, comp, a::rest) = ...
Обновление: теперь я продвинулся немного дальше, мне просто нужно знать, как это отлаживать, какие-нибудь рекомендации?
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);
Обновление 2: Моя новая цель — выяснить, как объединить эти две функции в одну. В конечном итоге названный 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);
Ответы 1
Есть три случая:
- Список
nil.- Вы уже освещали это. :-)
- Список не
nil, и его первый элемент меньшеx, поэтому нам нужно продолжать искать, куда вставитьx.- В этом случае результатом должен быть первый элемент, за которым следует результат вставки
xв остальную часть списка.
- В этом случае результатом должен быть первый элемент, за которым следует результат вставки
- Список не
nil, и его первый элемент больше или равенx, поэтому мы можем вставитьxпрямо здесь.- В этом случае результатом должно быть
x, за которым следует весь список.
- В этом случае результатом должно быть
Различение случаев № 2 и № 3 включает if/then/else; реализация случая № 2 включает рекурсию.
@MasonGarcia: извините, я не понимаю вашего вопроса. Что вы подразумеваете под "как я мог пройти сравнение"?
Таким образом, цель функции insertSorted состоит в том, чтобы взять число (для вставки), оператор сравнения (т. е. a < b) и список для вставки. У меня возникли проблемы со вставкой сравнительного оператора в мой код.
Извините, что так часто отмечаю вас, я все еще привыкаю к переполнению стека
Ваш тестовый код точно показывает, как это сделать. fn(a, b) => a < b — это функция, которая принимает пару значений и возвращает значение, меньшее ли первое значение второго. (Кстати, это функция или функциональное выражение, а не оператор. Стандартный ML на самом деле не имеет «операторов», но его ближайшим аналогом будет «декларация», которой нет.)
Спасибо за разъяснения, я долго мучился с терминологией! Я собираюсь опубликовать редактирование: обновление 2. Теперь мой новый вопрос: как я могу выполнить 2 сравнительные функции в одной и той же «основной» функции?
@MasonGarcia: О, кажется, я понял - ваш вопрос о том, как вызвать функцию сравнения? Вы можете написать, например. comp (x, y).
@rukah, я не могу найти никакой документации по функции comp. Любая идея, как реализовать это в моем коде?
@MasonGarcia: рассмотрим функцию fun double i = 2 * i, которая принимает целое число и возвращает его в два раза (например, double 3 равно 6). Вы не найдете никакой документации по целому числу i, потому что это не конкретное целое число; это просто параметр функции и может быть любым целым числом. Точно так же в вашем случае comp не является конкретной функцией; это просто параметр функции и может быть любой функцией типа int * int -> bool.
(Если эта концепция для вас нова и вам трудно ее понять, посмотрите «Первоклассная функция» в Википедии.)
Большое спасибо, что нашли время ответить! У меня есть один вопрос: как я могу пройти сравнение. Код, который мне дали для проверки, выглядит следующим образом: 'insertSorted(5, fn(a, b) => a < b, [8, 6, 5, 3, 1]));'