Как написать функцию в SML / NJ, которая сортирует элементы из списка в классы эквивалентности?

Question

Мне нужно написать функцию в SML / NJ, которая сортирует элементы из списка в классы эквивалентности. Порядок элементов внутри каждого класса эквивалентности должен быть таким же, как в исходном списке. Отношение эквивалентности задается функцией f, которая возвращает true, если два элемента эквивалентны.

Функция должна выглядеть следующим образом:

fun equivalenceClasses (f: ''a * ''a -> bool, xs: ''a list): ''a list list

Я могу использовать только анонимные функции и структуры List, ListPair и Math.

Понятия не имею, как это сделать. Может кто-нибудь помочь мне?

Answer 1

Предположим, я дал вам список классов эквивалентности. Можете ли вы выяснить, как вставить еще один элемент в этот список?

Например, предположим, что элементы - это строки, а классы эквивалентности - строки одинаковой длины. Тогда список [["fox","the","dog"],["brown","jumps"],["over","lazy"]] является списком классов эквивалентности, потому что, например, "fox" соответствует длине "dog", "brown" соответствует длине "jumps" и т. Д.

Если мы теперь вставим строку "quick" в этот список классов, как должен выглядеть результат? Ясно, что он должен быть добавлен в список ["brown","jumps"], поэтому, возможно, результат будет выглядеть как [["fox","the","dog"],["quick","brown","jumps"],["over","lazy"]]

Как только вы решите эту проблему, все остальное легко. Вот подсказка:

fun equivalenceClasses (f, xs) =
  case xs of
    [] => ???
  | x :: xs' => let
                  val c = equivalenceClasses xs'
                in
                  ???
                end