collections - 更好的收藏功能

Question

在回答SO中的一个问题时，我偶然发现了这个问题:

(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]

该代码完成了应做的工作。
但是， insert-x并不是那么优雅。
如何以对所有集合有效的方式编写 insert-x？
这样更简单/更优雅？
向量应返回向量，列表应返回列表等。

Answer 1

我想你想得太多了。
您有两个任务:

将项目插入已排序集合

内的适当位置

输入向量的返回向量和输入列表的列表

首先，我将像这样重写 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 [])
;;=> []