slist 0.1.1.0 → 0.2.0.0

raw patch · 10 files changed

+1106/−384 lines, 10 filesdep +containersdep +hedgehogdep +hspecdep ~basePVP ok

version bump matches the API change (PVP)

Dependencies added: containers, hedgehog, hspec, hspec-hedgehog, slist

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +31/−7
• README.md +12/−4
• slist.cabal +28/−8
• src/Slist.hs +366/−359
• src/Slist/Containers.hs +79/−0
• src/Slist/Maybe.hs +149/−0
• src/Slist/Size.hs +28/−6
• src/Slist/Type.hs +309/−0
• test/Spec.hs +9/−0
• test/Test/Slist/Size.hs +95/−0

@@ -3,29 +3,53 @@ `slist` uses [PVP Versioning][1]. The changelog is available [on GitHub][2]. +## 0.2.0.0 — Mar 18, 2021++* [#45](https://github.com/kowainik/slist/issues/45):+  Support GHC-9.0. Update older GHC's bounds.+* [#36](https://github.com/kowainik/slist/issues/36):+  Add strict functions: `append'`, `concat'` and `concatMap'`.+* [#30](https://github.com/kowainik/slist/issues/30):+  Add `cons` and `cons'` functions.+* [#35](https://github.com/kowainik/slist/issues/35):+  Add integration with the `containers` library: `mapToKeys`, `mapToVals`,+  `mapToPairs`, `setToSlist`.++  Add `ordNub`.+* [#34](https://github.com/kowainik/slist/issues/34):+  Add `partitionWith` and `listPartitionWith`.+* [#29](https://github.com/kowainik/slist/issues/29):+  Add `Slist.Maybe` module with `maybeToSlist`, `slistToMaybe`, `catMaybes`,+  `mapMaybe`, `slistWith` functions.+* [#31](https://github.com/kowainik/slist/issues/31):+  Add `sortWith`.+* [#24](https://github.com/kowainik/slist/issues/24):+  Add `chunksOf` for `Slist` and `listChunksOf` for ordinary lists.+* Move the `Slist` data type into the separate `Slist.Type` module.+ ## 0.1.1.0 — Apr 18, 2020  * Fix `mconcat` for `Slist` `Monoid` instance.-* [#25](https://github.com/vrom911/slist/issues/25):+* [#25](https://github.com/kowainik/slist/issues/25):   Support GHC-8.10. * Update to GHC-8.8.3 from GHC-8.8.1.  ## 0.1.0.0 -* [#13](https://github.com/vrom911/slist/issues/13):+* [#13](https://github.com/kowainik/slist/issues/13):   Support GHC-8.8.1.-* [#16](https://github.com/vrom911/slist/issues/16):+* [#16](https://github.com/kowainik/slist/issues/16):   Use `DerivingStrategies`.-* [#9](https://github.com/vrom911/slist/issues/9):+* [#9](https://github.com/kowainik/slist/issues/9):   Implement `fromRange` function.   (by @zfnmxt)-* [#6](https://github.com/vrom911/slist/issues/6):+* [#6](https://github.com/kowainik/slist/issues/6):   Add generic function over the size and indices.   (by @waynee95) * Make `dropWhile` work better on infinite lists.   (by @chshersh) * Support GHC-8.6.5 instead of GHC-8.6.3.-* [#6](https://github.com/vrom911/slist/issues/6):+* [#6](https://github.com/kowainik/slist/issues/6):   Build with Stack.  ## 0.0.0@@ -33,4 +57,4 @@ * Initially created.  [1]: https://pvp.haskell.org-[2]: https://github.com/vrom911/slist/releases+[2]: https://github.com/kowainik/slist/releases

@@ -1,12 +1,16 @@ # slist -[![GitHub CI](https://github.com/vrom911/slist/workflows/CI/badge.svg)](https://github.com/vrom911/slist/actions)-[![Build status](https://img.shields.io/travis/vrom911/slist.svg?logo=travis)](https://travis-ci.org/vrom911/slist)+[![GitHub CI](https://github.com/kowainik/slist/workflows/CI/badge.svg)](https://github.com/kowainik/slist/actions)+[![Build status](https://img.shields.io/travis/kowainik/slist.svg?logo=travis)](https://travis-ci.org/kowainik/slist) [![Hackage](https://img.shields.io/hackage/v/slist.svg?logo=haskell)](https://hackage.haskell.org/package/slist) [![Stackage LTS](http://stackage.org/package/slist/badge/lts)](http://stackage.org/lts/package/slist) [![Stackage Nightly](http://stackage.org/package/slist/badge/nightly)](http://stackage.org/nightly/package/slist) [![MPL-2.0 license](https://img.shields.io/badge/license-MPL--2.0-blue.svg)](LICENSE) +> ⚠️ Caution: this is a very opinionated library. There is no intention to replace the standard list data type.+> We are aware of every design decision we made for this package, and we are taking responsibility for that design.+> If you find it inappropriate, please, consider to use another library instead, that would fulfil your requirements.+ This package introduces sized list data type — `Slist`. The data type has the following shape: @@ -27,6 +31,10 @@     | Infinity ``` +> ⚠️ Caution: `Int` is used for the size by design. We had to make some trade-offs+> to provide the better (as we think) interface for users. For more details on the+> choice, see the Haddock documentation for the `Size` data type.+ This representation of the list gives some additional advantages. Getting the length of the list is the "free" operation (runs in `O(1)`). This property helps to improve the performance for a bunch of functions like `take`, `drop`,@@ -51,10 +59,10 @@  ## Potential usage cases -* When you ask the length of the list too frequently.+* When you ask the size of the list too frequently. * When you need to convert to data structures that require to know the list   size in advance for allocating an array of the elements.   _Example:_ [Vector data structure](https://hackage.haskell.org/package/vector).-* When you need to serialised lists.+* When you need to serialise lists. * When you need to control the behaviour depending on the finiteness of the list. * When you need a more efficient or safe implementation of some functions.

@@ -1,16 +1,17 @@ cabal-version:       2.4 name:                slist-version:             0.1.1.0+version:             0.2.0.0 synopsis:            Sized list description:         This package implements @Slist@ data structure that stores the size                      of the list along with the list itself.-homepage:            https://github.com/vrom911/slist-bug-reports:         https://github.com/vrom911/slist/issues+homepage:            https://github.com/kowainik/slist+bug-reports:         https://github.com/kowainik/slist/issues license:             MPL-2.0 license-file:        LICENSE author:              Veronika Romashkina-maintainer:          vrom911@gmail.com+maintainer:          Kowainik <xrom.xkov@gmail.com> copyright:           2019-2020 Veronika Romashkina+                     2020-2021 Kowainik category:            Data Structures, List build-type:          Simple extra-doc-files:     README.md@@ -18,15 +19,16 @@ tested-with:         GHC == 8.2.2                    , GHC == 8.4.4                    , GHC == 8.6.5-                   , GHC == 8.8.3-                   , GHC == 8.10.1+                   , GHC == 8.8.4+                   , GHC == 8.10.4+                   , GHC == 9.0.1  source-repository head   type:                git-  location:            https://github.com/vrom911/slist.git+  location:            https://github.com/kowainik/slist.git  common common-options-  build-depends:       base >= 4.10.1.0 && < 4.15+  build-depends:       base >= 4.10.1.0 && < 4.16    ghc-options:         -Wall                        -Wincomplete-uni-patterns@@ -60,9 +62,13 @@  library   import:              common-options+  build-depends:       containers >= 0.5 && <= 0.7   hs-source-dirs:      src   exposed-modules:     Slist+                         Slist.Containers+                         Slist.Maybe                          Slist.Size+                         Slist.Type  test-suite slist-doctest   import:              common-options@@ -72,3 +78,17 @@   build-depends:       doctest                      , Glob   ghc-options:         -threaded++test-suite slist-test+  import:              common-options+  type:                exitcode-stdio-1.0+  hs-source-dirs:      test+  main-is:             Spec.hs+  other-modules:       Test.Slist.Size+  build-depends:       slist+                     , hedgehog ^>= 1.0+                     , hspec+                     , hspec-hedgehog ^>= 0.0.1+  ghc-options:         -threaded+                       -rtsopts+                       -with-rtsopts=-N

@@ -7,8 +7,11 @@  {- | Copyright:  (c) 2019-2020 Veronika Romashkina-License:    MPL-2.0-Maintainer: Veronika Romashkina <vrom911@gmail.com>+            (c) 2020-2021 Kowainik+SPDX-License-Identifier: MPL-2.0+Maintainer: Kowainik <xrom.xkov@gmail.com>+Stability:   Stable+Portability: Portable  This module introduces sized list data type — 'Slist'. The data type has the following shape:@@ -75,343 +78,187 @@ -}  module Slist-       ( -- * Types-         Slist-       , Size-         -- ** Smart constructors-       , slist-       , infiniteSlist-       , one-       , iterate+    ( -- * Types+      Slist+    , Size+      -- ** Smart constructors+    , slist+    , infiniteSlist+    , one+    , iterate #if ( __GLASGOW_HASKELL__ > 802 )-       , iterate'+    , iterate' #endif-       , repeat-       , replicate-       , cycle-       , fromRange-         -- * Basic functions-       , len-       , size-       , isEmpty-       , head-       , safeHead-       , last-       , safeLast-       , init-       , tail-       , uncons+    , repeat+    , replicate+    , cycle+    , fromRange+      -- * Basic functions+    , len+    , size+    , isEmpty+    , head+    , safeHead+    , last+    , safeLast+    , init+    , tail+    , append'+    , cons+    , cons'+    , uncons -         -- * Transformations-       , map-       , reverse-       , safeReverse-       , intersperse-       , intercalate-       , transpose-       , subsequences-       , permutations+      -- * Transformations+    , map+    , reverse+    , safeReverse+    , intersperse+    , intercalate+    , transpose+    , subsequences+    , permutations -         -- *  Reducing slists (folds)-       , concat-       , concatMap+      -- *  Reducing slists (folds)+    , concat+    , concat'+    , concatMap+    , concatMap' -         -- * Building slists-         -- ** Scans-       , scanl-       , scanl'-       , scanl1-       , scanr-       , scanr1+      -- * Building slists+      -- ** Scans+    , scanl+    , scanl'+    , scanl1+    , scanr+    , scanr1 -         -- ** Unfolding-       , unfoldr+      -- ** Unfolding+    , unfoldr -         -- * Subslists-         -- ** Extracting-       , take-       , drop-       , splitAt-       , takeWhile-       , dropWhile-       , span-       , break-       , stripPrefix-       , safeStripPrefix-       , group-       , groupBy-       , inits-       , tails-         -- ** Predicates-       , isPrefixOf-       , safeIsPrefixOf-       , isSuffixOf-       , safeIsSuffixOf-       , isInfixOf-       , safeIsInfixOf-       , isSubsequenceOf-       , safeIsSubsequenceOf+      -- * Subslists+      -- ** Extracting+    , take+    , drop+    , splitAt+    , takeWhile+    , dropWhile+    , span+    , break+    , stripPrefix+    , safeStripPrefix+    , group+    , groupBy+    , inits+    , tails+    , chunksOf+    , listChunksOf+      -- ** Predicates+    , isPrefixOf+    , safeIsPrefixOf+    , isSuffixOf+    , safeIsSuffixOf+    , isInfixOf+    , safeIsInfixOf+    , isSubsequenceOf+    , safeIsSubsequenceOf -         -- * Searching-         -- ** Searching by equality-       , lookup-         -- ** Searching with a predicate-       , filter-       , partition+      -- * Searching+      -- ** Searching by equality+    , lookup+      -- ** Searching with a predicate+    , filter+    , partition+    , partitionWith+    , listPartitionWith -         -- * Indexing-       , at-       , unsafeAt-       , elemIndex-       , elemIndices-       , findIndex-       , findIndices+      -- * Indexing+    , at+    , unsafeAt+    , elemIndex+    , elemIndices+    , findIndex+    , findIndices -         -- * Zipping and unzipping-       , zip-       , zip3-       , zipWith-       , zipWith3-       , unzip-       , unzip3+      -- * Zipping and unzipping+    , zip+    , zip3+    , zipWith+    , zipWith3+    , unzip+    , unzip3 -         -- * Sets-         -- $sets-       , nub-       , nubBy-       , delete-       , deleteBy-       , deleteFirstsBy-       , diff-       , union-       , unionBy-       , intersect-       , intersectBy+      -- * Sets+      -- $sets+    , nub+    , nubBy+    , ordNub+    , delete+    , deleteBy+    , deleteFirstsBy+    , diff+    , union+    , unionBy+    , intersect+    , intersectBy -         -- * Ordered slists-       , sort-       , sortBy-       , sortOn-       , insert-       , insertBy+      -- * Ordered slists+    , sort+    , sortBy+    , sortOn+    , sortWith+    , insert+    , insertBy -        -- * Generic functions-       , genericLength-       , genericTake-       , genericDrop-       , genericSplitAt-       , genericAt-       , genericUnsafeAt-       , genericReplicate-       ) where+     -- * Generic functions+    , genericLength+    , genericTake+    , genericDrop+    , genericSplitAt+    , genericAt+    , genericUnsafeAt+    , genericReplicate -import Control.Applicative (Alternative (empty, (<|>)), liftA2)+         -- * Maybe+    , maybeToSlist+    , slistToMaybe+    , catMaybes+    , mapMaybe+    , slistWith++      -- * Containers+      -- ** Map+    , mapToVals+    , mapToKeys+    , mapToPairs++      -- ** Set+    , setToSlist++    ) where+ import Data.Bifunctor (bimap, first, second)+import Data.Either (partitionEithers)+import Data.Foldable (foldl') #if ( __GLASGOW_HASKELL__ == 802 ) import Data.Semigroup (Semigroup (..)) #endif+import GHC.Exts (fromListN) import Prelude hiding (break, concat, concatMap, cycle, drop, dropWhile, filter, head, init,                 iterate, last, lookup, map, repeat, replicate, reverse, scanl, scanl1, scanr,                 scanr1, span, splitAt, tail, take, takeWhile, unzip, unzip3, zip, zip3, zipWith,                 zipWith3) +import Slist.Containers (mapToKeys, mapToPairs, mapToVals, setToSlist)+import Slist.Maybe (catMaybes, mapMaybe, maybeToSlist, slistToMaybe, slistWith) import Slist.Size (Size (..), sizes)+import Slist.Type (Slist (..), cons, infiniteSlist, isEmpty, len, map, one, size, slist) -import qualified Data.Foldable as F (Foldable (..)) import qualified Data.List as L-import qualified GHC.Exts as L (IsList (..))+import qualified Data.Set as Set+import qualified GHC.Exts as Exts import qualified Prelude as P -{- | Data type that represents sized list.-Size can be both finite or infinite, it is established using-'Size' data type.--}-data Slist a = Slist-    { sList :: [a]-    , sSize :: Size-    } deriving stock (Show, Read) -{- | Equality of sized lists is checked more efficiently-due to the fact that the check on the list sizes can be-done first for the constant time.--}-instance (Eq a) => Eq (Slist a) where-    (Slist l1 s1) == (Slist l2 s2) = s1 == s2 && l1 == l2-    {-# INLINE (==) #-}---- | Lexicographical comparison of the lists.-instance (Ord a) => Ord (Slist a) where-    compare (Slist l1 _) (Slist l2 _) = compare l1 l2-    {-# INLINE compare #-}--{- | List appending. Use '<>' for 'Slist' concatenation instead of-'L.++' operator that is common in ordinary list concatenations.--}-instance Semigroup (Slist a) where-    (<>) :: Slist a -> Slist a -> Slist a-    (Slist l1 s1) <> (Slist l2 s2) = Slist (l1 <> l2) (s1 + s2)-    {-# INLINE (<>) #-}--instance Monoid (Slist a) where-    mempty :: Slist a-    mempty = Slist [] 0-    {-# INLINE mempty #-}--    mappend :: Slist a -> Slist a -> Slist a-    mappend = (<>)-    {-# INLINE mappend #-}--    mconcat :: [Slist a] -> Slist a-    mconcat ls = let (l, s) = foldr f ([], 0) ls in Slist l s-      where-        -- foldr :: (a -> ([a], Size) -> ([a], Size)) -> ([a], Size) -> [Slist a] -> ([a], Size)-        f :: Slist a -> ([a], Size) -> ([a], Size)-        f (Slist l s) (xL, !xS) = (l ++ xL, s + xS)-    {-# INLINE mconcat #-}--instance Functor Slist where-    fmap :: (a -> b) -> Slist a -> Slist b-    fmap = map-    {-# INLINE fmap #-}--instance Applicative Slist where-    pure :: a -> Slist a-    pure = one-    {-# INLINE pure #-}--    (<*>) :: Slist (a -> b) -> Slist a -> Slist b-    fsl <*> sl = Slist-        { sList = sList fsl <*> sList sl-        , sSize = sSize fsl  *  sSize sl-        }-    {-# INLINE (<*>) #-}--    liftA2 :: (a -> b -> c) -> Slist a -> Slist b -> Slist c-    liftA2 f sla slb = Slist-        { sList = liftA2 f (sList sla) (sList slb)-        , sSize = sSize sla * sSize slb-        }-    {-# INLINE liftA2 #-}--instance Alternative Slist where-    empty :: Slist a-    empty = mempty-    {-# INLINE empty #-}--    (<|>) :: Slist a -> Slist a -> Slist a-    (<|>) = (<>)-    {-# INLINE (<|>) #-}--instance Monad Slist where-    return :: a -> Slist a-    return = pure-    {-# INLINE return #-}--    (>>=) :: Slist a -> (a -> Slist b) -> Slist b-    sl >>= f = mconcat $ P.map f $ sList sl-    {-# INLINE (>>=) #-}--{- | Efficient implementation of 'sum' and 'product' functions.-'length' returns 'Int's 'maxBound' on infinite lists.--}-instance Foldable Slist where-    foldMap :: (Monoid m) => (a -> m) -> Slist a -> m-    foldMap f = foldMap f . sList-    {-# INLINE foldMap #-}--    foldr :: (a -> b -> b) -> b -> Slist a -> b-    foldr f b = foldr f b . sList-    {-# INLINE foldr #-}--    -- | Is the element in the structure?-    elem :: (Eq a) => a -> Slist a -> Bool-    elem a = elem a . sList-    {-# INLINE elem #-}--    maximum :: (Ord a) => Slist a -> a-    maximum = maximum . sList-    {-# INLINE maximum #-}--    minimum :: (Ord a) => Slist a -> a-    minimum = minimum . sList-    {-# INLINE minimum #-}--    sum :: (Num a) => Slist a -> a-    sum = F.foldl' (+) 0 . sList-    {-# INLINE sum #-}--    product :: (Num a) => Slist a -> a-    product = F.foldl' (*) 1 . sList-    {-# INLINE product #-}--    null :: Slist a -> Bool-    null = isEmpty-    {-# INLINE null #-}--    length :: Slist a -> Int-    length = len-    {-# INLINE length #-}--    toList :: Slist a -> [a]-    toList = sList-    {-# INLINE toList #-}--instance Traversable Slist where-    traverse :: (Applicative f) => (a -> f b) -> Slist a -> f (Slist b)-    traverse f (Slist l s) = (`Slist` s) <$> traverse f l-    {-# INLINE traverse #-}--instance L.IsList (Slist a) where-    type (Item (Slist a)) = a-    fromList :: [a] -> Slist a-    fromList = slist-    {-# INLINE fromList #-}--    toList :: Slist a -> [a]-    toList = sList-    {-# INLINE toList #-}--    fromListN :: Int -> [a] -> Slist a-    fromListN n l = Slist l $ Size n-    {-# INLINE fromListN #-}--{- | @O(n)@. Constructs 'Slist' from the given list.-->>> slist [1..5]-Slist {sList = [1,2,3,4,5], sSize = Size 5}--/Note:/ works with finite lists. Use 'infiniteSlist'-to construct infinite lists.--}-slist :: [a] -> Slist a-slist l = Slist l (Size $ length l)-{-# INLINE slist #-}--{- | @O(1)@. Constructs 'Slist' from the given list.--@->> infiniteSlist [1..]-Slist {sList = [1..], sSize = Infinity}-@--/Note:/ works with infinite lists. Use 'slist'-to construct finite lists.--}-infiniteSlist :: [a] -> Slist a-infiniteSlist l = Slist l Infinity-{-# INLINE infiniteSlist #-}--{- | @O(1)@. Creates 'Slist' with a single element.-The size of such 'Slist' is always equals to @Size 1@.-->>> one "and only"-Slist {sList = ["and only"], sSize = Size 1}---}-one :: a -> Slist a-one a = Slist [a] 1-{-# INLINE one #-}- {- | Returns an infinite slist of repeated applications of the given function to the start element: @@ -526,46 +373,7 @@ -- Basic functions ---------------------------------------------------------------------------- -{- | @O(1)@. Returns the length of a structure as an 'Int'.-On infinite lists returns the 'Int's 'maxBound'. ->>> len $ one 42-1->>> len $ slist [1..3]-3->>> len $ infiniteSlist [1..]-9223372036854775807--}-len :: Slist a -> Int-len Slist{..} = case sSize of-    Infinity -> maxBound-    Size n   -> n-{-# INLINE len #-}--{- | @O(1)@. Returns the 'Size' of the slist.-->>> size $ slist "Hello World!"-Size 12->>> size $ infiniteSlist [1..]-Infinity--}-size :: Slist a -> Size-size = sSize-{-# INLINE size #-}--{- | @O(1)@. Checks if 'Slist' is empty-->>> isEmpty mempty-True->>> isEmpty $ slist []-True->>> isEmpty $ slist "Not Empty"-False--}-isEmpty :: Slist a -> Bool-isEmpty = (== 0) . size-{-# INLINE isEmpty #-}- {- | @O(1)@. Extracts the first element of a slist. Uses not total 'L.head' function, so use wisely. @@ -671,6 +479,44 @@     _        -> Slist (P.init sList) (sSize - 1) {-# INLINE init #-} +{- | Strict version of the 'Slist' appending operator '<>'.++@since 0.2.0.0+-}+append' :: Slist a -> Slist a -> Slist a+append' sl1 sl2+    | sSize sl1 == 0 = sl2+    | sSize sl2 == 0 = sl1+    | otherwise = let !newSize = sSize sl1 + sSize sl2 in Slist+        { sList = sList sl1 <> sList sl2+        , sSize = newSize+        }++{- | @O(1)@. Strict version of the 'cons' function+(in terms of the size evaluation).++The following property is preserved:++@+  'size' ('cons'' x xs) == 'size' xs + 1+@++Examples:++>>> cons' 'a' $ one 'b'+Slist {sList = "ab", sSize = Size 2}++@+>> __cons' 0 $ 'infiniteSlist' [1..]__+Slist {sList = [0..], sSize = 'Infinity'}+@++@since 0.2.0.0+-}+cons' :: a -> Slist a -> Slist a+cons' x (Slist xs !s) = let !newSize = s + 1 in Slist (x:xs) newSize+{-# INLINE cons' #-}+ {- | @O(1)@. Decomposes a slist into its head and tail. If the slist is empty, returns 'Nothing'. @@ -693,16 +539,7 @@ -- Transformations ---------------------------------------------------------------------------- -{- | @O(n)@. Applies the given function to each element of the slist. -> map f (slist [x1, x2, ..., xn])     == slist [f x1, f x2, ..., f xn]-> map f (infiniteSlist [x1, x2, ...]) == infiniteSlist [f x1, f x2, ...]---}-map :: (a -> b) -> Slist a -> Slist b-map f Slist{..} = Slist (P.map f sList) sSize-{-# INLINE map #-}- {- | @O(n)@. Returns the elements of the slist in reverse order.  >>> reverse $ slist "Hello"@@ -853,7 +690,7 @@ Slist {sList = [1,2,3,4,5,6,7,8,9,10], sSize = Size 10}  @->> __ concat $ slist [slist [1,2], 'infiniteSlist' [3..]]__+>> __concat $ slist [slist [1,2], 'infiniteSlist' [3..]]__ Slist {sList = [1..], sSize = 'Infinity'} @ -}@@ -861,6 +698,24 @@ concat = foldr (<>) mempty {-# INLINE concat #-} +{- | \( O(\sum n_i) \) The concatenation of all the elements of a container of slists.++The strict version of 'concat'.++>>> concat' [slist [1,2], slist [3..5], slist [6..10]]+Slist {sList = [1,2,3,4,5,6,7,8,9,10], sSize = Size 10}++@+>> __concat' $ slist [slist [1,2], 'infiniteSlist' [3..]]__+Slist {sList = [1..], sSize = 'Infinity'}+@++@since 0.2.0.0+-}+concat' :: Foldable t => t (Slist a) -> Slist a+concat' = foldl' append' mempty+{-# INLINE concat' #-}+ {- | Maps a function over all the elements of a container and concatenates the resulting slists. @@ -871,6 +726,20 @@ concatMap = foldMap {-# INLINE concatMap #-} +{- | Maps a function over all the elements of a container and concatenates the+resulting slists.++Strict version of 'concatMap'.++>>> concatMap' one "abc"+Slist {sList = "abc", sSize = Size 3}++@since 0.2.0.0+-}+concatMap' :: Foldable t => (a -> Slist b) -> t a -> Slist b+concatMap' f = foldl' (\acc x -> acc `append'` f x) mempty+{-# INLINE concatMap' #-}+ ---------------------------------------------------------------------------- -- Building lists ----------------------------------------------------------------------------@@ -1146,6 +1015,68 @@ break p = span (not . p) {-# INLINE break #-} +{- | @O(n)@. Splits a 'Slist' into components of the given length. The last+element may be shorter than the other chunks, depending on the length of the+input.++>>> chunksOf 3 $ slist [0..7]+Slist {sList = [Slist {sList = [0,1,2], sSize = Size 3},Slist {sList = [3,4,5], sSize = Size 3},Slist {sList = [6,7], sSize = Size 2}], sSize = Size 3}+>>> chunksOf 0 $ slist [0..10]+Slist {sList = [], sSize = Size 0}+>>> chunksOf (-13) $ slist [0..10]+Slist {sList = [], sSize = Size 0}+>>> chunksOf 100 $ slist [1,2,3]+Slist {sList = [Slist {sList = [1,2,3], sSize = Size 3}], sSize = Size 1}++>>> take 2 $ chunksOf 3 $ infiniteSlist [1..]+Slist {sList = [Slist {sList = [1,2,3], sSize = Size 3},Slist {sList = [4,5,6], sSize = Size 3}], sSize = Size 2}++@since 0.2.0.0+-}+chunksOf :: Int -> Slist a -> Slist (Slist a)+chunksOf i sl@Slist{..}+    | i <= 0 = mempty+    | sSize == Infinity = Slist (P.map (fromListN i) $ listChunksOf i sList) Infinity+    | otherwise = go sl+  where+    go :: Slist a -> Slist (Slist a)+    go x@(Slist _ s)+        | Size i >= s = one x+        | otherwise =+            let (chunk, rest) = splitAt i x+            in cons chunk $ go rest+{-# INLINE chunksOf #-}++{- | @O(n)@. Splits a list into components of the given length. The last+element may be shorter than the other chunks, depending on the length of the+input.++>>> listChunksOf 3 [0..7]+[[0,1,2],[3,4,5],[6,7]]+>>> listChunksOf 0 [0..10]+[]+>>> listChunksOf (-13) [0..10]+[]+>>> listChunksOf 100 [1,2,3]+[[1,2,3]]++>>> P.take 2 $ listChunksOf 3 [1..]+[[1,2,3],[4,5,6]]++@since 0.2.0.0+-}+listChunksOf :: Int -> [a] -> [[a]]+listChunksOf i l+    | i <= 0 = mempty+    | otherwise = go l+  where+    go :: [a] -> [[a]]+    go [] = []+    go x =+        let (chunk, rest) = P.splitAt i x+        in chunk : go rest+{-# INLINE listChunksOf #-}+ {- | @O(m)@. Drops the given prefix from a list. It returns 'Nothing' if the slist did not start with the given prefix, or 'Just' the slist after the prefix, if it does.@@ -1473,6 +1404,43 @@         else second (x:) $ go n xs {-# INLINE partition #-} +{- | @O(n)@.+Returns the pair of slists of elements resulting to 'Left' and resulting to+'Right' by applying the given function.++>>> onEven x = if even x then Right x else Left ("Oops: " ++ show x)+>>> partitionWith onEven $ slist [1..5]+(Slist {sList = ["Oops: 1","Oops: 3","Oops: 5"], sSize = Size 3},Slist {sList = [2,4], sSize = Size 2})++@since 0.2.0.0+-}+partitionWith :: forall a b c . (a -> Either b c) -> Slist a -> (Slist b, Slist c)+partitionWith f (Slist l Infinity) = bimap infiniteSlist infiniteSlist $ listPartitionWith f l+partitionWith f Slist{..} = let (s1, l1, l2) = go 0 sList in+    (Slist l1 $ Size s1, Slist l2 $ sSize - Size s1)+  where+    go :: Int -> [a] -> (Int, [b], [c])+    go !n [] = (n, [], [])+    go n (x:xs) = case f x of+        Left  b -> first  (b:) $ go (n + 1) xs+        Right c -> second (c:) $ go n xs+{-# INLINE partitionWith #-}++{- | @O(n)@.+Returns the pair of lists of elements resulting to 'Left' and resulting to+'Right' by applying the given function.+++>>> onEven x = if even x then Right x else Left ("Oops: " ++ show x)+>>> listPartitionWith onEven [1..5]+(["Oops: 1","Oops: 3","Oops: 5"],[2,4])++@since 0.2.0.0+-}+listPartitionWith :: forall a b c . (a -> Either b c) -> [a] -> ([b], [c])+listPartitionWith f = partitionEithers . L.map f+{-# INLINE listPartitionWith #-}+ ---------------------------------------------------------------------------- -- Indexing ----------------------------------------------------------------------------@@ -1715,6 +1683,29 @@         else go (n + 1) (res ++ [x]) xs {-# INLINE nubBy #-} +{- | Removes duplicate elements from a slist, keeping only the first occurance of+the element.++Like 'nub' but runs in \( O(n \log n) \)  time and requires 'Ord'.++>>> ordNub $ slist [3, 3, 3, 2, 2, -1, 1]+Slist {sList = [3,2,-1,1], sSize = Size 4}++-}+ordNub :: forall a . (Ord a) => Slist a -> Slist a+ordNub sl = let (s, l) = go 0 Set.empty (sList sl) in Slist+    { sList = l+    , sSize = Size s+    }+  where+    go :: Int -> Set.Set a -> [a] -> (Int, [a])+    go !i _ []     = (i, [])+    go i s (x:xs) =+      if x `Set.member` s+      then go i s xs+      else  second (x:) $ go (i + 1) (Set.insert x s) xs+{-# INLINEABLE ordNub #-}+ {- | @O(n)@. Removes the first occurrence of the given element from its slist argument. @@ -1886,6 +1877,22 @@ sortOn :: Ord b => (a -> b) -> Slist a -> Slist a sortOn f Slist{..} = Slist (L.sortOn f sList) sSize {-# INLINE sortOn #-}++{- | @O(n log n)@.+Sorts a list by comparing the results of a key function applied to each+element.++Elements are arranged from lowest to highest, keeping duplicates in+the order they appeared in the input.++>>> sortWith fst $ slist [(2, "world"), (4, "!"), (1, "Hello")]+Slist {sList = [(1,"Hello"),(2,"world"),(4,"!")], sSize = Size 3}++@since 0.2.0.0+-}+sortWith :: Ord b => (a -> b) -> Slist a -> Slist a+sortWith f Slist{..} = Slist (Exts.sortWith f sList) sSize+{-# INLINE sortWith #-}  {- | @O(n)@. Takes an element and a slist and inserts the element into the slist

@@ -0,0 +1,79 @@+{- |+Copyright:  (c) 2021 Kowainik+SPDX-License-Identifier: MPL-2.0+Maintainer:  Kowainik <xrom.xkov@gmail.com>+Stability:   Stable+Portability: Portable++Useful combinators to work with the data structures from @containers@ package+and 'Slist' together.++@since 0.2.0.0+-}+module Slist.Containers+    ( -- * Map+      mapToVals+    , mapToKeys+    , mapToPairs++      -- * Set+    , setToSlist+    ) where++import Data.Map.Strict (Map)+import Data.Set (Set)++import Slist.Size (Size (..))+import Slist.Type (Slist (..))++import qualified Data.Map.Strict as Map+import qualified Data.Set as Set+++{- | @O(n)@.+Returns a 'Slist' of all values of the map in the ascending order of their keys.++@since 0.2.0.0+-}+mapToVals :: Map k v -> Slist v+mapToVals m = Slist+    { sList = Map.elems m+    , sSize = Size $ Map.size m+    }+{-# INLINE mapToVals #-}++{- | @O(n)@.+Returns a 'Slist' of all keys of the map in the ascending order.++@since 0.2.0.0+-}+mapToKeys :: Map k v -> Slist k+mapToKeys m = Slist+    { sList = Map.keys m+    , sSize = Size $ Map.size m+    }+{-# INLINE mapToKeys #-}++{- | @O(n)@.+Returns a 'Slist' of all key-value pairs of the map in the ascending order of their keys.++@since 0.2.0.0+-}+mapToPairs :: Map k v -> Slist (k, v)+mapToPairs m = Slist+    { sList = Map.toAscList m+    , sSize = Size $ Map.size m+    }+{-# INLINE mapToPairs #-}++{- | @O(n)@.+Returns a 'Slist' of all elements of the set in the ascending order.++@since 0.2.0.0+-}+setToSlist :: Set a -> Slist a+setToSlist s = Slist+    { sList = Set.elems s+    , sSize = Size $ Set.size s+    }+{-# INLINE setToSlist #-}

@@ -0,0 +1,149 @@+{-# LANGUAGE BangPatterns #-}++{- |+Copyright:  (c) 2021 Kowainik+SPDX-License-Identifier: MPL-2.0+Maintainer:  Kowainik <xrom.xkov@gmail.com>+Stability:   Stable+Portability: Portable++Useful 'Maybe' combinators to work with the 'Maybe' data type and 'Slist'+together.++@since 0.2.0.0+-}+module Slist.Maybe+    ( maybeToSlist+    , slistToMaybe+    , catMaybes+    , mapMaybe+    , slistWith+    ) where++import Data.Bifunctor (second)++import Slist.Size (Size (..))+import Slist.Type (Slist (..), cons, one)++import qualified Data.Maybe as M+++{- | Returns an empty list when given 'Nothing' or a singleton list when given+'Just'.++>>> maybeToSlist (Just 42)+Slist {sList = [42], sSize = Size 1}+>>> maybeToSlist Nothing+Slist {sList = [], sSize = Size 0}++@since 0.2.0.0+-}+maybeToSlist :: Maybe a -> Slist a+maybeToSlist = maybe mempty one+{-# INLINE maybeToSlist #-}++{- | Returns 'Nothing' on an empty list or @'Just' a@ where @a@ is the first+element of the slist.++==== __Examples__++Basic usage:++>>> slistToMaybe mempty+Nothing++>>> slistToMaybe (one 42)+Just 42++>>> slistToMaybe (cons 1 $ cons 2 $ one 3)+Just 1++__Laws__ :++@+slistToMaybe . maybeToList ≡ id+@++Reverse is right only on singleton/empty lists++@+maybeToList . slistToMaybe {empty, singleton slist} ≡ {empty, singleton slist}+@++@since 0.2.0.0+-}+slistToMaybe :: Slist a -> Maybe a+slistToMaybe = foldr (const . Just) Nothing+{-# INLINE slistToMaybe #-}+-- We define listToMaybe using foldr so that it can fuse via the foldr/build+-- rule. See #14387+++{- | Takes a slist of 'Maybe's and returns a slist of all the 'Just' values.++>>> catMaybes (cons (Just 1) $ cons Nothing $ one $ Just 3)+Slist {sList = [1,3], sSize = Size 2}++@since 0.2.0.0+-}+catMaybes :: Slist (Maybe a) -> Slist a+catMaybes = mapMaybe id+{-# INLINE catMaybes #-}++{- | The 'Maybe' version of 'map' which can throw out elements.++If appliying the given function returns 'Nothing', no element is added on to the+result list. If it is @'Just' b@, then @b@ is included in the result list.++>>> maybeEven x = if even x then Just x else Nothing+>>> s = cons 1 $ cons 2 $ one 3++>>> mapMaybe maybeEven s+Slist {sList = [2], sSize = Size 1}++If we map the 'Just' constructor, the entire list should be returned:++>>> mapMaybe Just s+Slist {sList = [1,2,3], sSize = Size 3}++@since 0.2.0.0+-}+mapMaybe :: forall b a . (a -> Maybe b) -> Slist a -> Slist b+mapMaybe _ (Slist [] _) = mempty+mapMaybe f (Slist xs Infinity) = Slist (M.mapMaybe f xs) Infinity+mapMaybe f (Slist (x:xs) n) = case f x of+    Nothing -> rest+    Just r  -> cons r rest+  where+    rest :: Slist b+    rest = mapMaybe f (Slist xs (n - 1))+{-# NOINLINE [1] mapMaybe #-}++{- | Similar to 'mapMaybe' but works with the ordinary list as the input:++>>> maybeEven x = if even x then Just x else Nothing++>>> slistWith maybeEven [1,2,3]+Slist {sList = [2], sSize = Size 1}++@since 0.2.0.0+-}+slistWith :: forall b a . (a -> Maybe b) -> [a] -> Slist b+slistWith f l = let (n, sl) = go 0 l in Slist sl (Size n)+  where+    go :: Int -> [a] -> (Int, [b])+    go !accSize [] = (accSize, [])+    go !accSize (x:xs) = case f x of+        Nothing -> go accSize xs+        Just r  -> second (r:) $ go (accSize + 1) xs++-- {-# RULES+-- "mapMaybe"     [~1] forall f xs. mapMaybe f xs+--                     = build (\c n -> foldr (mapMaybeFB c f) n xs)+-- "mapMaybeList" [1]  forall f. foldr (mapMaybeFB (:) f) [] = mapMaybe f+--   #-}+-- {-# INLINE [0] mapMaybeFB #-} -- See Note [Inline FB functions] in GHC.List+-- mapMaybeFB :: (b -> r -> r) -> (a -> Maybe b) -> a -> r -> r+-- mapMaybeFB cons f x next = case f x of+--   Nothing -> next+--   Just r -> cons r next

@@ -1,7 +1,10 @@ {- | Copyright:  (c) 2019-2020 Veronika Romashkina-License:    MPL-2.0-Maintainer: Veronika Romashkina <vrom911@gmail.com>+            (c) 2020-2021 Kowainik+SPDX-License-Identifier: MPL-2.0+Maintainer: Kowainik <xrom.xkov@gmail.com>+Stability:   Stable+Portability: Portable  Lists size representation. -}@@ -36,15 +39,28 @@  {- | Efficient implementations of numeric operations with 'Size's. -Any operations with 'Infinity' size results into 'Infinity'.+Any operations with 'Infinity' size results into 'Infinity'. When+'Infinity' is a left argument, all operations are also+right-lazy. Operations are checked for integral overflow under the+assumption that all values inside 'Size' are positive. -TODO: checking on overflow when '+' or '*' sizes.+>>> Size 10 + Size 5+Size 15+>>> Size 5 * Infinity+Infinity+>>> Infinity + error "Unevaluated size"+Infinity+>>> Size (10 ^ 10) * Size (10 ^ 10)+Infinity -} instance Num Size where     (+) :: Size -> Size -> Size     Infinity + _ = Infinity     _ + Infinity = Infinity-    (Size x) + (Size y) = Size $ x + y+    (Size x) + (Size y) =+        if x + y < x  -- integer overflow+        then Infinity+        else Size $ x + y     {-# INLINE (+) #-}      (-) :: Size -> Size -> Size@@ -56,7 +72,13 @@     (*) :: Size -> Size -> Size     Infinity * _ = Infinity     _ * Infinity = Infinity-    (Size x) * (Size y) = Size (x * y)+    (Size x) * (Size y)+        | x == 0 || y == 0 = 0+        | otherwise =+            let result = x * y in+            if x == result `div` y+            then Size (x * y)+            else Infinity  -- multiplication overflow     {-# INLINE (*) #-}      abs :: Size -> Size

@@ -0,0 +1,309 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP          #-}+{-# LANGUAGE TypeFamilies #-}++{- |+Copyright:  (c) 2021 Kowainik+SPDX-License-Identifier: MPL-2.0+Maintainer:  Kowainik <xrom.xkov@gmail.com>+Stability:   Stable+Portability: Portable++The main 'Slist' data types and instances. Provides smart constructors and a few+basic functions.+-}+module Slist.Type+    ( Slist (..)+      -- ** Smart constructors+    , slist+    , infiniteSlist+    , one+      -- * Basic functions+    , len+    , size+    , isEmpty+    , cons+    , map+    ) where++import Control.Applicative (Alternative (empty, (<|>)), liftA2)+#if ( __GLASGOW_HASKELL__ == 802 )+import Data.Semigroup (Semigroup (..))+#endif+import Prelude hiding (map)++import Slist.Size (Size (..))++import qualified Data.Foldable as F (Foldable (..))+import qualified GHC.Exts as L (IsList (..))+import qualified Prelude as P+++{- | Data type that represents sized list.+Size can be both finite or infinite, it is established using+'Size' data type.+-}+data Slist a = Slist+    { sList :: [a]+    , sSize :: Size+    } deriving stock (Show, Read)++{- | Equality of sized lists is checked more efficiently+due to the fact that the check on the list sizes can be+done first for the constant time.+-}+instance (Eq a) => Eq (Slist a) where+    (Slist l1 s1) == (Slist l2 s2) = s1 == s2 && l1 == l2+    {-# INLINE (==) #-}++-- | Lexicographical comparison of the lists.+instance (Ord a) => Ord (Slist a) where+    compare (Slist l1 _) (Slist l2 _) = compare l1 l2+    {-# INLINE compare #-}++{- | List appending. Use '<>' for 'Slist' concatenation instead of+'L.++' operator that is common in ordinary list concatenations.+-}+instance Semigroup (Slist a) where+    (<>) :: Slist a -> Slist a -> Slist a+    (Slist l1 s1) <> (Slist l2 s2) = Slist (l1 <> l2) (s1 + s2)+    {-# INLINE (<>) #-}++instance Monoid (Slist a) where+    mempty :: Slist a+    mempty = Slist [] 0+    {-# INLINE mempty #-}++    mappend :: Slist a -> Slist a -> Slist a+    mappend = (<>)+    {-# INLINE mappend #-}++    mconcat :: [Slist a] -> Slist a+    mconcat ls = let (l, s) = foldr f ([], 0) ls in Slist l s+      where+        -- foldr :: (a -> ([a], Size) -> ([a], Size)) -> ([a], Size) -> [Slist a] -> ([a], Size)+        f :: Slist a -> ([a], Size) -> ([a], Size)+        f (Slist l s) (xL, !xS) = (l ++ xL, s + xS)+    {-# INLINE mconcat #-}++instance Functor Slist where+    fmap :: (a -> b) -> Slist a -> Slist b+    fmap = map+    {-# INLINE fmap #-}++instance Applicative Slist where+    pure :: a -> Slist a+    pure = one+    {-# INLINE pure #-}++    (<*>) :: Slist (a -> b) -> Slist a -> Slist b+    fsl <*> sl = Slist+        { sList = sList fsl <*> sList sl+        , sSize = sSize fsl  *  sSize sl+        }+    {-# INLINE (<*>) #-}++    liftA2 :: (a -> b -> c) -> Slist a -> Slist b -> Slist c+    liftA2 f sla slb = Slist+        { sList = liftA2 f (sList sla) (sList slb)+        , sSize = sSize sla * sSize slb+        }+    {-# INLINE liftA2 #-}++instance Alternative Slist where+    empty :: Slist a+    empty = mempty+    {-# INLINE empty #-}++    (<|>) :: Slist a -> Slist a -> Slist a+    (<|>) = (<>)+    {-# INLINE (<|>) #-}++instance Monad Slist where+    return :: a -> Slist a+    return = pure+    {-# INLINE return #-}++    (>>=) :: Slist a -> (a -> Slist b) -> Slist b+    sl >>= f = mconcat $ P.map f $ sList sl+    {-# INLINE (>>=) #-}++{- | Efficient implementation of 'sum' and 'product' functions.+'length' returns 'Int's 'maxBound' on infinite lists.+-}+instance Foldable Slist where+    foldMap :: (Monoid m) => (a -> m) -> Slist a -> m+    foldMap f = foldMap f . sList+    {-# INLINE foldMap #-}++    foldr :: (a -> b -> b) -> b -> Slist a -> b+    foldr f b = foldr f b . sList+    {-# INLINE foldr #-}++    -- | Is the element in the structure?+    elem :: (Eq a) => a -> Slist a -> Bool+    elem a = elem a . sList+    {-# INLINE elem #-}++    maximum :: (Ord a) => Slist a -> a+    maximum = maximum . sList+    {-# INLINE maximum #-}++    minimum :: (Ord a) => Slist a -> a+    minimum = minimum . sList+    {-# INLINE minimum #-}++    sum :: (Num a) => Slist a -> a+    sum = F.foldl' (+) 0 . sList+    {-# INLINE sum #-}++    product :: (Num a) => Slist a -> a+    product = F.foldl' (*) 1 . sList+    {-# INLINE product #-}++    null :: Slist a -> Bool+    null = isEmpty+    {-# INLINE null #-}++    length :: Slist a -> Int+    length = len+    {-# INLINE length #-}++    toList :: Slist a -> [a]+    toList = sList+    {-# INLINE toList #-}++instance Traversable Slist where+    traverse :: (Applicative f) => (a -> f b) -> Slist a -> f (Slist b)+    traverse f (Slist l s) = (`Slist` s) <$> traverse f l+    {-# INLINE traverse #-}++instance L.IsList (Slist a) where+    type (Item (Slist a)) = a+    fromList :: [a] -> Slist a+    fromList = slist+    {-# INLINE fromList #-}++    toList :: Slist a -> [a]+    toList = sList+    {-# INLINE toList #-}++    fromListN :: Int -> [a] -> Slist a+    fromListN n l = Slist l $ Size n+    {-# INLINE fromListN #-}++{- | @O(n)@. Constructs 'Slist' from the given list.++>>> slist [1..5]+Slist {sList = [1,2,3,4,5], sSize = Size 5}++/Note:/ works with finite lists. Use 'infiniteSlist'+to construct infinite lists.+-}+slist :: [a] -> Slist a+slist l = Slist l (Size $ length l)+{-# INLINE slist #-}++{- | @O(1)@. Constructs 'Slist' from the given list.++@+>> infiniteSlist [1..]+Slist {sList = [1..], sSize = Infinity}+@++/Note:/ works with infinite lists. Use 'slist'+to construct finite lists.+-}+infiniteSlist :: [a] -> Slist a+infiniteSlist l = Slist l Infinity+{-# INLINE infiniteSlist #-}++{- | @O(1)@. Creates 'Slist' with a single element.+The size of such 'Slist' is always equals to @Size 1@.++>>> one "and only"+Slist {sList = ["and only"], sSize = Size 1}++-}+one :: a -> Slist a+one a = Slist [a] 1+{-# INLINE one #-}++----------------------------------------------------------------------------+-- Basic functions+----------------------------------------------------------------------------+++{- | @O(1)@. Returns the length of a structure as an 'Int'.+On infinite lists returns the 'Int's 'maxBound'.++>>> len $ one 42+1+>>> len $ slist [1..3]+3+>>> len $ infiniteSlist [1..]+9223372036854775807+-}+len :: Slist a -> Int+len Slist{..} = case sSize of+    Infinity -> maxBound+    Size n   -> n+{-# INLINE len #-}++{- | @O(1)@. Returns the 'Size' of the slist.++>>> size $ slist "Hello World!"+Size 12+>>> size $ infiniteSlist [1..]+Infinity+-}+size :: Slist a -> Size+size = sSize+{-# INLINE size #-}++{- | @O(1)@. Checks if 'Slist' is empty++>>> isEmpty mempty+True+>>> isEmpty $ slist []+True+>>> isEmpty $ slist "Not Empty"+False+-}+isEmpty :: Slist a -> Bool+isEmpty = (== 0) . size+{-# INLINE isEmpty #-}++{- | @O(1)@. 'cons' is 'Slist' analogue to ':' for lists.+It adds the given element to the beginning of the list.++The following property is preserved:++@+  'size' ('cons' x xs) == 'size' xs + 1+@++Examples:++>>> cons 'a' $ one 'b'+Slist {sList = "ab", sSize = Size 2}++@+>> __'cons' 0 $ 'infiniteSlist' [1..]__+Slist {sList = [0..], sSize = 'Infinity'}+@+-}+cons :: a -> Slist a -> Slist a+cons x (Slist xs s) = Slist (x:xs) $ s + 1+{-# INLINE cons #-}+++{- | @O(n)@. Applies the given function to each element of the slist.++> map f (slist [x1, x2, ..., xn])     == slist [f x1, f x2, ..., f xn]+> map f (infiniteSlist [x1, x2, ...]) == infiniteSlist [f x1, f x2, ...]++-}+map :: (a -> b) -> Slist a -> Slist b+map f Slist{..} = Slist (P.map f sList) sSize+{-# INLINE map #-}

@@ -0,0 +1,9 @@+module Main (main) where++import Test.Hspec (hspec)++import Test.Slist.Size (sizeSpec)+++main :: IO ()+main = hspec sizeSpec

@@ -0,0 +1,95 @@+{- HLINT ignore "Redundant fromInteger" -}+{- HLINT ignore "Reduce duplication" -}++module Test.Slist.Size+    ( sizeSpec+    ) where++import Hedgehog (Gen, PropertyT, forAll, (===))+import Test.Hspec (Spec, describe, it)+import Test.Hspec.Hedgehog (hedgehog)++import Slist.Size (Size (..))++import qualified Hedgehog.Gen as Gen+import qualified Hedgehog.Range as Range+++type Property = PropertyT IO ()++sizeSpec :: Spec+sizeSpec = describe "Size tests" $+    describe "'Num' laws" $ do+        it "Neutrality of 0 over addition" zeroAdditionNeutrality+        it "Commutativity of (+)" additionCommutativity+        it "Associativity of (+)" additionAssotiavity+        it "Neutrality of 1 over multiplication" oneMultiplicationNeutrality+        it "Commutativity of (*)" multiplicationCommutavity+        it "Associativity of (*)" multiplicationAssociativity+        it "Distributivity of (*) with respect to (+)" distributivity+        it "'abs' and 'signum' correspondence" absSignum++zeroAdditionNeutrality :: Property+zeroAdditionNeutrality = hedgehog $ do+    x <- forAll genSize++    fromInteger 0 + x === x+    x + fromInteger 0 === x++additionCommutativity :: Property+additionCommutativity = hedgehog $ do+    x <- forAll genSize+    y <- forAll genSize++    x + y === y + x++additionAssotiavity :: Property+additionAssotiavity = hedgehog $ do+    x <- forAll genSize+    y <- forAll genSize+    z <- forAll genSize++    (x + y) + z === x + (y + z)++oneMultiplicationNeutrality :: Property+oneMultiplicationNeutrality = hedgehog $ do+    x <- forAll genSize++    fromInteger 1 * x === x+    x * fromInteger 1 === x++multiplicationCommutavity :: Property+multiplicationCommutavity = hedgehog $ do+    x <- forAll genSize+    y <- forAll genSize++    x * y === y * x++multiplicationAssociativity :: Property+multiplicationAssociativity = hedgehog $ do+    x <- forAll genSize+    y <- forAll genSize+    z <- forAll genSize++    (x * y) * z === x * (y * z)++distributivity :: Property+distributivity = hedgehog $ do+    x <- forAll genSize+    y <- forAll genSize+    z <- forAll genSize++    x * (y + z) === (x * y) + (x * z)+    (y + z) * x === (y * x) + (z * x)++absSignum :: Property+absSignum = hedgehog $ do+    x <- forAll genSize++    abs x * signum x === x++genSize :: Gen Size+genSize = Gen.frequency+    [ (1, pure Infinity)+    , (9, Size <$> Gen.int (Range.constant 0 maxBound))+    ]