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

Question

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

fun group (xs: ''a list): (''a * int) list

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

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

Answer 1

Простой, но неэффективный способ - написать эту версию group:

val group : ''a list -> ''a list list

и преобразовать вывод далее в:

val group_count : ''a list -> (''a * int) list

следующим образом:

fun group_count xss = map (fn xs => (hd xs, length xs)) xss

Но более эффективным способом было бы написать функцию span_count:

fun span_count p x [] count = (count, [])
  | span_count p x (y::xs) count =
    if p (x, y)
    then span_count p x xs (count+1)
    else (count, y::xs)

и использовать его рекурсивно:

fun group_count [] = []
  | group_count (x::xs) =
    case span_count op= x xs 1 of
      (count, ys) => (x, count) :: group_count ys