2

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

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

wherepartial-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]
4

3 回答 3

2 
(defn partial-compare [x y]
  (when (= (type x) (type y))
    (compare x y)))

(defn remove-smaller [coll partial-order-fn]
  (filter
    (fn [x] (every? #(let [p (partial-order-fn x %)]
                       (or (nil? p) (>= p 0)))
                    coll))
    coll))

(defn -main []
  (remove-smaller [1 9 \a \f 3 4 \z] partial-compare))

这将输出(9 \z)，这是正确的，除非您希望返回值与coll.

于 2013-03-23T02:16:31.830 回答
1

In practice I might just use tom's answer, since no algorithm can guarantee better than O(n^2) worst-case performance and it's easy to read. But if performance matters, choosing an algorithm that is always n^2 isn't good if you can avoid it; the below solution avoids re-iterating over any items which are known not to be maxes, and therefore can be as good as O(n) if the set turns out to actually be totally ordered. (of course, this relies on transitivity of the ordering relation, but since you call this a partial order that's implied)

(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))
于 2013-03-23T09:57:25.750 回答
0 
(def data [1 9 \a \f 3 4 \z])

(defn my-fn [x y]
  (when (= (type x) (type y))
    (compare x y)))

(defn remove-smaller [coll partial-order-fn] 
  (mapv #(->> % (sort partial-order-fn) last) (vals (group-by type data))))

(remove-smaller data my-fn)
;=> [9 \z]

Potentially the order of the remaining items might differ to the input collection, but there is no order between the equality 'partitions'

于 2013-03-23T07:10:51.023 回答