[project @ 1996-01-22 18:37:39 by partain]

[ghc-hetmet.git] / ghc / lib / ghc / Util.lhs

diff --git a/ghc/lib/ghc/Util.lhs b/ghc/lib/ghc/Util.lhs
index 7f0d406..4b00e92 100644 (file)
--- a/ghc/lib/ghc/Util.lhs
+++ b/ghc/lib/ghc/Util.lhs
@@ -797,27 +797,28 @@ From: Carsten Kehler Holst <kehler@cs.chalmers.se>
 To: partain@dcs.gla.ac.uk
 Subject: natural merge sort beats quick sort [ and it is prettier ]
 
-   Here a piece of Haskell code that I'm rather fond of. See it as an
-attempt to get rid of the ridiculous quick-sort rutine. group is quite
-useful by itself I think it was John's idea originally though I
+Here a piece of Haskell code that I'm rather fond of. See it as an
+attempt to get rid of the ridiculous quick-sort routine. group is
+quite useful by itself I think it was John's idea originally though I
 believe the lazy version is due to me [surprisingly complicated].
-gamma [used to be called] called gamma because I got inspired by the Gamma calculus. It
-is not very close to the calculus but does behave less sequential that
-both foldr and foldl. One could imagine a version of gamma that took a
-unit element as well thereby avoiding the problem with empty lists.
+gamma [used to be called] is called gamma because I got inspired by
+the Gamma calculus. It is not very close to the calculus but does
+behave less sequentially than both foldr and foldl. One could imagine a
+version of gamma that took a unit element as well thereby avoiding the
+problem with empty lists.
 
 I've tried this code against
 
    1) insertion sort - as provided by haskell
    2) the normal implementation of quick sort
    3) a deforested version of quick sort due to Jan Sparud
-   4) a super-optimized-quick-sort of Lennarts
+   4) a super-optimized-quick-sort of Lennart's
 
 If the list is partially sorted both merge sort and in particular
 natural merge sort wins. If the list is random [ average length of
 rising subsequences = approx 2 ] mergesort still wins and natural
-merge sort is marginally beeten by lennart's soqs. The space
-consumption of merge sort is a bit worse than Lennarts quick sort
+merge sort is marginally beaten by Lennart's soqs. The space
+consumption of merge sort is a bit worse than Lennart's quick sort
 approx a factor of 2. And a lot worse if Sparud's bug-fix [see his
 fpca article ] isn't used because of group.
 
@@ -827,6 +828,7 @@ Carsten
 
 \begin{code}
 group :: (a -> a -> Bool) -> [a] -> [[a]]
+
 group p [] = [[]]
 group p (x:xs) = 
    let ((h1:t1):tt1) = group p xs
@@ -838,8 +840,8 @@ group p (x:xs) =
 generalMerge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 generalMerge p xs [] = xs
 generalMerge p [] ys = ys
-generalMerge p (x:xs) (y:ys) | x `p` y = x : generalMerge p xs (y:ys)
-                             | y `p` x = y : generalMerge p (x:xs) ys
+generalMerge p (x:xs) (y:ys) | x `p` y   = x : generalMerge p xs (y:ys)
+                             | otherwise = y : generalMerge p (x:xs) ys
 
 -- gamma is now called balancedFold
 
@@ -852,8 +854,11 @@ balancedFold' :: (a -> a -> a) -> [a] -> [a]
 balancedFold' f (x:y:xs) = f x y : balancedFold' f xs
 balancedFold' f xs = xs
 
-generalMergeSort p = balancedFold (generalMerge p) . map (:[])
-generalNaturalMergeSort p = balancedFold (generalMerge p) . group p
+generalMergeSort p [] = []
+generalMergeSort p xs = (balancedFold (generalMerge p) . map (: [])) xs
+
+generalNaturalMergeSort p [] = []
+generalNaturalMergeSort p xs = (balancedFold (generalMerge p) . group p) xs
 
 mergeSort, naturalMergeSort :: Ord a => [a] -> [a]