Блог

Главная - Вопросы по программированию - Пользовательская сортировка компаратора в SML?

Пользовательская сортировка компаратора в SML?

#sml #smlnj

#sml #smlnj

Вопрос:

Я немного застрял с этой проблемой в 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:

Есть три случая:

  1. Список есть nil .
    • Вы уже рассмотрели это. 🙂
  2. Списка нет nil , и его первый элемент меньше x , поэтому нам нужно продолжать поиск, куда вставить x .
    • В этом случае результатом должен быть первый элемент, за которым следует результат вставки x в остальную часть списка.
  3. Список не nil является, и его первый элемент больше или равен x , поэтому мы можем вставить x прямо здесь.
    • В этом случае результат должен быть x , за которым следует весь список.

Различение случаев #2 и #3 включает if / then / else ; реализация случая #2 включает рекурсию.

Комментарии:

1. Большое спасибо, что нашли время ответить! У меня есть один вопрос: как я могу передать сравнение. Код, который мне дали для его тестирования, выглядит следующим образом: ‘insertSorted(5, fn(a, b) => a < b, [8, 6, 5, 3, 1]);’

2. @MasonGarcia: Извините, я не понимаю вашего вопроса. Что вы подразумеваете под «как я могу передать сравнение»?

3. Ваш тестовый код точно показывает, как это сделать. fn(a, b) => a < b это функция, которая принимает пару значений и возвращает, является ли первое значение меньше второго. (Кстати, это функция или выражение функции , а не оператор . В стандартном ML на самом деле нет «утверждений», но его ближайшим аналогом было бы «объявление», которым это не является.)

4. @MasonGarcia: рассмотрим функцию fun double i = 2 * i , которая принимает целое число и возвращает его в два раза больше (например double 3 , is 6 ). Вы не найдете никакой документации по целому i числу, потому что это не конкретное целое число; это просто параметр функции и может быть любым целым числом. Аналогично, в вашем случае comp это не конкретная функция; это просто параметр функции и может быть любой функцией типа int * int -> bool .

5. (Если эта концепция для вас нова и вам трудно разобраться в ней, ознакомьтесь с «Первоклассной функцией» в Википедии .)