SML: вычесть один список из другого списка - PullRequest
Новая
       13

SML: вычесть один список из другого списка

0 голосов
/ 20 декабря 2011

Какой самый простой способ вычесть один список из другого? Нужно ли мне использовать ListPair для решения этой задачи? Обратите внимание, что мне нужно сравнивать строки, а не отдельные элементы. Например, есть два списка «L1» и «L2»: 

L1 = 
[(1, 2, 3), 
(4, 5, 6)]

L2 = 
[(1, 2, 3), 
(4, 5, 6),  
(3, 2, 3]

Мне нужно получить "L3", применив L3 = L2-L1: 

L3 = 
[(3, 2, 3)]

Спасибо.

1 Ответ

2 голосов
/ 21 декабря 2011

Как я понимаю вопрос, вы хотите удалить элементы в L2, которые также находятся в L1, но только один раз за вхождение.

Простое решение может включать вспомогательную функцию, сообщающую, был ли найден элемент в L1, вместе с остальной частью L1 с удаленным этим элементом. 

fun remFirst _ [] rest = (false, rev rest)
  | remFirst x (y::ys) rest =
    if x = y then
        (true, rev rest @ ys)
    else
        remFirst x ys (y :: rest)

Теперь вы можете перебирать L2, отбрасывая элементы каждый раз, когда remFirst возвращает true, а затем продолжая работу с остальным списком.

Если вместо этого вы хотите удалить префикс, который L2 имеет общее с L1, все становится немного проще. 

fun remPref [] _            = []
  | remPref xs []           = xs
  | remPref (x::xs) (y::ys) = if x = y then remPref xs ys else (x::xs)

ОБНОВЛЕНИЕ: вопрос теперь изменен.

Если теперь требуется удалить элементы из L2, которые находятся в L1, фильтр будет полезен. 

List.filter (fn x => List.all (fn y => x <> y) L1) L2
...