title: Is it possible to implement a general in-place quicksort in haskell?
body: <p>The term <em>general</em> (contrary to <em>specialized</em>) in the question means the function can sort the items as long as they are of a type that is an instance of <code>Ord</code>.<br/></p>
  
  <p>Consider one of the most famous haskell ads</p>
  
  <pre><code>quicksort :: Ord a =&gt; [a] -&gt; [a]
  quicksort []     = []
  quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
      where
          lesser  = filter (&lt; p) xs
          greater = filter (&gt;= p) xs
  </code></pre>
  
  <p>The above implementation is not in-place.<br/> 
  I was trying to write an in-place version. 
  It's easy to make quicksort in-place. Usually, we just need a mutable array and I chose <code>Foreign.Marshal.Array</code>.<br/>
  My implementation is in-place and runs very well, but I am not satisfied with its type signature</p>
  
  <pre><code>(Ord a, Storable a) =&gt; [a] -&gt; IO [a]
  </code></pre>
  
  <p>To be more precise, the type constraint <code>Storable a</code> annoyed me.</p>
  
  <p>Obviously, if we want to sort items, <code>Ord</code> constraint is needed, while <code>Storable</code> is unnecessary.<br/>
  In contrast, the type signatures of the classic quicksort or <code>sort</code> in <code>Data.List</code>, is <code>Ord a =&gt; [a] -&gt; [a]</code>. The constraint is just <code>Ord</code>.<br/></p>
  
  <p>I didn't find a way to get rid of the additional constraint. </p>
  
  <p>I searched Stackoverflow, and found some questions about in-place quicksort in haskell, e.g.<br/> 
  <a href="https://stackoverflow.com/questions/5268156/how-do-you-do-an-in-place-quicksort-in-haskell">How do you do an in-place quicksort in Haskell</a><br/>
  <a href="https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort">Why is the minimalist, example Haskell quicksort not a &quot;true&quot; quicksort?</a></p>
  
  <p>Unfortunately, their major concern is just in-place. All of the in-place quicksort examples given there have additional type constraints as well.<br/>
  For example, <a href="https://stackoverflow.com/a/7833043/779412"><code>iqsort</code> given by klapaucius</a>  has the type signature</p>
  
  <pre><code>iqsort :: (Vector v a, Ord a) =&gt; v a -&gt; v a
  </code></pre>
  
  <p>Does anyone know how to implement an in-place quicksort haskell function with type signature <code>Ord a =&gt; [a] -&gt; [a]</code>?<br/>
  I know how to make an in-place quicksort, but I don't know how to make it <em>general</em>.</p>