Betterfunctionforcollections
Answering a question in SO, I stumbled into this problem:
(def x [7 4 8 9 10 54 55 2 23 30 12 5])
(defn insert-x
([sorted-coll x]
(insert-x sorted-coll x
(if (= (type sorted-coll) clojure.lang.PersistentVector) [] '())))
([sorted-coll x acc]
(let [is-vector (= (type sorted-coll) clojure.lang.PersistentVector)
format-it #(into (if is-vector [] '()) %)
compare (if is-vector < >)]
(cond
(empty? sorted-coll) (format-it (cons x acc))
(compare (peek sorted-coll) x)
(format-it (concat
((if is-vector identity reverse) sorted-coll)
(conj acc x)))
:else (recur (pop sorted-coll) x (cons (peek sorted-coll) acc))))))
(defn bubble-sort [coll]
"Insert x into a sorted collection"
(reduce insert-x [] coll))
(bubble-sort x)
;; => [2 4 5 7 8 9 10 12 23 30 54 55]
The code does what it should.
However, insert-x is not so elegant.
How to write insert-x in a way that it is valid for all collections?
So that it is simpler/more elegant?
vectors should return vectors, lists should return lists etc.
回答
您需要的是insert-x处理常规列表（即'()或 nil）并重写bubble-sort以使用empty函数创建与输入相同的类型。
empty 返回相同类型的空集合：
(class (empty [1 2]))
;; => clojure.lang.PersistentVector
(class (empty #{1 2}))
;; => clojure.lang.PersistentHashSet
(class (empty '(1 2)))
;; => clojure.lang.PersistentList$EmptyList
你bubble-sort可以这样看：
(defn bubble-sort [coll]
"Insert x into a sorted collection"
(into (empty coll) (reduce insert-x nil coll)))
这样你就可以摆脱里面的所有类型检查 insert-x
回答
我猜你想多了。
你有两个任务：
- 在已排序集合中的适当位置插入项目
- 输入向量的返回向量和输入列表的列表
首先，我会重写insert-x这样的，例如：
(defn insert-x [sorted-coll x]
(let [[l r] (split-with #(<= % x) sorted-coll)]
`(~@l ~x ~@r)))
请注意，它的作用或多或少与您的变体相同：取值直到所需位置，然后将左右部分与x它们之间连接起来。另请注意，它始终生成正确排序的列表，与输入类型无关。
user> (insert-x [1 3 5 7 9] 10)
;;=> (1 3 5 7 9 10)
user> (insert-x [1 3 5 7 9] 0)
;;=> (0 1 3 5 7 9)
user> (insert-x [1 3 5 7 9] 4)
;;=> (1 3 4 5 7 9)
因此，您接下来需要做的就是减少输入并返回正确键入的结果：
(defn my-sort [coll]
(let [sorted (reduce insert-x () coll)]
(if (vector? coll)
(vec sorted)
sorted)))
user> (my-sort '(0 3 1 4 2 5 10 7))
;;=> (0 1 2 3 4 5 7 10)
user> (my-sort [0 3 1 4 2 5 10 7])
;;=> [0 1 2 3 4 5 7 10]
user> (my-sort ())
;;=> ()
user> (my-sort [])
;;=> []
- @Gwang-JinKim it essentially depends on your task and input size. Generally, built-in `sort` is good enough, so you should consider optimizing it iff it is necessary. You could also take a look at sorted-sets, in in case you need to keep your changing data sorted, which is better then resorting it every time it changes. But again, we can't reason about it unless we have any task specific information