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

[Heinrich Apfelmus]

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