1

The term general (contrary to specialized) in the question means the function can sort the items as long as they are of a type that is an instance of Ord.

Consider one of the most famous haskell ads

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

The above implementation is not in-place.
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 Foreign.Marshal.Array.
My implementation is in-place and runs very well, but I am not satisfied with its type signature

(Ord a, Storable a) => [a] -> IO [a]

To be more precise, the type constraint Storable a annoyed me.

Obviously, if we want to sort items, Ord constraint is needed, while Storable is unnecessary.
In contrast, the type signatures of the classic quicksort or sort in Data.List, is Ord a => [a] -> [a]. The constraint is just Ord.

I didn't find a way to get rid of the additional constraint.

I searched Stackoverflow, and found some questions about in-place quicksort in haskell, e.g.
How do you do an in-place quicksort in Haskell
Why is the minimalist, example Haskell quicksort not a "true" quicksort?

Unfortunately, their major concern is just in-place. All of the in-place quicksort examples given there have additional type constraints as well.
For example, iqsort given by klapaucius has the type signature

iqsort :: (Vector v a, Ord a) => v a -> v a

Does anyone know how to implement an in-place quicksort haskell function with type signature Ord a => [a] -> [a]?
I know how to make an in-place quicksort, but I don't know how to make it general.

Community
  • 1
  • 1
nymk
  • 3,323
  • 3
  • 34
  • 36
  • 1
    isn't the intention of Haskell (i mean being _pure_ functional language) against the in-place sort of things (as the in-place modifications are kind of the side-effects of functions, it is not pure function if it modify arguments) – VB9-UANIC Feb 03 '13 at 18:24
  • 1
    In place and `Ord a => [a] -> [a]` don't make sense together. Haskell lists simply don't do in-place. You're going to need to use IO or ST or State for in-place, because in-place implies mutability. Notice that the instances of [`Vector v a`](http://hackage.haskell.org/packages/archive/vector/0.10.0.1/doc/html/Data-Vector-Generic.html) are choc-full of fixed-size types that are easy to unbox. – AndrewC Feb 03 '13 at 18:42
  • 2
    @VB9-UANIC It's fine to have mutations hidden under pure interface if user cannot possibly detect them. See `ST` monad for example. – Matvey Aksenov Feb 03 '13 at 18:44
  • 1
    Why `Foreign`? What's wrong with `IOArray` and `STArray`? – n. m. could be an AI Feb 03 '13 at 18:57
  • As an example of what others are talking about, see my `vsort` function in [this previous answer](http://stackoverflow.com/questions/10357663/python-faster-than-compiled-haskell/10360424#10360424). – Thomas M. DuBuisson Feb 03 '13 at 19:03
  • can you please explain what exactly to be in-place mean? if I take an array (not a dictionary), does it matter if a sorting algorithm is in-place or not? – Alan Coromano Jul 25 '13 at 14:17
  • As all the answers indicate: it is possible, but in general not actually good for performance. Quicksort is O(n^2) worst-case and O(n.log n) best-case. The algorithm used by `sort` in `Data.List` is O(n.log n) worst-case and O(n) best-case. – Jeremy List Jul 08 '15 at 03:06

2 Answers2

5

iqsort actually looks fully general to me. If you look at the Data.Vector.Generic haddocks, you in fact can use that interface for any a! The difference is that the function as given is more generic, because it allows you to choose an unboxed vector, which of course only works over some a.

Here's the link: http://hackage.haskell.org/packages/archive/vector/0.10.0.1/doc/html/Data-Vector-Generic.html

So if you pick your V to be boxed, the vector constraint goes away.

sclv
  • 38,665
  • 7
  • 99
  • 204
  • 3
    Said another way: the `Ord a` constraint is necessary to generalize to "any" `a`, while the `Vector v a` constraint is necessary to generalize to "any" vector. By specializing to a particular vector type, you eliminate the `Vector v a` constraint, just as by specializing to a particular `a` type, you eliminate the `Ord a` constraint. – Dan Burton Feb 03 '13 at 19:35
  • @DanBurton My understanding is: `Vector v a` is a constrait to `a`. `[a]` is also a constraint to 'a' and is stronger than `Vector v a`. Namely, all `a` subject to `[a]` can be regarded as some `Vector v a`. `Vector [] a` is not yet implemented, but it is trivial to add. Is that correct? – nymk Feb 03 '13 at 20:33
  • That makes no sense. `Vector v a` is a typeclass constraint. `[a]` is a type that is polymorphic in `a`, not a constraint. You don't want to sort a *list* inplace. [a] is a list of a, which is a singly-linked-list. You want to use `MVector ST a`, which is a mutable vector of `a` in the ST monad. – sclv Feb 03 '13 at 20:39
  • I know where my mistake is. `quicksort` with type signature `Ord a => [a] -> [a]` is not the same as `quicksort` can sort the items as long as they are of a type that is an instance of `Ord`. Actually `iqsort` given by klapaucius is a valid general in-place quicksort. – nymk Feb 03 '13 at 21:11
3

Yes it is possible. (Although in Haskell you want to use this kind of imperative algorithms only in cases where you really need top performance.)

I know of 2 such algorithms:

(Introsort is basically refined quicksort that has O(n log n) worst case complexity.)

I'm not sure about MVector, but for MArrays, you don't have to worry about the additional constraints MArray a e m. They're there to make the type more general, not less. Signatures like

qsort :: (MArray a e m, Ord e) => a Int e -> m ()

allow to use the same algorithm for different array representations. For some data types, you can have specialized arrays of that type which are faster and more compact than generic arrays. For example, if you want to sort 8-bit integers, there is a specialized instance MArray IOUArray Int8 IO for unboxed arrays. And a specialization of qsort for this kind of arrays just using polymorphism is

qsort :: IOUArray Int Int8 -> IO ()

But you also have instance MArray IOArray e IO that works arbitrary e. By using qsort with IOArray, you get a specialization without constraints on e:

qsort :: (Ord e) => IOArray Int e -> IO ()

Furthermore, if you use STArrays and the ST monad, you can sort an array in-place using the same function, and get the result later as a pure value, without IO.

Petr
  • 62,528
  • 13
  • 153
  • 317
  • Ah! `MArray IOArray e IO`, how can I missed that? I thought all of them were specializations. Thanks a lot! – nymk Feb 03 '13 at 20:46