clojure - 给定一个部分有序的集合，删除所有较小的项目

Question

我正在努力寻找一种漂亮的、惯用的方式来编写函数

(defn remove-smaller
  [coll partial-order-fn]
  ___
)

哪里 partial-order-fn接受两个参数并返回 -1 0 或 1 它们是否具有可比性(分别为更小、相等、更大)或 nil否则。
remove-smaller的结果应该是 coll，所有小于 coll 中任何其他项目的项目都将被删除。

例子:如果我们定义了一个偏序，比如数字正常比较，字母也是，但是一个字母和一个数字是不可比较的:

1 < 2    a < t    2 ? a

那么我们将有:

(remove-smaller [1 9 a f 3 4 z])
==> [9 z]

Answer 1

在实践中，我可能只使用 tom 的答案，因为没有算法可以保证比 O(n^2) 最坏情况下的性能更好，而且很容易阅读。但是如果性能很重要，那么选择一个总是 n^2 的算法并不好，如果你能避免它的话；下面的解决方案避免了重复任何已知不是最大值的项目，因此如果集合实际上是完全有序的，则可以像 O(n) 一样好。 (当然，这依赖于排序关系的传递性，但由于您将其称为隐含的偏序)

(defn remove-smaller [cmp coll]
  (reduce (fn [maxes x]
            (let [[acc keep-x]
                  ,,(reduce (fn [[acc keep-x] [max diff]]
                              (cond (neg? diff) [(conj acc max) false]
                                    (pos? diff) [acc keep-x]
                                    :else [(conj acc max) keep-x]))
                            [[] true], (map #(list % (or (cmp x %) 0))
                                            maxes))]
              (if keep-x
                (conj acc x)
                acc)))
          (), coll))