Description: Two way partitioning forces equals into one or other partition, leading to quadratic behaviour in the number of duplicates if they are retrained. Difference lists are a logic programming technique to avoid explicit append, and hence extra passes through lists that increase the computational time, and sometimes order. This extends the Difference List examples in the style of the Michael Hanus smap. The 3-way example is stable but still has a quadratic worst case related to preordering.

Source code (Latest version): -- Computations (reverse and quicksort) with difference lists. -- Infix operator for writing difference lists: infixr 4 # -- A difference lists consists of a head and a tail: data DList a = [a] # [a] -- cons on a difference list: consD :: a -> DList a -> DList a consD x (h#t) = (x:h#t) -- Transform a difference list into a standard list: fromD :: DList a -> [a] fromD (xs#[]) = xs -- Concatenation of difference lists: appD :: DList a -> DList a -> DList a appD (a#b) (b#n) = (a#n) -- Reverse with difference lists: revD :: [a] -> DList a revD [] = (m#m) where m free revD (x:xs) = appD (revD xs) (x:m # m) where m free -- Quicksort with difference lists: qsortD :: [a] -> DList a qsortD [] = (m#m) where m free qsortD (x:xs) = let (l,r) = split x xs in appD (qsortD l) (consD x (qsortD r)) -- Splitting a list into smaller and larger elements: split :: a -> [a] -> ([a],[a]) split _ [] = ([],[]) split e (x:xs) | e>=x = (x:l,r) | e<x = (l,x:r) where (l,r) = split e xs -- Two-way Quicksort with difference lists: qsort2D :: [a] -> DList a qsort2D [] = (m#m) where m free qsort2D (p:xs) = appD (qsort2D ss) (consD p (qsort2D gs)) where (ss,gs) = split2 p xs -- Two-way Split on pivot without difference lists or duplicates: split2 :: a -> [a] -> ([a],[a]) split2 _ [] = ([],[]) split2 p (x:xs) | x<p = (x:ss, gs) | x==p = (ss, gs) | x>p = (ss, x:gs) where (ss,gs) = split2 p xs -- Two-way Quicksort with difference list splits: qsort2DS :: [a] -> DList a qsort2DS [] = (m#m) where m free qsort2DS (p:xs) = appD (qsort2DS (fromD sd)) (consD p (qsort2DS (fromD gd))) where (sd,gd) = split2D p xs -- Two-way Split on pivot with difference lists but no duplicates: split2D :: a -> [a] -> (DList a, DList a) split2D _ [] = (sn#sn,gn#gn) where sn, gn free split2D p (x:xs) | x<p = (x:ss#sn,gs#gn) | x==p = (ss#sn,gs#gn) | x>p = (ss#sn,x:gs#gn) where (ss#sn,gs#gn) = split2D p xs -- Three-way Quicksort with difference list splits: qsort3DS :: [a] -> DList a qsort3DS [] = (m#m) where m free qsort3DS (p:xs) = appD (qsort3DS (fromD sd)) (appD ed (qsort3DS (fromD gd))) where (sd,ed,gd) = split3D p xs -- Three-way Split on pivot with difference lists and equal pivots: split3D :: a -> [a] -> (DList a, DList a, DList a) split3D p [] = (sn#sn,p:en#en,gn#gn) where sn, en, gn free split3D p (x:xs) | x<p = (x:ss#sn,es#en,gs#gn) | x==p = (ss#sn,x:es#en,gs#gn) | x>p = (ss#sn,es#en,x:gs#gn) where (ss#sn,es#en,gs#gn) = split3D p xs main = fromD (revD [1..10]) main = fromD (qsortD [2,3,5,4,3,2,1,0]) main = fromD (qsort2D [2,3,5,4,3,2,1,0]) main = fromD (qsort2DS [2,3,5,4,3,2,1,0]) main = fromD (qsort3DS [2,3,5,4,3,2,1,0])