[Haskell-cafe] Re: excercise - a completely lazy sorting algorithm

[Heinrich Apfelmus]

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