data-ordlist 0.4 → 0.4.1

raw patch · 3 files changed

+35/−37 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGES +7/−0
• Data/List/Ordered.hs +26/−35
• data-ordlist.cabal +2/−2

@@ -1,3 +1,10 @@+Version 0.4.1:  (2010-02-17)++  * Simplified the implementation of `mergeAll` and `unionAll` thanks+    to some pointers by Heinrich Apfelmus++  * Minor documentation fixes+ Version 0.4:    (2010-02-15)    * The "CHANGES" file was added to document the changes between releases.

@@ -141,7 +141,7 @@ -- this module follow this idiom for this reason.  genSectBy :: (a -> a -> Ordering)-          -> (a -> a -> Bool)+          -> (Bool -> Bool -> Bool)           -> [a] -> [a] -> [a] genSectBy cmp p = loop   where@@ -299,9 +299,8 @@     loop [xs] = xs     loop xss  = loop (merge_pairs xss) -    merge_pairs []          = []-    merge_pairs [xs]        = [xs]     merge_pairs (xs:ys:xss) = mergeBy cmp xs ys : merge_pairs xss+    merge_pairs xs          = xs -}  -- |  The 'sortOn' function provides the decorate-sort-undecorate idiom,@@ -332,15 +331,14 @@     loop [xs] = xs     loop xss  = loop (union_pairs xss) -    union_pairs []          = []-    union_pairs [xs]        = [xs]     union_pairs (xs:ys:xss) = unionBy cmp xs ys : union_pairs xss+    union_pairs xs          = xs  -- |  The 'nubSortOn' function provides decorate-sort-undecorate for 'nubSort'. nubSortOn :: Ord b => (a -> b) -> [a] -> [a] nubSortOn f = map snd . nubSortOn' fst . map (\x -> (f x, x)) --- |  This variant of 'nubSortOn' recomputes the  for each comparison.+-- |  This variant of 'nubSortOn' recomputes the sorting key for each comparison. nubSortOn' :: Ord b => (a -> b) -> [a] -> [a] nubSortOn' f = nubSortBy (\x y -> compare (f x) (f y)) @@ -374,6 +372,19 @@  data People a = VIP a (People a) | Crowd [a] +foldTree f xs = loop xs+  where+    loop [x]    = x+    loop (x:xs) = x `f` loop (pairs xs)++    pairs (x:y:ys) = f x y : pairs ys+    pairs xs = xs++serve (VIP x xs) = x:serve xs+serve (Crowd xs) = xs++vips xss = [ VIP x (Crowd xs) | (x:xs) <- xss ]+ -- | The 'mergeAll' function generalizes \"'foldr' 'merge' []\" to a -- (possibly infinite) list of (possibly infinite) ordered lists.  To make -- this possible,  it adds the assumption that the heads of the non-empty@@ -392,25 +403,18 @@ -- >   where  merge' []     ys = ys -- >          merge' (x:xs) ys = x : merge xs ys ----- This definition uses a linear chain of comparisons whereas the provided--- implementation uses a tree of comparisons, which is faster on a wide range--- of inputs.+-- This simplification uses a linear chain of comparisons.  The+-- implementation provided uses a tree of comparisons, which is faster on a+-- wide range of inputs. mergeAll :: (Ord a) => [[a]] -> [a] mergeAll = mergeAllBy compare  -- | The 'mergeAllBy' function is the non-overloaded variant of the 'mergeAll' function. mergeAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]-mergeAllBy cmp xss = loop [ (VIP x (Crowd xs)) | (x:xs) <- xss ]+mergeAllBy cmp xss = case vips xss of+                      [] -> []+                      xss' -> serve (foldTree merge' xss')   where-    loop [] = []-    loop ((VIP x xs):xss) = x : loop (xs:xss)-    loop [Crowd xs] = xs-    loop xss = loop (mergePairs xss)--    mergePairs [] = []-    mergePairs [x] = [x]-    mergePairs (x:y:zs) = merge' x y : mergePairs zs-     merge' (VIP x xs) ys = VIP x (merge' xs ys)     merge' (Crowd []) ys = ys     merge' (Crowd xs) (Crowd ys) = Crowd (mergeBy cmp xs ys)@@ -446,23 +450,10 @@  -- | The 'unionAllBy' function is the non-overloaded variant of the 'unionAll' function. unionAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]-unionAllBy cmp xss = loop [ (VIP x (Crowd xs)) | (x:xs) <- xss ]+unionAllBy cmp xss = case vips xss of+                      [] -> []+                      xss' -> serve (foldTree union' xss')   where-    loop [] = []-    loop (  VIP x xs  :  VIP y ys  :  xss  )-      = case cmp x y of-          LT -> x : loop (  xs  :  VIP y ys  :  xss  )-          EQ ->     loop (  VIP x (union' xs ys)  :  unionPairs xss  )-          GT -> error "Data.List.Ordered.unionAllBy:  the heads of the lists are not sorted"-    loop (  VIP x xs  :  xss  )-      =  x : loop (xs:xss)-    loop [Crowd xs] = xs-    loop (xs:xss) = loop (unionPairs (xs:xss))--    unionPairs [] = []-    unionPairs [x] = [x]-    unionPairs (x:y:zs) = union' x y : unionPairs zs-     union' (VIP x xs) (VIP y ys)        = case cmp x y of            LT -> VIP x (union' xs (VIP y ys))

@@ -1,5 +1,5 @@ Name:                data-ordlist-Version:             0.4+Version:             0.4.1 Description:    This module provides set and multiset operations on ordered lists. License:             BSD3@@ -22,4 +22,4 @@ source-repository this   type:      darcs   location:  http://patch-tag.com/r/lpsmith/data-ordlist/pullrepo-  tag:       0.4+  tag:       0.4.1