2

任何人都可以为 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));
4

2 回答 2

2

您的尝试似乎几乎是正确的，但fn x => x = x没有任何意义，因为它总是返回 true。我想你想要fn y => y = x。

其他一些评论：

  • 您可以将您的使用替换List.find为List.filter更接近您想要的。

  • 不要del(xs,L) @ [x]为递归步骤做。追加到列表末尾的成本与第一个列表的长度成线性关系，因此如果您在每一步都这样做，您的函数将具有二次运行时间。改为这样做x :: del(xs,L)，这也允许您最终删除列表反转。

  • 您在这里所说的“XOR”通常称为对称差异，至少对于类似集合的结构而言。

于 2013-01-19T10:44:49.850 回答
1

最简单的方法是从每个列表中过滤掉重复项，然后连接两个结果列表。使用 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

这应该是一个更好的解决方案，仍然保持简单。它使用 SML/NJ 特定的 ListMergeSort 模块对组合列表进行排序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

但是，这仍然有点愚蠢。由于排序功能会遍历组合列表中的所有元素，因此它也应该是“负责”删除重复项的功能。

于 2013-01-19T03:49:31.177 回答