If someone can translate my algorithm into a non-side-effecting one, I'd appreciate it, but I think that like disjoint set/union, this is probably inherently side-effecting.  Yes, yes, we could use functional arrays, but short of that I don't see a way to avoid side effects to take care of my amortized work.

I am just working on a side-effect-free version.

It seems to me, that you just need a selection algorithm which works in O(n * k) time for k arbitrary elements. If you combine O(n*k) selection algorithm with any O(n * lg n) sort, you furfil your time constrain.

I guess, we also want the list to be sorted in O(1) after having selected every element. Matthias.

The "sorted array of bags of unsorted input" is a nice idea. However, you have to use the data structure in a single-threaded [1] fashion to obtain the claimed bounds. Here's a pure solution that uses amortization and laziness.

import qualified Data.Sequence as S import Data.Sequence ((><)) import Data.Foldable import Data.Monoid

Suppose we have a function to find the the median of a list, and partition it into three sublists: Smaller than the median, equal to the media, larger than the median. That function should run in linear time.

partitionOnMedian :: forall a. (Ord a) => (S.Seq a) -> BTreeRaw a (S.Seq a)

where the following data structure holds the sublists and some bookkeeping information:

data BTreeRaw a m = Leaf | Node {cmp::(a->Ordering) , lN :: Int , less::m , eq :: (S.Seq a) , gN :: Int , greater::m }

where 'lN' and 'gN' are the length of 'less' and 'greater'. We can make BTreeRaw a functor:

instance Functor (BTreeRaw a) where fmap f Leaf = Leaf fmap f (Node c lN l e gN g) = Node c lN (f l) e gN (f g)

Now using a fixed-point construction we can bootstrap a sorting algorithm from partitionOnMedian:

data Fix m = Fix {unfix :: (m (Fix m))} type BTree a = Fix (BTreeRaw a)

treeSort :: forall a. (Ord a) => S.Seq a -> BTree a treeSort = Fix . helper . partitionOnMedian where helper = fmap (Fix . helper . partitionOnMedian)

Now treeSort produces the thunk of a balanced binary search tree. Of course we can get a sorted list out of it (forcing the whole structure):

flatten :: BTree a -> S.Seq a flatten (Fix Leaf) = S.empty flatten (Fix (Node _ lN l e gN g)) = flatten l >< e >< flatten g

mySort = flatten . treeSort

But we can also get elements efficently, forcing only a linear amount of comparisions in the worst case:

index :: BTree a -> Int -> a index (Fix Leaf) _ = error "tried to get an element of Leaf" index (Fix (Node lN l e gN g)) i | i < lN = index l i | i - lN < S.length e = S.index e (i-lN) | i - lN - S.length e < gN = index g (i - lN - S.length e) | i - lN - S.length e - gN >= 0 = error "index out of bounds"

Although we do have to force comparisions only once every time we touch the same element in the tree, we do still have to traverse the tree (in logarithmic time). If you want linear time access on first touch of an element and constant time access afterwards us toArray:

toArray :: (IA.IArray a t) => Fix (BTreeRaw t) -> a Int t toArray tree = IA.listArray (0,maxI) (map (index tree) [0..maxI]) where size (Fix Leaf) = 0 size (Fix (Node lN _ e gN _)) = lN + S.length e + gN maxI = size tree - 1

[1] Single-Threaded in the sense of Okasaki's use of the word.

Matthias Görgens wrote:

...

So, a tree like Matthias implements it is the way to go. Basically, it reifies the recursive calls of quicksort as a lazy data struture which can be evaluated piecemeal.

Yes. I wonder if it is possible to use a standard (randomized quicksort) and employ some type class magic (like continuations) to make the reification [1] transparent to the code.

Matthias. [1] I reified reify.

Well, you can perform an abstraction similar to what leads to the definition of fold . Starting with say sum [] = 0 sum (x:xs) = x + sum xs we can replace the special values 0 and + by variables, leading to a function (fold f z) [] = z (fold f z) (x:xs) = x `f` (fold f z) xs In other words, if we specialize the variables to 0 and + again, we get fold (+) 0 = sum Similarly, we can start with quicksort quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (x:xs) = quicksort ls ++ [x] ++ quicksort rs where ls = filter (<= x) xs rs = filter (> x) xs and replace the operations on the return type with variables quicksort :: Ord a => (a -> b -> b -> b) -> b -> [a] -> b quicksort f z [] = z quicksort f z (x:xs) = f x (quicksort f z ls) (quicksort f z rs) where ls = filter (<= x) xs rs = filter (> x) xs Note however that this is not quite enough to handle the case of a random access tree like you wrote it, because the latter depends on the fact that quicksorts *preserves* the length of the list. What I mean is that we have to keep track of the lengths of the lists, for instance like this: quicksort :: Ord a => (a -> (Int,b) -> (Int,b) -> b) -> b -> [a] -> (Int,b) quicksort f z [] = (0,z) quicksort f z (x:xs) = (length xs + 1, f x (quicksort f z ls) (quicksort f z rs)) where ls = filter (<= x) xs rs = filter (> x) xs And we can implement a random access tree type Sized a = (Int, a) size = fst data Tree a = Empty | Branch a (Sized (Tree a)) (Sized (Tree a)) mySort :: [a] -> Sized (Tree a) mySort = quicksort Branch Empty index :: Sized (Tree a) -> Int -> Maybe a index (0,Empty) _ = Nothing index (n,Branch x a b) k | 1 <= k && k <= size a = index a k | k == size a + 1 = Just x | size a + 1 < k && k <= n = index b (k - size a - 1) | otherwise = Nothing or an ordinary sort qsort :: Ord a => [a] -> [a] qsort = quicksort (\x a b -> snd a ++ [x] ++ snd b) [] Regards, apfelmus -- http://apfelmus.nfshost.com

Matthias Görgens wrote:

Interesting. Can you make the definition of quicksort non-recursive, too? Perhaps with help of a bootstrapping combinator like the one implicit in the approach I have given earlier?

...

treeSort = bootstrap partitionOnMedian bootstrap f = Fix . helper . f where helper = fmap (Fix . helper . f)

...

partitionOnMedian :: forall a. (Ord a) => (S.Seq a) -> BTreeRaw a (S.Seq a)

Extra points if you can give 'bootstrap' or an equivalent in terms of existing Haskell combinators.

Sure, no problem. Of course, some part of algorithm has to be recursive, but this can be outsourced to a general recursion scheme, like the hylomorphism hylo :: Functor f => (a -> f a) -> (f b -> b) -> (a -> b) hylo f g = g . fmap (hylo f g) . f This scheme is a combination of the anamorphism which builds the tree of recursive calls data Fix f = In { out :: f (Fix f) } ana :: Functor f => (a -> f a) -> a -> Fix f ana f = In . fmap (ana f) . f and a catamorphism which combines the results cata :: Functor f => (f b -> b) -> Fix f -> b cata g = g . fmap (cata g) . out so we could also write hylo f g = cata g . ana f For quicksort, the call tree is the fixed point of the functor type Size = Int data Q a b = Empty | Merge Size a b b instance Functor (Q a) where fmap f (Merge n x b b') = Merge n x (f b) (f b') fmap f Empty = Empty The algorithm quicksort = hylo partition merge proceeds in the two well-known phases: first, the input list is partitioned into two parts separated by a pivot partition [] = Empty partition (x:xs) = Merge (length xs + 1) x ls xs where ls = filter (<= x) xs rs = filter (> x) xs and then the sorted results are merged merge Empty = [] merge (Merge _ x a b) = a ++ [x] ++ b The random access tree implementation can be obtained by using a different merge function. In particular, the quicksort from my previous post was parametrized on merge (with a slightly different way to indicate the list lengths); any function of type (Size -> a -> b -> b -> b) -> b -> c is equivalent to a function of type (Q a b -> b) -> c Incidentally, the random access tree *is* the call tree for quicksort, so we'd have merge = In and we can shorten the whole thing to quicksort = ana partition which is essentially what you coded. To read about hylo f g = cata g . ana f with quicksort as example again in a slightly different light, see also the following blog post by Ulisses Costa http://ulissesaraujo.wordpress.com/2009/04/09/hylomorphisms-in-haskell/ Regards, apfelmus -- http://apfelmus.nfshost.com

Matthias Görgens wrote:

Thanks. I heard about the hylo-, ana- and catamorphisms before, but never explicitly used them. Time to get started.

You did use them explicitly :) , namely in treeSort = bootstrap partitionOnMedian bootstrap f = Fix . helper . f where helper = fmap (Fix . helper . f) partitionOnMedian :: (Ord a) => (S.Seq a) -> BTreeRaw a (S.Seq a) since bootstrap f = ana f In particular, we have this slight reformulation bootstrap f = helper' where helper = fmap helper' helper' = Fix . helper . f and hence bootstrap f = helper' where helper' = Fix . fmap helper' . f and thus bootstrap f = Fix . fmap (bootstrap f) . f which is the definition of ana f .

And yet another question: One can get the median in deterministic linear time. For quicksort choosing the median as pivot keeps the O(n log n) average running time and brings down the expected worst case, too. Do you know of a (natural) way to combine selecting the median and doing the quicksort, so that you don't compare unnecessarily?

The way to de-randomize quickselect is to calculate medians of medians. I.e. solve the problem for smaller instances first. I suspect if we follow this strategy with the reified quicksort call-trees, the de-randomized quicksort will look a lot like mergesort.

Interesting question! (Of which I don't know the answer of. ;) ) I never understood the median of median method because I always thought that it calculates an approximate median of approximate medians, which I now realize is not the case. I concur that there should be something better than "recursively wasting" comparisons in quickselect just for finding the median pivot in quicksort, especially since both are the same algorithm modulo lazy evaluation. Concerning quicksort looking like mergesort, it seems like a good idea to somehow merge the groups of 5 from the median-of-medians calculation. However, there is an important difference between quicksort and mergesort, namely lazy quicksort is able to produce the batch of the first k smallest elements in O(n + k log k) total time [1] while lazy mergesort needs O(n + k log n) total time [2] There is something about quicksort that makes it "better" than mergesort. [1] Proof goes like this: First, quicksort chooses a sublist of smallest items recursively until a list of the smallest k items remains, this takes O(n) time. Then the list consisting of the smallest k items is sorted in Θ(k log k). [2] Mergesort builds a tournament tree in Θ(n) time and then performs k tournaments that take O(log n) time each, so the the second phase is O(k log n). I need to think about this. Regards, apfelmus -- http://apfelmus.nfshost.com

Raynor Vliegendhart wrote:

On 7/9/09, Heinrich Apfelmus wrote:

...

Of course, some part of algorithm has to be recursive, but this can be outsourced to a general recursion scheme, like the hylomorphism

hylo :: Functor f => (a -> f a) -> (f b -> b) -> (a -> b) hylo f g = g . fmap (hylo f g) . f

Is that definition of hylo actually usable? A few on IRC tried to use that definition for a few examples, but the examples failed to terminate or blew up the stack.

The implementation of quicksort with hylo works fine for me, given medium sized inputs like for example quicksort (reverse [1..1000]) . What were the examples you tried? Regards, apfelmus -- http://apfelmus.nfshost.com