data-ordlist 0.4.4 → 0.4.5

raw patch · 3 files changed

+154/−60 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGES +28/−5
• Data/List/Ordered.hs +124/−53
• data-ordlist.cabal +2/−2

@@ -1,15 +1,33 @@+Version 0.4.5:  (2012-03-12)++  * New function, `minus'`++  * Exported `foldt` and `foldt'`++  * Documentation improvements++  * Reverted the implementation of `mergeAll` and `unionAll` to version+    0.4.2 because the simplified implementation would force the head of+    the inner list appearing at the next highest power of 2 well before+    it was necessary to do so.+ Version 0.4.4:  (2010-12-24)    * Simplified the implementation of `mergeAll` and `unionAll` based on     comments from Will Ness. +    <http://www.haskell.org/pipermail/haskell-cafe/2010-December/087587.html>+ Version 0.4.3:  (2010-03-02)    * Improved the implementation of `nubSort`,  mirroring the improvements made-    to `Data.List.sort` currently in GHC HEAD.  Instead of initially breaking-    the input list into singletons before the merge process,  the improved-    version breaks the input list into monotonic runs.+    to `Data.List.sort` in GHC-6.13.20091224 and first released in GHC-7.0.1.+    Thanks to Gwern Branwen for calling the change to my attention.  Instead+    of initially breaking the input list into singletons before the merge+    process,  the improved version breaks the input list into monotonic runs. +    <http://www.haskell.org/pipermail/libraries/2010-March/013066.html>+   * Minor formatting improvements in the Haddock documentation.  Version 0.4.2:  (2010-02-18)@@ -18,15 +36,20 @@     of lists.  Thanks to Omar Antolín Camarena for reporting the bug and     Heinrich Apfelmus for some useful comments. +    <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073403.html>+    <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073437.html>+   * Added regression test to test suite.  Version 0.4.1:  (2010-02-17)    * Simplified the implementation of `mergeAll` and `unionAll` thanks     to some pointers by Heinrich Apfelmus.  This introduced an infinite-    non-productive loop into `unionAll`,  which was later fixed without+    non-productive loop into `unionAll`,  which was fixed in 0.4.2 without     giving up the simplifications. +    <http://www.haskell.org/pipermail/haskell-cafe/2010-February/073356.html>+   * Minor documentation fixes  Version 0.4:    (2010-02-15)@@ -57,7 +80,7 @@     mailing list on 2007 Jul 22.  It also appears as "BayerPrimes.hs"     inside of Melissa O'Neill's "haskell-primes.zip": -    <http://www.mail-archive.com/haskell-cafe@haskell.org/msg27612.html>+    <http://www.haskell.org/pipermail/haskell-cafe/2007-July/029391.html>     <http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip>  Version 0.2:    (2010-02-07)

@@ -1,23 +1,35 @@ ----------------------------------------------------------------------------- -- | -- Module      :  Data.List.Ordered--- Copyright   :  (c) 2009-2010 Leon P Smith+-- Copyright   :  (c) 2009-2011 Leon P Smith -- License     :  BSD3 -- -- Maintainer  :  leon@melding-monads.com -- Stability   :  experimental -- Portability :  portable ----- This module implements bag and set operations on ordered lists.--- Except for variations of the  'sort' and 'isSorted' functions,--- every function assumes that any list arguments are sorted lists.--- Assuming this precondition is met,  every resulting list is also+-- This module implements bag and set operations on ordered lists.  For the+-- purposes of this module,  a \"bag\" (or \"multiset\") is a non-decreasing+-- list, whereas a \"set\" is a strictly ascending list.  Bags are sorted+-- lists that may contain duplicates,  whereas sets are sorted lists that+-- do not contain duplicates.+--+-- Except for the  'nub', 'sort', 'nubSort', and 'isSorted' families of+-- functions, every function assumes that any list arguments are sorted+-- lists. Assuming this precondition is met,  every resulting list is also -- sorted. ----- Note that these functions handle multisets, and are left-biased.--- Thus, even assuming the arguments are sorted,  'isect' does not always--- return the same results as Data.List.intersection,  due to multiplicity.+-- Because 'isect' handles multisets correctly, it does not return results+-- comparable to @Data.List.'Data.List.intersect'@ on them.  Thus @isect@+-- is more than just a more efficient @intersect@ on ordered lists. Similar+-- statements apply to other associations between functions this module and+-- functions in @Data.List@,  such as 'union' and @Data.List.'union'@. --+-- All functions in this module are left biased.  Elements that appear in+-- earlier arguments have priority over equal elements that appear in later+-- arguments,  and elements that appear earlier in a single list have+-- priority over equal elements that appear later in that list.+-- -----------------------------------------------------------------------------  module  Data.List.Ordered@@ -35,10 +47,11 @@      ,  isect, isectBy      ,  union, unionBy      ,  minus, minusBy+     ,  minus', minusBy'      ,  xunion, xunionBy      ,  merge, mergeBy-     ,  mergeAll  , mergeAllBy-     ,  unionAll  , unionAllBy+     ,  mergeAll, mergeAllBy+     ,  unionAll, unionAllBy          -- * Lists to Ordered Lists      ,  nub, nubBy@@ -47,11 +60,15 @@      ,  nubSort, nubSortBy      ,  nubSortOn, nubSortOn' +        -- * Miscellaneous folds+     ,  foldt, foldt'+      )  where -import Data.List(sort,sortBy)+import Data.List(sort,sortBy,intersect) --- |  The 'isSorted' predicate returns 'True' if the elements of a list occur in non-descending order,  equivalent to @'isSortedBy' ('<=')@.+-- |  The 'isSorted' predicate returns 'True' if the elements of a list occur+-- in non-descending order,  equivalent to @'isSortedBy' ('<=')@. isSorted :: Ord a => [a] -> Bool isSorted = isSortedBy (<=) @@ -242,6 +259,29 @@           EQ ->     loop xs ys           GT ->     loop (x:xs) ys +-- |  The 'minus'' function computes the difference of two ordered lists.+-- The result consists of elements from the first list that do not appear+-- in the second list.  If the first input is a set, then the output is+-- a set.+--+-- > minus' [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 1,2 ]+-- > minus' [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == []+-- > minus' [ 1,1, 2,2 ] [ 2 ]          == [ 1,1 ]+minus' :: Ord a => [a] -> [a] -> [a]+minus' = minusBy' compare++-- |  The 'minusBy'' function is the non-overloaded version of 'minus''.+minusBy' :: (a -> a -> Ordering) -> [a] -> [a] -> [a]+minusBy' cmp = loop+  where+     loop [] _ys = []+     loop xs [] = xs+     loop (x:xs) (y:ys)+       = case cmp x y of+          LT -> x : loop xs (y:ys)+          EQ ->     loop xs (y:ys)+          GT ->     loop (x:xs) ys+ -- |  The 'xunion' function computes the exclusive union of two ordered lists. -- An element occurs in the output as many times as the absolute difference -- between the number of occurrences in the inputs.  If both inputs@@ -266,7 +306,8 @@  -- |  The 'merge' function combines all elements of two ordered lists. -- An element occurs in the output as many times as the sum of the--- occurrences in the lists.+-- occurrences in both lists.   The output is a set if and only if+-- the inputs are disjoint sets. -- -- > merge [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 1,2,  3,3,4,4,  5,6 ] -- > merge [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1,1,  2,2,2,2,2 ]@@ -310,7 +351,7 @@ sort = sortBy compare  sortBy :: (a -> a -> Ordering) -> [a] -> [a]-sortBy cmp = foldTree (mergeBy cmp) [] . map (\x -> [x])+sortBy cmp = foldt (mergeBy cmp) [] . map (\x -> [x]) -}  -- |  The 'sortOn' function provides the decorate-sort-undecorate idiom,@@ -327,14 +368,17 @@ sortOn' f = sortBy (\x y -> compare (f x) (f y))  -- |  The 'nubSort' function is equivalent to @'nub' '.' 'sort'@,  except--- somewhat more efficient as duplicates are removed as it sorts.  It is--- essentially Data.List.sort,  with 'merge' replaced by 'union'.+-- that duplicates are removed as it sorts. It is essentially the same+-- implementation as @Data.List.sort@, with 'merge' replaced by 'union'.+-- Thus the performance of 'nubSort' should better than or nearly equal+-- to 'sort' alone.  It is faster than @'nub' '.' 'sort'@ when the+-- input contains significant quantities of duplicated elements. nubSort :: Ord a => [a] -> [a] nubSort = nubSortBy compare  -- |  The 'nubSortBy' function is the non-overloaded version of 'nubSort'. nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]-nubSortBy cmp = foldTree' (unionBy cmp) [] . runs+nubSortBy cmp = foldt' (unionBy cmp) [] . runs   where     -- 'runs' partitions the input into sublists that are monotonic,     -- contiguous,  and non-overlapping.   Descending runs are reversed@@ -366,7 +410,7 @@ nubSortOn :: Ord b => (a -> b) -> [a] -> [a] nubSortOn f = map snd . nubSortOn' fst . map (\x -> (f x, x)) --- |  This variant of 'nubSortOn' recomputes the sorting key 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)) @@ -377,7 +421,6 @@ -- > nub [1,1,1,2,2] == [1,2] -- > nub [2,0,1,3,3] == [2,3] -- > nub = nubBy (<)- nub :: Ord a => [a] -> [a] nub = nubBy (<) @@ -398,13 +441,12 @@        | p x y     = y : loop y ys        | otherwise = loop x ys --- | The function @'foldTree'' plus zero@ computes the sum of a list--- using a balanced tree of operations.  'foldTree'' necessarily diverges--- on infinite lists, hence it is a stricter variant of 'foldTree'.--- 'foldTree'' is used in the implementation of 'sort' and 'nubSort'.--foldTree' :: (a -> a -> a) -> a -> [a] -> a-foldTree' plus zero xs+-- | The function @'foldt'' plus zero@ computes the sum of a list+-- using a balanced tree of operations.  'foldt'' necessarily diverges+-- on infinite lists, hence it is a stricter variant of 'foldt'.+-- 'foldt'' is used in the implementation of 'sort' and 'nubSort'.+foldt' :: (a -> a -> a) -> a -> [a] -> a+foldt' plus zero xs   = case xs of       []    -> zero       (_:_) -> loop xs@@ -415,14 +457,13 @@     pairs (x:y:zs) = plus x y : pairs zs     pairs zs       = zs --- | The function @'foldTree' plus zero@ computes the sum of a list using+-- | The function @'foldt' plus zero@ computes the sum of a list using -- a sequence of balanced trees of operations.   Given an appropriate @plus@ -- operator,  this function can be productive on an infinite list, hence it--- is lazier than 'foldTree''.   'foldTree' is used in the implementation of+-- is lazier than 'foldt''.   'foldt' is used in the implementation of -- 'mergeAll' and 'unionAll'.--foldTree :: (a -> a -> a) -> a -> [a] -> a-foldTree plus zero xs+foldt :: (a -> a -> a) -> a -> [a] -> a+foldt plus zero xs   = case xs of       []    -> zero       (_:_) -> loop xs@@ -433,6 +474,15 @@     pairs (x:y:zs) = plus x y : pairs zs     pairs zs       = zs +-- helper functions used in 'mergeAll' and 'unionAll'++data People a = VIP a (People a) | Crowd [a]++serve (VIP x xs) = x:serve xs+serve (Crowd xs) = xs++vips xss = [ VIP x (Crowd xs) | (x:xs) <- xss ]+ -- | The 'mergeAll' function merges a (potentially) infinite number of -- ordered lists, under the assumption that the heads of the inner lists -- are sorted.  An element is duplicated in the result as many times as@@ -440,22 +490,28 @@ -- -- The 'mergeAll' function is closely related to @'foldr' 'merge' []@. -- The former does not assume that the outer list is finite, whereas--- the latter makes no assumption about the heads of the inner lists.+-- the latter does not assume that the heads of the inner lists are sorted. -- When both sets of assumptions are met,  these two functions are -- equivalent. -- -- This implementation of 'mergeAll'  uses a tree of comparisons, and is -- based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin Camarena,--- and Will Ness.+-- and Will Ness.  See @CHANGES@ for details. mergeAll :: Ord a => [[a]] -> [a] mergeAll = mergeAllBy compare --- | The 'mergeAllBy' function is the non-overloaded variant of the 'mergeAll' function.+-- | The 'mergeAllBy' function is the non-overloaded variant of the 'mergeAll'+-- function. mergeAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]-mergeAllBy cmp = foldTree merge' []+mergeAllBy cmp = serve . foldt merge' (Crowd []) . vips   where-    merge' []     ys = ys-    merge' (x:xs) ys = x : mergeBy cmp xs ys+    merge' (VIP x xs) ys = VIP x (merge' xs ys)+    merge' (Crowd []) ys = ys+    merge' (Crowd xs) (Crowd ys) = Crowd (mergeBy cmp xs ys)+    merge' xs@(Crowd (x:xt)) ys@(VIP y yt)+      = case cmp x y of+         GT -> VIP y (merge' xs yt)+         _  -> VIP x (merge' (Crowd xt) ys)  -- | The 'unionAll' computes the union of a (potentially) infinite number -- of lists,  under the assumption that the heads of the inner lists@@ -463,27 +519,42 @@ -- the maximum number of occurrences in any single list.  Thus, the result -- is a set if and only if every inner list is a set. ----- Analogous to 'mergeAll',  'unionAll' is closely related to--- @'foldr' 'union' []@;  The outer does not assume that the outer list--- is finite,  whereas the right fold does not assume anything about the--- heads of the inner lists. When both sets of assumptions are met,  the--- functions are equivalent.+-- The 'unionAll' function is closely related to @'foldr' 'union' []@.+-- The former does not assume that the outer list is finite, whereas+-- the latter does not assume that the heads of the inner lists are sorted.+-- When both sets of assumptions are met,  these two functions are+-- equivalent. ----- This implementation is also based on implicit heaps,  providing--- a tree of comparisons.+-- Note that there is no simple way to express 'unionAll' in terms of+-- 'mergeAll' or vice versa on arbitrary valid inputs.  They are related+-- via 'nub' however,  as @'nub' . 'mergeAll' == 'unionAll' . 'map' 'nub'@.+-- If every list is a set,  then @map nub == id@,  and in this special case+-- (and only in this special case) does @nub . mergeAll == unionAll@.+--+-- This implementation of 'unionAll'  uses a tree of comparisons, and is+-- based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin Camarena,+-- and Will Ness.  See @CHANGES@ for details. unionAll :: Ord a => [[a]] -> [a] unionAll = unionAllBy compare --- | The 'unionAllBy' function is the non-overloaded variant of the 'unionAll' function.+-- | The 'unionAllBy' function is the non-overloaded variant of the 'unionAll'+-- function. unionAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]-unionAllBy cmp = foldTree union' []+unionAllBy cmp = serve . foldt union' (Crowd []) . vips   where     msg = "Data.List.Ordered.unionAllBy:  the heads of the lists are not sorted" -    union' []     ys = ys-    union' (x:xs) ys = x : case ys of-                             []     -> xs-                             (y:yt) -> case cmp x y of-                                         LT -> unionBy cmp xs ys-                                         EQ -> unionBy cmp xs yt-                                         GT -> error msg+    union' (VIP x xs) ys+       = VIP x $ case ys of+                  Crowd _ -> union' xs ys+                  VIP y yt -> case cmp x y of+                               LT -> union' xs ys+                               EQ -> union' xs yt+                               GT -> error msg+    union' (Crowd []) ys = ys+    union' (Crowd xs) (Crowd ys) = Crowd (unionBy cmp xs ys)+    union' xs@(Crowd (x:xt)) ys@(VIP y yt)+       = case cmp x y of+           LT -> VIP x (union' (Crowd xt) ys)+           EQ -> VIP x (union' (Crowd xt) yt)+           GT -> VIP y (union' xs yt)

@@ -1,5 +1,5 @@ Name:                data-ordlist-Version:             0.4.4+Version:             0.4.5 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.4+  tag:       0.4.5