slist 0.0.0 → 0.1.0.0
raw patch · 6 files changed
+257/−54 lines, 6 filesdep ~base
Dependency ranges changed: base
Files
- CHANGELOG.md +19/−2
- README.md +6/−4
- slist.cabal +23/−38
- src/Slist.hs +207/−9
- src/Slist/Size.hs +1/−1
- test/Doctest.hs +1/−0
CHANGELOG.md view
@@ -3,8 +3,25 @@ `slist` uses [PVP Versioning][1]. The changelog is available [on GitHub][2]. -0.0.0-=====+## 0.1.0.0++* [#13](https://github.com/vrom911/slist/issues/13):+ Support GHC-8.8.1.+* [#16](https://github.com/vrom911/slist/issues/16):+ Use `DerivingStrategies`.+* [#9](https://github.com/vrom911/slist/issues/9):+ Implement `fromRange` function.+ (by @zfnmxt)+* [#6](https://github.com/vrom911/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 os GHC-8.6.3.+* [#6](https://github.com/vrom911/slist/issues/6):+ Build with Stack.++## 0.0.0 * Initially created.
README.md view
@@ -1,8 +1,10 @@ # slist -[](https://hackage.haskell.org/package/slist)+[](https://travis-ci.org/vrom911/slist)+[](https://hackage.haskell.org/package/slist)+[](http://stackage.org/lts/package/slist)+[](http://stackage.org/nightly/package/slist) [](LICENSE)-[](https://travis-ci.org/vrom911/slist) This package introduces sized list data type — `Slist`. The data type has the following shape:@@ -14,7 +16,7 @@ } ``` -As you can see along with the familiar list, it contains `Size` field that+As you can see that along with the familiar list, it contains `Size` field that represents the size of the structure. Slists can be finite or infinite, and this is expressed with `Size`. @@ -41,7 +43,7 @@ |-------------------|-----------------------------------|-----------------------------|----------------------------------------|------------------| | `length` | `O(n)` | <_hangs_> | `O(1)` | `O(1)` | | `safeLast` | `O(n)` | <_hangs_> | `O(n)` | `O(1)` |-| `init` | `O(n)` | <_hangs_> | `O(n)` | `O(1)` |+| `init` | `O(n)` | <_works infinitely_> | `O(n)` | `O(1)` | | `take` | `O(min i n)` | `O(i)` | `0 < i < n`: `O(i)`; otherwise: `O(1)` | `O(i)` | | `at` | `O(min i n)` (run-time exception) | `O(i)` (run-time exception) | `0 < i < n`: `O(i)`; otherwise: `O(1)` | `O(i)` | | `safeStripPrefix` | `O(m)` | `O(m)` (can hang) | `O(m)` | `O(m)` |
slist.cabal view
@@ -1,6 +1,6 @@-cabal-version: 2.0+cabal-version: 2.4 name: slist-version: 0.0.0+version: 0.1.0.0 synopsis: Sized list description: This package implements @Slist@ data structure that stores the size of the list along with the list itself.@@ -17,18 +17,15 @@ , CHANGELOG.md tested-with: GHC == 8.2.2 , GHC == 8.4.4- , GHC == 8.6.3+ , GHC == 8.6.5+ , GHC == 8.8.1 source-repository head type: git location: https://github.com/vrom911/slist.git -library- hs-source-dirs: src- exposed-modules: Slist- Slist.Size-- build-depends: base >= 4.10.1.0 && < 4.13+common common-options+ build-depends: base >= 4.10.1.0 && < 4.14 ghc-options: -Wall -Wincomplete-uni-patterns@@ -37,10 +34,13 @@ -Widentities -Wredundant-constraints -fhide-source-paths+ if impl(ghc >= 8.8.1)+ ghc-options: -Wmissing-deriving-strategies+ -Werror=missing-deriving-strategies - default-language: Haskell2010 default-extensions: ConstraintKinds DeriveGeneric+ DerivingStrategies GeneralizedNewtypeDeriving InstanceSigs KindSignatures@@ -53,48 +53,33 @@ TypeApplications ViewPatterns + default-language: Haskell2010++library+ import: common-options+ hs-source-dirs: src+ exposed-modules: Slist+ Slist.Size+ test-suite slist-test+ import: common-options type: exitcode-stdio-1.0 hs-source-dirs: test main-is: Spec.hs - build-depends: base >= 4.10.1.0 && < 4.13- , slist+ build-depends: slist - ghc-options: -Wall- -threaded+ ghc-options: -threaded -rtsopts -with-rtsopts=-N- -Wincomplete-uni-patterns- -Wincomplete-record-updates- -Wcompat- -Widentities- -Wredundant-constraints- -fhide-source-paths - default-language: Haskell2010- default-extensions: ConstraintKinds- DeriveGeneric- GeneralizedNewtypeDeriving- InstanceSigs- KindSignatures- LambdaCase- OverloadedStrings- RecordWildCards- ScopedTypeVariables- StandaloneDeriving- TupleSections- TypeApplications- ViewPatterns- test-suite slist-doctest+ import: common-options type: exitcode-stdio-1.0 hs-source-dirs: test main-is: Doctest.hs - build-depends: base >= 4.9 && < 5- , doctest+ build-depends: doctest , Glob ghc-options: -threaded- default-language: Haskell2010
src/Slist.hs view
@@ -1,7 +1,10 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE ViewPatterns #-} +{- HLINT ignore "Use mconcat" -}+ {- | Copyright: (c) 2019 vrom911 License: MPL-2.0@@ -86,6 +89,7 @@ , repeat , replicate , cycle+ , fromRange -- * Basic functions , len , size@@ -190,6 +194,15 @@ , sortOn , insert , insertBy++ -- * Generic functions+ , genericLength+ , genericTake+ , genericDrop+ , genericSplitAt+ , genericAt+ , genericUnsafeAt+ , genericReplicate ) where import Control.Applicative (Alternative (empty, (<|>)), liftA2)@@ -216,7 +229,7 @@ data Slist a = Slist { sList :: [a] , sSize :: Size- } deriving (Show, Read)+ } 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@@ -345,7 +358,7 @@ instance Traversable Slist where traverse :: (Applicative f) => (a -> f b) -> Slist a -> f (Slist b)- traverse f (Slist l s) = (\x -> Slist x s) <$> traverse f l+ traverse f (Slist l s) = (`Slist` s) <$> traverse f l {-# INLINE traverse #-} instance L.IsList (Slist a) where@@ -490,6 +503,25 @@ cycle Slist{..} = infiniteSlist $ L.cycle sList {-# INLINE cycle #-} +{- | @O(1)@. An slist equivalent of 'P.enumFromTo' function or @[from..to]@ notation:+creates an 'Slist' of sequentially ordered values starting at @from@ and ending at @to@ inclusively.++>>> fromRange 0 5+Slist {sList = [0,1,2,3,4,5], sSize = Size 6}+>>> fromRange 5 0+Slist {sList = [], sSize = Size 0}+>>> fromRange 0 0+Slist {sList = [0], sSize = Size 1}+>>> fromRange 'a' 'd'+Slist {sList = "abcd", sSize = Size 4}+-}+fromRange :: Enum a => a -> a -> Slist a+fromRange from to = Slist [from..to] s+ where+ s :: Size+ s = Size $ max 0 (fromEnum to - fromEnum from + 1)+{-# INLINE fromRange #-}+ ---------------------------------------------------------------------------- -- Basic functions ----------------------------------------------------------------------------@@ -798,7 +830,7 @@ -} permutations :: Slist a -> Slist (Slist a) permutations (Slist l s) = Slist- { sList = P.map (\a -> Slist a s) $ L.permutations l+ { sList = P.map (`Slist` s) $ L.permutations l , sSize = fact s } where@@ -1053,8 +1085,14 @@ Slist {sList = [1,2,3,4,5,6,7,8,9,10], sSize = Size 10} >>> take 5 $ dropWhile (<3) $ infiniteSlist [1..] Slist {sList = [3,4,5,6,7], sSize = Size 5}++@+>> __dropWhile (< 5) $ 'infiniteSlist' [1..]__+Slist {sList = [5,6..], sSize = 'Infinity'}+@ -} dropWhile :: forall a . (a -> Bool) -> Slist a -> Slist a+dropWhile p (Slist l Infinity) = Slist (P.dropWhile p l) Infinity dropWhile p Slist{..} = let (s, l) = go 0 sList in Slist l (sSize - Size s) where@@ -1236,7 +1274,7 @@ isPrefixOf :: Eq a => Slist a -> Slist a -> Bool isPrefixOf (Slist l1 s1) (Slist l2 s2) | s1 > s2 = False- | otherwise = L.isPrefixOf l1 l2+ | otherwise = l1 `L.isPrefixOf` l2 {-# INLINE isPrefixOf #-} {- | Similar to 'isPrefixOf', but never hangs on infinite lists@@ -1250,7 +1288,7 @@ safeIsPrefixOf :: Eq a => Slist a -> Slist a -> Bool safeIsPrefixOf sl1@(Slist _ s1) sl2@(Slist _ s2) | s1 == Infinity && s2 == Infinity = False- | otherwise = isPrefixOf sl1 sl2+ | otherwise = sl1 `isPrefixOf` sl2 {-# INLINE safeIsPrefixOf #-} {- |@@ -1276,7 +1314,7 @@ isSuffixOf :: Eq a => Slist a -> Slist a -> Bool isSuffixOf (Slist l1 s1) (Slist l2 s2) | s1 > s2 = False- | otherwise = L.isSuffixOf l1 l2+ | otherwise = l1 `L.isSuffixOf` l2 {-# INLINE isSuffixOf #-} {- | Similar to 'isSuffixOf', but never hangs on infinite lists@@ -1290,7 +1328,7 @@ safeIsSuffixOf :: Eq a => Slist a -> Slist a -> Bool safeIsSuffixOf sl1 sl2@(Slist _ s2) | s2 == Infinity = False- | otherwise = isSuffixOf sl1 sl2+ | otherwise = sl1 `isSuffixOf` sl2 {-# INLINE safeIsSuffixOf #-} {- |@@ -1316,7 +1354,7 @@ isInfixOf :: Eq a => Slist a -> Slist a -> Bool isInfixOf (Slist l1 s1) (Slist l2 s2) | s1 > s2 = False- | otherwise = L.isInfixOf l1 l2+ | otherwise = l1 `L.isInfixOf` l2 {-# INLINE isInfixOf #-} {- | Similar to 'isInfixOf', but never hangs on infinite lists@@ -1330,7 +1368,7 @@ safeIsInfixOf :: Eq a => Slist a -> Slist a -> Bool safeIsInfixOf sl1@(Slist _ s1) sl2@(Slist _ s2) | s1 == Infinity && s2 == Infinity = False- | otherwise = isInfixOf sl1 sl2+ | otherwise = sl1 `isInfixOf` sl2 {-# INLINE safeIsInfixOf #-} {- |@@ -1866,3 +1904,163 @@ insertBy :: (a -> a -> Ordering) -> a -> Slist a -> Slist a insertBy f a Slist{..} = Slist (L.insertBy f a sList) (sSize + 1) {-# INLINE insertBy #-}++----------------------------------------------------------------------------+-- Generic fuctions+----------------------------------------------------------------------------++{- | @O(1)@.+The 'genericLength' function is an overloaded version of 'length'.+In particular, instead of returning an 'Int', it returns any type which is an+instance of 'Num'.++>>> genericLength $ one 42+1+>>> genericLength $ slist [1..3]+3+>>> genericLength $ infiniteSlist [1..]+9223372036854775807+-}+genericLength :: Num i => Slist a -> i+genericLength = fromIntegral . length+{-# INLINE genericLength #-}++{- | @O(i) | i < n@ and @O(1) | otherwise@.+The 'genericTake' function is an overloaded version of 'take', which+accepts any 'Integral' value as the number of elements to take.++>>> genericTake 5 $ slist "Hello world!"+Slist {sList = "Hello", sSize = Size 5}+>>> genericTake 20 $ slist "small"+Slist {sList = "small", sSize = Size 5}+>>> genericTake 0 $ slist "none"+Slist {sList = "", sSize = Size 0}+>>> genericTake (-11) $ slist "hmm"+Slist {sList = "", sSize = Size 0}+>>> genericTake 4 $ infiniteSlist [1..]+Slist {sList = [1,2,3,4], sSize = Size 4}+-}+genericTake :: Integral i => i -> Slist a -> Slist a+genericTake (fromIntegral -> i) sl@Slist{..}+ | Size i >= sSize = sl+ | i <= 0 = mempty+ | otherwise = Slist+ { sList = L.genericTake i sList+ , sSize = min sSize (Size i)+ }+{-# INLINE genericTake #-}++{- | @O(i) | i < n@ and @O(1) | otherwise@.+The 'genericDrop' function is an overloaded version of 'drop', which accepts+any 'Integral' value as the number of elements to drop.++>>> genericDrop 6 $ slist "Hello World"+Slist {sList = "World", sSize = Size 5}+>>> genericDrop 42 $ slist "oops!"+Slist {sList = "", sSize = Size 0}+>>> genericDrop 0 $ slist "Hello World!"+Slist {sList = "Hello World!", sSize = Size 12}+>>> genericDrop (-4) $ one 42+Slist {sList = [42], sSize = Size 1}++@+>> __drop 5 $ 'infiniteSlist' [1..]__+Slist {sList = [6..], sSize = 'Infinity'}+@++-}+genericDrop :: Integral i => i -> Slist a -> Slist a+genericDrop (fromIntegral -> i) sl@Slist{..}+ | i <= 0 = sl+ | Size i >= sSize = mempty+ | otherwise = Slist+ { sList = L.genericDrop i sList+ , sSize = sSize - Size i+ }+{-# INLINE genericDrop #-}++{- | @O(i) | i < n@ and @O(1) | otherwise@.+The 'genericSplitAt' function is an overloaded version of 'splitAt', which+accepts any 'Integral' value as the position at which to split.++>>> genericSplitAt 5 $ slist "Hello World!"+(Slist {sList = "Hello", sSize = Size 5},Slist {sList = " World!", sSize = Size 7})+>>> genericSplitAt 0 $ slist "abc"+(Slist {sList = "", sSize = Size 0},Slist {sList = "abc", sSize = Size 3})+>>> genericSplitAt 4 $ slist "abc"+(Slist {sList = "abc", sSize = Size 3},Slist {sList = "", sSize = Size 0})+>>> genericSplitAt (-42) $ slist "??"+(Slist {sList = "", sSize = Size 0},Slist {sList = "??", sSize = Size 2})++@+>> __genericSplitAt 2 $ 'infiniteSlist' [1..]__+(Slist {sList = [1,2], sSize = 'Size' 2}, Slist {sList = [3..], sSize = 'Infinity'})+@++-}+genericSplitAt :: Integral i => i -> Slist a -> (Slist a, Slist a)+genericSplitAt (fromIntegral -> i) sl@Slist{..}+ | i <= 0 = (mempty, sl)+ | Size i >= sSize = (sl, mempty)+ | otherwise =+ let (l1, l2) = L.genericSplitAt i sList+ s2 = sSize - Size i+ in (Slist l1 $ Size i, Slist l2 s2)+{-# INLINE genericSplitAt #-}++{- | @O(i) | i < n@ and @O(1) | otherwise@.+The 'genericAt' function is an overloaded version of 'at', which+accepts any 'Integral' value as the position. If the element on the given+position does not exist it will return 'Nothing'.++>>> let sl = slist [1..10]+>>> genericAt 0 sl+Just 1+>>> genericAt (-1) sl+Nothing+>>> genericAt 11 sl+Nothing+>>> genericAt 9 sl+Just 10+-}+genericAt :: Integral i => i -> Slist a -> Maybe a+genericAt = at . fromIntegral+{-# INLINE genericAt #-}++{- | @O(min i n)@.+The 'genericUnsafeAt' function is an overloaded version of 'unsafeAt', which+accepts any 'Integral' value as the position. If the element on the given+position does not exist it throws the exception at run-time.++>>> let sl = slist [1..10]+>>> genericUnsafeAt 0 sl+1+>>> genericUnsafeAt (-1) sl+*** Exception: Slist.genericUnsafeAt: negative argument+>>> genericUnsafeAt 11 sl+*** Exception: Slist.genericUnsafeAt: index too large+>>> genericUnsafeAt 9 sl+10+-}+genericUnsafeAt :: Integral i => i -> Slist a -> a+genericUnsafeAt i _ | i < 0 = errorWithoutStackTrace "Slist.genericUnsafeAt: negative argument"+genericUnsafeAt i (Slist l Infinity) = L.genericIndex l i+genericUnsafeAt i (Slist l (Size n))+ | i >= fromIntegral n = errorWithoutStackTrace "Slist.genericUnsafeAt: index too large"+ | otherwise = L.genericIndex l i+{-# INLINE genericUnsafeAt #-}++{- | @O(n)@.+The 'genericReplicate' function is an overloaded version of 'replicate',+which accepts any 'Integral' value as the number of repetitions to make.++>>> genericReplicate 3 'o'+Slist {sList = "ooo", sSize = Size 3}+>>> genericReplicate (-11) "hmm"+Slist {sList = [], sSize = Size 0}+-}+genericReplicate :: Integral i => i -> a -> Slist a+genericReplicate n x+ | n <= 0 = mempty+ | otherwise = Slist (L.genericReplicate n x) $ Size (fromIntegral n)+{-# INLINE genericReplicate #-}
src/Slist/Size.hs view
@@ -26,7 +26,7 @@ = Size !Int -- | Infinite size. | Infinity- deriving (Show, Read, Eq, Ord)+ deriving stock (Show, Read, Eq, Ord) {- | Efficient implementations of numeric operations with 'Size's.
test/Doctest.hs view
@@ -10,4 +10,5 @@ $ "-XInstanceSigs" : "-XScopedTypeVariables" : "-XRecordWildCards"+ : "-XDerivingStrategies" : sourceFiles