Сортировать список кортежей лексикографически - PullRequest
Новая
       34

Сортировать список кортежей лексикографически

0 голосов
/ 14 мая 2018

Я пытался создать функцию в Standard ML, которая получает список string * int и возвращает отсортированный лексикографический список.

Например, foo [("y",5),("x",10)] вернет [("x,10),("y",5)] (важен только первый элемент каждого кортежа).

Я написал следующие строки: 

fun foo ([]:(string * int)) = []
  | foo [x] = [x]
  | foo ((x,y)::xs) = 
    let
      val (s,t) = hd(xs) (* gets next element string *)
      fun sort ... = ...
    in

    end

Я не знаю, как реализовать функцию sort, но мне бы хотелось, чтобы в ней был следующий код, который я написал: 

    case String.compare(x,s) of
      LESS => ...
    | EQUAL => ...
    | GREATER => ...

Также мне нужно использовать val (s,t) = hd(xs) в функции sort, чтобы она была рекурсивной, но я не уверен. Более того, мне не разрешено никаких дополнительных библиотек - работать только со скрытым let / local.

1 Ответ

0 голосов
/ 14 мая 2018

(Если вам было разрешено использовать библиотечные функции,) ListMergeSort.sort в SML / NJ выглядит следующим образом: 

val sort : ('a * 'a -> bool) -> 'a list -> 'a list

sort f l возвращает список элементов в l, отсортированных в неубывающем порядке, как указано в предикате «больше чем» f,В частности, если f(x,y) имеет значение true, тогда x появится после y в результирующем списке.

Использование этой библиотечной функции для записи вашего foo: 

fun foo pairs = ListMergeSort.sort (fn ((s : string,_), (t,_)) => s > t)

Это может выглядеть немного иначе, если вы используете другой компилятор, чем SML / NJ.

Чтобы решить ваши подзадачи,

Я не знаю, как реализовать функцию sort

(Поскольку выне допускаются никакие библиотечные функции,) вы можете построить функцию сортировки, которая принимает String.compare в качестве аргумента.В зависимости от алгоритма сортировки, грубый эскиз функции сортировки может выглядеть следующим образом: 

fun sort cmp [] = []
  | sort cmp [x] = [x]
  | sort cmp xs = ... partially sort xs using `cmp`, combine results ...

и его подпись будет ('a * 'a -> order) -> 'a list -> 'a list.

Вы не спрашиваете, как сделатьфункция сортировки (но просто сказать, что вы не знаете, как это сделать), и если бы вы это сделали, я был бы склонен сказать, что этот вопрос слишком широкий, если вы не укажете, какой тип алгоритма вы хотите реализовать или гдеВы застряли в процессе.См., Например, MergeSort Rosetta Code или Q & A Стандартные функции сортировки в SML?

Мне бы хотелось, чтобы у меня был следующий код, который я написал: 

case String.compare (x,s) of ...

[...] Мне запрещены дополнительные библиотеки [...]

Но String.compare это тоже библиотечная функция!Вы можете написать свой String.compare.Либо (a) разнесите строк в списки символов и используйте рекурсию списка для определения их лексикографического порядка, либо (b) count theдлину строк и используйте String.sub (s, i), чтобы получить i th char s для каждой строки, пока не будет определен лексикографический порядок.В то время как (b) более эффективен (поскольку он использует небольшой постоянный объем памяти), (a) является хорошим упражнением в рекурсии списка.

Для (a) вы можете начать с: 

fun stringCompare (s, t) =
    let fun cmp (x::xs, y::ys) = if x < y then ... else ...
          | cmp (_::_, [])     = ...
          | cmp ([], _::_)     = ...
          | cmp ([], [])       = EQUAL
    in cmp (explode s, explode t) end

Затем вы можете составить их таким же образом: 

fun foo pairs = sort (fn ((s,_), (t,_)) => stringCompare (s, t)) pairs
...