SML функция с 2 списками, которая возвращает XOR--- исправлено

Question

Любой, кто может предложить какой-либо совет для функции в SML, которая будет принимать 2 списка и возвращать XOR из них, так что если у вас есть списки [a,b,c,d], [c,d,e,f] функция возвращает [a,b,e,f]?

Я пытался сделать это с 2 функциями, но даже это не работает должным образом.

fun del(nil,L2) = nil
|del(x::xs,L2)=
if (List.find (fn y => y = x) L2) <> (SOME x) then
del(xs, L2) @ [x]
else 
del(xs, L2);

fun xor(L3,L4) = 
rev(del(L3,L4)) @ rev(del(L4,L3));

Answer 1

Ваша попытка кажется почти правильной, за исключением того, что fn x => x = x не имеет смысла, так как всегда возвращает true. Я думаю ты хочешь fn y => y = x вместо.

Пара других замечаний:

• Вы можете заменить свое использование List.find с List.filter что ближе к тому, что вы хотите.

• Не делай del(xs,L) @ [x] для рекурсивного шага. Добавление в конец списка имеет стоимость, линейную по отношению к длине первого списка, поэтому, если вы будете делать это на каждом шаге, ваша функция будет иметь квадратичное время выполнения. Делать x :: del(xs,L) вместо этого, что также позволяет вам в конце удалить список обращений.

• То, что вы называете здесь "XOR", обычно называется симметричной разностью, по крайней мере, для структур, подобных множеству.

Answer 2

Простейшим способом было бы отфильтровать дубликаты из каждого списка, а затем объединить два результирующих списка. Используя List.filter, вы можете удалить любой элемент, который является членом (List.exists) другого списка.

Однако это довольно неэффективно, и приведенный ниже код является скорее примером того, как этого не делать в реальной жизни, хотя на это "функционально" приятно смотреть:)

fun symDiff a b =
    let
      fun diff xs ys =
          List.filter (fn x => not (List.exists ( fn y => x = y) ys)) xs
      val a' = diff a b
      val b' = diff b a
    in
      a' @ b'
    end

Это должно быть лучшее решение, которое все еще остается простым. Он использует специальный модуль ListMergeSort для SML/NJ для сортировки комбинированного списка. a @ b,

fun symDiff1 a b =
    let
      val ab' = ListMergeSort.sort op> (a @ b)
      (* Remove elements if they occur more than once. Flag indicates whether x
         should be removed when no further matches are found *)
      fun symDif' (x :: y :: xs) flag  =
          (case (x = y, flag) of
             (* Element is not flagged for removal, so keep it *)
             (false, false) => x :: symDif' (y :: xs) false
             (* Reset the flag and remove x as it was marked for removal *)
           | (false, true) => symDif' (y::xs) false

             (* Remove y and flag x for removal if it wasn't already *)
           | (true, _) => symDif' (x::xs) true)
        | symDif' xs _ = xs
    in
      symDif' ab' false
    end

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