sorted-list 0.1.3.0 → 0.1.4.0

raw patch · 3 files changed

+164/−15 lines, 3 filesdep +criteriondep +deepseqdep +sorted-listdep ~basePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: criterion, deepseq, sorted-list

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/SortedList.hs +128/−14
• bench/map.hs +25/−0
• sorted-list.cabal +11/−1

@@ -24,30 +24,48 @@   , take   , drop   , splitAt+  , takeWhile+  , dropWhile+  , span   , filter+  , partition     -- * Queries #if !MIN_VERSION_base(4,8,0)   , null #endif   , elemOrd-    -- * Others+  , findIndices+    -- * @map@ function   , map+  , mapDec+    -- * Unfolding+  , unfoldr+    -- * Others   , nub+#if MIN_VERSION_base(4,6,0)+  , reverse, reverseDown+#endif   ) where  import Prelude hiding   ( take, drop, splitAt, filter   , repeat, replicate, iterate-  , null, map+  , null, map, reverse+  , span, takeWhile, dropWhile #if !MIN_VERSION_base(4,8,0)   , foldr #endif     ) import qualified Data.List as List+import Data.Foldable (Foldable (..))+import Control.DeepSeq (NFData (..))+-- #if MIN_VERSION_base(4,5,0) import Data.Monoid ((<>)) #endif-import Data.Foldable (Foldable (..))+#if MIN_VERSION_base(4,6,0)+import Data.Ord (Down (..))+#endif #if !MIN_VERSION_base(4,8,0) import Data.Monoid (Monoid (..)) #endif@@ -60,13 +78,19 @@ instance Show a => Show (SortedList a) where   show = show . fromSortedList +instance NFData a => NFData (SortedList a) where+  {-# INLINE rnf #-}+  rnf (SortedList xs) = rnf xs+ #if !MIN_VERSION_base(4,8,0) -- | Check if a sorted list is empty.+--   /This function dissappears in @base@ version 4.8.0.0 in favor of @null@/+--   /from "Data.Traversable"./ null :: SortedList a -> Bool null = List.null . fromSortedList #endif --- | Decompose a sorted list into its minimal element and the rest.+-- | /O(1)/. Decompose a sorted list into its minimal element and the rest. --   If the list is empty, it returns 'Nothing'. uncons :: SortedList a -> Maybe (a, SortedList a) uncons (SortedList []) = Nothing@@ -76,7 +100,7 @@ toSortedList :: Ord a => [a] -> SortedList a toSortedList = SortedList . List.sort --- | Create a list from a 'SortedList'. The returned list+-- | /O(1)/. Create a list from a 'SortedList'. The returned list --   is guaranteed to be sorted. fromSortedList :: SortedList a -> [a] fromSortedList (SortedList xs) = xs@@ -106,6 +130,25 @@ replicate :: Int -> a -> SortedList a replicate n = SortedList . List.replicate n +-- | Dual (sort of) to 'foldr' for sorted lists. It builds a sorted list from+--   a generator function and an initial element. The generator function is+--   applied to the initial element, and then it will produce either 'Nothing'+--   - meaning that the list building must stop - or 'Just' applied to the+--   value that is going to be added to the list, and a new accumulator to be fed+--   to the generator function. The list building will stop prematurely if the+--   generator function happens to create an element for the list that is strictly+--   smaller than the previous value.+unfoldr :: Ord a => (b -> Maybe (a,b)) -> b -> SortedList a+unfoldr f e = SortedList $+  let g (prev,acc) = do+        (curr,acc') <- f acc+        if prev <= curr+           then Just (curr, (curr, acc'))+           else Nothing+  in  case f e of+        Just (x0,e') -> x0 : List.unfoldr g (x0,e')+        _ -> []+ -- | Create a sorted list by repeatedly applying the same --   function to an element, until the image by that function --   is stricly less than its argument. In other words:@@ -115,13 +158,13 @@ --   With the list ending whenever --   @f (f (... (f (f x)) ...)) < f (... (f (f x)) ...)@. --   If this never happens, the list will be infinite.+--+--   By definition:+--+-- > iterate f = unfoldr (\x -> Just (x, f x))+-- iterate :: Ord a => (a -> a) -> a -> SortedList a-iterate f x = SortedList $ x : go x (f x)-  where-    go prev fprev =-      if prev <= fprev-         then fprev : go fprev (f fprev)-         else []+iterate f = unfoldr $ \x -> Just (x, f x)  -- | /O(n)/. Insert a new element in a sorted list. insert :: Ord a => a -> SortedList a -> SortedList a@@ -148,9 +191,17 @@   let (ys,zs) = List.splitAt n xs   in  (SortedList ys, SortedList zs) +-- | /O(n)/. Divide a sorted list into two lists, one with all the elements+--   that satisfy the given predicate, and another list with the rest of+--   elements.+partition :: (a -> Bool) -> SortedList a -> (SortedList a, SortedList a)+partition f (SortedList xs) =+  let (ys,zs) = List.partition f xs+  in  (SortedList ys, SortedList zs)+ -- | /O(n)/. Extract the elements of a list that satisfy the predicate. filter :: (a -> Bool) -> SortedList a -> SortedList a-filter f (SortedList xs) = SortedList $ List.filter f xs+filter f = fst . partition f  -- | /O(n)/. An efficient implementation of 'elem', using the 'Ord' --   instance of the elements in a sorted list. It only traverses@@ -193,16 +244,79 @@ --   Note that 'map' will hang if the argument is an infinite list. -- --   Even though 'SortedList' can't be made an instance of 'Functor',---   'map' /does/ hold the 'Functor' laws. The problem to write the---   the instance is the 'Ord' instance requirement on the type of+--   'map' /does/ hold the 'Functor' laws. The problem to write+--   this instance is the 'Ord' instance requirement on the type of --   the elements of the result list. Therefore, while 'SortedList' --   is not a functor type in general, it is when restricted to elements of --   orderable types.+--+--   The complexity range goes from /O(n)/ (if the function is monotonically increasing)+--   to /O(n²)/ (if the function is monotonically decreasing). These are the best+--   and worst case scenarios. We provide an alternative ('mapDec') where monotonically+--   decreasing functions are the best case scenario. map :: Ord b => (a -> b) -> SortedList a -> SortedList b {-# INLINE[1] map #-} map f = foldr (insert . f) mempty +-- | Just like 'map', but favoring functions that are monotonically decreasing instead+--   of those that are monotonically increasing.+mapDec :: Ord b => (a -> b) -> SortedList a -> SortedList b+{-# INLINE[1] mapDec #-}+mapDec f = foldl (\xs x -> insert (f x) xs) mempty+ {-# RULES "SortedList:map/map" forall f g xs. map f (map g xs) = map (f . g) xs "SortedList:map/id"  forall xs.     map id xs = xs++"SortedList:mapDec/mapDec" forall f g xs. mapDec f (map g xs) = mapDec (f . g) xs+"SortedList:mapDec/map" forall f g xs. mapDec f (map g xs) = map (f . g) xs+"SortedList:map/mapDec" forall f g xs. map f (mapDec g xs) = map (f . g) xs+"SortedList:mapDec/id"  forall xs.     mapDec id xs = xs   #-}++#if MIN_VERSION_base(4,6,0)++-- | /O(n)/. Reverse a sorted list. The result uses 'Down', thus it is a sorted+--   list as well. The following equality holds for any sorted list @xs@:+--+-- > map Down xs = reverse xs+--+--   /Only available from @base@ version 4.6.0.0./+reverse :: SortedList a -> SortedList (Down a)+{-# INLINE[2] reverse #-}+reverse = SortedList . List.reverse . fmap Down . fromSortedList++{-# RULES+"SortedList:map/Down" forall xs. map Down xs = reverse xs+  #-}++-- | /O(n)/. Reverse a sorted list with elements embedded in the 'Down' type.+--+--   /Only available from @base@ version 4.6.0.0./+reverseDown :: SortedList (Down a) -> SortedList a+{-# INLINE[2] reverseDown #-}+reverseDown = SortedList . List.reverse . fmap unDown . fromSortedList+  where+    unDown (Down a) = a++#endif++-- | Return the longest prefix of a sorted list of elements that satisfy the given condition,+--   and the rest of the list.+span :: (a -> Bool) -> SortedList a -> (SortedList a, SortedList a)+span f (SortedList xs) =+  let (ys,zs) = List.span f xs+  in  (SortedList ys, SortedList zs)++-- | Return the longest prefix of a sorted list of elements that satisfy the given condition.+takeWhile :: (a -> Bool) -> SortedList a -> SortedList a+takeWhile f = fst . span f++-- | Return the suffix remaining after dropping the longest prefix of elements that satisfy+--   the given condition.+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.+findIndices :: (a -> Bool) -> SortedList a -> SortedList Int+findIndices f (SortedList xs) = SortedList $ List.findIndices f xs

@@ -0,0 +1,25 @@++module Main (main) where++import Data.SortedList (SortedList)+import qualified Data.SortedList as SL+import Criterion.Main (defaultMain, bench, nf)++list :: SortedList Int+list = SL.take 100 $ SL.iterate (+1) 1++-- | Monotonically increasing function.+incf :: Int -> Int+incf x = 2 * x++-- | Monotonically decreasing function.+decf :: Int -> Int+decf x = (-2) * x++main :: IO ()+main = defaultMain+  [ bench "increasing/map"    $ nf (SL.map    incf) list+  , bench "increasing/mapDec" $ nf (SL.mapDec incf) list+  , bench "decreasing/map"    $ nf (SL.map    decf) list+  , bench "decreasing/mapDec" $ nf (SL.mapDec decf) list+    ]

@@ -1,5 +1,5 @@ name:                sorted-list-version:             0.1.3.0+version:             0.1.4.0 synopsis:            Type-enforced sorted lists and related functions. description:         Type-enforced sorted lists and related functions.                      .@@ -20,5 +20,15 @@ library   exposed-modules:     Data.SortedList   build-depends:       base == 4.*+               ,       deepseq   default-language:    Haskell2010   ghc-options:         -Wall++benchmark sorted-list-map-bench+  type: exitcode-stdio-1.0+  hs-source-dirs: bench+  main-is: map.hs+  build-depends: base == 4.*+               , sorted-list+               , criterion+  ghc-options: -O2 -Wall