Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package ghc-streaming for openSUSE:Factory checked in at 2022-02-11 23:08:01 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/ghc-streaming (Old) and /work/SRC/openSUSE:Factory/.ghc-streaming.new.1956 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ghc-streaming" Fri Feb 11 23:08:01 2022 rev:4 rq:953401 version:0.2.3.1 Changes: -------- --- /work/SRC/openSUSE:Factory/ghc-streaming/ghc-streaming.changes 2021-08-25 20:58:59.149099940 +0200 +++ /work/SRC/openSUSE:Factory/.ghc-streaming.new.1956/ghc-streaming.changes 2022-02-11 23:09:54.907033712 +0100 @@ -1,0 +2,11 @@ +Mon Dec 20 20:05:34 UTC 2021 - Peter Simons <[email protected]> + +- Update streaming to version 0.2.3.1. + - 0.2.4.0 + Bifoldable and Bitraversable instances for Of. + + Various documentation fixes. + + Bump `mmorph` upper bounds: [1.0, 1.2) -> [1.0, 1.3) + +------------------------------------------------------------------- Old: ---- streaming-0.2.3.0.tar.gz New: ---- streaming-0.2.3.1.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ ghc-streaming.spec ++++++ --- /var/tmp/diff_new_pack.AVJBUI/_old 2022-02-11 23:09:56.279037680 +0100 +++ /var/tmp/diff_new_pack.AVJBUI/_new 2022-02-11 23:09:56.287037704 +0100 @@ -1,7 +1,7 @@ # # spec file for package ghc-streaming # -# Copyright (c) 2020 SUSE LLC +# Copyright (c) 2021 SUSE LLC # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -17,8 +17,9 @@ %global pkg_name streaming +%bcond_with tests Name: ghc-%{pkg_name} -Version: 0.2.3.0 +Version: 0.2.3.1 Release: 0 Summary: An elementary streaming prelude and general stream type License: BSD-3-Clause @@ -32,6 +33,10 @@ BuildRequires: ghc-transformers-base-devel BuildRequires: ghc-transformers-devel ExcludeArch: %{ix86} +%if %{with tests} +BuildRequires: ghc-QuickCheck-devel +BuildRequires: ghc-hspec-devel +%endif %description This package contains two modules, @@ -204,7 +209,6 @@ %prep %autosetup -n %{pkg_name}-%{version} -cabal-tweak-dep-ver mmorph '<1.2' '<1.3' %build %ghc_lib_build @@ -212,6 +216,9 @@ %install %ghc_lib_install +%check +%cabal_test + %post devel %ghc_pkg_recache ++++++ streaming-0.2.3.0.tar.gz -> streaming-0.2.3.1.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/streaming-0.2.3.0/README.md new/streaming-0.2.3.1/README.md --- old/streaming-0.2.3.0/README.md 2001-09-09 03:46:40.000000000 +0200 +++ new/streaming-0.2.3.1/README.md 2001-09-09 03:46:40.000000000 +0200 @@ -140,7 +140,7 @@ ?? 6. Didn't I hear that free monads are a dog from the point of view of efficiency? ------------------------------------------------------------------------------------- -We noted above that if we instantiate `Stream f m r` to `Stream ((,) a) m r` or the like, we get the standard idea of a producer or generator. If it is instantiated to `Stream f Identity m r` then we have the standard \_free monad construction/. This construction is subject to certain familiar objections from an efficiency perspective; efforts have been made to substitute exotic cps-ed implementations and so forth. It is an interesting topic. +We noted above that if we instantiate `Stream f m r` to `Stream ((,) a) m r` or the like, we get the standard idea of a producer or generator. If it is instantiated to `Stream Identity m r` then we have the standard \_free monad construction/. This construction is subject to certain familiar objections from an efficiency perspective; efforts have been made to substitute exotic cps-ed implementations and so forth. It is an interesting topic. But in fact, the standard alarmist talk about *retraversing binds* and *quadratic explosions* and *costly appends*, and so on become transparent nonsense with `Stream f m r`\ in its streaming use. The conceptual power needed to see this is basically nil: Where `m` is read as `IO`, or some transformed `IO`, then the dreaded *retraversing of the binds* in a stream expression would involve repeating all the past actions. Don't worry, to get e.g. the second chunk of bytes from a handle, you won't need to start over and get the first one again! The first chunk has vanished into an unrepeatable past. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/streaming-0.2.3.0/changelog.md new/streaming-0.2.3.1/changelog.md --- old/streaming-0.2.3.0/changelog.md 2001-09-09 03:46:40.000000000 +0200 +++ new/streaming-0.2.3.1/changelog.md 2001-09-09 03:46:40.000000000 +0200 @@ -1,3 +1,10 @@ +- 0.2.4.0 + Bifoldable and Bitraversable instances for Of. + + Various documentation fixes. + + Bump `mmorph` upper bounds: [1.0, 1.2) -> [1.0, 1.3) + - 0.2.3.0 Add `wrapEffect`. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/streaming-0.2.3.0/src/Data/Functor/Of.hs new/streaming-0.2.3.1/src/Data/Functor/Of.hs --- old/streaming-0.2.3.0/src/Data/Functor/Of.hs 2001-09-09 03:46:40.000000000 +0200 +++ new/streaming-0.2.3.1/src/Data/Functor/Of.hs 2001-09-09 03:46:40.000000000 +0200 @@ -13,6 +13,10 @@ import Data.Foldable (Foldable) import Data.Traversable (Traversable) #endif +#if MIN_VERSION_base(4,10,0) +import Data.Bifoldable (Bifoldable, bifoldMap) +import Data.Bitraversable (Bitraversable, bitraverse) +#endif import GHC.Generics (Generic, Generic1) -- | A left-strict pair; the base functor for streams of individual elements. @@ -49,6 +53,18 @@ {-#INLINE second #-} #endif +#if MIN_VERSION_base(4,10,0) +-- | @since 0.2.4.0 +instance Bifoldable Of where + bifoldMap f g (a :> b) = f a `mappend` g b + {-#INLINE bifoldMap #-} + +-- | @since 0.2.4.0 +instance Bitraversable Of where + bitraverse f g (a :> b) = (:>) <$> f a <*> g b + {-#INLINE bitraverse #-} +#endif + instance Monoid a => Applicative (Of a) where pure x = mempty :> x {-#INLINE pure #-} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/streaming-0.2.3.0/src/Streaming/Prelude.hs new/streaming-0.2.3.1/src/Streaming/Prelude.hs --- old/streaming-0.2.3.0/src/Streaming/Prelude.hs 2001-09-09 03:46:40.000000000 +0200 +++ new/streaming-0.2.3.1/src/Streaming/Prelude.hs 2001-09-09 03:46:40.000000000 +0200 @@ -134,6 +134,12 @@ , show , cons , slidingWindow + , slidingWindowMin + , slidingWindowMinBy + , slidingWindowMinOn + , slidingWindowMax + , slidingWindowMaxBy + , slidingWindowMaxOn , wrapEffect -- * Splitting and inspecting streams of elements @@ -272,6 +278,7 @@ import qualified Data.IntSet as IntSet import qualified Data.Sequence as Seq import qualified Data.Set as Set +import Data.Word (Word64) import qualified GHC.IO.Exception as G import qualified Prelude import qualified System.IO as IO @@ -825,19 +832,21 @@ {-| An infinite stream of enumerable values, starting from a given value. It is the same as @S.iterate succ@. - Because their return type is polymorphic, @enumFrom@, @enumFromThen@ - and @iterate@ are useful for example with @zip@ - and @zipWith@, which require the same return type in the zipped streams. - With @each [1..]@ the following bit of connect-and-resume would be impossible: - ->>> rest <- S.print $ S.zip (S.enumFrom 'a') $ S.splitAt 3 $ S.enumFrom 1 -('a',1) -('b',2) -('c',3) + Because their return type is polymorphic, @enumFrom@, @enumFromThen@ + and @iterate@ are useful with functions like @zip@ and @zipWith@, which + require the zipped streams to have the same return type. + + For example, with + @each [1..]@ the following bit of connect-and-resume would not compile: + +>>> rest <- S.print $ S.zip (S.enumFrom 1) $ S.splitAt 3 $ S.each ['a'..'z'] +(1,'a') +(2,'b') +(3,'c') >>> S.print $ S.take 3 rest -4 -5 -6 +'d' +'e' +'f' -} enumFrom :: (Monad m, Enum n) => n -> Stream (Of n) m r @@ -1381,13 +1390,24 @@ {- | Map layers of one functor to another with a transformation involving the base monad. - This could be trivial, e.g. + + This function is completely functor-general. It is often useful with the more concrete type + +@ +mapped :: (forall x. Stream (Of a) IO x -> IO (Of b x)) -> Stream (Stream (Of a) IO) IO r -> Stream (Of b) IO r +@ -> let noteBeginning text x = putStrLn text >> return text + to process groups which have been demarcated in an effectful, @IO@-based + stream by grouping functions like 'Streaming.Prelude.group', + 'Streaming.Prelude.split' or 'Streaming.Prelude.breaks'. Summary functions + like 'Streaming.Prelude.fold', 'Streaming.Prelude.foldM', + 'Streaming.Prelude.mconcat' or 'Streaming.Prelude.toList' are often used + to define the transformation argument. For example: - this is completely functor-general +>>> S.toList_ $ S.mapped S.toList $ S.split 'c' (S.each "abcde") +["ab","de"] - @maps@ and @mapped@ obey these rules: + 'Streaming.Prelude.maps' and 'Streaming.Prelude.mapped' obey these rules: > maps id = id > mapped return = id @@ -1396,8 +1416,9 @@ > maps f . mapped g = mapped (fmap f . g) > mapped f . maps g = mapped (f <=< fmap g) - @maps@ is more fundamental than @mapped@, which is best understood as a convenience - for effecting this frequent composition: + 'Streaming.Prelude.maps' is more fundamental than + 'Streaming.Prelude.mapped', which is best understood as a convenience for + effecting this frequent composition: > mapped phi = decompose . maps (Compose . phi) @@ -1942,7 +1963,7 @@ @Streaming@ module, but since this module is imported qualified, it can usurp a Prelude name. It specializes to: -> splitAt :: (Monad m, Functor f) => Int -> Stream (Of a) m r -> Stream (Of a) m (Stream (Of a) m r) +> splitAt :: (Monad m) => Int -> Stream (Of a) m r -> Stream (Of a) m (Stream (Of a) m r) -} splitAt :: (Monad m, Functor f) => Int -> Stream f m r -> Stream f m (Stream f m r) @@ -2634,7 +2655,7 @@ @copy@ can be considered a special case of 'expand': @ - copy = 'expand' $ \p (a :> as) -> a :> p (a :> as) + copy = 'expand' $ \\p (a :> as) -> a :> p (a :> as) @ If 'Of' were an instance of 'Control.Comonad.Comonad', then one could write @@ -2710,8 +2731,8 @@ 'unzip' can be considered a special case of either 'unzips' or 'expand': @ - unzip = 'unzips' . 'maps' (\((a,b) :> x) -> Compose (a :> b :> x)) - unzip = 'expand' $ \p ((a,b) :> abs) -> b :> p (a :> abs) + unzip = 'unzips' . 'maps' (\\((a,b) :> x) -> Compose (a :> b :> x)) + unzip = 'expand' $ \\p ((a,b) :> abs) -> b :> p (a :> abs) @ -} unzip :: Monad m => Stream (Of (a,b)) m r -> Stream (Of a) (Stream (Of b) m) r @@ -2859,6 +2880,216 @@ Right (x,rest) -> setup (m-1) (sequ Seq.|> x) rest {-# INLINABLE slidingWindow #-} +-- | 'slidingWindowMin' finds the minimum in every sliding window of @n@ +-- elements of a stream. If within a window there are multiple elements that are +-- the least, it prefers the first occurrence (if you prefer to have the last +-- occurrence, use the max version and flip your comparator). It satisfies: +-- +-- @ +-- 'slidingWindowMin' n s = 'map' 'Foldable.minimum' ('slidingWindow' n s) +-- @ +-- +-- Except that it is far more efficient, especially when the window size is +-- large: it calls 'compare' /O(m)/ times overall where /m/ is the total number +-- of elements in the stream. +slidingWindowMin :: (Monad m, Ord a) => Int -> Stream (Of a) m b -> Stream (Of a) m b +slidingWindowMin = slidingWindowMinBy compare +{-# INLINE slidingWindowMin #-} + +-- | 'slidingWindowMax' finds the maximum in every sliding window of @n@ +-- elements of a stream. If within a window there are multiple elements that are +-- the largest, it prefers the last occurrence (if you prefer to have the first +-- occurrence, use the min version and flip your comparator). It satisfies: +-- +-- @ +-- 'slidingWindowMax' n s = 'map' 'Foldable.maximum' ('slidingWindow' n s) +-- @ +-- +-- Except that it is far more efficient, especially when the window size is +-- large: it calls 'compare' /O(m)/ times overall where /m/ is the total number +-- of elements in the stream. +slidingWindowMax :: (Monad m, Ord a) => Int -> Stream (Of a) m b -> Stream (Of a) m b +slidingWindowMax = slidingWindowMaxBy compare +{-# INLINE slidingWindowMax #-} + +-- | 'slidingWindowMinBy' finds the minimum in every sliding window of @n@ +-- elements of a stream according to the given comparison function (which should +-- define a total ordering). See notes above about elements that are equal. It +-- satisfies: +-- +-- @ +-- 'slidingWindowMinBy' f n s = 'map' ('Foldable.minimumBy' f) ('slidingWindow' n s) +-- @ +-- +-- Except that it is far more efficient, especially when the window size is +-- large: it calls the comparison function /O(m)/ times overall where /m/ is the +-- total number of elements in the stream. +slidingWindowMinBy :: Monad m => (a -> a -> Ordering) -> Int -> Stream (Of a) m b -> Stream (Of a) m b +slidingWindowMinBy cmp = slidingWindowOrd id (\a b -> cmp a b == GT) +{-# INLINE slidingWindowMinBy #-} + +-- | 'slidingWindowMaxBy' finds the maximum in every sliding window of @n@ +-- elements of a stream according to the given comparison function (which should +-- define a total ordering). See notes above about elements that are equal. It +-- satisfies: +-- +-- @ +-- 'slidingWindowMaxBy' f n s = 'map' ('Foldable.maximumBy' f) ('slidingWindow' n s) +-- @ +-- +-- Except that it is far more efficient, especially when the window size is +-- large: it calls the comparison function /O(m)/ times overall where /m/ is the +-- total number of elements in the stream. +slidingWindowMaxBy :: Monad m => (a -> a -> Ordering) -> Int -> Stream (Of a) m b -> Stream (Of a) m b +slidingWindowMaxBy cmp = slidingWindowOrd id (\a b -> cmp a b /= GT) +{-# INLINE slidingWindowMaxBy #-} + +-- | 'slidingWindowMinOn' finds the minimum in every sliding window of @n@ +-- elements of a stream according to the given projection function. See notes +-- above about elements that are equal. It satisfies: +-- +-- @ +-- 'slidingWindowMinOn' f n s = 'map' ('Foldable.minimumOn' ('comparing' f)) ('slidingWindow' n s) +-- @ +-- +-- Except that it is far more efficient, especially when the window size is +-- large: it calls 'compare' on the projected value /O(m)/ times overall where +-- /m/ is the total number of elements in the stream, and it calls the +-- projection function exactly /m/ times. +slidingWindowMinOn :: (Monad m, Ord p) => (a -> p) -> Int -> Stream (Of a) m b -> Stream (Of a) m b +slidingWindowMinOn proj = slidingWindowOrd proj (\a b -> compare a b == GT) +{-# INLINE slidingWindowMinOn #-} + +-- | 'slidingWindowMaxOn' finds the maximum in every sliding window of @n@ +-- elements of a stream according to the given projection function. See notes +-- above about elements that are equal. It satisfies: +-- +-- @ +-- 'slidingWindowMaxOn' f n s = 'map' ('Foldable.maximumOn' ('comparing' f)) ('slidingWindow' n s) +-- @ +-- +-- Except that it is far more efficient, especially when the window size is +-- large: it calls 'compare' on the projected value /O(m)/ times overall where +-- /m/ is the total number of elements in the stream, and it calls the +-- projection function exactly /m/ times. +slidingWindowMaxOn :: (Monad m, Ord p) => (a -> p) -> Int -> Stream (Of a) m b -> Stream (Of a) m b +slidingWindowMaxOn proj = slidingWindowOrd proj (\a b -> compare a b /= GT) +{-# INLINE slidingWindowMaxOn #-} + +-- IMPLEMENTATION NOTE [the slidingWindow{Min,Max} functions] +-- +-- When one wishes to compute the minimum (or maximum; without loss of +-- generality we will only discuss the minimum case) of a sliding window of a +-- stream, the naive method is to collect all such sliding windows, and then run +-- 'Foldable.minimum' over each window. The issue is that this algorithm is very +-- inefficient: if the stream has $n$ elements, and the sliding window has $k$ +-- elements, then there are $n-k+1$ windows, and computing the minimum in each +-- window requires $k-1$ comparisons. So a total of $(k-1)*(n-k+1)$ comparisons +-- are needed, or simply $O(nk)$ when $k$ is much smaller than $n$. +-- +-- We can motivate an improvement as follows. Suppose the window size is 3 and +-- the current sliding window has numbers 4, 6, 8; if the next element happens +-- to be 5, there would then be no need to keep the numbers 6 and 8 in the +-- window. Because in the next window we have 6, 8, 5 so 5 will be yielded. In +-- the window after the next we have 8, 5, x so either 5 or x will be yielded. +-- So 6 and 8 will never be yielded. +-- +-- This leads to the idea that we can keep a window that is a subsequence of the +-- actual window. But immediately the next problem is, if we don't keep a window +-- of the original window size, there would be no way for us to tell which +-- elements are out of the window. So the idea is to also keep an index of the +-- item along with the item itself. We then have several important invariants: +-- +-- (a) The window is sorted according to the index. +-- (b) The window is sorted according to the item itself. +-- (c) The size of the window never has more elements than $k$. +-- +-- The window is initially empty. The three-step algorithm to update the window +-- maintains these invariants. +-- +-- The overall asymptotic complexity is great. Comparisons only happen in the +-- first part of the update. Each comparison either results in an element being +-- removed from the window (so there can be at most $O(n)$ such comparisons); or +-- that comparison does not result in an element being removed, but such +-- comparisons happen at most once for each element being inserted, which is +-- also $O(n)$. This means an overall $O(n)$ number of comparisons needed. +-- +-- I did not invent this algorithm; it's pretty well-known. I'm not sure the +-- algorithm has a name. +slidingWindowOrd :: Monad m => (a -> p) -> (p -> p -> Bool) -> Int -> Stream (Of a) m b -> Stream (Of a) m b +slidingWindowOrd proj f n = + dropButRetainAtLeastOne (k-1) . catMaybes . scan update initial extract + -- The use of dropButRetainAtLeastOne is to gracefully handle edge cases where + -- the window size is bigger than the length of the entire sequence. + where + k = max 1 n -- window size + initial = SlidingWindowOrdState 0 mempty + -- All three invariants are satisfied initially. The window is trivially + -- sorted because it is empty. Its size, zero, is also less than the window + -- size. + update (SlidingWindowOrdState i w0) a = + let projected = proj a + w1 = Seq.dropWhileR (\(SlidingWindowOrdElement _ _ p) -> f p projected) w0 + -- Step 1: pop all elements at the back greater than the current one, + -- because they will never be yielded: the current element will always be + -- yielded until those popped elements go out of the window. This is + -- extracting a subsequence of the window, so invariants (a) and (b) + -- remain satisfied. Since this operation deletes elements, invariant (c) + -- is maintained. + w2 = w1 Seq.|> SlidingWindowOrdElement i a projected + -- Step 2: add the current element to the back. Since the current index is + -- greater than all previous indices, invariant (a) is satisfied. + -- Invariant (b) is also satisfied because in step 1 we popped elements + -- greater than the current, so either the window is empty or the back of + -- the window is smaller than the current one. Invariant (c) may be + -- violated, but this is fixed below. + w3 = Seq.dropWhileL (\(SlidingWindowOrdElement j _ _) -> j + fromIntegral k <= i) w2 + -- Step 3: remove elements that are out of the window. Again this is + -- extracting a subsequence so invariants (a) and (b) are maintained. + -- Invariant (c) is maintained because the least index still possibly in + -- the window is i+1-k, in which case we have k elements. + in SlidingWindowOrdState (i + 1) w3 + -- Extract the front. + extract (SlidingWindowOrdState _ w) = + case Seq.viewl w of + SlidingWindowOrdElement _ m _ Seq.:< _ -> Just m + _ -> Nothing +{-# INLINABLE slidingWindowOrd #-} + +-- | A 'SlidingWindowOrdState' keeps track of the current sliding window state +-- in 'slidingWindowOrd'. It keeps track of the current index of the item from +-- the stream as well as a 'Seq.Seq' of the current window. See comments above +-- for properties satisfied by the window. +data SlidingWindowOrdState a p = + SlidingWindowOrdState !Word64 + !(Seq.Seq (SlidingWindowOrdElement a p)) + +-- | A 'SlidingWindowOrdElement' is an element with a 'Word64'-based index as +-- well as the projection used for comparison. It is used in the sliding window +-- functions to associate an item with their index and the projected element in +-- the stream. +data SlidingWindowOrdElement a p = SlidingWindowOrdElement !Word64 a p + +-- | Similar to 'drop', except that if the input stream doesn't have enough +-- elements, the last one will be yielded. However, if there's none to begin +-- with, this function will also produce none. +dropButRetainAtLeastOne :: Monad m => Int -> Stream (Of a) m r -> Stream (Of a) m r +dropButRetainAtLeastOne 0 = id +dropButRetainAtLeastOne n = loop Nothing n + where + loop (Just final) (-1) str = yield final >> str + loop final m str = do + e <- lift (next str) + case e of + Left r -> do + case final of + Nothing -> pure () + Just l -> yield l + return r + Right (x, rest) -> loop (Just x) (m - 1) rest +{-# INLINABLE dropButRetainAtLeastOne #-} + + -- | Map monadically over a stream, producing a new stream -- only containing the 'Just' values. mapMaybeM :: Monad m => (a -> m (Maybe b)) -> Stream (Of a) m r -> Stream (Of b) m r diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/streaming-0.2.3.0/streaming.cabal new/streaming-0.2.3.1/streaming.cabal --- old/streaming-0.2.3.0/streaming.cabal 2001-09-09 03:46:40.000000000 +0200 +++ new/streaming-0.2.3.1/streaming.cabal 2001-09-09 03:46:40.000000000 +0200 @@ -1,5 +1,5 @@ name: streaming -version: 0.2.3.0 +version: 0.2.3.1 cabal-version: >=1.10 build-type: Simple synopsis: an elementary streaming prelude and general stream type. @@ -207,7 +207,7 @@ build-depends: base >=4.8 && <5 , mtl >=2.1 && <2.3 - , mmorph >=1.0 && <1.2 + , mmorph >=1.0 && <1.3 , transformers >=0.4 && <0.6 , transformers-base < 0.5 , ghc-prim @@ -222,3 +222,16 @@ src default-language: Haskell2010 + +test-suite spec + type: exitcode-stdio-1.0 + hs-source-dirs: + test + main-is: test.hs + build-depends: + streaming + , QuickCheck >= 2.13 + , hspec >= 2.7 + , base >=4.8 && <5 + default-language: + Haskell2010 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/streaming-0.2.3.0/test/test.hs new/streaming-0.2.3.1/test/test.hs --- old/streaming-0.2.3.0/test/test.hs 1970-01-01 01:00:00.000000000 +0100 +++ new/streaming-0.2.3.1/test/test.hs 2001-09-09 03:46:40.000000000 +0200 @@ -0,0 +1,91 @@ +module Main where + +import qualified Data.Foldable as Foldable +import Data.Functor.Identity +import Data.Ord +import qualified Streaming.Prelude as S +import Test.Hspec +import Test.QuickCheck + +toL :: S.Stream (S.Of a) Identity b -> [a] +toL = runIdentity . S.toList_ + +main :: IO () +main = + hspec $ do + describe "slidingWindowMin" $ do + it "works with a few simple cases" $ do + toL (S.slidingWindowMin 2 (S.each [1, 3, 9, 4, 6, 4])) `shouldBe` [1, 3, 4, 4, 4] + toL (S.slidingWindowMin 3 (S.each [1, 3, 2, 6, 3, 7, 8, 9])) `shouldBe` [1, 2, 2, 3, 3, 7] + it "produces no results with empty streams" $ + property $ \k -> toL (S.slidingWindowMin k (mempty :: S.Stream (S.Of Int) Identity ())) `shouldBe` [] + it "behaves like a (S.map Foldable.minimum) (slidingWindow) for non-empty streams" $ + property $ \(NonEmpty xs) k -- we use NonEmpty because Foldable.minimum crashes on empty lists + -> + toL (S.slidingWindowMin k (S.each xs)) === + toL (S.map Foldable.minimum (S.slidingWindow k (S.each (xs :: [Int])))) + it "behaves like identity when window size is 1" $ + property $ \xs -> toL (S.slidingWindowMin 1 (S.each (xs :: [Int]))) === xs + it "produces a prefix when the stream elements are sorted" $ + property $ \(Sorted xs) k -> + (length xs >= k) ==> (toL (S.slidingWindowMin k (S.each (xs :: [Int]))) === take (length xs - (k - 1)) xs) + describe "slidingWindowMinBy" $ do + it "prefers earlier elements when several elements compare equal" $ do + toL (S.slidingWindowMinBy (comparing fst) 2 (S.each [(1, 1), (2, 2), (2, 3), (2, 4)])) `shouldBe` + [(1, 1), (2, 2), (2, 3)] + it "behaves like a (S.map (Foldable.minimumBy f)) (slidingWindow) for non-empty streams" $ do + property $ \(NonEmpty xs) k -- we use NonEmpty because Foldable.minimumBy crashes on empty lists + -> + toL (S.slidingWindowMinBy (comparing fst) k (S.each xs)) === + toL (S.map (Foldable.minimumBy (comparing fst)) (S.slidingWindow k (S.each (xs :: [(Int, Int)])))) + describe "slidingWindowMinOn" $ do + it "behaves like a (S.map (Foldable.minimumBy (comparing p))) (slidingWindow) for non-empty streams" $ do + property $ \(NonEmpty xs) k -- we use NonEmpty because Foldable.minimumBy crashes on empty lists + -> + toL (S.slidingWindowMinOn fst k (S.each xs)) === + toL (S.map (Foldable.minimumBy (comparing fst)) (S.slidingWindow k (S.each (xs :: [(Int, Int)])))) + it "does not force the projected value to WHNF" $ + property $ \xs k -> + (length xs >= k) ==> + (toL (S.slidingWindowMinOn (const (undefined :: UnitWithLazyEq)) k (S.each (xs :: [Int]))) === + take (length xs - (k - 1)) xs) + describe "slidingWindowMax" $ do + it "produces no results with empty streams" $ + property $ \k -> toL (S.slidingWindowMax k (mempty :: S.Stream (S.Of Int) Identity ())) `shouldBe` [] + it "behaves like a (S.map Foldable.maximum) (slidingWindow n s) for non-empty streams" $ + property $ \(NonEmpty xs) k -- we use NonEmpty because Foldable.maximum crashes on empty lists + -> + toL (S.slidingWindowMax k (S.each xs)) === + toL (S.map Foldable.maximum (S.slidingWindow k (S.each (xs :: [Int])))) + it "behaves like identity when window size is 1" $ + property $ \xs -> toL (S.slidingWindowMax 1 (S.each (xs :: [Int]))) === xs + it "produces a suffix when the stream elements are sorted" $ + property $ \(Sorted xs) k -> + (length xs >= k) ==> (toL (S.slidingWindowMax k (S.each (xs :: [Int]))) === drop (k - 1) xs) + describe "slidingWindowMaxBy" $ do + it "prefers later elements when several elements compare equal" $ do + toL (S.slidingWindowMaxBy (comparing fst) 2 (S.each [(1, 1), (2, 2), (2, 3), (2, -900)])) `shouldBe` + [(2, 2), (2, 3), (2, -900)] + it "behaves like a (S.map (Foldable.maximumBy f)) (slidingWindow) for non-empty streams" $ do + property $ \(NonEmpty xs) k -- we use NonEmpty because Foldable.maximumBy crashes on empty lists + -> + toL (S.slidingWindowMaxBy (comparing fst) k (S.each xs)) === + toL (S.map (Foldable.maximumBy (comparing fst)) (S.slidingWindow k (S.each (xs :: [(Int, Int)])))) + describe "slidingWindowMaxOn" $ do + it "behaves like a (S.map (Foldable.maximumBy (comparing p))) (slidingWindow) for non-empty streams" $ do + property $ \(NonEmpty xs) k -- we use NonEmpty because Foldable.maximumBy crashes on empty lists + -> + toL (S.slidingWindowMaxOn fst k (S.each xs)) === + toL (S.map (Foldable.maximumBy (comparing fst)) (S.slidingWindow k (S.each (xs :: [(Int, Int)])))) + it "does not force the projected value to WHNF" $ + property $ \xs k -> + (length xs >= k) ==> + (toL (S.slidingWindowMaxOn (const (undefined :: UnitWithLazyEq)) k (S.each (xs :: [Int]))) === drop (k - 1) xs) + +data UnitWithLazyEq = UnitWithLazyEq + +instance Eq UnitWithLazyEq where + _ == _ = True + +instance Ord UnitWithLazyEq where + compare _ _ = EQ
