SML: создать список из списка кортежей со вторым элементом каждого кортежа - PullRequest
Новая
       12

SML: создать список из списка кортежей со вторым элементом каждого кортежа

1 голос
/ 26 октября 2019

Здравствуйте, я новичок в SML, и я пытался написать функцию, которая получает в качестве параметра список (в моем случае - список пруссий), который имеет кортежи с двумя целыми числами и строку, моя функция должна создатьсписок со всеми годами, которые появляются в списке без повторений (2-й элемент каждого кортежа списка). Я должен сделать это, создав две функции (append_if_new берет год из списка и добавляет его в список, это работает), и год должен сделать это для всех кортежей в списке, я попробовал это с помощью foldl, но я получил Tyconнесоответствие.

Pd. чтобы сделать это, мне нужно использовать карту функций, фильтр или сложить, и я могу переместить функциональные возможности append_if_new в функцию year. Я думаю, что ошибка в вызове сгиба, где функция, которую я передаю как параметр, не является типом функции, которую я должен передать, но я не уверен, в чем проблема. Спасибо 

    val prussia =
  [(0,1875,"G"),(2,1876,"G"),(2,1877,"G"),(1,1878,"G"),(0,1879,"G"),
   (0,1880,"G"),(1,1881,"G"),(1,1882,"G"),(0,1883,"G"),(3,1884,"G"),
   (0,1885,"G"),(2,1886,"G"),...] : (int * int * string) list

fun append_if_new (lista:(int*int*string)list): int list =
    let 
        val lista2 = []
        val x = hd lista
        val z = #2x
    in
        if (List.exists (fn y => y = z) lista2) 
        then lista2
        else lista2@[z]
    end

fun years (lista:(int*int*string)list): int list =
    List.foldl append_if_new 0 lista

Ответы [ 2 ]

0 голосов
/ 28 октября 2019

Есть две проблемы:

  • неверно ваше начальное значение сгиба - поскольку результатом должен быть список, начальное значение также должно быть списком;
  • вашappend_if_new функция имеет как слишком мало аргументов, так и слишком много ошибок.

Если вы подставите определения с привязкой по буквам, append_if_new станет 

fun append_if_new (lista:(int*int*string)list): int list =
    if List.exists (fn y => y = #2 (hd lista)) [] 
    then []
    else []@[#2 (hd lista)]

Поскольку условие всегдаfalse - вы никогда не найдете ничего в пустом списке - и [] @ xs эквивалентно [xs], мы можем уменьшить это значение до 

fun append_if_new (lista:(int*int*string)list): int list =
    [#2 (hd lista)]

, что явно неверно - эта функция всегда будет выдаватьсписок, единственным элементом которого является год первой записи.

Пример: 

- append_if_new prussia;
val it = [1875] : int list

Функция, которую вы передаете foldl, принимает две вещи - «текущий элемент» и «результаты на данный момент» - и объединяетих для получения «следующего» результата.
Пример: 

fun add_if_new ((_,y,_), so_far) = if List.exists (fn z => y = z) so_far 
                                   then so_far 
                                   else y :: so_far;

Тест: 

- add_if_new ((1,2,3), []);
val it = [2] : int list
- add_if_new ((1,2,3), [3]);
val it = [2,3] : int list
- add_if_new ((1,2,3), [2]);
val it = [2] : int list

и: 

fun years (lista: (int*int*string) list): int list =
    List.foldl add_if_new [] lista

Тест: 

- years [(12,0, "G"), (12,1,"G"), (12,0,"G")];
val it = [1,0] : int list
0 голосов
/ 26 октября 2019

создать список со всеми годами, которые появляются в списке без повторений

(2-й элемент каждого кортежа списка)

Вы можете создать списокс повторениями, использующими map и последующим фильтрованием дубликатов: 

fun year_of (_, year, _) = year
fun member (y, xs) = List.exists (fn x => y = x) xs
fun nub [] = []
  | nub (x::xs) = if member (x, xs)
                  then nub xs
                  else x :: nub xs

fun years records = nub (map year_of records)

Здесь nub имеет асимптотическую сложность во время выполнения O (n²) , что является плохим и ненужным. Вы также можете пойти дальше и сложить список так, чтобы никогда не вставлять дубликаты для начала: 

fun member (y, xs) = List.exists (fn x => y = x) xs

fun years records =
    let
      fun insert ((_, year, _), years) =
          if member (year, years)
          then years
          else year :: years
    in
      foldr insert [] records
    end

, но асимптотическое время выполнения то же самое, и его немного более неясно читать. Если вы хотите эффективно фильтровать дубликаты, вам нужно использовать более эффективную структуру данных для управления дубликатами, например, набор на основе дерева или аналогичный. В Хаскеле это разница между nub и nubOrd.

...