[project @ 1996-07-01 09:16:34 by partain]

[ghc-hetmet.git] / ghc / lib / hbc / QSort.hs

diff --git a/ghc/lib/hbc/QSort.hs b/ghc/lib/hbc/QSort.hs
deleted file mode 100644 (file)
index f19eb43..0000000
--- a/ghc/lib/hbc/QSort.hs
+++ /dev/null
@@ -1,47 +0,0 @@
-{-
-   This module implements a sort function using a variation on
-   quicksort.  It is stable, uses no concatenation and compares
-   only with <=.
-  
-   sortLe sorts with a given predicate
-   sort   uses the <= method
-  
-   Author: Lennart Augustsson
--}
-
-module QSort(sortLe, sort) where
-sortLe :: (a -> a -> Bool) -> [a] -> [a]
-sortLe le l = qsort le   l []
-
-sort :: (Ord a) => [a] -> [a]
-sort      l = qsort (<=) l []
-
--- qsort is stable and does not concatenate.
-qsort le []     r = r
-qsort le [x]    r = x:r
-qsort le (x:xs) r = qpart le x xs [] [] r
-
--- qpart partitions and sorts the sublists
-qpart le x [] rlt rge r =
-    -- rlt and rge are in reverse order and must be sorted with an
-    -- anti-stable sorting
-    rqsort le rlt (x:rqsort le rge r)
-qpart le x (y:ys) rlt rge r =
-    if le x y then
-       qpart le x ys rlt (y:rge) r
-    else
-       qpart le x ys (y:rlt) rge r
-
--- rqsort is as qsort but anti-stable, i.e. reverses equal elements
-rqsort le []     r = r
-rqsort le [x]    r = x:r
-rqsort le (x:xs) r = rqpart le x xs [] [] r
-
-rqpart le x [] rle rgt r =
-    qsort le rle (x:qsort le rgt r)
-rqpart le x (y:ys) rle rgt r =
-    if le y x then
-       rqpart le x ys (y:rle) rgt r
-    else
-       rqpart le x ys rle (y:rgt) r
-