sorted-list 0.2.1.2 → 0.3.1.0
raw patch · 8 files changed
Files
- Data/SortedList.hs +83/−8
- LICENSE +0/−30
- Setup.hs +0/−2
- bench/map.hs +2/−0
- changelog.md +21/−0
- license +21/−0
- sorted-list.cabal +14/−9
- tests/Main.hs +5/−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@@ -22,6 +24,7 @@ , insert -- * Deleting , delete+ , deleteAll -- * Sublists , take , drop@@ -42,9 +45,13 @@ #endif , elemOrd , findIndices- -- * @map@ function+ -- * Functor functions , map , mapDec+ -- * Applicative functions+ , liftA2+ -- * Traversable functions+ , traverse -- * Unfolding , unfoldr -- * Others@@ -55,20 +62,28 @@ , nub , intersect , union+ -- * Unsafe+ , unsafeToSortedList+ -- * Testing+ , isSorted ) where import Prelude hiding ( take, drop, splitAt, filter , repeat, replicate, iterate- , null, map, reverse+ , null, map, reverse, traverse , span, takeWhile, dropWhile #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 (..))+import Data.Foldable (Foldable (..), foldrM) -- #if MIN_VERSION_base(4,5,0) && !MIN_VERSION_base(4,9,0) import Data.Monoid ((<>))@@ -89,12 +104,41 @@ #if MIN_VERSION_base(4,9,0) import Data.Semigroup (Semigroup (..)) #endif+--+#if !MIN_VERSION_base(4,18,0)+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 @@ -102,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@@ -206,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@@ -224,6 +273,17 @@ EQ -> xs go [] = [] +-- | Delete /all/ occurrences of the given element.+deleteAll :: Ord a => a -> SortedList a -> SortedList a+deleteAll a (SortedList l) = SortedList $ go l+ where+ go (x:xs) =+ case x `compare` a of+ LT -> x : go xs+ GT -> x : xs+ EQ -> go xs+ go [] = []+ -- | Extract the prefix with the given length from a sorted list. take :: Int -> SortedList a -> SortedList a take n = fst . splitAt n@@ -351,6 +411,21 @@ "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 #-}++-- | 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 -> Base.liftA2 insert (f x) $ pure xs) mempty #if MIN_VERSION_base(4,6,0)
− LICENSE
@@ -1,30 +0,0 @@-Copyright (c) 2023, Daniel Casanueva--All rights reserved.--Redistribution and use in source and binary forms, with or without-modification, are permitted provided that the following conditions are met:-- * Redistributions of source code must retain the above copyright- notice, this list of conditions and the following disclaimer.-- * Redistributions in binary form must reproduce the above- copyright notice, this list of conditions and the following- disclaimer in the documentation and/or other materials provided- with the distribution.-- * Neither the name of Daniel Casanueva nor the names of other- contributors may be used to endorse or promote products derived- from this software without specific prior written permission.--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS-"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT-LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR-A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT-OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,-SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
− Setup.hs
@@ -1,2 +0,0 @@-import Distribution.Simple-main = defaultMain
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,24 @@+## 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.++## 0.2.3.0+* Update metadata.+* Add `traverse`.+* License changed from BSD3 to MIT for consistency.++## 0.2.2.0+* Add `deleteAll`.+ ## 0.2.1.2 * Use `compare` instead of inequalities in `delete` implementation. * Add test.
+ license view
@@ -0,0 +1,21 @@+MIT License++Copyright (c) 2025 Daniel Díaz Casanueva++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all+copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE+SOFTWARE.
sorted-list.cabal view
@@ -1,5 +1,5 @@ name: sorted-list-version: 0.2.1.2+version: 0.3.1.0 synopsis: Type-enforced sorted lists and related functions. description: Type-enforced sorted lists and related functions. .@@ -24,21 +24,27 @@ . If you are missing a feature, do not hesitate to ask by opening an issue at the bug-tracker.-license: BSD3-license-file: LICENSE-author: Daniel Casanueva (daniel.casanueva `at` proton.me)-maintainer: Daniel Casanueva (daniel.casanueva `at` proton.me)-bug-reports: https://gitlab.com/daniel-casanueva/haskell/sorted-list/-/issues+license: MIT+license-file: license+author: Daniel Casanueva (coding `at` danielcasanueva.eu)+maintainer: Daniel Casanueva (coding `at` danielcasanueva.eu)+bug-reports: https://codeberg.org/daniel-casanueva/sorted-list/issues category: Data build-type: Simple 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@@ -46,7 +52,7 @@ type: exitcode-stdio-1.0 hs-source-dirs: bench main-is: map.hs- ghc-options: -O2 -Wall+ ghc-options: -Wall build-depends: base == 4.* , sorted-list , criterion@@ -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 ()@@ -20,9 +15,6 @@ 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 @@ -36,6 +28,8 @@ \x xs -> let ys :: SortedList Int ys = SL.toSortedList $ x : xs in SL.delete x ys == applyAsList (List.delete x) ys+ quickCheck "deleteAll" $+ \x xs -> SL.deleteAll (x :: Int) xs == SL.filter (/=x) xs quickCheck "elemOrd" $ \x xs -> SL.elemOrd x xs == List.elem (x :: Int) (SL.fromSortedList xs) quickCheck "nub" $