title: Can you formulate the insertion sort as a monoid in Clojure?
body: <p>This is the code for an insertion sort in Clojure:</p>
  
  <pre class="lang-clj prettyprint-override"><code>(defn in-sort! [data]
    (letfn [(insert ([raw x](insert [] raw x))
            ([sorted [y &amp; raw] x]
               (if (nil? y) (conj sorted x)
               (if (&lt;= 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]
  </code></pre>
  
  <p>This is <a href="https://stackoverflow.com/questions/21877572/can-you-formulate-the-bubble-sort-as-a-monoid-or-semigroup">the insertion sort formulated as a monoid</a> in Haskell:</p>
  
  <pre class="lang-hs prettyprint-override"><code>newtype OL x = OL [x]
  instance Ord x =&gt; 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 &lt;= y = x : merge xs' ys
         | otherwise = y : merge xs ys'
  
  isort :: Ord x =&gt; [x] -&gt; OL x
  isort = foldMap (OL . pure)
  </code></pre>
  
  <p><a href="http://www.leonardoborges.com/writings/2012/12/05/monads-in-small-bites-part-iii-monoids/" rel="nofollow noreferrer">This is how</a> to write a monoid in Clojure:</p>
  
  <pre class="lang-clj prettyprint-override"><code>(def  mempty (+)) ;; 0
  (def  mappend +)
  (defn mconcat [ms]
      (reduce mappend mempty ms))
  
  (mappend 3 4) ;; 7
  
  (mconcat [2 3 4]) ;; 9
  </code></pre>
  
  <p>My question is: <strong>Can you formulate the insertion sort as a monoid in Clojure?</strong></p>