sorted-list 0.2.0.0 → 0.2.1.0

raw patch · 2 files changed

+60/−6 lines, 2 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/SortedList.hs +59/−5
• sorted-list.cabal +1/−1

@@ -29,10 +29,13 @@   , takeWhile   , dropWhile   , span+    -- ** Filtering+  , partition   , filter+  , filterLT+  , filterGT   , filterLE   , filterGE-  , partition     -- * Queries #if !MIN_VERSION_base(4,8,0)   , null@@ -45,10 +48,13 @@     -- * Unfolding   , unfoldr     -- * Others-  , nub #if MIN_VERSION_base(4,6,0)   , reverse, reverseDown #endif+    -- * Set operations+  , nub+  , intersect+  , union   ) where  import Prelude hiding@@ -64,7 +70,7 @@ import Control.DeepSeq (NFData (..)) import Data.Foldable (Foldable (..)) ---#if MIN_VERSION_base(4,5,0)+#if MIN_VERSION_base(4,5,0) && !MIN_VERSION_base(4,9,0) import Data.Monoid ((<>)) #endif --@@ -80,9 +86,13 @@ import Data.Monoid (Monoid (..)) #endif --+#if MIN_VERSION_base(4,9,0)+import Data.Semigroup (Semigroup (..))+#endif  -- | Type of sorted lists. Any (non-bottom) value of this type---   is a sorted list.+--   is a sorted list. Use the 'Monoid' instance to append sorted+--   lists. newtype SortedList a = SortedList [a] deriving (Eq, Ord)  instance Show a => Show (SortedList a) where@@ -123,6 +133,8 @@ fromSortedList :: SortedList a -> [a] fromSortedList (SortedList xs) = xs +-- | Merge two sorted lists. This assumes that both input lists+--   are sorted. mergeSortedLists :: Ord a => [a] -> [a] -> [a] mergeSortedLists xs [] = xs mergeSortedLists [] ys = ys@@ -131,9 +143,17 @@      then x : mergeSortedLists xs (y:ys)      else y : mergeSortedLists (x:xs) ys +#if MIN_VERSION_base(4,9,0)+instance Ord a => Semigroup (SortedList a) where+  SortedList xs <> SortedList ys = SortedList $ mergeSortedLists xs ys instance Ord a => Monoid (SortedList a) where   mempty = SortedList []+  mappend = (<>)+#else+instance Ord a => Monoid (SortedList a) where+  mempty = SortedList []   mappend (SortedList xs) (SortedList ys) = SortedList $ mergeSortedLists xs ys+#endif  -- | /O(1)/. Create a sorted list with only one element. singleton :: a -> SortedList a@@ -226,6 +246,20 @@ filter :: (a -> Bool) -> SortedList a -> SortedList a filter f = fst . partition f +-- | /O(n)/. Select only elements that are strictly less than the argument.+filterLT :: Ord a => a -> SortedList a -> SortedList a+filterLT a (SortedList l) = SortedList $ go l+  where+    go (x:xs) = if x < a then x : go xs else []+    go [] = []++-- | /O(n)/. Select only elements that are strictly greater than the argument.+filterGT :: Ord a => a -> SortedList a -> SortedList a+filterGT a (SortedList l) = SortedList $ go l+  where+    go (x:xs) = if a < x then x : xs else go xs+    go [] = []+ -- | /O(n)/. Select only elements less or equal to the argument. filterLE :: Ord a => a -> SortedList a -> SortedList a filterLE a (SortedList l) = SortedList $ go l@@ -354,6 +388,26 @@ dropWhile :: (a -> Bool) -> SortedList a -> SortedList a dropWhile f = snd . span f --- | Return the indices of all elements in a sorted list that satisfy the given condition.+-- | /O(n)/. Return the indices of all elements in a sorted list that satisfy the given condition. findIndices :: (a -> Bool) -> SortedList a -> SortedList Int findIndices f (SortedList xs) = SortedList $ List.findIndices f xs++-- | /O(n+m)/. Intersection of sorted lists. If the first list contains duplicates, so will the result.+intersect :: Ord a => SortedList a -> SortedList a -> SortedList a+intersect xs ys =+  let SortedList xs' = xs+      SortedList ys' = nub ys+      go [] _  = []+      go _  [] = []+      go pp@(p:ps) qq@(q:qs) =+        case p `compare` q of+          LT ->     go ps qq+          EQ -> p : go ps qq+          GT ->     go pp qs+  in  SortedList $ go xs' ys'++-- | Union of sorted lists.+--   Duplicates, and elements of the first list, are removed from the the second list,+--   but if the first list contains duplicates, so will the result.+union :: Ord a => SortedList a -> SortedList a -> SortedList a+union xs ys = xs `mappend` foldl (flip delete) (nub ys) xs

@@ -1,5 +1,5 @@ name:                sorted-list-version:             0.2.0.0+version:             0.2.1.0 synopsis:            Type-enforced sorted lists and related functions. description:         Type-enforced sorted lists and related functions.                      .