git.iko.soy/streamly
on 16dfa56 help sign in
streamly/test/Streamly/Test/Data/Fold.hs
527 lines 15 kB history raw
1module Main (main) where
3import Data.Semigroup (Sum(..), getSum)
4import Streamly.Test.Common (checkListEqual, listEquals)
5import Test.QuickCheck
6 ( Gen
7 , Property
8 , arbitrary
9 , choose
10 , forAll
11 , listOf
12 , listOf1
13 , property
14 , vectorOf
15 , withMaxSuccess
16 )
17import Test.QuickCheck.Monadic (monadicIO, assert, run)
19import qualified Prelude
20import qualified Streamly.Internal.Data.Fold as F
21import qualified Streamly.Prelude as S
22import qualified Streamly.Internal.Data.Stream.IsStream as Stream
23import qualified Streamly.Data.Fold as FL
25import Prelude hiding
26 (maximum, minimum, elem, notElem, null, product, sum, head, last, take)
27import Test.Hspec as H
28import Test.Hspec.QuickCheck
30maxStreamLen :: Int
31maxStreamLen = 1000
33intMin :: Int
34intMin = minBound
36intMax :: Int
37intMax = maxBound
39min_value :: Int
40min_value = 0
42max_value :: Int
43max_value = 10000
45chooseInt :: (Int, Int) -> Gen Int
46chooseInt = choose
48{-# INLINE maxStreamLen #-}
49{-# INLINE intMin #-}
50{-# INLINE intMax #-}
52rollingHashFirstN :: Property
53rollingHashFirstN =
54 forAll (choose (0, maxStreamLen)) $ \len ->
55 forAll (choose (0, len)) $ \n ->
56 forAll (vectorOf len (arbitrary :: Gen Int)) $ \vec -> monadicIO $ do
57 a <- run $ S.fold F.rollingHash $ S.take n $ S.fromList vec
58 b <- run $ S.fold (F.rollingHashFirstN n) $ S.fromList vec
59 assert $ a == b
61head :: [Int] -> Expectation
62head ls = S.fold FL.head (S.fromList ls) `shouldReturn` headl ls
64headl :: [a] -> Maybe a
65headl [] = Nothing
66headl (x:_) = Just x
68length :: [Int] -> Expectation
69length ls = S.fold FL.length (S.fromList ls) `shouldReturn` Prelude.length ls
71sum :: [Int] -> Expectation
72sum ls = S.fold FL.sum (S.fromList ls) `shouldReturn` Prelude.sum ls
74product :: [Int] -> Expectation
75product ls =
76 S.fold FL.product (S.fromList ls) `shouldReturn` Prelude.product ls
78lesser :: (a -> a -> Ordering) -> a -> a -> a
79lesser f x y = if f x y == LT then x else y
81greater :: (a -> a -> Ordering) -> a -> a -> a
82greater f x y = if f x y == GT then x else y
84foldMaybe :: (b -> a -> b) -> b -> [a] -> Maybe b
85foldMaybe f acc ls =
86 case ls of
87 [] -> Nothing
88 _ -> Just (foldl f acc ls)
90maximumBy :: (Ord a, Show a) => a -> (a -> a -> Ordering) -> [a] -> Expectation
91maximumBy genmin f ls =
92 S.fold (FL.maximumBy f) (S.fromList ls)
93 `shouldReturn` foldMaybe (greater f) genmin ls
95maximum :: (Show a, Ord a) => a -> [a] -> Expectation
96maximum genmin ls =
97 S.fold FL.maximum (S.fromList ls)
98 `shouldReturn` foldMaybe (greater compare) genmin ls
100minimumBy :: (Ord a, Show a) => a -> (a -> a -> Ordering) -> [a] -> Expectation
101minimumBy genmax f ls =
102 S.fold (FL.minimumBy f) (S.fromList ls)
103 `shouldReturn` foldMaybe (lesser f) genmax ls
105minimum :: (Show a, Ord a) => a -> [a] -> Expectation
106minimum genmax ls =
107 S.fold FL.minimum (S.fromList ls)
108 `shouldReturn` foldMaybe (lesser compare) genmax ls
110toList :: [Int] -> Expectation
111toList ls = S.fold FL.toList (S.fromList ls) `shouldReturn` ls
113safeLast :: [a] -> Maybe a
114safeLast [] = Nothing
115safeLast (x:[]) = Just x
116safeLast (_:xs) = safeLast xs
118last :: [String] -> Expectation
119last ls = S.fold FL.last (S.fromList ls) `shouldReturn` safeLast ls
121mapMaybe :: [Int] -> Expectation
122mapMaybe ls =
123 let maybeEven x =
124 if even x
125 then Just x
126 else Nothing
127 f = F.mapMaybe maybeEven FL.toList
128 in S.fold f (S.fromList ls) `shouldReturn` filter even ls
130nth :: Int -> [a] -> Maybe a
131nth idx (x : xs)
132 | idx == 0 = Just x
133 | idx < 0 = Nothing
134 | otherwise = nth (idx - 1) xs
135nth _ [] = Nothing
137index :: Int -> [String] -> Expectation
138index idx ls =
139 let x = S.fold (FL.index idx) (S.fromList ls)
140 in x `shouldReturn` nth idx ls
142find :: (Show a, Eq a) => (a -> Bool) -> [a] -> Expectation
143find f ls = do
144 y <- S.fold (FL.findIndex f) (S.fromList ls)
145 case y of
146 Nothing ->
147 let fld = S.fold (FL.find f) (S.fromList ls)
148 in fld `shouldReturn` Nothing
149 Just idx ->
150 let fld = S.fold (FL.any f) (S.fromList $ Prelude.take idx ls)
151 in fld `shouldReturn` False
153neg :: (a -> Bool) -> a -> Bool
154neg f x = not (f x)
156findIndex :: (a -> Bool) -> [a] -> Expectation
157findIndex f ls = do
158 y <- S.fold (FL.findIndex f) (S.fromList ls)
159 case y of
160 Nothing ->
161 let fld = S.fold (FL.all $ neg f) (S.fromList ls)
162 in fld `shouldReturn` True
163 Just idx ->
164 if idx == 0
165 then
166 S.fold (FL.all f) (S.fromList []) `shouldReturn` True
167 else
168 S.fold (FL.all f) (S.fromList $ Prelude.take idx ls)
169 `shouldReturn` False
171predicate :: Int -> Bool
172predicate x = x * x < 100
174elemIndex :: Int -> [Int] -> Expectation
175elemIndex elm ls = do
176 y <- S.fold (FL.elemIndex elm) (S.fromList ls)
177 case y of
178 Nothing ->
179 let fld = S.fold (FL.any (== elm)) (S.fromList ls)
180 in fld `shouldReturn` False
181 Just idx ->
182 let fld = S.fold (FL.any (== elm)) (S.fromList $ Prelude.take idx ls)
183 in fld `shouldReturn` False
185null :: [Int] -> Expectation
186null ls =
187 S.fold FL.null (S.fromList ls)
188 `shouldReturn`
189 case ls of
190 [] -> True
191 _ -> False
193elem :: Int -> [Int] -> Expectation
194elem elm ls = do
195 y <- S.fold (FL.elem elm) (S.fromList ls)
196 let fld = S.fold (FL.any (== elm)) (S.fromList ls)
197 fld `shouldReturn` y
199notElem :: Int -> [Int] -> Expectation
200notElem elm ls = do
201 y <- S.fold (FL.notElem elm) (S.fromList ls)
202 let fld = S.fold (FL.any (== elm)) (S.fromList ls)
203 fld `shouldReturn` not y
205all :: (a -> Bool) -> [a] -> Expectation
206all f ls =
207 S.fold (FL.all f) (S.fromList ls) `shouldReturn` Prelude.all f ls
209any :: (a -> Bool) -> [a] -> Expectation
210any f ls = S.fold (FL.any f) (S.fromList ls) `shouldReturn` Prelude.any f ls
212and :: [Bool] -> Expectation
213and ls = S.fold FL.and (S.fromList ls) `shouldReturn` Prelude.and ls
215or :: [Bool] -> Expectation
216or ls = S.fold FL.or (S.fromList ls) `shouldReturn` Prelude.or ls
218take :: [Int] -> Property
219take ls =
220 forAll (chooseInt (-1, Prelude.length ls + 2)) $ \n ->
221 S.fold (F.take n FL.toList) (S.fromList ls)
222 `shouldReturn` Prelude.take n ls
224takeEndBy_ :: Property
225takeEndBy_ =
226 forAll (listOf (chooseInt (0, 1))) $ \ls ->
227 let p = (== 1)
228 f = F.takeEndBy_ p FL.toList
229 ys = Prelude.takeWhile (not . p) ls
230 in case S.fold f (S.fromList ls) of
231 Right xs -> checkListEqual xs ys
232 Left _ -> property False
234takeEndByOrMax :: Property
235takeEndByOrMax =
236 forAll (chooseInt (min_value, max_value)) $ \n ->
237 forAll (listOf (chooseInt (0, 1))) $ \ls ->
238 let p = (== 1)
239 f = F.takeEndBy_ p (F.take n FL.toList)
240 ys = Prelude.take n (Prelude.takeWhile (not . p) ls)
241 in case S.fold f (S.fromList ls) of
242 Right xs -> checkListEqual xs ys
243 Left _ -> property False
245chooseFloat :: (Float, Float) -> Gen Float
246chooseFloat = choose
248drain :: [Int] -> Expectation
249drain ls = S.fold FL.drain (S.fromList ls) `shouldReturn` ()
251drainBy :: [Int] -> Expectation
252drainBy ls = S.fold (FL.drainBy return) (S.fromList ls) `shouldReturn` ()
254mean :: Property
255mean =
256 forAll (listOf1 (chooseFloat (-100.0, 100.0)))
257 $ \ls0 -> withMaxSuccess 1000 $ monadicIO $ action ls0
259 where
261 action ls = do
262 v1 <- run $ S.fold FL.mean (S.fromList ls)
263 let v2 = Prelude.sum ls / fromIntegral (Prelude.length ls)
264 assert (abs (v1 - v2) < 0.0001)
266stdDev :: Property
267stdDev =
268 forAll (listOf1 (chooseFloat (-100.0, 100.0)))
269 $ \ls0 -> withMaxSuccess 1000 $ monadicIO $ action ls0
271 where
273 action ls = do
274 v1 <- run $ S.fold FL.stdDev (S.fromList ls)
275 let avg = Prelude.sum ls / fromIntegral (Prelude.length ls)
276 se = Prelude.sum (fmap (\x -> (x - avg) * (x - avg)) ls)
277 sd = sqrt $ se / fromIntegral (Prelude.length ls)
278 assert (abs (v1 - sd) < 0.0001 )
280variance :: Property
281variance =
282 forAll (listOf1 (chooseFloat (-100.0, 100.0)))
283 $ \ls0 -> withMaxSuccess 1000 $ monadicIO $ action ls0
285 where
287 action ls = do
288 v1 <- run $ S.fold FL.variance (S.fromList ls)
289 let avg = Prelude.sum ls / fromIntegral (Prelude.length ls)
290 se = Prelude.sum (fmap (\x -> (x - avg) * (x - avg)) ls)
291 vr = se / fromIntegral (Prelude.length ls)
292 assert (abs (v1 - vr) < 0.01 )
294mconcat :: Property
295mconcat =
296 forAll (listOf1 (chooseInt (intMin, intMax)))
297 $ \ls0 -> monadicIO $ action ls0
299 where
301 action ls = do
302 v1 <- run $ S.fold FL.mconcat (S.map Sum $ S.fromList ls)
303 let v2 = Prelude.sum ls
304 assert (getSum v1 == v2)
306foldMap :: Property
307foldMap =
308 forAll (listOf1 (chooseInt (intMin, intMax)))
309 $ \ls0 -> monadicIO $ action ls0
311 where
313 action ls = do
314 v1 <- run $ S.fold (FL.foldMap Sum) $ S.fromList ls
315 let v2 = Prelude.sum ls
316 assert (getSum v1 == v2)
318foldMapM :: Property
319foldMapM =
320 forAll (listOf1 (chooseInt (intMin, intMax)))
321 $ \ls0 -> monadicIO $ action ls0
323 where
325 action ls = do
326 v1 <- run $ S.fold (FL.foldMapM (return . Sum)) $ S.fromList ls
327 let v2 = Prelude.sum ls
328 assert (getSum v1 == v2)
330lookup :: Property
331lookup =
332 forAll (chooseInt (1, 15))
333 $ \key0 ->monadicIO $ action key0
335 where
337 action key = do
338 let ls = [(1, "first"), (2, "second"), (3, "third"), (4, "fourth")
339 , (5, "fifth"), (6, "fifth+first"), (7, "fifth+second")
340 , (8, "fifth+third"), (9, "fifth+fourth")
341 , (10, "fifth+fifth")]
342 v1 <- run $ S.fold (FL.lookup key) $ S.fromList ls
343 let v2 = Prelude.lookup key ls
344 assert (v1 == v2)
346rmapM :: Property
347rmapM =
348 forAll (listOf1 (chooseInt (intMin, intMax)))
349 $ \ls0 -> monadicIO $ action ls0
351 where
353 action ls = do
354 let addLen x = return $ x + Prelude.length ls
355 fld = FL.rmapM addLen FL.sum
356 v2 = foldl (+) (Prelude.length ls) ls
357 v1 <- run $ S.fold fld $ S.fromList ls
358 assert (v1 == v2)
360teeWithLength :: Property
361teeWithLength =
362 forAll (listOf1 (chooseInt (intMin, intMax)))
363 $ \ls0 -> monadicIO $ action ls0
365 where
367 action ls = do
368 v1 <- run $ S.fold (FL.tee FL.sum FL.length) $ S.fromList ls
369 let v2 = Prelude.sum ls
370 v3 = Prelude.length ls
371 assert (v1 == (v2, v3))
373teeWithMax :: Property
374teeWithMax =
375 forAll (listOf1 (chooseInt (intMin, intMax)))
376 $ \ls0 -> monadicIO $ action ls0
378 where
380 action ls = do
381 v1 <- run $ S.fold (FL.tee FL.sum FL.maximum) $ S.fromList ls
382 let v2 = Prelude.sum ls
383 v3 = foldMaybe (greater compare) intMin ls
384 assert (v1 == (v2, v3))
386distribute :: Property
387distribute =
388 forAll (listOf1 (chooseInt (intMin, intMax)))
389 $ \ls0 -> monadicIO $ action ls0
391 where
393 action ls = do
394 v1 <- run $ S.fold (FL.distribute [FL.sum, FL.length]) $ S.fromList ls
395 let v2 = Prelude.sum ls
396 v3 = Prelude.length ls
397 assert (v1 == [v2, v3])
399partition :: Property
400partition =
401 monadicIO $ do
402 v1 :: (Int, [String]) <-
403 run
404 $ S.fold (FL.partition FL.sum FL.toList)
405 $ S.fromList
406 [Left 1, Right "abc", Left 3, Right "xy", Right "pp2"]
407 let v2 = (4,["abc","xy","pp2"])
408 assert (v1 == v2)
410unzip :: Property
411unzip =
412 monadicIO $ do
413 v1 :: (Int, [String]) <-
414 run
415 $ S.fold (FL.unzip FL.sum FL.toList)
416 $ S.fromList [(1, "aa"), (2, "bb"), (3, "cc")]
417 let v2 = (6, ["aa", "bb", "cc"])
418 assert (v1 == v2)
420many :: Property
421many =
422 forAll (listOf (chooseInt (0, 100))) $ \lst ->
423 forAll (chooseInt (1, 100)) $ \i ->
424 monadicIO $ do
425 let strm = S.fromList lst
426 r1 <- S.fold (F.many (split i) F.toList) strm
427 r2 <- S.toList $ Stream.foldMany (split i) strm
428 assert $ r1 == r2
430 where
432 split i = F.take i F.toList
434headAndRest :: [Int] -> Property
435headAndRest ls = monadicIO $ do
436 (mbh, rest) <- run $ Stream.fold_ FL.head (S.fromList ls)
437 rests <- run $ S.toList rest
438 assert (mbh == headl ls)
439 listEquals (==) rests (taill ls)
441 where
443 taill :: [a] -> [a]
444 taill [] = []
445 taill (_:xs) = xs
447main :: IO ()
448main = hspec $ do
449 describe "Fold" $ do
450 -- Folds
451 -- Accumulators
452 prop "mconcat" Main.mconcat
453 prop "foldMap" Main.foldMap
454 prop "foldMapM" Main.foldMapM
456 prop "drain" Main.drain
457 prop "drainBy" Main.drainBy
458 prop "last" last
459 prop "length" Main.length
460 prop "sum" sum
461 prop "product" product
462 prop "maximumBy" $ maximumBy intMin compare
463 prop "maximum" $ maximum intMin
464 prop "minimumBy" $ minimumBy intMax compare
465 prop "minimum" $ minimum intMax
466 prop "mean" Main.mean
467 prop "stdDev" Main.stdDev
468 prop "variance" Main.variance
469 prop "rollingHashFirstN" rollingHashFirstN
471 prop "toList" toList
473 -- Terminating folds
474 prop "index" index
475 prop "head" head
476 prop "find" $ find predicate
477 prop "lookup" Main.lookup
478 prop "findIndex" $ findIndex predicate
479 prop "elemIndex" $ elemIndex 10
480 prop "null" null
481 prop "elem" $ elem 10
482 prop "notElem" $ notElem 10
483 prop "all" $ Main.all predicate
484 prop "any" $ Main.any predicate
485 prop "and" Main.and
486 prop "or" Main.or
488 -- Combinators
490 -- Transformation
491 -- rsequence
492 -- Functor instance
493 prop "rmapM" Main.rmapM
494 -- lmap/lmapM
496 -- Filtering
497 -- filter/filterM
498 -- catMaybes
499 prop "mapMaybe" mapMaybe
501 -- Trimming
502 prop "take" take
503 -- takeEndBy
504 prop "takeEndBy_" takeEndBy_
505 prop "takeEndByOrMax" takeEndByOrMax
507 -- Appending
508 -- serialWith
510 -- Distributing
511 -- tee
512 prop "teeWithLength" Main.teeWithLength
513 prop "teeWithMax" Main.teeWithMax
514 prop "distribute" Main.distribute
516 -- Partitioning
517 prop "partition" Main.partition
519 -- Unzipping
520 prop "unzip" Main.unzip
522 -- Nesting
523 prop "many" Main.many
524 -- concatMap
525 -- chunksOf
526 describe "FoldAndReturn s" $ do
527 prop "head from fold_" headAndRest