sorted-list 0.2.3.1 → 0.3.1.0

raw patch · 5 files changed

Files

Data/SortedList.hs +58/−9
bench/map.hs +2/−0
changelog.md +10/−0
sorted-list.cabal +8/−3
tests/Main.hs +3/−11

Data/SortedList.hs view

@@ -5,6 +5,8 @@ --   with several functions to create and use values of that --   type. Many operations are optimized to take advantage --   of the list being sorted.+--+--   It is recommended to import this module qualified. module Data.SortedList (     -- * Type     SortedList@@ -43,10 +45,12 @@ #endif   , elemOrd   , findIndices-    -- * @map@ function+    -- * Functor functions   , map   , mapDec-    -- * @traverse@ function+    -- * Applicative functions+  , liftA2+    -- * Traversable functions   , traverse     -- * Unfolding   , unfoldr@@ -58,6 +62,10 @@   , nub   , intersect   , union+    -- * Unsafe+  , unsafeToSortedList+    -- * Testing+  , isSorted   ) where  import Prelude hiding@@ -68,7 +76,11 @@ #if !MIN_VERSION_base(4,8,0)   , foldr, foldl #endif+#if MIN_VERSION_base(4,18,0)+  , liftA2+#endif     )+import qualified Prelude as Base import qualified Data.List as List import Control.DeepSeq (NFData (..)) import Data.Foldable (Foldable (..), foldrM)@@ -94,14 +106,39 @@ #endif -- #if !MIN_VERSION_base(4,18,0)-import Control.Applicative (liftA2)+import qualified Control.Applicative as Base #endif+-- QuickCheck+import Test.QuickCheck.Arbitrary (Arbitrary (..))  -- | Type of sorted lists. Any (non-bottom) value of this type --   is a sorted list. Use the 'Monoid' instance to merge sorted --   lists. newtype SortedList a = SortedList [a] deriving (Eq, Ord) +-- | Convert a regular list into a sorted list /without sorting it/.+--   By using this function, /you/ are responsible of ensuring that the+--   input is already sorted. If it's not, things will break badly.+--+--   @since 0.3.0.0+unsafeToSortedList :: [a] -> SortedList a+unsafeToSortedList = SortedList++isListSorted :: Ord a => [a] -> Bool+isListSorted xs =+  case xs of+    _ : txs -> and $ zipWith (<=) xs txs+    _ -> True++-- | Check whether a sorted list is sorted.+--   Of course, this function should always return 'True'.+--   It's used mostly for testing.+--+--   @since 0.3.0.0+isSorted :: Ord a => SortedList a -> Bool+{-# INLINE isSorted #-}+isSorted (SortedList xs) = isListSorted xs+ instance Show a => Show (SortedList a) where   show = show . fromSortedList @@ -109,6 +146,11 @@   {-# INLINE rnf #-}   rnf (SortedList xs) = rnf xs +-- | @since 0.3.0.0+instance (Arbitrary a, Ord a) => Arbitrary (SortedList a) where+  arbitrary = toSortedList <$> arbitrary+  shrink (SortedList xs) = toSortedList <$> shrink xs+ #if MIN_VERSION_base(4,7,0) instance Ord a => Exts.IsList (SortedList a) where   type (Item (SortedList a)) = a@@ -213,11 +255,11 @@  -- | /O(n)/. Insert a new element in a sorted list. insert :: Ord a => a -> SortedList a -> SortedList a-#if MIN_VERSION_base(4,5,0)-insert x xs = singleton x <> xs-#else-insert x xs = mappend (singleton x) xs-#endif+{-# INLINE insert #-}+insert a (SortedList xs0) = SortedList $ go xs0+  where+    go [] = [a]+    go l@(x:xs) = if a <= x then a : l else x : go xs  -- | Delete the first occurrence of the given element. delete :: Ord a => a -> SortedList a -> SortedList a@@ -370,13 +412,20 @@ "SortedList:mapDec/id"  forall xs.     mapDec id xs = xs   #-} +-- | Like 'Base.liftA2', but for sorted lists, requiring an 'Ord' instance.+--   The behavior is same as with lists, but with sorted results.+--+--   @since 0.3.1.0+liftA2 :: Ord c => (a -> b -> c) -> SortedList a -> SortedList b -> SortedList c+liftA2 f (SortedList xs) (SortedList ys) = toSortedList $ Base.liftA2 f xs ys+ -- | Traverse a sorted list with a function that returns in a monad. --   The same performance observations apply here as in 'map', as --   changing the values may involve reordering the list. -- --   @since 0.2.3.0 traverse :: (Monad m, Ord b) => (a -> m b) -> SortedList a -> m (SortedList b)-traverse f = foldrM (\x xs -> liftA2 insert (f x) $ pure xs) mempty+traverse f = foldrM (\x xs -> Base.liftA2 insert (f x) $ pure xs) mempty  #if MIN_VERSION_base(4,6,0)

bench/map.hs view

@@ -22,4 +22,6 @@   , bench "increasing/mapDec" $ nf (SL.mapDec incf) list   , bench "decreasing/map"    $ nf (SL.map    decf) list   , bench "decreasing/mapDec" $ nf (SL.mapDec decf) list+  , bench "insert"            $ nf (SL.insert 60) list+  , bench "liftA2"            $ nf (\xs -> SL.liftA2 (+) xs xs) list     ]

changelog.md view

@@ -1,3 +1,13 @@+## 0.3.1.0+* Performance improvements.+* Add function: `liftA2`.++## 0.3.0.0+* Add `Arbitrary` instance for `SortedList`.+  This added a library dependency on QuickCheck.+* Add function: `unsafeToSortedList`.+* Add function: `isSorted`.+ ## 0.2.3.1 * Extend support below base-4.18.

sorted-list.cabal view

@@ -1,5 +1,5 @@ name:                sorted-list-version:             0.2.3.1+version:             0.3.1.0 synopsis:            Type-enforced sorted lists and related functions. description:         Type-enforced sorted lists and related functions.                      .@@ -34,11 +34,17 @@ cabal-version:       1.18 extra-doc-files:     readme.md, changelog.md +source-repository head+  type: git+  location: https://codeberg.org/daniel-casanueva/sorted-list.git+  branch: main+ library   default-language:    Haskell2010-  ghc-options:         -Wall+  ghc-options:         -Wall -Wunused-packages   build-depends:       base == 4.*                ,       deepseq+               ,       QuickCheck   exposed-modules:     Data.SortedList  benchmark sorted-list-map-bench@@ -57,5 +63,4 @@   hs-source-dirs: tests   main-is: Main.hs   ghc-options: -Wall-  default-extensions: ImportQualifiedPost   build-depends: base, sorted-list, QuickCheck

tests/Main.hs view

@@ -1,17 +1,12 @@ -{-# OPTIONS_GHC -Wno-orphans #-}- module Main (main) where  import Control.Monad (unless)-import Test.QuickCheck-  ( Testable, isSuccess, quickCheckResult-  , Arbitrary, arbitrary-    )+import Test.QuickCheck (Testable, isSuccess, quickCheckResult) import System.Exit (exitFailure) import Data.SortedList (SortedList)-import Data.SortedList qualified as SL-import Data.List qualified as List+import qualified Data.SortedList as SL+import qualified Data.List as List  -- | Test a property. quickCheck :: Testable prop => String -> prop -> IO ()@@ -19,9 +14,6 @@   putStrLn $ "Testing property: " ++ n   r <- quickCheckResult p   unless (isSuccess r) exitFailure--instance (Arbitrary a, Ord a) => Arbitrary (SortedList a) where-  arbitrary = SL.toSortedList <$> arbitrary  applyAsList :: Ord a => ([a] -> [a]) -> SortedList a -> SortedList a applyAsList f = SL.toSortedList . f . SL.fromSortedList