QuickSort with differential list

gistfile1.hs

module QuickSortWithDL where

import Data.Monoid

data DL a = DL ([a] -> [a])

instance Monoid (DL a) where
    mempty              = DL ([] ++)
    DL f `mappend` DL g = DL (f . g)
    
singleton :: a -> DL a
singleton x = DL ([x] ++)

qsort :: Ord a => [a] -> [a]
qsort xs = builder []
  where
    DL builder = qsort' xs

qsort' :: Ord a => [a] -> DL a
qsort' []     = mempty
qsort' (x:xs) = le <> singleton x <> gt
  where
    le = qsort' [y|y<-xs,y<x]
    gt = qsort' [y|y<-xs,y>x]