在 clojure 中的两个集合之间实现 XOR

Question

我正在努力学习 Clojure——而且还很新手。我正在尝试实现两个集合之间设置差异的递归版本。

我想做的是首先组合两个列表，将组合转换为一个集合以删除重复项，然后将混乱传递回它自己并检查组合集合的第一个元素是否在两个输入列表。如果它将组合集合的其余部分与原始集合一起传回并重复该过程......但它总是传回一个空列表。我不假设代码就那么好。我是函数式编程的新手。

也许我没有正确使用逻辑？我做了一个测试，common-elms 开始时不是空的，但它可能会提前返回一个空列表？任何帮助将非常感激。谢谢。

(defn alone 
([l1 l2]
    (cond (empty? l1) l2
      (empty? l2) l1
      :else (alone (vec (set (into l1 l2))) '() l1 l2)))

([common-elms return-list l1 l2]
    "common-elms = set of common elements
     return-list = list of XOR items 
     l1 = list 1
     l2 = list 2 "
    (cond (empty? common-elms) return-list
          (and (contains? (first common-elms) l1) (contains? (first common-elms) l2))
            (alone (rest common-elms) return-list l1 l2)
          :else (alone (rest common-elms) return-list l1 l2))))

Answer 1

您尝试递归执行此操作是否有原因？如果这不是必需的，请使用 clojure.set 命名空间：

(defn xor-list [l1 l2]
  (let [s1 (set l1)
        s2 (set l2)
        i (clojure.set/intersection s1 s2)]
    (seq (clojure.set/union
          (clojure.set/difference s1 i)
          (clojure.set/difference s2 i)))))

Answer 2

或者更简单，使用 clojure.set 命名空间：

(defn xor-list [l1 l2]
  (let [s1 (set l1)
        s2 (set l2)]
    (seq (clojure.set/difference 
           (clojure.set/union s1 s2) 
           (clojure.set/intersection s1 s2)))))

但这只是两个参数返回列表的函数。这应该针对一般情况 clojure.set/xor 进行增强，例如 clojure.set/intersection 对于返回集合的任意数量的集合。

Answer 3

首先，@ivanpierre 解决方案当然是最好的，因为它实际上使用了 symmetric difference 的第一个属性并利用了 clojure.set。但是您自己基于递归的解决方案是有效的，尽管代码中存在一些缺陷。下面的修改版本带有解释：

(defn alone
  ([l1 l2]
   (cond (empty? l1) l2
         (empty? l2) l1
         :else (alone (vec (set (into l1 l2))) '() l1 l2)))

  ([common-elms return-list l1 l2]
   "common-elms = set of common elements
     return-list = list of XOR items
     l1 = list 1
     l2 = list 2 "
   (cond (empty? common-elms) return-list
         (let [ce (first common-elms)]   ;; see [1]
           (and (some #{ce} l1)
                (some #{ce} l2)))
         (alone (rest common-elms) 
                return-list 
                l1 l2)
         :else (alone (rest common-elms) 
                      (conj return-list (first common-elms)) ;; see [2] 
                      l1 l2))))

user> (alone '(1 2 3 4 5) '(3 4 5 6 7))
(2 6 1 7)
user>

你必须知道 contains? 仅适用于关联集合，如地图或向量（向量是一个关联集合，其键是索引）。请参阅 this 问题。 some 的 documentation 给出了在任何类型的集合中测试它是否包含给定元素的惯用方法。
在没有找到公共元素的情况下 (:else)，您忘记 conj 将元素 return-list。

注意：风格比 Clojurian 更像 Lispy；要保持基于递归的解决方案，您可以使用 loop/recur。这是 N 个列表的通用解决方案：

(defn xor
  ([l1 l2]
   (loop [l1 (set l1)
          l2 (set l2)
          xor '()]
     (if (seq l1)
       (let [e (first l1)]
         (if (l2 e) ;; l2 is a set, test if e is in l2
           (recur (rest l1) (disj l2 e) xor)
           (recur (rest l1) l2 (conj xor e))))
       (reduce conj xor l2)))) ;; when l1 is empty, add all element left in l2
  ([l1 l2 & more]
   (reduce xor (xor l1 l2) more)))

user> (let [l1 '(1 1 2 3 4 5)
            l2 '(3 4 5 5 6 7)
            l3 '(1 10 11 13)
            l4 '(1 2 11 6 6)]
        (println (xor l1 l2 l3 l4)))

(1 10 13 7)
nil

在 clojure 中的两个集合之间实现 XOR

implementing XOR between two collections in clojure

recursion

functional-programming

clojure