2

在惰性集合中查找重复值的惯用方法是什么，从检查中排除某些值？

喜欢：

(duplicates? '(1 2 3 4 1) '(1)) ;; 1 is excluded from the check
false

(duplicates? '(1 2 3 4 1) ()) ;; no exclusions
true

我的要求是代码应该能够处理无限列表。换句话说，如果可以通过查看第一个N元素来说明可重复性，则代码不应该处理整个惰性集合。

我可怕的混乱尝试是：

(defn duplicates? [coll except]
  (let [_duplicates? (fn [coll except accum]
                         (let [item (first coll)]
                           (if (nil? item)
                             false
                             (if (some #{item} except)
                               (recur (rest coll) except accum)
                               (if (some #{item} accum)
                                 true
                                 (recur (rest coll) except (conj accum item)))))))]
    (_duplicates? coll except ())))
4

3 回答 3

4

重用现有功能比手动发明要好得多。该解决方案按要求短路，乍一看显然是正确的，因为它只是建立在现有原语的基础上，这比其他建议的解决方案有很大的优势：它们很长且涉及的内容足够多，以至于必须对其进行检查和仔细检查对于错误（并且这些错误很容易产生，正如所提出的每个解决方案都经过一两轮修复这一事实所表明的那样）。

(defn duplicates? [coll except]
  (let [except (set except)
        filtered (remove #(contains? except %) coll)]
    (not= filtered (distinct filtered))))

这不适用于无限except列表，因为它使用集合，但显然没有解决方案可以处理两个参数都是无限的，所以这并不是一个真正的缺点，只是需要注意的事情。

于 2013-09-09T06:57:01.900 回答
3

我只会做这样简单的事情：

(defn duplicates? [xs]
  (not= (count (distinct xs)) (count xs)))

至于删除重复项，您可以提供一个可选的第二个参数，但这对我来说似乎不是很地道。相反，我只使用内置remove函数，例如：

user=> (duplicates? '(1 2 3 4 1))
true
user=> (duplicates? (remove #{1} '(1 2 3 4 1)))
false

在函数式语言中，“idomatic”解决方案通常包括使用一些现有的高级函数来创建新功能。在这种情况下，我们使用distinct删除重复项，并remove（使用集合作为过滤器功能）从检查中排除元素。

如果你真的想要一些懒惰的东西，这里有一个解决方案，当你发现重复时会退出。它松散地基于以下实现distinct：

(defn duplicates? [xs]
  (loop [[x & xs :as coll] xs, seen #{}]
    (if (empty? coll) false
      (or (contains? seen x) (recur xs (conj seen x))))))

如果您真的想将“排除项目”设置为参数（而不仅仅是使用remove），我会通过使函数具有多个参数来使其成为可选：

(defn duplicates?
  ([xs exclude?] (duplicates? (remove exclude? xs)))
  ([xs] (loop [[x & xs :as coll] xs, seen #{}]
          (if (empty? coll) false
            (or (contains? seen x) (recur xs (conj seen x)))))))

nil此解决方案对于包含and的集合也是安全的false：

user=> (duplicates? '(1 2 3 4 1) #{1})
false
user=> (duplicates? '(1 2 3 4 1) #{})
true
user=> (duplicates? [true false false])
true
于 2013-09-08T21:42:19.010 回答
2

您可以尝试对异常和累加器使用集合而不是列表。然后检查就像：是累加器中的项目还是异常？可能要快得多，同时仍然保持懒惰。

(defn duplicates? [coll except]
  (let [_duplicates?
        (fn [coll except accum]
          (if (seq coll)
            (let [item (first coll)]
              (if (contains? except item)
                (recur (rest coll) except accum)
                (if (contains? accum item)
                  true
                  (recur (rest coll) except (conj accum item)))))
              false))]
    (_duplicates? coll except #{})))

user=> (duplicates? '(1 2 3 4 1) #{1})
false
user=> (duplicates? '(1 2 3 4 1) #{})
true

笔记：

user=> (duplicates? (repeat 1) #{})
true
于 2013-09-08T21:39:17.887 回答