sorting - 您可以在Clojure中将插入排序表述为类对称吗？

这是Clojure中插入排序的代码:

(defn in-sort! [data]
  (letfn [(insert ([raw x](insert [] raw x))
          ([sorted [y & raw] x]
             (if (nil? y) (conj sorted x)
             (if (<= x y ) (concat sorted [x,y] raw)
                 (recur (conj sorted y)  raw x )))))]
    (reduce insert [] data)))
;Usage:(in-sort! [6,8,5,9,3,2,1,4,7])
;Returns: [1 2 3 4 5 6 7 8 9]

这是Haskell中的the insertion sort formulated as a monoid:

newtype OL x = OL [x]
instance Ord x => Monoid (OL x) where
  mempty = OL []
  mappend (OL xs) (OL ys) = OL (merge xs ys) where
    merge [] ys = ys
    merge xs [] = xs
    merge xs@(x : xs') ys@(y : ys')
       | x <= y = x : merge xs' ys
       | otherwise = y : merge xs ys'

isort :: Ord x => [x] -> OL x
isort = foldMap (OL . pure)

This is how在Clojure中编写一个monoid:

(def  mempty (+)) ;; 0
(def  mappend +)
(defn mconcat [ms]
    (reduce mappend mempty ms))

(mappend 3 4) ;; 7

(mconcat [2 3 4]) ;; 9

我的问题是:您能在Clojure中将插入排序表述为类吗？

最佳答案

作为引用，这里是另一个版本，该版本使用累加器将tail recursion modulo cons转换为尾递归。出于多样性的考虑，这也是部分模拟不存在的类型类的一种方法。

(defprotocol Monoid
  (mempty [_] )
  (mappend [_ xs ys]))

(defn fold-map
  [monoid f xs]
  (reduce (partial mappend monoid) (mempty monoid) (map f xs)))

(defn- ord-mappend*
  [[x & rx :as xs] [y & ry :as ys] a]
  (cond
    (empty? xs) (concat a ys)
    (empty? ys) (concat a xs)
    :else (if (< x y)
             (recur rx ys (conj a x))
             (recur xs ry (conj a y)))))

(def Ord
  (reify Monoid
    (mempty [_] (list))
    (mappend [_ xs ys] (ord-mappend* xs ys []))))

(defn isort [xs] (fold-map Ord list xs))

(defn is-sorted? [xs] (apply < xs))

(is-sorted? (isort (shuffle (range 10000))))
;=> true (sometime later)

关于sorting - 您可以在Clojure中将插入排序表述为类对称吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21984769/