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就没那么优雅了。如何以对所有 collections 都有效的方式编写 insert-x？这样就simpler/more优雅了？向量应该 return 向量，列表应该 return 列表等

Answer 1

你需要的是让 insert-x 处理常规列表（即 '() 或 nil）并重写 bubble-sort 以使用 [=15= 创建与输入相同的类型] 函数。

emptyreturns同类型空集合：

(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

中摆脱所有类型检查

Answer 2

我猜你想多了。

你有两个任务：

在已排序集合中的适当位置插入项目
return 输入向量的向量和输入列表的列表

首先，我会像这样重写 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)

所以，接下来您需要做的就是减少输入和 return 正确输入的结果：

(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 [])
;;=> []

Answer 3

谢谢你们！

我采纳了你们的两个答案并生成了这个解决方案：

(defn insert-x [sq x]
  (apply concat (interleave (split-with #(<= % x) sq) [[x] []])))

(defn bubble-sort [sq]
  ((if (vector? sq) vec identity)
   (reduce insert-x () sq)))

测试：

user=> (bubble-sort '(0 2 8 3 9 7))
(0 2 3 7 8 9)
user=> (bubble-sort [0 2 8 3 9 7])
[0 2 3 7 8 9]

或者可能更易读：

(defn insert [q x]
  (let [[l r] (split-with #(< % x) sq)] 
    (concat l [x] r)))

(defn bubble-sort [sq]
  ((if (vector? sq) vec identity) 
   (reduce insert () sq)))

或：

(defn insert [sq x]
  (let [[l r] (split-with #(< % x) sq)] 
    `(~@l ~x ~@r)))

(defn intoo [x sq] ;; direction neutral `into`
  (into x (into x sq))) 

(defn bubble-sort [sq]
  (intoo (empty sq) (reduce insert () sq)))

需要

intoo 因为

(into () '(1 2 3)) ;;=> '(3 2 1)
(into () [1 2 3])  ;;=> '(3 2 1)
(into [] '(1 2 3)) ;;=> [1 2 3]
(into [] [1 2 3])  ;;=> [1 2 3]
# `into` uses `conj` underneath!

连续应用两次into修复了这个：

(into () (into () '(1 2 3))) ;; '(1 2 3)
(into () (into () [1 2 3]))  ;; '(1 2 3)
(into [] (into [] '(1 2 3))) ;; [1 2 3]
(into [] (into [] [1 2 3]))  ;; [1 2 3]

因此 intoo 是 into 的方向中性版本。

实际上，intoo 的最高效版本可能是：

(defmacro intoo [x sq]
  (if (vector? x)
      `(into ~x ~sq)
      `(reverse (into ~x ~sq))))

;; user=> (intoo () '(1 2 3))
;; (1 2 3)
;; user=> (intoo () [1 2 3])
;; (1 2 3)
;; user=> (intoo [] [1 2 3])
;; [1 2 3]
;; user=> (intoo [] '(1 2 3))
;; [1 2 3]

;; or as a function:
(defn intoo [x & args]
  (if (vector? x)
      (apply into x args)
      (reverse (apply into x args))))

collections 更好的功能

Better function for collections

collections

clojure

bubble-sort