1{-# LANGUAGE CPP, ExistentialQuantification, MultiParamTypeClasses, FlexibleInstances, Rank2Types, BangPatterns, KindSignatures, GADTs, ScopedTypeVariables #-} 2 3-- | 4-- Module : Data.Vector.Fusion.Stream.Monadic 5-- Copyright : (c) Roman Leshchinskiy 2008-2010 6-- License : BSD-style 7-- 8-- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au> 9-- Stability : experimental 10-- Portability : non-portable 11-- 12-- Monadic stream combinators. 13-- 14 15module Data.Vector.Fusion.Stream.Monadic ( 16 Stream(..), Step(..), SPEC(..), 17 18 -- * Length 19 length, null, 20 21 -- * Construction 22 empty, singleton, cons, snoc, replicate, replicateM, generate, generateM, (++), 23 24 -- * Accessing elements 25 head, last, (!!), (!?), 26 27 -- * Substreams 28 slice, init, tail, take, drop, 29 30 -- * Mapping 31 map, mapM, mapM_, trans, unbox, concatMap, flatten, 32 33 -- * Zipping 34 indexed, indexedR, zipWithM_, 35 zipWithM, zipWith3M, zipWith4M, zipWith5M, zipWith6M, 36 zipWith, zipWith3, zipWith4, zipWith5, zipWith6, 37 zip, zip3, zip4, zip5, zip6, 38 39 -- * Comparisons 40 eqBy, cmpBy, 41 42 -- * Filtering 43 filter, filterM, uniq, mapMaybe, takeWhile, takeWhileM, dropWhile, dropWhileM, 44 45 -- * Searching 46 elem, notElem, find, findM, findIndex, findIndexM, 47 48 -- * Folding 49 foldl, foldlM, foldl1, foldl1M, foldM, fold1M, 50 foldl', foldlM', foldl1', foldl1M', foldM', fold1M', 51 foldr, foldrM, foldr1, foldr1M, 52 53 -- * Specialised folds 54 and, or, concatMapM, 55 56 -- * Unfolding 57 unfoldr, unfoldrM, 58 unfoldrN, unfoldrNM, 59 iterateN, iterateNM, 60 61 -- * Scans 62 prescanl, prescanlM, prescanl', prescanlM', 63 postscanl, postscanlM, postscanl', postscanlM', 64 scanl, scanlM, scanl', scanlM', 65 scanl1, scanl1M, scanl1', scanl1M', 66 67 -- * Enumerations 68 enumFromStepN, enumFromTo, enumFromThenTo, 69 70 -- * Conversions 71 toList, fromList, fromListN 72) where 73 74import Data.Vector.Fusion.Util ( Box(..) ) 75 76import Data.Char ( ord ) 77import GHC.Base ( unsafeChr ) 78import Control.Monad ( liftM ) 79import Prelude hiding ( length, null, 80 replicate, (++), 81 head, last, (!!), 82 init, tail, take, drop, 83 map, mapM, mapM_, concatMap, 84 zipWith, zipWith3, zip, zip3, 85 filter, takeWhile, dropWhile, 86 elem, notElem, 87 foldl, foldl1, foldr, foldr1, 88 and, or, 89 scanl, scanl1, 90 enumFromTo, enumFromThenTo ) 91 92import Data.Int ( Int8, Int16, Int32 ) 93import Data.Word ( Word8, Word16, Word32, Word64 ) 94 95#if !MIN_VERSION_base(4,8,0) 96import Data.Word ( Word8, Word16, Word32, Word, Word64 ) 97#endif 98 99#if __GLASGOW_HASKELL__ >= 708 100import GHC.Types ( SPEC(..) ) 101#elif __GLASGOW_HASKELL__ >= 700 102import GHC.Exts ( SpecConstrAnnotation(..) ) 103#endif 104 105#include "vector.h" 106#include "MachDeps.h" 107 108#if WORD_SIZE_IN_BITS > 32 109import Data.Int ( Int64 ) 110#endif 111 112#if __GLASGOW_HASKELL__ < 708 113data SPEC = SPEC | SPEC2 114#if __GLASGOW_HASKELL__ >= 700 115{-# ANN type SPEC ForceSpecConstr #-} 116#endif 117#endif 118 119emptyStream :: String 120{-# NOINLINE emptyStream #-} 121emptyStream = "empty stream" 122 123#define EMPTY_STREAM (\state -> ERROR state emptyStream) 124 125-- | Result of taking a single step in a stream 126data Step s a where 127 Yield :: a -> s -> Step s a 128 Skip :: s -> Step s a 129 Done :: Step s a 130 131instance Functor (Step s) where 132 {-# INLINE fmap #-} 133 fmap f (Yield x s) = Yield (f x) s 134 fmap _ (Skip s) = Skip s 135 fmap _ Done = Done 136 137-- | Monadic streams 138data Stream m a = forall s. Stream (s -> m (Step s a)) s 139 140-- Length 141-- ------ 142 143-- | Length of a 'Stream' 144length :: Monad m => Stream m a -> m Int 145{-# INLINE_FUSED length #-} 146length = foldl' (\n _ -> n+1) 0 147 148-- | Check if a 'Stream' is empty 149null :: Monad m => Stream m a -> m Bool 150{-# INLINE_FUSED null #-} 151null (Stream step t) = null_loop t 152 where 153 null_loop s = do 154 r <- step s 155 case r of 156 Yield _ _ -> return False 157 Skip s' -> null_loop s' 158 Done -> return True 159 160-- Construction 161-- ------------ 162 163-- | Empty 'Stream' 164empty :: Monad m => Stream m a 165{-# INLINE_FUSED empty #-} 166empty = Stream (const (return Done)) () 167 168-- | Singleton 'Stream' 169singleton :: Monad m => a -> Stream m a 170{-# INLINE_FUSED singleton #-} 171singleton x = Stream (return . step) True 172 where 173 {-# INLINE_INNER step #-} 174 step True = Yield x False 175 step False = Done 176 177-- | Replicate a value to a given length 178replicate :: Monad m => Int -> a -> Stream m a 179{-# INLINE_FUSED replicate #-} 180replicate n x = replicateM n (return x) 181 182-- | Yield a 'Stream' of values obtained by performing the monadic action the 183-- given number of times 184replicateM :: Monad m => Int -> m a -> Stream m a 185{-# INLINE_FUSED replicateM #-} 186replicateM n p = Stream step n 187 where 188 {-# INLINE_INNER step #-} 189 step i | i <= 0 = return Done 190 | otherwise = do { x <- p; return $ Yield x (i-1) } 191 192generate :: Monad m => Int -> (Int -> a) -> Stream m a 193{-# INLINE generate #-} 194generate n f = generateM n (return . f) 195 196-- | Generate a stream from its indices 197generateM :: Monad m => Int -> (Int -> m a) -> Stream m a 198{-# INLINE_FUSED generateM #-} 199generateM n f = n `seq` Stream step 0 200 where 201 {-# INLINE_INNER step #-} 202 step i | i < n = do 203 x <- f i 204 return $ Yield x (i+1) 205 | otherwise = return Done 206 207-- | Prepend an element 208cons :: Monad m => a -> Stream m a -> Stream m a 209{-# INLINE cons #-} 210cons x s = singleton x ++ s 211 212-- | Append an element 213snoc :: Monad m => Stream m a -> a -> Stream m a 214{-# INLINE snoc #-} 215snoc s x = s ++ singleton x 216 217infixr 5 ++ 218-- | Concatenate two 'Stream's 219(++) :: Monad m => Stream m a -> Stream m a -> Stream m a 220{-# INLINE_FUSED (++) #-} 221Stream stepa ta ++ Stream stepb tb = Stream step (Left ta) 222 where 223 {-# INLINE_INNER step #-} 224 step (Left sa) = do 225 r <- stepa sa 226 case r of 227 Yield x sa' -> return $ Yield x (Left sa') 228 Skip sa' -> return $ Skip (Left sa') 229 Done -> return $ Skip (Right tb) 230 step (Right sb) = do 231 r <- stepb sb 232 case r of 233 Yield x sb' -> return $ Yield x (Right sb') 234 Skip sb' -> return $ Skip (Right sb') 235 Done -> return $ Done 236 237-- Accessing elements 238-- ------------------ 239 240-- | First element of the 'Stream' or error if empty 241head :: Monad m => Stream m a -> m a 242{-# INLINE_FUSED head #-} 243head (Stream step t) = head_loop SPEC t 244 where 245 head_loop !_ s 246 = do 247 r <- step s 248 case r of 249 Yield x _ -> return x 250 Skip s' -> head_loop SPEC s' 251 Done -> EMPTY_STREAM "head" 252 253 254 255-- | Last element of the 'Stream' or error if empty 256last :: Monad m => Stream m a -> m a 257{-# INLINE_FUSED last #-} 258last (Stream step t) = last_loop0 SPEC t 259 where 260 last_loop0 !_ s 261 = do 262 r <- step s 263 case r of 264 Yield x s' -> last_loop1 SPEC x s' 265 Skip s' -> last_loop0 SPEC s' 266 Done -> EMPTY_STREAM "last" 267 268 last_loop1 !_ x s 269 = do 270 r <- step s 271 case r of 272 Yield y s' -> last_loop1 SPEC y s' 273 Skip s' -> last_loop1 SPEC x s' 274 Done -> return x 275 276infixl 9 !! 277-- | Element at the given position 278(!!) :: Monad m => Stream m a -> Int -> m a 279{-# INLINE (!!) #-} 280Stream step t !! j | j < 0 = ERROR "!!" "negative index" 281 | otherwise = index_loop SPEC t j 282 where 283 index_loop !_ s i 284 = i `seq` 285 do 286 r <- step s 287 case r of 288 Yield x s' | i == 0 -> return x 289 | otherwise -> index_loop SPEC s' (i-1) 290 Skip s' -> index_loop SPEC s' i 291 Done -> EMPTY_STREAM "!!" 292 293infixl 9 !? 294-- | Element at the given position or 'Nothing' if out of bounds 295(!?) :: Monad m => Stream m a -> Int -> m (Maybe a) 296{-# INLINE (!?) #-} 297Stream step t !? j = index_loop SPEC t j 298 where 299 index_loop !_ s i 300 = i `seq` 301 do 302 r <- step s 303 case r of 304 Yield x s' | i == 0 -> return (Just x) 305 | otherwise -> index_loop SPEC s' (i-1) 306 Skip s' -> index_loop SPEC s' i 307 Done -> return Nothing 308 309-- Substreams 310-- ---------- 311 312-- | Extract a substream of the given length starting at the given position. 313slice :: Monad m => Int -- ^ starting index 314 -> Int -- ^ length 315 -> Stream m a 316 -> Stream m a 317{-# INLINE slice #-} 318slice i n s = take n (drop i s) 319 320-- | All but the last element 321init :: Monad m => Stream m a -> Stream m a 322{-# INLINE_FUSED init #-} 323init (Stream step t) = Stream step' (Nothing, t) 324 where 325 {-# INLINE_INNER step' #-} 326 step' (Nothing, s) = liftM (\r -> 327 case r of 328 Yield x s' -> Skip (Just x, s') 329 Skip s' -> Skip (Nothing, s') 330 Done -> EMPTY_STREAM "init" 331 ) (step s) 332 333 step' (Just x, s) = liftM (\r -> 334 case r of 335 Yield y s' -> Yield x (Just y, s') 336 Skip s' -> Skip (Just x, s') 337 Done -> Done 338 ) (step s) 339 340-- | All but the first element 341tail :: Monad m => Stream m a -> Stream m a 342{-# INLINE_FUSED tail #-} 343tail (Stream step t) = Stream step' (Left t) 344 where 345 {-# INLINE_INNER step' #-} 346 step' (Left s) = liftM (\r -> 347 case r of 348 Yield _ s' -> Skip (Right s') 349 Skip s' -> Skip (Left s') 350 Done -> EMPTY_STREAM "tail" 351 ) (step s) 352 353 step' (Right s) = liftM (\r -> 354 case r of 355 Yield x s' -> Yield x (Right s') 356 Skip s' -> Skip (Right s') 357 Done -> Done 358 ) (step s) 359 360-- | The first @n@ elements 361take :: Monad m => Int -> Stream m a -> Stream m a 362{-# INLINE_FUSED take #-} 363take n (Stream step t) = n `seq` Stream step' (t, 0) 364 where 365 {-# INLINE_INNER step' #-} 366 step' (s, i) | i < n = liftM (\r -> 367 case r of 368 Yield x s' -> Yield x (s', i+1) 369 Skip s' -> Skip (s', i) 370 Done -> Done 371 ) (step s) 372 step' (_, _) = return Done 373 374-- | All but the first @n@ elements 375drop :: Monad m => Int -> Stream m a -> Stream m a 376{-# INLINE_FUSED drop #-} 377drop n (Stream step t) = Stream step' (t, Just n) 378 where 379 {-# INLINE_INNER step' #-} 380 step' (s, Just i) | i > 0 = liftM (\r -> 381 case r of 382 Yield _ s' -> Skip (s', Just (i-1)) 383 Skip s' -> Skip (s', Just i) 384 Done -> Done 385 ) (step s) 386 | otherwise = return $ Skip (s, Nothing) 387 388 step' (s, Nothing) = liftM (\r -> 389 case r of 390 Yield x s' -> Yield x (s', Nothing) 391 Skip s' -> Skip (s', Nothing) 392 Done -> Done 393 ) (step s) 394 395-- Mapping 396-- ------- 397 398instance Monad m => Functor (Stream m) where 399 {-# INLINE fmap #-} 400 fmap = map 401 402-- | Map a function over a 'Stream' 403map :: Monad m => (a -> b) -> Stream m a -> Stream m b 404{-# INLINE map #-} 405map f = mapM (return . f) 406 407 408-- | Map a monadic function over a 'Stream' 409mapM :: Monad m => (a -> m b) -> Stream m a -> Stream m b 410{-# INLINE_FUSED mapM #-} 411mapM f (Stream step t) = Stream step' t 412 where 413 {-# INLINE_INNER step' #-} 414 step' s = do 415 r <- step s 416 case r of 417 Yield x s' -> liftM (`Yield` s') (f x) 418 Skip s' -> return (Skip s') 419 Done -> return Done 420 421consume :: Monad m => Stream m a -> m () 422{-# INLINE_FUSED consume #-} 423consume (Stream step t) = consume_loop SPEC t 424 where 425 consume_loop !_ s 426 = do 427 r <- step s 428 case r of 429 Yield _ s' -> consume_loop SPEC s' 430 Skip s' -> consume_loop SPEC s' 431 Done -> return () 432 433-- | Execute a monadic action for each element of the 'Stream' 434mapM_ :: Monad m => (a -> m b) -> Stream m a -> m () 435{-# INLINE_FUSED mapM_ #-} 436mapM_ m = consume . mapM m 437 438-- | Transform a 'Stream' to use a different monad 439trans :: (Monad m, Monad m') 440 => (forall z. m z -> m' z) -> Stream m a -> Stream m' a 441{-# INLINE_FUSED trans #-} 442trans f (Stream step s) = Stream (f . step) s 443 444unbox :: Monad m => Stream m (Box a) -> Stream m a 445{-# INLINE_FUSED unbox #-} 446unbox (Stream step t) = Stream step' t 447 where 448 {-# INLINE_INNER step' #-} 449 step' s = do 450 r <- step s 451 case r of 452 Yield (Box x) s' -> return $ Yield x s' 453 Skip s' -> return $ Skip s' 454 Done -> return $ Done 455 456-- Zipping 457-- ------- 458 459-- | Pair each element in a 'Stream' with its index 460indexed :: Monad m => Stream m a -> Stream m (Int,a) 461{-# INLINE_FUSED indexed #-} 462indexed (Stream step t) = Stream step' (t,0) 463 where 464 {-# INLINE_INNER step' #-} 465 step' (s,i) = i `seq` 466 do 467 r <- step s 468 case r of 469 Yield x s' -> return $ Yield (i,x) (s', i+1) 470 Skip s' -> return $ Skip (s', i) 471 Done -> return Done 472 473-- | Pair each element in a 'Stream' with its index, starting from the right 474-- and counting down 475indexedR :: Monad m => Int -> Stream m a -> Stream m (Int,a) 476{-# INLINE_FUSED indexedR #-} 477indexedR m (Stream step t) = Stream step' (t,m) 478 where 479 {-# INLINE_INNER step' #-} 480 step' (s,i) = i `seq` 481 do 482 r <- step s 483 case r of 484 Yield x s' -> let i' = i-1 485 in 486 return $ Yield (i',x) (s', i') 487 Skip s' -> return $ Skip (s', i) 488 Done -> return Done 489 490-- | Zip two 'Stream's with the given monadic function 491zipWithM :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> Stream m c 492{-# INLINE_FUSED zipWithM #-} 493zipWithM f (Stream stepa ta) (Stream stepb tb) = Stream step (ta, tb, Nothing) 494 where 495 {-# INLINE_INNER step #-} 496 step (sa, sb, Nothing) = liftM (\r -> 497 case r of 498 Yield x sa' -> Skip (sa', sb, Just x) 499 Skip sa' -> Skip (sa', sb, Nothing) 500 Done -> Done 501 ) (stepa sa) 502 503 step (sa, sb, Just x) = do 504 r <- stepb sb 505 case r of 506 Yield y sb' -> 507 do 508 z <- f x y 509 return $ Yield z (sa, sb', Nothing) 510 Skip sb' -> return $ Skip (sa, sb', Just x) 511 Done -> return $ Done 512 513-- FIXME: This might expose an opportunity for inplace execution. 514{-# RULES 515 516"zipWithM xs xs [Vector.Stream]" forall f xs. 517 zipWithM f xs xs = mapM (\x -> f x x) xs #-} 518 519 520zipWithM_ :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> m () 521{-# INLINE zipWithM_ #-} 522zipWithM_ f sa sb = consume (zipWithM f sa sb) 523 524zipWith3M :: Monad m => (a -> b -> c -> m d) -> Stream m a -> Stream m b -> Stream m c -> Stream m d 525{-# INLINE_FUSED zipWith3M #-} 526zipWith3M f (Stream stepa ta) 527 (Stream stepb tb) 528 (Stream stepc tc) = Stream step (ta, tb, tc, Nothing) 529 where 530 {-# INLINE_INNER step #-} 531 step (sa, sb, sc, Nothing) = do 532 r <- stepa sa 533 return $ case r of 534 Yield x sa' -> Skip (sa', sb, sc, Just (x, Nothing)) 535 Skip sa' -> Skip (sa', sb, sc, Nothing) 536 Done -> Done 537 538 step (sa, sb, sc, Just (x, Nothing)) = do 539 r <- stepb sb 540 return $ case r of 541 Yield y sb' -> Skip (sa, sb', sc, Just (x, Just y)) 542 Skip sb' -> Skip (sa, sb', sc, Just (x, Nothing)) 543 Done -> Done 544 545 step (sa, sb, sc, Just (x, Just y)) = do 546 r <- stepc sc 547 case r of 548 Yield z sc' -> f x y z >>= (\res -> return $ Yield res (sa, sb, sc', Nothing)) 549 Skip sc' -> return $ Skip (sa, sb, sc', Just (x, Just y)) 550 Done -> return $ Done 551 552zipWith4M :: Monad m => (a -> b -> c -> d -> m e) 553 -> Stream m a -> Stream m b -> Stream m c -> Stream m d 554 -> Stream m e 555{-# INLINE zipWith4M #-} 556zipWith4M f sa sb sc sd 557 = zipWithM (\(a,b) (c,d) -> f a b c d) (zip sa sb) (zip sc sd) 558 559zipWith5M :: Monad m => (a -> b -> c -> d -> e -> m f) 560 -> Stream m a -> Stream m b -> Stream m c -> Stream m d 561 -> Stream m e -> Stream m f 562{-# INLINE zipWith5M #-} 563zipWith5M f sa sb sc sd se 564 = zipWithM (\(a,b,c) (d,e) -> f a b c d e) (zip3 sa sb sc) (zip sd se) 565 566zipWith6M :: Monad m => (a -> b -> c -> d -> e -> f -> m g) 567 -> Stream m a -> Stream m b -> Stream m c -> Stream m d 568 -> Stream m e -> Stream m f -> Stream m g 569{-# INLINE zipWith6M #-} 570zipWith6M fn sa sb sc sd se sf 571 = zipWithM (\(a,b,c) (d,e,f) -> fn a b c d e f) (zip3 sa sb sc) 572 (zip3 sd se sf) 573 574zipWith :: Monad m => (a -> b -> c) -> Stream m a -> Stream m b -> Stream m c 575{-# INLINE zipWith #-} 576zipWith f = zipWithM (\a b -> return (f a b)) 577 578zipWith3 :: Monad m => (a -> b -> c -> d) 579 -> Stream m a -> Stream m b -> Stream m c -> Stream m d 580{-# INLINE zipWith3 #-} 581zipWith3 f = zipWith3M (\a b c -> return (f a b c)) 582 583zipWith4 :: Monad m => (a -> b -> c -> d -> e) 584 -> Stream m a -> Stream m b -> Stream m c -> Stream m d 585 -> Stream m e 586{-# INLINE zipWith4 #-} 587zipWith4 f = zipWith4M (\a b c d -> return (f a b c d)) 588 589zipWith5 :: Monad m => (a -> b -> c -> d -> e -> f) 590 -> Stream m a -> Stream m b -> Stream m c -> Stream m d 591 -> Stream m e -> Stream m f 592{-# INLINE zipWith5 #-} 593zipWith5 f = zipWith5M (\a b c d e -> return (f a b c d e)) 594 595zipWith6 :: Monad m => (a -> b -> c -> d -> e -> f -> g) 596 -> Stream m a -> Stream m b -> Stream m c -> Stream m d 597 -> Stream m e -> Stream m f -> Stream m g 598{-# INLINE zipWith6 #-} 599zipWith6 fn = zipWith6M (\a b c d e f -> return (fn a b c d e f)) 600 601zip :: Monad m => Stream m a -> Stream m b -> Stream m (a,b) 602{-# INLINE zip #-} 603zip = zipWith (,) 604 605zip3 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m (a,b,c) 606{-# INLINE zip3 #-} 607zip3 = zipWith3 (,,) 608 609zip4 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d 610 -> Stream m (a,b,c,d) 611{-# INLINE zip4 #-} 612zip4 = zipWith4 (,,,) 613 614zip5 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d 615 -> Stream m e -> Stream m (a,b,c,d,e) 616{-# INLINE zip5 #-} 617zip5 = zipWith5 (,,,,) 618 619zip6 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d 620 -> Stream m e -> Stream m f -> Stream m (a,b,c,d,e,f) 621{-# INLINE zip6 #-} 622zip6 = zipWith6 (,,,,,) 623 624-- Comparisons 625-- ----------- 626 627-- | Check if two 'Stream's are equal 628eqBy :: (Monad m) => (a -> b -> Bool) -> Stream m a -> Stream m b -> m Bool 629{-# INLINE_FUSED eqBy #-} 630eqBy eq (Stream step1 t1) (Stream step2 t2) = eq_loop0 SPEC t1 t2 631 where 632 eq_loop0 !_ s1 s2 = do 633 r <- step1 s1 634 case r of 635 Yield x s1' -> eq_loop1 SPEC x s1' s2 636 Skip s1' -> eq_loop0 SPEC s1' s2 637 Done -> eq_null s2 638 639 eq_loop1 !_ x s1 s2 = do 640 r <- step2 s2 641 case r of 642 Yield y s2' 643 | eq x y -> eq_loop0 SPEC s1 s2' 644 | otherwise -> return False 645 Skip s2' -> eq_loop1 SPEC x s1 s2' 646 Done -> return False 647 648 eq_null s2 = do 649 r <- step2 s2 650 case r of 651 Yield _ _ -> return False 652 Skip s2' -> eq_null s2' 653 Done -> return True 654 655-- | Lexicographically compare two 'Stream's 656cmpBy :: (Monad m) => (a -> b -> Ordering) -> Stream m a -> Stream m b -> m Ordering 657{-# INLINE_FUSED cmpBy #-} 658cmpBy cmp (Stream step1 t1) (Stream step2 t2) = cmp_loop0 SPEC t1 t2 659 where 660 cmp_loop0 !_ s1 s2 = do 661 r <- step1 s1 662 case r of 663 Yield x s1' -> cmp_loop1 SPEC x s1' s2 664 Skip s1' -> cmp_loop0 SPEC s1' s2 665 Done -> cmp_null s2 666 667 cmp_loop1 !_ x s1 s2 = do 668 r <- step2 s2 669 case r of 670 Yield y s2' -> case x `cmp` y of 671 EQ -> cmp_loop0 SPEC s1 s2' 672 c -> return c 673 Skip s2' -> cmp_loop1 SPEC x s1 s2' 674 Done -> return GT 675 676 cmp_null s2 = do 677 r <- step2 s2 678 case r of 679 Yield _ _ -> return LT 680 Skip s2' -> cmp_null s2' 681 Done -> return EQ 682 683-- Filtering 684-- --------- 685 686-- | Drop elements which do not satisfy the predicate 687filter :: Monad m => (a -> Bool) -> Stream m a -> Stream m a 688{-# INLINE filter #-} 689filter f = filterM (return . f) 690 691mapMaybe :: Monad m => (a -> Maybe b) -> Stream m a -> Stream m b 692{-# INLINE_FUSED mapMaybe #-} 693mapMaybe f (Stream step t) = Stream step' t 694 where 695 {-# INLINE_INNER step' #-} 696 step' s = do 697 r <- step s 698 case r of 699 Yield x s' -> do 700 return $ case f x of 701 Nothing -> Skip s' 702 Just b' -> Yield b' s' 703 Skip s' -> return $ Skip s' 704 Done -> return $ Done 705 706-- | Drop elements which do not satisfy the monadic predicate 707filterM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a 708{-# INLINE_FUSED filterM #-} 709filterM f (Stream step t) = Stream step' t 710 where 711 {-# INLINE_INNER step' #-} 712 step' s = do 713 r <- step s 714 case r of 715 Yield x s' -> do 716 b <- f x 717 return $ if b then Yield x s' 718 else Skip s' 719 Skip s' -> return $ Skip s' 720 Done -> return $ Done 721 722-- | Drop repeated adjacent elements. 723uniq :: (Eq a, Monad m) => Stream m a -> Stream m a 724{-# INLINE_FUSED uniq #-} 725uniq (Stream step st) = Stream step' (Nothing,st) 726 where 727 {-# INLINE_INNER step' #-} 728 step' (Nothing, s) = do r <- step s 729 case r of 730 Yield x s' -> return $ Yield x (Just x , s') 731 Skip s' -> return $ Skip (Nothing, s') 732 Done -> return Done 733 step' (Just x0, s) = do r <- step s 734 case r of 735 Yield x s' | x == x0 -> return $ Skip (Just x0, s') 736 | otherwise -> return $ Yield x (Just x , s') 737 Skip s' -> return $ Skip (Just x0, s') 738 Done -> return Done 739 740-- | Longest prefix of elements that satisfy the predicate 741takeWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a 742{-# INLINE takeWhile #-} 743takeWhile f = takeWhileM (return . f) 744 745-- | Longest prefix of elements that satisfy the monadic predicate 746takeWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a 747{-# INLINE_FUSED takeWhileM #-} 748takeWhileM f (Stream step t) = Stream step' t 749 where 750 {-# INLINE_INNER step' #-} 751 step' s = do 752 r <- step s 753 case r of 754 Yield x s' -> do 755 b <- f x 756 return $ if b then Yield x s' else Done 757 Skip s' -> return $ Skip s' 758 Done -> return $ Done 759 760-- | Drop the longest prefix of elements that satisfy the predicate 761dropWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a 762{-# INLINE dropWhile #-} 763dropWhile f = dropWhileM (return . f) 764 765data DropWhile s a = DropWhile_Drop s | DropWhile_Yield a s | DropWhile_Next s 766 767-- | Drop the longest prefix of elements that satisfy the monadic predicate 768dropWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a 769{-# INLINE_FUSED dropWhileM #-} 770dropWhileM f (Stream step t) = Stream step' (DropWhile_Drop t) 771 where 772 -- NOTE: we jump through hoops here to have only one Yield; local data 773 -- declarations would be nice! 774 775 {-# INLINE_INNER step' #-} 776 step' (DropWhile_Drop s) 777 = do 778 r <- step s 779 case r of 780 Yield x s' -> do 781 b <- f x 782 return $ if b then Skip (DropWhile_Drop s') 783 else Skip (DropWhile_Yield x s') 784 Skip s' -> return $ Skip (DropWhile_Drop s') 785 Done -> return $ Done 786 787 step' (DropWhile_Yield x s) = return $ Yield x (DropWhile_Next s) 788 789 step' (DropWhile_Next s) 790 = liftM (\r -> 791 case r of 792 Yield x s' -> Skip (DropWhile_Yield x s') 793 Skip s' -> Skip (DropWhile_Next s') 794 Done -> Done 795 ) (step s) 796 797-- Searching 798-- --------- 799 800infix 4 `elem` 801-- | Check whether the 'Stream' contains an element 802elem :: (Monad m, Eq a) => a -> Stream m a -> m Bool 803{-# INLINE_FUSED elem #-} 804elem x (Stream step t) = elem_loop SPEC t 805 where 806 elem_loop !_ s 807 = do 808 r <- step s 809 case r of 810 Yield y s' | x == y -> return True 811 | otherwise -> elem_loop SPEC s' 812 Skip s' -> elem_loop SPEC s' 813 Done -> return False 814 815infix 4 `notElem` 816-- | Inverse of `elem` 817notElem :: (Monad m, Eq a) => a -> Stream m a -> m Bool 818{-# INLINE notElem #-} 819notElem x s = liftM not (elem x s) 820 821-- | Yield 'Just' the first element that satisfies the predicate or 'Nothing' 822-- if no such element exists. 823find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a) 824{-# INLINE find #-} 825find f = findM (return . f) 826 827-- | Yield 'Just' the first element that satisfies the monadic predicate or 828-- 'Nothing' if no such element exists. 829findM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe a) 830{-# INLINE_FUSED findM #-} 831findM f (Stream step t) = find_loop SPEC t 832 where 833 find_loop !_ s 834 = do 835 r <- step s 836 case r of 837 Yield x s' -> do 838 b <- f x 839 if b then return $ Just x 840 else find_loop SPEC s' 841 Skip s' -> find_loop SPEC s' 842 Done -> return Nothing 843 844-- | Yield 'Just' the index of the first element that satisfies the predicate 845-- or 'Nothing' if no such element exists. 846findIndex :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe Int) 847{-# INLINE_FUSED findIndex #-} 848findIndex f = findIndexM (return . f) 849 850-- | Yield 'Just' the index of the first element that satisfies the monadic 851-- predicate or 'Nothing' if no such element exists. 852findIndexM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe Int) 853{-# INLINE_FUSED findIndexM #-} 854findIndexM f (Stream step t) = findIndex_loop SPEC t 0 855 where 856 findIndex_loop !_ s i 857 = do 858 r <- step s 859 case r of 860 Yield x s' -> do 861 b <- f x 862 if b then return $ Just i 863 else findIndex_loop SPEC s' (i+1) 864 Skip s' -> findIndex_loop SPEC s' i 865 Done -> return Nothing 866 867-- Folding 868-- ------- 869 870-- | Left fold 871foldl :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a 872{-# INLINE foldl #-} 873foldl f = foldlM (\a b -> return (f a b)) 874 875-- | Left fold with a monadic operator 876foldlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a 877{-# INLINE_FUSED foldlM #-} 878foldlM m w (Stream step t) = foldlM_loop SPEC w t 879 where 880 foldlM_loop !_ z s 881 = do 882 r <- step s 883 case r of 884 Yield x s' -> do { z' <- m z x; foldlM_loop SPEC z' s' } 885 Skip s' -> foldlM_loop SPEC z s' 886 Done -> return z 887 888-- | Same as 'foldlM' 889foldM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a 890{-# INLINE foldM #-} 891foldM = foldlM 892 893-- | Left fold over a non-empty 'Stream' 894foldl1 :: Monad m => (a -> a -> a) -> Stream m a -> m a 895{-# INLINE foldl1 #-} 896foldl1 f = foldl1M (\a b -> return (f a b)) 897 898-- | Left fold over a non-empty 'Stream' with a monadic operator 899foldl1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a 900{-# INLINE_FUSED foldl1M #-} 901foldl1M f (Stream step t) = foldl1M_loop SPEC t 902 where 903 foldl1M_loop !_ s 904 = do 905 r <- step s 906 case r of 907 Yield x s' -> foldlM f x (Stream step s') 908 Skip s' -> foldl1M_loop SPEC s' 909 Done -> EMPTY_STREAM "foldl1M" 910 911-- | Same as 'foldl1M' 912fold1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a 913{-# INLINE fold1M #-} 914fold1M = foldl1M 915 916-- | Left fold with a strict accumulator 917foldl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a 918{-# INLINE foldl' #-} 919foldl' f = foldlM' (\a b -> return (f a b)) 920 921-- | Left fold with a strict accumulator and a monadic operator 922foldlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a 923{-# INLINE_FUSED foldlM' #-} 924foldlM' m w (Stream step t) = foldlM'_loop SPEC w t 925 where 926 foldlM'_loop !_ z s 927 = z `seq` 928 do 929 r <- step s 930 case r of 931 Yield x s' -> do { z' <- m z x; foldlM'_loop SPEC z' s' } 932 Skip s' -> foldlM'_loop SPEC z s' 933 Done -> return z 934 935-- | Same as 'foldlM'' 936foldM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a 937{-# INLINE foldM' #-} 938foldM' = foldlM' 939 940-- | Left fold over a non-empty 'Stream' with a strict accumulator 941foldl1' :: Monad m => (a -> a -> a) -> Stream m a -> m a 942{-# INLINE foldl1' #-} 943foldl1' f = foldl1M' (\a b -> return (f a b)) 944 945-- | Left fold over a non-empty 'Stream' with a strict accumulator and a 946-- monadic operator 947foldl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a 948{-# INLINE_FUSED foldl1M' #-} 949foldl1M' f (Stream step t) = foldl1M'_loop SPEC t 950 where 951 foldl1M'_loop !_ s 952 = do 953 r <- step s 954 case r of 955 Yield x s' -> foldlM' f x (Stream step s') 956 Skip s' -> foldl1M'_loop SPEC s' 957 Done -> EMPTY_STREAM "foldl1M'" 958 959-- | Same as 'foldl1M'' 960fold1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a 961{-# INLINE fold1M' #-} 962fold1M' = foldl1M' 963 964-- | Right fold 965foldr :: Monad m => (a -> b -> b) -> b -> Stream m a -> m b 966{-# INLINE foldr #-} 967foldr f = foldrM (\a b -> return (f a b)) 968 969-- | Right fold with a monadic operator 970foldrM :: Monad m => (a -> b -> m b) -> b -> Stream m a -> m b 971{-# INLINE_FUSED foldrM #-} 972foldrM f z (Stream step t) = foldrM_loop SPEC t 973 where 974 foldrM_loop !_ s 975 = do 976 r <- step s 977 case r of 978 Yield x s' -> f x =<< foldrM_loop SPEC s' 979 Skip s' -> foldrM_loop SPEC s' 980 Done -> return z 981 982-- | Right fold over a non-empty stream 983foldr1 :: Monad m => (a -> a -> a) -> Stream m a -> m a 984{-# INLINE foldr1 #-} 985foldr1 f = foldr1M (\a b -> return (f a b)) 986 987-- | Right fold over a non-empty stream with a monadic operator 988foldr1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a 989{-# INLINE_FUSED foldr1M #-} 990foldr1M f (Stream step t) = foldr1M_loop0 SPEC t 991 where 992 foldr1M_loop0 !_ s 993 = do 994 r <- step s 995 case r of 996 Yield x s' -> foldr1M_loop1 SPEC x s' 997 Skip s' -> foldr1M_loop0 SPEC s' 998 Done -> EMPTY_STREAM "foldr1M" 999 1000 foldr1M_loop1 !_ x s 1001 = do 1002 r <- step s 1003 case r of 1004 Yield y s' -> f x =<< foldr1M_loop1 SPEC y s' 1005 Skip s' -> foldr1M_loop1 SPEC x s' 1006 Done -> return x 1007 1008-- Specialised folds 1009-- ----------------- 1010 1011and :: Monad m => Stream m Bool -> m Bool 1012{-# INLINE_FUSED and #-} 1013and (Stream step t) = and_loop SPEC t 1014 where 1015 and_loop !_ s 1016 = do 1017 r <- step s 1018 case r of 1019 Yield False _ -> return False 1020 Yield True s' -> and_loop SPEC s' 1021 Skip s' -> and_loop SPEC s' 1022 Done -> return True 1023 1024or :: Monad m => Stream m Bool -> m Bool 1025{-# INLINE_FUSED or #-} 1026or (Stream step t) = or_loop SPEC t 1027 where 1028 or_loop !_ s 1029 = do 1030 r <- step s 1031 case r of 1032 Yield False s' -> or_loop SPEC s' 1033 Yield True _ -> return True 1034 Skip s' -> or_loop SPEC s' 1035 Done -> return False 1036 1037concatMap :: Monad m => (a -> Stream m b) -> Stream m a -> Stream m b 1038{-# INLINE concatMap #-} 1039concatMap f = concatMapM (return . f) 1040 1041concatMapM :: Monad m => (a -> m (Stream m b)) -> Stream m a -> Stream m b 1042{-# INLINE_FUSED concatMapM #-} 1043concatMapM f (Stream step t) = Stream concatMap_go (Left t) 1044 where 1045 concatMap_go (Left s) = do 1046 r <- step s 1047 case r of 1048 Yield a s' -> do 1049 b_stream <- f a 1050 return $ Skip (Right (b_stream, s')) 1051 Skip s' -> return $ Skip (Left s') 1052 Done -> return Done 1053 concatMap_go (Right (Stream inner_step inner_s, s)) = do 1054 r <- inner_step inner_s 1055 case r of 1056 Yield b inner_s' -> return $ Yield b (Right (Stream inner_step inner_s', s)) 1057 Skip inner_s' -> return $ Skip (Right (Stream inner_step inner_s', s)) 1058 Done -> return $ Skip (Left s) 1059 1060-- | Create a 'Stream' of values from a 'Stream' of streamable things 1061flatten :: Monad m => (a -> m s) -> (s -> m (Step s b)) -> Stream m a -> Stream m b 1062{-# INLINE_FUSED flatten #-} 1063flatten mk istep (Stream ostep u) = Stream step (Left u) 1064 where 1065 {-# INLINE_INNER step #-} 1066 step (Left t) = do 1067 r <- ostep t 1068 case r of 1069 Yield a t' -> do 1070 s <- mk a 1071 s `seq` return (Skip (Right (s,t'))) 1072 Skip t' -> return $ Skip (Left t') 1073 Done -> return $ Done 1074 1075 1076 step (Right (s,t)) = do 1077 r <- istep s 1078 case r of 1079 Yield x s' -> return $ Yield x (Right (s',t)) 1080 Skip s' -> return $ Skip (Right (s',t)) 1081 Done -> return $ Skip (Left t) 1082 1083-- Unfolding 1084-- --------- 1085 1086-- | Unfold 1087unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a 1088{-# INLINE_FUSED unfoldr #-} 1089unfoldr f = unfoldrM (return . f) 1090 1091-- | Unfold with a monadic function 1092unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a 1093{-# INLINE_FUSED unfoldrM #-} 1094unfoldrM f t = Stream step t 1095 where 1096 {-# INLINE_INNER step #-} 1097 step s = liftM (\r -> 1098 case r of 1099 Just (x, s') -> Yield x s' 1100 Nothing -> Done 1101 ) (f s) 1102 1103unfoldrN :: Monad m => Int -> (s -> Maybe (a, s)) -> s -> Stream m a 1104{-# INLINE_FUSED unfoldrN #-} 1105unfoldrN n f = unfoldrNM n (return . f) 1106 1107-- | Unfold at most @n@ elements with a monadic functions 1108unfoldrNM :: Monad m => Int -> (s -> m (Maybe (a, s))) -> s -> Stream m a 1109{-# INLINE_FUSED unfoldrNM #-} 1110unfoldrNM m f t = Stream step (t,m) 1111 where 1112 {-# INLINE_INNER step #-} 1113 step (s,n) | n <= 0 = return Done 1114 | otherwise = liftM (\r -> 1115 case r of 1116 Just (x,s') -> Yield x (s',n-1) 1117 Nothing -> Done 1118 ) (f s) 1119 1120-- | Apply monadic function n times to value. Zeroth element is original value. 1121iterateNM :: Monad m => Int -> (a -> m a) -> a -> Stream m a 1122{-# INLINE_FUSED iterateNM #-} 1123iterateNM n f x0 = Stream step (x0,n) 1124 where 1125 {-# INLINE_INNER step #-} 1126 step (x,i) | i <= 0 = return Done 1127 | i == n = return $ Yield x (x,i-1) 1128 | otherwise = do a <- f x 1129 return $ Yield a (a,i-1) 1130 1131-- | Apply function n times to value. Zeroth element is original value. 1132iterateN :: Monad m => Int -> (a -> a) -> a -> Stream m a 1133{-# INLINE_FUSED iterateN #-} 1134iterateN n f x0 = iterateNM n (return . f) x0 1135 1136-- Scans 1137-- ----- 1138 1139-- | Prefix scan 1140prescanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a 1141{-# INLINE prescanl #-} 1142prescanl f = prescanlM (\a b -> return (f a b)) 1143 1144-- | Prefix scan with a monadic operator 1145prescanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a 1146{-# INLINE_FUSED prescanlM #-} 1147prescanlM f w (Stream step t) = Stream step' (t,w) 1148 where 1149 {-# INLINE_INNER step' #-} 1150 step' (s,x) = do 1151 r <- step s 1152 case r of 1153 Yield y s' -> do 1154 z <- f x y 1155 return $ Yield x (s', z) 1156 Skip s' -> return $ Skip (s', x) 1157 Done -> return Done 1158 1159-- | Prefix scan with strict accumulator 1160prescanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a 1161{-# INLINE prescanl' #-} 1162prescanl' f = prescanlM' (\a b -> return (f a b)) 1163 1164-- | Prefix scan with strict accumulator and a monadic operator 1165prescanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a 1166{-# INLINE_FUSED prescanlM' #-} 1167prescanlM' f w (Stream step t) = Stream step' (t,w) 1168 where 1169 {-# INLINE_INNER step' #-} 1170 step' (s,x) = x `seq` 1171 do 1172 r <- step s 1173 case r of 1174 Yield y s' -> do 1175 z <- f x y 1176 return $ Yield x (s', z) 1177 Skip s' -> return $ Skip (s', x) 1178 Done -> return Done 1179 1180-- | Suffix scan 1181postscanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a 1182{-# INLINE postscanl #-} 1183postscanl f = postscanlM (\a b -> return (f a b)) 1184 1185-- | Suffix scan with a monadic operator 1186postscanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a 1187{-# INLINE_FUSED postscanlM #-} 1188postscanlM f w (Stream step t) = Stream step' (t,w) 1189 where 1190 {-# INLINE_INNER step' #-} 1191 step' (s,x) = do 1192 r <- step s 1193 case r of 1194 Yield y s' -> do 1195 z <- f x y 1196 return $ Yield z (s',z) 1197 Skip s' -> return $ Skip (s',x) 1198 Done -> return Done 1199 1200-- | Suffix scan with strict accumulator 1201postscanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a 1202{-# INLINE postscanl' #-} 1203postscanl' f = postscanlM' (\a b -> return (f a b)) 1204 1205-- | Suffix scan with strict acccumulator and a monadic operator 1206postscanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a 1207{-# INLINE_FUSED postscanlM' #-} 1208postscanlM' f w (Stream step t) = w `seq` Stream step' (t,w) 1209 where 1210 {-# INLINE_INNER step' #-} 1211 step' (s,x) = x `seq` 1212 do 1213 r <- step s 1214 case r of 1215 Yield y s' -> do 1216 z <- f x y 1217 z `seq` return (Yield z (s',z)) 1218 Skip s' -> return $ Skip (s',x) 1219 Done -> return Done 1220 1221-- | Haskell-style scan 1222scanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a 1223{-# INLINE scanl #-} 1224scanl f = scanlM (\a b -> return (f a b)) 1225 1226-- | Haskell-style scan with a monadic operator 1227scanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a 1228{-# INLINE scanlM #-} 1229scanlM f z s = z `cons` postscanlM f z s 1230 1231-- | Haskell-style scan with strict accumulator 1232scanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a 1233{-# INLINE scanl' #-} 1234scanl' f = scanlM' (\a b -> return (f a b)) 1235 1236-- | Haskell-style scan with strict accumulator and a monadic operator 1237scanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a 1238{-# INLINE scanlM' #-} 1239scanlM' f z s = z `seq` (z `cons` postscanlM f z s) 1240 1241-- | Scan over a non-empty 'Stream' 1242scanl1 :: Monad m => (a -> a -> a) -> Stream m a -> Stream m a 1243{-# INLINE scanl1 #-} 1244scanl1 f = scanl1M (\x y -> return (f x y)) 1245 1246-- | Scan over a non-empty 'Stream' with a monadic operator 1247scanl1M :: Monad m => (a -> a -> m a) -> Stream m a -> Stream m a 1248{-# INLINE_FUSED scanl1M #-} 1249scanl1M f (Stream step t) = Stream step' (t, Nothing) 1250 where 1251 {-# INLINE_INNER step' #-} 1252 step' (s, Nothing) = do 1253 r <- step s 1254 case r of 1255 Yield x s' -> return $ Yield x (s', Just x) 1256 Skip s' -> return $ Skip (s', Nothing) 1257 Done -> EMPTY_STREAM "scanl1M" 1258 1259 step' (s, Just x) = do 1260 r <- step s 1261 case r of 1262 Yield y s' -> do 1263 z <- f x y 1264 return $ Yield z (s', Just z) 1265 Skip s' -> return $ Skip (s', Just x) 1266 Done -> return Done 1267 1268-- | Scan over a non-empty 'Stream' with a strict accumulator 1269scanl1' :: Monad m => (a -> a -> a) -> Stream m a -> Stream m a 1270{-# INLINE scanl1' #-} 1271scanl1' f = scanl1M' (\x y -> return (f x y)) 1272 1273-- | Scan over a non-empty 'Stream' with a strict accumulator and a monadic 1274-- operator 1275scanl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> Stream m a 1276{-# INLINE_FUSED scanl1M' #-} 1277scanl1M' f (Stream step t) = Stream step' (t, Nothing) 1278 where 1279 {-# INLINE_INNER step' #-} 1280 step' (s, Nothing) = do 1281 r <- step s 1282 case r of 1283 Yield x s' -> x `seq` return (Yield x (s', Just x)) 1284 Skip s' -> return $ Skip (s', Nothing) 1285 Done -> EMPTY_STREAM "scanl1M" 1286 1287 step' (s, Just x) = x `seq` 1288 do 1289 r <- step s 1290 case r of 1291 Yield y s' -> do 1292 z <- f x y 1293 z `seq` return (Yield z (s', Just z)) 1294 Skip s' -> return $ Skip (s', Just x) 1295 Done -> return Done 1296 1297-- Enumerations 1298-- ------------ 1299 1300-- The Enum class is broken for this, there just doesn't seem to be a 1301-- way to implement this generically. We have to specialise for as many types 1302-- as we can but this doesn't help in polymorphic loops. 1303 1304-- | Yield a 'Stream' of the given length containing the values @x@, @x+y@, 1305-- @x+y+y@ etc. 1306enumFromStepN :: (Num a, Monad m) => a -> a -> Int -> Stream m a 1307{-# INLINE_FUSED enumFromStepN #-} 1308enumFromStepN x y n = x `seq` y `seq` n `seq` Stream step (x,n) 1309 where 1310 {-# INLINE_INNER step #-} 1311 step (w,m) | m > 0 = return $ Yield w (w+y,m-1) 1312 | otherwise = return $ Done 1313 1314-- | Enumerate values 1315-- 1316-- /WARNING:/ This operation can be very inefficient. If at all possible, use 1317-- 'enumFromStepN' instead. 1318enumFromTo :: (Enum a, Monad m) => a -> a -> Stream m a 1319{-# INLINE_FUSED enumFromTo #-} 1320enumFromTo x y = fromList [x .. y] 1321 1322-- NOTE: We use (x+1) instead of (succ x) below because the latter checks for 1323-- overflow which can't happen here. 1324 1325-- FIXME: add "too large" test for Int 1326enumFromTo_small :: (Integral a, Monad m) => a -> a -> Stream m a 1327{-# INLINE_FUSED enumFromTo_small #-} 1328enumFromTo_small x y = x `seq` y `seq` Stream step (Just x) 1329 where 1330 {-# INLINE_INNER step #-} 1331 step Nothing = return $ Done 1332 step (Just z) | z == y = return $ Yield z Nothing 1333 | z < y = return $ Yield z (Just (z+1)) 1334 | otherwise = return $ Done 1335 1336{-# RULES 1337 1338"enumFromTo<Int8> [Stream]" 1339 enumFromTo = enumFromTo_small :: Monad m => Int8 -> Int8 -> Stream m Int8 1340 1341"enumFromTo<Int16> [Stream]" 1342 enumFromTo = enumFromTo_small :: Monad m => Int16 -> Int16 -> Stream m Int16 1343 1344"enumFromTo<Word8> [Stream]" 1345 enumFromTo = enumFromTo_small :: Monad m => Word8 -> Word8 -> Stream m Word8 1346 1347"enumFromTo<Word16> [Stream]" 1348 enumFromTo = enumFromTo_small :: Monad m => Word16 -> Word16 -> Stream m Word16 #-} 1349 1350 1351#if WORD_SIZE_IN_BITS > 32 1352 1353{-# RULES 1354 1355"enumFromTo<Int32> [Stream]" 1356 enumFromTo = enumFromTo_small :: Monad m => Int32 -> Int32 -> Stream m Int32 1357 1358"enumFromTo<Word32> [Stream]" 1359 enumFromTo = enumFromTo_small :: Monad m => Word32 -> Word32 -> Stream m Word32 #-} 1360 1361 1362#endif 1363 1364-- NOTE: We could implement a generic "too large" test: 1365-- 1366-- len x y | x > y = 0 1367-- | n > 0 && n <= fromIntegral (maxBound :: Int) = fromIntegral n 1368-- | otherwise = error 1369-- where 1370-- n = y-x+1 1371-- 1372-- Alas, GHC won't eliminate unnecessary comparisons (such as n >= 0 for 1373-- unsigned types). See http://hackage.haskell.org/trac/ghc/ticket/3744 1374-- 1375 1376enumFromTo_int :: forall m. Monad m => Int -> Int -> Stream m Int 1377{-# INLINE_FUSED enumFromTo_int #-} 1378enumFromTo_int x y = x `seq` y `seq` Stream step (Just x) 1379 where 1380 -- {-# INLINE [0] len #-} 1381 -- len :: Int -> Int -> Int 1382 -- len u v | u > v = 0 1383 -- | otherwise = BOUNDS_CHECK(check) "enumFromTo" "vector too large" 1384 -- (n > 0) 1385 -- $ n 1386 -- where 1387 -- n = v-u+1 1388 1389 {-# INLINE_INNER step #-} 1390 step Nothing = return $ Done 1391 step (Just z) | z == y = return $ Yield z Nothing 1392 | z < y = return $ Yield z (Just (z+1)) 1393 | otherwise = return $ Done 1394 1395 1396enumFromTo_intlike :: (Integral a, Monad m) => a -> a -> Stream m a 1397{-# INLINE_FUSED enumFromTo_intlike #-} 1398enumFromTo_intlike x y = x `seq` y `seq` Stream step (Just x) 1399 where 1400 {-# INLINE_INNER step #-} 1401 step Nothing = return $ Done 1402 step (Just z) | z == y = return $ Yield z Nothing 1403 | z < y = return $ Yield z (Just (z+1)) 1404 | otherwise = return $ Done 1405 1406{-# RULES 1407 1408"enumFromTo<Int> [Stream]" 1409 enumFromTo = enumFromTo_int :: Monad m => Int -> Int -> Stream m Int 1410 1411#if WORD_SIZE_IN_BITS > 32 1412 1413"enumFromTo<Int64> [Stream]" 1414 enumFromTo = enumFromTo_intlike :: Monad m => Int64 -> Int64 -> Stream m Int64 #-} 1415 1416#else 1417 1418"enumFromTo<Int32> [Stream]" 1419 enumFromTo = enumFromTo_intlike :: Monad m => Int32 -> Int32 -> Stream m Int32 #-} 1420 1421#endif 1422 1423enumFromTo_big_word :: (Integral a, Monad m) => a -> a -> Stream m a 1424{-# INLINE_FUSED enumFromTo_big_word #-} 1425enumFromTo_big_word x y = x `seq` y `seq` Stream step (Just x) 1426 where 1427 {-# INLINE_INNER step #-} 1428 step Nothing = return $ Done 1429 step (Just z) | z == y = return $ Yield z Nothing 1430 | z < y = return $ Yield z (Just (z+1)) 1431 | otherwise = return $ Done 1432 1433{-# RULES 1434 1435"enumFromTo<Word> [Stream]" 1436 enumFromTo = enumFromTo_big_word :: Monad m => Word -> Word -> Stream m Word 1437 1438"enumFromTo<Word64> [Stream]" 1439 enumFromTo = enumFromTo_big_word 1440 :: Monad m => Word64 -> Word64 -> Stream m Word64 1441 1442#if WORD_SIZE_IN_BITS == 32 1443 1444"enumFromTo<Word32> [Stream]" 1445 enumFromTo = enumFromTo_big_word 1446 :: Monad m => Word32 -> Word32 -> Stream m Word32 1447 1448#endif 1449 1450"enumFromTo<Integer> [Stream]" 1451 enumFromTo = enumFromTo_big_word 1452 :: Monad m => Integer -> Integer -> Stream m Integer #-} 1453 1454 1455 1456#if WORD_SIZE_IN_BITS > 32 1457 1458-- FIXME: the "too large" test is totally wrong 1459enumFromTo_big_int :: (Integral a, Monad m) => a -> a -> Stream m a 1460{-# INLINE_FUSED enumFromTo_big_int #-} 1461enumFromTo_big_int x y = x `seq` y `seq` Stream step (Just x) 1462 where 1463 {-# INLINE_INNER step #-} 1464 step Nothing = return $ Done 1465 step (Just z) | z == y = return $ Yield z Nothing 1466 | z < y = return $ Yield z (Just (z+1)) 1467 | otherwise = return $ Done 1468 1469{-# RULES 1470 1471"enumFromTo<Int64> [Stream]" 1472 enumFromTo = enumFromTo_big_int :: Monad m => Int64 -> Int64 -> Stream m Int64 #-} 1473 1474 1475 1476#endif 1477 1478enumFromTo_char :: Monad m => Char -> Char -> Stream m Char 1479{-# INLINE_FUSED enumFromTo_char #-} 1480enumFromTo_char x y = x `seq` y `seq` Stream step xn 1481 where 1482 xn = ord x 1483 yn = ord y 1484 1485 {-# INLINE_INNER step #-} 1486 step zn | zn <= yn = return $ Yield (unsafeChr zn) (zn+1) 1487 | otherwise = return $ Done 1488 1489{-# RULES 1490 1491"enumFromTo<Char> [Stream]" 1492 enumFromTo = enumFromTo_char #-} 1493 1494 1495 1496------------------------------------------------------------------------ 1497 1498-- Specialise enumFromTo for Float and Double. 1499-- Also, try to do something about pairs? 1500 1501enumFromTo_double :: (Monad m, Ord a, RealFrac a) => a -> a -> Stream m a 1502{-# INLINE_FUSED enumFromTo_double #-} 1503enumFromTo_double n m = n `seq` m `seq` Stream step ini 1504 where 1505 lim = m + 1/2 -- important to float out 1506 1507-- GHC changed definition of Enum for Double in GHC8.6 so we have to 1508-- accomodate both definitions in order to preserve validity of 1509-- rewrite rule 1510-- 1511-- ISSUE: https://gitlab.haskell.org/ghc/ghc/issues/15081 1512-- COMMIT: https://gitlab.haskell.org/ghc/ghc/commit/4ffaf4b67773af4c72d92bb8b6c87b1a7d34ac0f 1513#if MIN_VERSION_base(4,12,0) 1514 ini = 0 1515 step x | x' <= lim = return $ Yield x' (x+1) 1516 | otherwise = return $ Done 1517 where 1518 x' = x + n 1519#else 1520 ini = n 1521 step x | x <= lim = return $ Yield x (x+1) 1522 | otherwise = return $ Done 1523#endif 1524 1525{-# RULES 1526 1527"enumFromTo<Double> [Stream]" 1528 enumFromTo = enumFromTo_double :: Monad m => Double -> Double -> Stream m Double 1529 1530"enumFromTo<Float> [Stream]" 1531 enumFromTo = enumFromTo_double :: Monad m => Float -> Float -> Stream m Float #-} 1532 1533 1534 1535------------------------------------------------------------------------ 1536 1537-- | Enumerate values with a given step. 1538-- 1539-- /WARNING:/ This operation is very inefficient. If at all possible, use 1540-- 'enumFromStepN' instead. 1541enumFromThenTo :: (Enum a, Monad m) => a -> a -> a -> Stream m a 1542{-# INLINE_FUSED enumFromThenTo #-} 1543enumFromThenTo x y z = fromList [x, y .. z] 1544 1545-- FIXME: Specialise enumFromThenTo. 1546 1547-- Conversions 1548-- ----------- 1549 1550-- | Convert a 'Stream' to a list 1551toList :: Monad m => Stream m a -> m [a] 1552{-# INLINE toList #-} 1553toList = foldr (:) [] 1554 1555-- | Convert a list to a 'Stream' 1556fromList :: Monad m => [a] -> Stream m a 1557{-# INLINE fromList #-} 1558fromList zs = Stream step zs 1559 where 1560 step (x:xs) = return (Yield x xs) 1561 step [] = return Done 1562 1563-- | Convert the first @n@ elements of a list to a 'Bundle' 1564fromListN :: Monad m => Int -> [a] -> Stream m a 1565{-# INLINE_FUSED fromListN #-} 1566fromListN m zs = Stream step (zs,m) 1567 where 1568 {-# INLINE_INNER step #-} 1569 step (_, n) | n <= 0 = return Done 1570 step (x:xs,n) = return (Yield x (xs,n-1)) 1571 step ([],_) = return Done 1572 1573{- 1574fromVector :: (Monad m, Vector v a) => v a -> Stream m a 1575{-# INLINE_FUSED fromVector #-} 1576fromVector v = v `seq` n `seq` Stream (Unf step 0) 1577 (Unf vstep True) 1578 (Just v) 1579 (Exact n) 1580 where 1581 n = basicLength v 1582 1583 {-# INLINE step #-} 1584 step i | i >= n = return Done 1585 | otherwise = case basicUnsafeIndexM v i of 1586 Box x -> return $ Yield x (i+1) 1587 1588 1589 {-# INLINE vstep #-} 1590 vstep True = return (Yield (Chunk (basicLength v) (\mv -> basicUnsafeCopy mv v)) False) 1591 vstep False = return Done 1592 1593fromVectors :: forall m a. (Monad m, Vector v a) => [v a] -> Stream m a 1594{-# INLINE_FUSED fromVectors #-} 1595fromVectors vs = Stream (Unf pstep (Left vs)) 1596 (Unf vstep vs) 1597 Nothing 1598 (Exact n) 1599 where 1600 n = List.foldl' (\k v -> k + basicLength v) 0 vs 1601 1602 pstep (Left []) = return Done 1603 pstep (Left (v:vs)) = basicLength v `seq` return (Skip (Right (v,0,vs))) 1604 1605 pstep (Right (v,i,vs)) 1606 | i >= basicLength v = return $ Skip (Left vs) 1607 | otherwise = case basicUnsafeIndexM v i of 1608 Box x -> return $ Yield x (Right (v,i+1,vs)) 1609 1610 -- FIXME: work around bug in GHC 7.6.1 1611 vstep :: [v a] -> m (Step [v a] (Chunk v a)) 1612 vstep [] = return Done 1613 vstep (v:vs) = return $ Yield (Chunk (basicLength v) 1614 (\mv -> INTERNAL_CHECK(check) "concatVectors" "length mismatch" 1615 (M.basicLength mv == basicLength v) 1616 $ basicUnsafeCopy mv v)) vs 1617 1618 1619concatVectors :: (Monad m, Vector v a) => Stream m (v a) -> Stream m a 1620{-# INLINE_FUSED concatVectors #-} 1621concatVectors (Stream step s} 1622 = Stream (Unf pstep (Left s)) 1623 (Unf vstep s) 1624 Nothing 1625 Unknown 1626 where 1627 pstep (Left s) = do 1628 r <- step s 1629 case r of 1630 Yield v s' -> basicLength v `seq` return (Skip (Right (v,0,s'))) 1631 Skip s' -> return (Skip (Left s')) 1632 Done -> return Done 1633 1634 pstep (Right (v,i,s)) 1635 | i >= basicLength v = return (Skip (Left s)) 1636 | otherwise = case basicUnsafeIndexM v i of 1637 Box x -> return (Yield x (Right (v,i+1,s))) 1638 1639 1640 vstep s = do 1641 r <- step s 1642 case r of 1643 Yield v s' -> return (Yield (Chunk (basicLength v) 1644 (\mv -> INTERNAL_CHECK(check) "concatVectors" "length mismatch" 1645 (M.basicLength mv == basicLength v) 1646 $ basicUnsafeCopy mv v)) s') 1647 Skip s' -> return (Skip s') 1648 Done -> return Done 1649 1650reVector :: Monad m => Stream m a -> Stream m a 1651{-# INLINE_FUSED reVector #-} 1652reVector (Stream step s, sSize = n} = Stream step s n 1653 1654{-# RULES 1655 1656"reVector [Vector]" 1657 reVector = id 1658 1659"reVector/reVector [Vector]" forall s. 1660 reVector (reVector s) = s #-} 1661 1662 1663-} 1664 1665