2

関数を書くための美しく慣用的な方法を見つけるのに苦労しています

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

wherepartial-order-fnは 2 つの引数を取り、-1 を返しnilます。

の結果はremove-smallercoll で、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

実際には、アルゴリズムは 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))
于 2013-03-23T09:57:25.750 に答える