git.iko.soy/streamly
on 3feeec2 help sign in
streamly/test/Streamly/Test/Data/Fold.hs
530 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
447moduleName :: String
448moduleName = "Data.Fold"
450main :: IO ()
451main = hspec $ do
452 describe moduleName $ do
453 -- Folds
454 -- Accumulators
455 prop "mconcat" Main.mconcat
456 prop "foldMap" Main.foldMap
457 prop "foldMapM" Main.foldMapM
459 prop "drain" Main.drain
460 prop "drainBy" Main.drainBy
461 prop "last" last
462 prop "length" Main.length
463 prop "sum" sum
464 prop "product" product
465 prop "maximumBy" $ maximumBy intMin compare
466 prop "maximum" $ maximum intMin
467 prop "minimumBy" $ minimumBy intMax compare
468 prop "minimum" $ minimum intMax
469 prop "mean" Main.mean
470 prop "stdDev" Main.stdDev
471 prop "variance" Main.variance
472 prop "rollingHashFirstN" rollingHashFirstN
474 prop "toList" toList
476 -- Terminating folds
477 prop "index" index
478 prop "head" head
479 prop "find" $ find predicate
480 prop "lookup" Main.lookup
481 prop "findIndex" $ findIndex predicate
482 prop "elemIndex" $ elemIndex 10
483 prop "null" null
484 prop "elem" $ elem 10
485 prop "notElem" $ notElem 10
486 prop "all" $ Main.all predicate
487 prop "any" $ Main.any predicate
488 prop "and" Main.and
489 prop "or" Main.or
491 -- Combinators
493 -- Transformation
494 -- rsequence
495 -- Functor instance
496 prop "rmapM" Main.rmapM
497 -- lmap/lmapM
499 -- Filtering
500 -- filter/filterM
501 -- catMaybes
502 prop "mapMaybe" mapMaybe
504 -- Trimming
505 prop "take" take
506 -- takeEndBy
507 prop "takeEndBy_" takeEndBy_
508 prop "takeEndByOrMax" takeEndByOrMax
510 -- Appending
511 -- serialWith
513 -- Distributing
514 -- tee
515 prop "teeWithLength" Main.teeWithLength
516 prop "teeWithMax" Main.teeWithMax
517 prop "distribute" Main.distribute
519 -- Partitioning
520 prop "partition" Main.partition
522 -- Unzipping
523 prop "unzip" Main.unzip
525 -- Nesting
526 prop "many" Main.many
527 -- concatMap
528 -- chunksOf
530 prop "head from fold_" headAndRest