3-- Module : Streamly.Internal.Data.Stream.StreamD.Generate
4-- Copyright : (c) 2020 Composewell Technologies and Contributors
5-- (c) Roman Leshchinskiy 2008-2010
6-- License : BSD-3-Clause
7-- Maintainer : streamly@composewell.com
8-- Stability : experimental
12-- A few combinators in this module have been adapted from the vector package
13-- (c) Roman Leshchinskiy. See the notes in specific combinators.
15module Streamly.Internal.Data.Stream.StreamD.Generate
39 -- ** Enumerating 'Num' Types
40 , enumerateFromStepNum
42 , enumerateFromThenNum
44 -- ** Enumerating 'Bounded' 'Enum' Types
47 , enumerateFromBounded
49 -- ** Enumerating 'Enum' Types not larger than 'Int'
50 , enumerateFromToSmall
51 , enumerateFromThenToSmall
52 , enumerateFromThenSmallBounded
54 -- ** Enumerating 'Bounded' 'Integral' Types
55 , enumerateFromIntegral
56 , enumerateFromThenIntegral
58 -- ** Enumerating 'Integral' Types
59 , enumerateFromToIntegral
60 , enumerateFromThenToIntegral
62 -- ** Enumerating unbounded 'Integral' Types
63 , enumerateFromStepIntegral
65 -- ** Enumerating 'Fractional' Types
66 , enumerateFromFractional
67 , enumerateFromToFractional
68 , enumerateFromThenFractional
69 , enumerateFromThenToFractional
71 -- ** Enumerable Type Class
85 -- | Generate a monadic stream from a seed.
96 -- | Transform an input structure into a stream.
115#include "ArrayMacros.h"
117import Control.Monad.IO.Class (MonadIO(..))
118import Data.Functor.Identity (Identity(..))
119import Foreign.Ptr (Ptr, plusPtr)
120import Foreign.Storable (Storable (peek), sizeOf)
121import GHC.Exts (Addr#, Ptr (Ptr))
122import Streamly.Internal.Data.Time.Clock
123 (Clock(Monotonic), asyncClock, readClock)
124import Streamly.Internal.Data.Time.Units
125 (toAbsTime, AbsTime, toRelTime64, RelTime64, addToAbsTime64)
126import Streamly.Internal.System.IO (unsafeInlineIO)
128#ifdef USE_UNFOLDS_EVERYWHERE
129import qualified Streamly.Internal.Data.Unfold as Unfold
130import qualified Streamly.Internal.Data.Unfold.Enumeration as Unfold
137import Numeric.Natural
138import Prelude hiding (iterate, repeat, replicate, take, takeWhile)
139import Streamly.Internal.Data.Stream.StreamD.Type
141#include "DocTestDataStream.hs"
143------------------------------------------------------------------------------
145------------------------------------------------------------------------------
147-- XXX implement in terms of nilM?
149-- | A stream that terminates without producing any output or side effect.
151-- >>> Stream.toList Stream.nil
154{-# INLINE_NORMAL nil #-}
155nil :: Applicative m => Stream m a
156nil = Stream (\_ _ -> pure Stop) ()
158-- XXX implement in terms of consM?
159-- cons x = consM (return x)
161-- | WARNING! You almost always need StreamK.'Streamly.Data.StreamK.cons'
164-- Fuse a pure value at the head of an existing stream::
166-- >>> s = 1 `Stream.cons` Stream.fromList [2,3]
167-- >>> Stream.toList s
170-- From an implementation perspective, StreamK.cons translates into a
171-- functional call whereas fused cons translates into a conditional branch
172-- (jump). However, the overhead of the function call in StreamK.cons only
173-- occurs once, while the overhead of the conditional branch in fused cons is
174-- incurred for each subsequent element in the stream. As a result,
175-- StreamK.cons has a time complexity of O(n), while fused cons has a time
176-- complexity of O(n^2), where @n@ represents the number of 'cons' used.
180-- >>> cons x xs = return x `Stream.consM` xs
182{-# INLINE_NORMAL cons #-}
183cons :: Applicative m => a -> Stream m a -> Stream m a
184cons x (Stream step state) = Stream step1 Nothing
186 {-# INLINE_LATE step1 #-}
187 step1 _ Nothing = pure $ Yield x (Just state)
188 step1 gst (Just st) = do
190 Yield a s -> Yield a (Just s)
191 Skip s -> Skip (Just s)
192 Stop -> Stop) <$> step gst st
194------------------------------------------------------------------------------
196------------------------------------------------------------------------------
198-- Adapted from vector package
200-- | Build a stream by unfolding a /monadic/ step function starting from a
201-- seed. The step function returns the next element in the stream and the next
202-- seed value. When it is done it returns 'Nothing' and the stream ends. For
208-- then return Nothing
209-- else return (Just (b, b + 1))
210-- in Stream.toList $ Stream.unfoldrM f 0
214{-# INLINE_NORMAL unfoldrM #-}
215unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
216#ifdef USE_UNFOLDS_EVERYWHERE
217unfoldrM next = unfold (Unfold.unfoldrM next)
219unfoldrM next = Stream step
221 {-# INLINE_LATE step #-}
225 Just (x, s) -> Yield x s
229-- | Build a stream by unfolding a /pure/ step function @step@ starting from a
230-- seed @s@. The step function returns the next element in the stream and the
231-- next seed value. When it is done it returns 'Nothing' and the stream ends.
238-- else Just (b, b + 1)
239-- in Stream.toList $ Stream.unfoldr f 0
243{-# INLINE_LATE unfoldr #-}
244unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
245unfoldr f = unfoldrM (return . f)
247------------------------------------------------------------------------------
249------------------------------------------------------------------------------
252-- >>> repeatM = Stream.sequence . Stream.repeat
254-- Generate a stream by repeatedly executing a monadic action forever.
258-- Stream.repeatM (threadDelay 1000000 >> print 1)
260-- & Stream.fold Fold.drain
263{-# INLINE_NORMAL repeatM #-}
264repeatM :: Monad m => m a -> Stream m a
265#ifdef USE_UNFOLDS_EVERYWHERE
266repeatM = unfold Unfold.repeatM
268repeatM x = Stream (\_ _ -> x >>= \r -> return $ Yield r ()) ()
272-- Generate an infinite stream by repeating a pure value.
274-- >>> repeat x = Stream.repeatM (pure x)
276{-# INLINE_NORMAL repeat #-}
277repeat :: Monad m => a -> Stream m a
278#ifdef USE_UNFOLDS_EVERYWHERE
279repeat x = repeatM (pure x)
281repeat x = Stream (\_ _ -> return $ Yield x ()) ()
284-- Adapted from the vector package
287-- >>> replicateM n = Stream.sequence . Stream.replicate n
289-- Generate a stream by performing a monadic action @n@ times.
290{-# INLINE_NORMAL replicateM #-}
291replicateM :: Monad m => Int -> m a -> Stream m a
292#ifdef USE_UNFOLDS_EVERYWHERE
293replicateM n p = unfold Unfold.replicateM (n, p)
295replicateM n p = Stream step n
297 {-# INLINE_LATE step #-}
299 | i <= 0 = return Stop
302 return $ Yield x (i - 1)
306-- >>> replicate n = Stream.take n . Stream.repeat
307-- >>> replicate n x = Stream.replicateM n (pure x)
309-- Generate a stream of length @n@ by repeating a value @n@ times.
311{-# INLINE_NORMAL replicate #-}
312replicate :: Monad m => Int -> a -> Stream m a
313replicate n x = replicateM n (return x)
315------------------------------------------------------------------------------
317------------------------------------------------------------------------------
319-- | For floating point numbers if the increment is less than the precision then
320-- it just gets lost. Therefore we cannot always increment it correctly by just
322-- 9007199254740992 + 1 + 1 :: Double => 9.007199254740992e15
323-- 9007199254740992 + 2 :: Double => 9.007199254740994e15
325-- Instead we accumulate the increment counter and compute the increment
326-- every time before adding it to the starting number.
328-- This works for Integrals as well as floating point numbers, but
329-- enumerateFromStepIntegral is faster for integrals.
330{-# INLINE_NORMAL enumerateFromStepNum #-}
331enumerateFromStepNum :: (Monad m, Num a) => a -> a -> Stream m a
332#ifdef USE_UNFOLDS_EVERYWHERE
333enumerateFromStepNum from stride =
334 unfold Unfold.enumerateFromStepNum (from, stride)
336enumerateFromStepNum from stride = Stream step 0
338 {-# INLINE_LATE step #-}
339 step _ !i = return $ (Yield $! (from + i * stride)) $! (i + 1)
342{-# INLINE_NORMAL enumerateFromNum #-}
343enumerateFromNum :: (Monad m, Num a) => a -> Stream m a
344enumerateFromNum from = enumerateFromStepNum from 1
346{-# INLINE_NORMAL enumerateFromThenNum #-}
347enumerateFromThenNum :: (Monad m, Num a) => a -> a -> Stream m a
348enumerateFromThenNum from next = enumerateFromStepNum from (next - from)
350------------------------------------------------------------------------------
351-- Enumeration of Integrals
352------------------------------------------------------------------------------
354#ifndef USE_UNFOLDS_EVERYWHERE
355data EnumState a = EnumInit | EnumYield a a a | EnumStop
357{-# INLINE_NORMAL enumerateFromThenToIntegralUp #-}
358enumerateFromThenToIntegralUp
359 :: (Monad m, Integral a)
360 => a -> a -> a -> Stream m a
361enumerateFromThenToIntegralUp from next to = Stream step EnumInit
363 {-# INLINE_LATE step #-}
369 else Yield from EnumStop
370 else -- from <= next <= to
371 let stride = next - from
372 in Skip $ EnumYield from stride (to - stride)
374 step _ (EnumYield x stride toMinus) =
377 then Yield x EnumStop
378 else Yield x $ EnumYield (x + stride) stride toMinus
380 step _ EnumStop = return Stop
382{-# INLINE_NORMAL enumerateFromThenToIntegralDn #-}
383enumerateFromThenToIntegralDn
384 :: (Monad m, Integral a)
385 => a -> a -> a -> Stream m a
386enumerateFromThenToIntegralDn from next to = Stream step EnumInit
388 {-# INLINE_LATE step #-}
390 return $ if to > next
393 else Yield from EnumStop
394 else -- from >= next >= to
395 let stride = next - from
396 in Skip $ EnumYield from stride (to - stride)
398 step _ (EnumYield x stride toMinus) =
401 then Yield x EnumStop
402 else Yield x $ EnumYield (x + stride) stride toMinus
404 step _ EnumStop = return Stop
407-- XXX This can perhaps be simplified and written in terms of
408-- enumeratFromStepIntegral as we have done in unfolds.
410-- | Enumerate an 'Integral' type in steps up to a given limit.
411-- @enumerateFromThenToIntegral from then to@ generates a finite stream whose
412-- first element is @from@, the second element is @then@ and the successive
413-- elements are in increments of @then - from@ up to @to@.
415-- >>> Stream.toList $ Stream.enumerateFromThenToIntegral 0 2 6
418-- >>> Stream.toList $ Stream.enumerateFromThenToIntegral 0 (-2) (-6)
421{-# INLINE_NORMAL enumerateFromThenToIntegral #-}
422enumerateFromThenToIntegral
423 :: (Monad m, Integral a)
424 => a -> a -> a -> Stream m a
425#ifdef USE_UNFOLDS_EVERYWHERE
426enumerateFromThenToIntegral from next to =
427 unfold Unfold.enumerateFromThenToIntegral (from, next, to)
429enumerateFromThenToIntegral from next to
430 | next >= from = enumerateFromThenToIntegralUp from next to
431 | otherwise = enumerateFromThenToIntegralDn from next to
434-- | Enumerate an 'Integral' type in steps. @enumerateFromThenIntegral from
435-- then@ generates a stream whose first element is @from@, the second element
436-- is @then@ and the successive elements are in increments of @then - from@.
437-- The stream is bounded by the size of the 'Integral' type.
439-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) 2
442-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) (-2)
445{-# INLINE_NORMAL enumerateFromThenIntegral #-}
446enumerateFromThenIntegral
447 :: (Monad m, Integral a, Bounded a)
448 => a -> a -> Stream m a
449#ifdef USE_UNFOLDS_EVERYWHERE
450enumerateFromThenIntegral from next =
451 unfold Unfold.enumerateFromThenIntegralBounded (from, next)
453enumerateFromThenIntegral from next =
455 then enumerateFromThenToIntegralUp from next maxBound
456 else enumerateFromThenToIntegralDn from next minBound
459-- | @enumerateFromStepIntegral from step@ generates an infinite stream whose
460-- first element is @from@ and the successive elements are in increments of
463-- CAUTION: This function is not safe for finite integral types. It does not
464-- check for overflow, underflow or bounds.
466-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromStepIntegral 0 2
469-- >>> Stream.toList $ Stream.take 3 $ Stream.enumerateFromStepIntegral 0 (-2)
472{-# INLINE_NORMAL enumerateFromStepIntegral #-}
473enumerateFromStepIntegral :: (Integral a, Monad m) => a -> a -> Stream m a
474#ifdef USE_UNFOLDS_EVERYWHERE
475enumerateFromStepIntegral from stride =
476 unfold Unfold.enumerateFromStepIntegral (from, stride)
478enumerateFromStepIntegral from stride =
479 from `seq` stride `seq` Stream step from
481 {-# INLINE_LATE step #-}
482 step _ !x = return $ Yield x $! (x + stride)
485-- | Enumerate an 'Integral' type up to a given limit.
486-- @enumerateFromToIntegral from to@ generates a finite stream whose first
487-- element is @from@ and successive elements are in increments of @1@ up to
490-- >>> Stream.toList $ Stream.enumerateFromToIntegral 0 4
493{-# INLINE enumerateFromToIntegral #-}
494enumerateFromToIntegral :: (Monad m, Integral a) => a -> a -> Stream m a
495enumerateFromToIntegral from to =
496 takeWhile (<= to) $ enumerateFromStepIntegral from 1
498-- | Enumerate an 'Integral' type. @enumerateFromIntegral from@ generates a
499-- stream whose first element is @from@ and the successive elements are in
500-- increments of @1@. The stream is bounded by the size of the 'Integral' type.
502-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromIntegral (0 :: Int)
505{-# INLINE enumerateFromIntegral #-}
506enumerateFromIntegral :: (Monad m, Integral a, Bounded a) => a -> Stream m a
507enumerateFromIntegral from = enumerateFromToIntegral from maxBound
509------------------------------------------------------------------------------
510-- Enumeration of Fractionals
511------------------------------------------------------------------------------
513-- We cannot write a general function for Num. The only way to write code
514-- portable between the two is to use a 'Real' constraint and convert between
515-- Fractional and Integral using fromRational which is horribly slow.
517-- Even though the underlying implementation of enumerateFromFractional and
518-- enumerateFromThenFractional works for any 'Num' we have restricted these to
519-- 'Fractional' because these do not perform any bounds check, in contrast to
520-- integral versions and are therefore not equivalent substitutes for those.
522-- | Numerically stable enumeration from a 'Fractional' number in steps of size
523-- @1@. @enumerateFromFractional from@ generates a stream whose first element
524-- is @from@ and the successive elements are in increments of @1@. No overflow
525-- or underflow checks are performed.
527-- This is the equivalent to 'enumFrom' for 'Fractional' types. For example:
529-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromFractional 1.1
532{-# INLINE enumerateFromFractional #-}
533enumerateFromFractional :: (Monad m, Fractional a) => a -> Stream m a
534enumerateFromFractional = enumerateFromNum
536-- | Numerically stable enumeration from a 'Fractional' number in steps.
537-- @enumerateFromThenFractional from then@ generates a stream whose first
538-- element is @from@, the second element is @then@ and the successive elements
539-- are in increments of @then - from@. No overflow or underflow checks are
542-- This is the equivalent of 'enumFromThen' for 'Fractional' types. For
545-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 2.1
548-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 (-2.1)
549-- [1.1,-2.1,-5.300000000000001,-8.500000000000002]
551{-# INLINE enumerateFromThenFractional #-}
552enumerateFromThenFractional
553 :: (Monad m, Fractional a)
554 => a -> a -> Stream m a
555enumerateFromThenFractional = enumerateFromThenNum
557-- | Numerically stable enumeration from a 'Fractional' number to a given
558-- limit. @enumerateFromToFractional from to@ generates a finite stream whose
559-- first element is @from@ and successive elements are in increments of @1@ up
562-- This is the equivalent of 'enumFromTo' for 'Fractional' types. For
565-- >>> Stream.toList $ Stream.enumerateFromToFractional 1.1 4
568-- >>> Stream.toList $ Stream.enumerateFromToFractional 1.1 4.6
569-- [1.1,2.1,3.1,4.1,5.1]
571-- Notice that the last element is equal to the specified @to@ value after
572-- rounding to the nearest integer.
574{-# INLINE_NORMAL enumerateFromToFractional #-}
575enumerateFromToFractional
576 :: (Monad m, Fractional a, Ord a)
577 => a -> a -> Stream m a
578enumerateFromToFractional from to =
579 takeWhile (<= to + 1 / 2) $ enumerateFromStepNum from 1
581-- | Numerically stable enumeration from a 'Fractional' number in steps up to a
582-- given limit. @enumerateFromThenToFractional from then to@ generates a
583-- finite stream whose first element is @from@, the second element is @then@
584-- and the successive elements are in increments of @then - from@ up to @to@.
586-- This is the equivalent of 'enumFromThenTo' for 'Fractional' types. For
589-- >>> Stream.toList $ Stream.enumerateFromThenToFractional 0.1 2 6
590-- [0.1,2.0,3.9,5.799999999999999]
592-- >>> Stream.toList $ Stream.enumerateFromThenToFractional 0.1 (-2) (-6)
593-- [0.1,-2.0,-4.1000000000000005,-6.200000000000001]
595{-# INLINE_NORMAL enumerateFromThenToFractional #-}
596enumerateFromThenToFractional
597 :: (Monad m, Fractional a, Ord a)
598 => a -> a -> a -> Stream m a
599enumerateFromThenToFractional from next to =
600 takeWhile predicate $ enumerateFromThenFractional from next
602 mid = (next - from) / 2
603 predicate | next >= from = (<= to + mid)
604 | otherwise = (>= to + mid)
606-------------------------------------------------------------------------------
607-- Enumeration of Enum types not larger than Int
608-------------------------------------------------------------------------------
610-- | 'enumerateFromTo' for 'Enum' types not larger than 'Int'.
612{-# INLINE enumerateFromToSmall #-}
613enumerateFromToSmall :: (Monad m, Enum a) => a -> a -> Stream m a
614enumerateFromToSmall from to =
616 $ enumerateFromToIntegral (fromEnum from) (fromEnum to)
618-- | 'enumerateFromThenTo' for 'Enum' types not larger than 'Int'.
620{-# INLINE enumerateFromThenToSmall #-}
621enumerateFromThenToSmall :: (Monad m, Enum a)
622 => a -> a -> a -> Stream m a
623enumerateFromThenToSmall from next to =
625 $ enumerateFromThenToIntegral
626 (fromEnum from) (fromEnum next) (fromEnum to)
628-- | 'enumerateFromThen' for 'Enum' types not larger than 'Int'.
630-- Note: We convert the 'Enum' to 'Int' and enumerate the 'Int'. If a
631-- type is bounded but does not have a 'Bounded' instance then we can go on
632-- enumerating it beyond the legal values of the type, resulting in the failure
633-- of 'toEnum' when converting back to 'Enum'. Therefore we require a 'Bounded'
634-- instance for this function to be safely used.
636{-# INLINE enumerateFromThenSmallBounded #-}
637enumerateFromThenSmallBounded :: (Monad m, Enumerable a, Bounded a)
638 => a -> a -> Stream m a
639enumerateFromThenSmallBounded from next =
640 if fromEnum next >= fromEnum from
641 then enumerateFromThenTo from next maxBound
642 else enumerateFromThenTo from next minBound
644-------------------------------------------------------------------------------
645-- Enumerable type class
646-------------------------------------------------------------------------------
648-- NOTE: We would like to rewrite calls to fromList [1..] etc. to stream
649-- enumerations like this:
651-- {-# RULES "fromList enumFrom" [1]
652-- forall (a :: Int). D.fromList (enumFrom a) = D.enumerateFromIntegral a #-}
654-- But this does not work because enumFrom is a class method and GHC rewrites
655-- it quickly, so we do not get a chance to have our rule fired.
657-- | Types that can be enumerated as a stream. The operations in this type
658-- class are equivalent to those in the 'Enum' type class, except that these
659-- generate a stream instead of a list. Use the functions in
660-- "Streamly.Internal.Data.Stream.Enumeration" module to define new instances.
662class Enum a => Enumerable a where
663 -- | @enumerateFrom from@ generates a stream starting with the element
664 -- @from@, enumerating up to 'maxBound' when the type is 'Bounded' or
665 -- generating an infinite stream when the type is not 'Bounded'.
667 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFrom (0 :: Int)
670 -- For 'Fractional' types, enumeration is numerically stable. However, no
671 -- overflow or underflow checks are performed.
673 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFrom 1.1
676 enumerateFrom :: (Monad m) => a -> Stream m a
678 -- | Generate a finite stream starting with the element @from@, enumerating
679 -- the type up to the value @to@. If @to@ is smaller than @from@ then an
680 -- empty stream is returned.
682 -- >>> Stream.toList $ Stream.enumerateFromTo 0 4
685 -- For 'Fractional' types, the last element is equal to the specified @to@
686 -- value after rounding to the nearest integral value.
688 -- >>> Stream.toList $ Stream.enumerateFromTo 1.1 4
691 -- >>> Stream.toList $ Stream.enumerateFromTo 1.1 4.6
692 -- [1.1,2.1,3.1,4.1,5.1]
694 enumerateFromTo :: (Monad m) => a -> a -> Stream m a
696 -- | @enumerateFromThen from then@ generates a stream whose first element
697 -- is @from@, the second element is @then@ and the successive elements are
698 -- in increments of @then - from@. Enumeration can occur downwards or
699 -- upwards depending on whether @then@ comes before or after @from@. For
700 -- 'Bounded' types the stream ends when 'maxBound' is reached, for
701 -- unbounded types it keeps enumerating infinitely.
703 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 2
706 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 (-2)
709 enumerateFromThen :: (Monad m) => a -> a -> Stream m a
711 -- | @enumerateFromThenTo from then to@ generates a finite stream whose
712 -- first element is @from@, the second element is @then@ and the successive
713 -- elements are in increments of @then - from@ up to @to@. Enumeration can
714 -- occur downwards or upwards depending on whether @then@ comes before or
717 -- >>> Stream.toList $ Stream.enumerateFromThenTo 0 2 6
720 -- >>> Stream.toList $ Stream.enumerateFromThenTo 0 (-2) (-6)
723 enumerateFromThenTo :: (Monad m) => a -> a -> a -> Stream m a
725-- MAYBE: Sometimes it is more convenient to know the count rather then the
726-- ending or starting element. For those cases we can define the folllowing
727-- APIs. All of these will work only for bounded types if we represent the
736-------------------------------------------------------------------------------
737-- Convenient functions for bounded types
738-------------------------------------------------------------------------------
741-- > enumerate = enumerateFrom minBound
743-- Enumerate a 'Bounded' type from its 'minBound' to 'maxBound'
745{-# INLINE enumerate #-}
746enumerate :: (Monad m, Bounded a, Enumerable a) => Stream m a
747enumerate = enumerateFrom minBound
750-- >>> enumerateTo = Stream.enumerateFromTo minBound
752-- Enumerate a 'Bounded' type from its 'minBound' to specified value.
754{-# INLINE enumerateTo #-}
755enumerateTo :: (Monad m, Bounded a, Enumerable a) => a -> Stream m a
756enumerateTo = enumerateFromTo minBound
759-- >>> enumerateFromBounded from = Stream.enumerateFromTo from maxBound
761-- 'enumerateFrom' for 'Bounded' 'Enum' types.
763{-# INLINE enumerateFromBounded #-}
764enumerateFromBounded :: (Monad m, Enumerable a, Bounded a)
766enumerateFromBounded from = enumerateFromTo from maxBound
768-------------------------------------------------------------------------------
769-- Enumerable Instances
770-------------------------------------------------------------------------------
772-- For Enum types smaller than or equal to Int size.
773#define ENUMERABLE_BOUNDED_SMALL(SMALL_TYPE) \
774instance Enumerable SMALL_TYPE where { \
775 {-# INLINE enumerateFrom #-}; \
776 enumerateFrom = enumerateFromBounded; \
777 {-# INLINE enumerateFromThen #-}; \
778 enumerateFromThen = enumerateFromThenSmallBounded; \
779 {-# INLINE enumerateFromTo #-}; \
780 enumerateFromTo = enumerateFromToSmall; \
781 {-# INLINE enumerateFromThenTo #-}; \
782 enumerateFromThenTo = enumerateFromThenToSmall }
784ENUMERABLE_BOUNDED_SMALL(())
785ENUMERABLE_BOUNDED_SMALL(Bool)
786ENUMERABLE_BOUNDED_SMALL(Ordering)
787ENUMERABLE_BOUNDED_SMALL(Char)
789-- For bounded Integral Enum types, may be larger than Int.
790#define ENUMERABLE_BOUNDED_INTEGRAL(INTEGRAL_TYPE) \
791instance Enumerable INTEGRAL_TYPE where { \
792 {-# INLINE enumerateFrom #-}; \
793 enumerateFrom = enumerateFromIntegral; \
794 {-# INLINE enumerateFromThen #-}; \
795 enumerateFromThen = enumerateFromThenIntegral; \
796 {-# INLINE enumerateFromTo #-}; \
797 enumerateFromTo = enumerateFromToIntegral; \
798 {-# INLINE enumerateFromThenTo #-}; \
799 enumerateFromThenTo = enumerateFromThenToIntegral }
801ENUMERABLE_BOUNDED_INTEGRAL(Int)
802ENUMERABLE_BOUNDED_INTEGRAL(Int8)
803ENUMERABLE_BOUNDED_INTEGRAL(Int16)
804ENUMERABLE_BOUNDED_INTEGRAL(Int32)
805ENUMERABLE_BOUNDED_INTEGRAL(Int64)
806ENUMERABLE_BOUNDED_INTEGRAL(Word)
807ENUMERABLE_BOUNDED_INTEGRAL(Word8)
808ENUMERABLE_BOUNDED_INTEGRAL(Word16)
809ENUMERABLE_BOUNDED_INTEGRAL(Word32)
810ENUMERABLE_BOUNDED_INTEGRAL(Word64)
812-- For unbounded Integral Enum types.
813#define ENUMERABLE_UNBOUNDED_INTEGRAL(INTEGRAL_TYPE) \
814instance Enumerable INTEGRAL_TYPE where { \
815 {-# INLINE enumerateFrom #-}; \
816 enumerateFrom from = enumerateFromStepIntegral from 1; \
817 {-# INLINE enumerateFromThen #-}; \
818 enumerateFromThen from next = \
819 enumerateFromStepIntegral from (next - from); \
820 {-# INLINE enumerateFromTo #-}; \
821 enumerateFromTo = enumerateFromToIntegral; \
822 {-# INLINE enumerateFromThenTo #-}; \
823 enumerateFromThenTo = enumerateFromThenToIntegral }
825ENUMERABLE_UNBOUNDED_INTEGRAL(Integer)
826ENUMERABLE_UNBOUNDED_INTEGRAL(Natural)
828#define ENUMERABLE_FRACTIONAL(FRACTIONAL_TYPE,CONSTRAINT) \
829instance (CONSTRAINT) => Enumerable FRACTIONAL_TYPE where { \
830 {-# INLINE enumerateFrom #-}; \
831 enumerateFrom = enumerateFromFractional; \
832 {-# INLINE enumerateFromThen #-}; \
833 enumerateFromThen = enumerateFromThenFractional; \
834 {-# INLINE enumerateFromTo #-}; \
835 enumerateFromTo = enumerateFromToFractional; \
836 {-# INLINE enumerateFromThenTo #-}; \
837 enumerateFromThenTo = enumerateFromThenToFractional }
839ENUMERABLE_FRACTIONAL(Float,)
840ENUMERABLE_FRACTIONAL(Double,)
841ENUMERABLE_FRACTIONAL((Fixed a),HasResolution a)
842ENUMERABLE_FRACTIONAL((Ratio a),Integral a)
844instance Enumerable a => Enumerable (Identity a) where
845 {-# INLINE enumerateFrom #-}
846 enumerateFrom (Identity from) =
847 fmap Identity $ enumerateFrom from
848 {-# INLINE enumerateFromThen #-}
849 enumerateFromThen (Identity from) (Identity next) =
850 fmap Identity $ enumerateFromThen from next
851 {-# INLINE enumerateFromTo #-}
852 enumerateFromTo (Identity from) (Identity to) =
853 fmap Identity $ enumerateFromTo from to
854 {-# INLINE enumerateFromThenTo #-}
855 enumerateFromThenTo (Identity from) (Identity next) (Identity to) =
857 $ enumerateFromThenTo from next to
861instance Enumerable a => Enumerable (Last a)
862instance Enumerable a => Enumerable (First a)
863instance Enumerable a => Enumerable (Max a)
864instance Enumerable a => Enumerable (Min a)
865instance Enumerable a => Enumerable (Const a b)
866instance Enumerable (f a) => Enumerable (Alt f a)
867instance Enumerable (f a) => Enumerable (Ap f a)
869------------------------------------------------------------------------------
871------------------------------------------------------------------------------
873-- | @timesWith g@ returns a stream of time value tuples. The first component
874-- of the tuple is an absolute time reference (epoch) denoting the start of the
875-- stream and the second component is a time relative to the reference.
877-- The argument @g@ specifies the granularity of the relative time in seconds.
878-- A lower granularity clock gives higher precision but is more expensive in
879-- terms of CPU usage. Any granularity lower than 1 ms is treated as 1 ms.
881-- >>> import Control.Concurrent (threadDelay)
882-- >>> f = Fold.drainMapM (\x -> print x >> threadDelay 1000000)
883-- >>> Stream.fold f $ Stream.take 3 $ Stream.timesWith 0.01
884-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
885-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
886-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
888-- Note: This API is not safe on 32-bit machines.
892{-# INLINE_NORMAL timesWith #-}
893timesWith :: MonadIO m => Double -> Stream m (AbsTime, RelTime64)
894timesWith g = Stream step Nothing
898 {-# INLINE_LATE step #-}
900 clock <- liftIO $ asyncClock Monotonic g
901 a <- liftIO $ readClock clock
902 return $ Skip $ Just (clock, a)
904 step _ s@(Just (clock, t0)) = do
905 a <- liftIO $ readClock clock
906 -- XXX we can perhaps use an AbsTime64 using a 64 bit Int for
907 -- efficiency. or maybe we can use a representation using Double for
908 -- floating precision time
909 return $ Yield (toAbsTime t0, toRelTime64 (a - t0)) s
911-- | @absTimesWith g@ returns a stream of absolute timestamps using a clock of
912-- granularity @g@ specified in seconds. A low granularity clock is more
913-- expensive in terms of CPU usage. Any granularity lower than 1 ms is treated
916-- >>> f = Fold.drainMapM print
917-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.absTimesWith 0.01
918-- AbsTime (TimeSpec {sec = ..., nsec = ...})
919-- AbsTime (TimeSpec {sec = ..., nsec = ...})
920-- AbsTime (TimeSpec {sec = ..., nsec = ...})
922-- Note: This API is not safe on 32-bit machines.
926{-# INLINE absTimesWith #-}
927absTimesWith :: MonadIO m => Double -> Stream m AbsTime
928absTimesWith = fmap (uncurry addToAbsTime64) . timesWith
930-- | @relTimesWith g@ returns a stream of relative time values starting from 0,
931-- using a clock of granularity @g@ specified in seconds. A low granularity
932-- clock is more expensive in terms of CPU usage. Any granularity lower than 1
933-- ms is treated as 1 ms.
935-- >>> f = Fold.drainMapM print
936-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.relTimesWith 0.01
937-- RelTime64 (NanoSecond64 ...)
938-- RelTime64 (NanoSecond64 ...)
939-- RelTime64 (NanoSecond64 ...)
941-- Note: This API is not safe on 32-bit machines.
945{-# INLINE relTimesWith #-}
946relTimesWith :: MonadIO m => Double -> Stream m RelTime64
947relTimesWith = fmap snd . timesWith
949-- | @times@ returns a stream of time value tuples with clock of 10 ms
950-- granularity. The first component of the tuple is an absolute time reference
951-- (epoch) denoting the start of the stream and the second component is a time
952-- relative to the reference.
954-- >>> f = Fold.drainMapM (\x -> print x >> threadDelay 1000000)
955-- >>> Stream.fold f $ Stream.take 3 $ Stream.times
956-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
957-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
958-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
960-- Note: This API is not safe on 32-bit machines.
965times :: MonadIO m => Stream m (AbsTime, RelTime64)
966times = timesWith 0.01
968-- | @absTimes@ returns a stream of absolute timestamps using a clock of 10 ms
971-- >>> f = Fold.drainMapM print
972-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.absTimes
973-- AbsTime (TimeSpec {sec = ..., nsec = ...})
974-- AbsTime (TimeSpec {sec = ..., nsec = ...})
975-- AbsTime (TimeSpec {sec = ..., nsec = ...})
977-- Note: This API is not safe on 32-bit machines.
981{-# INLINE absTimes #-}
982absTimes :: MonadIO m => Stream m AbsTime
983absTimes = fmap (uncurry addToAbsTime64) times
985-- | @relTimes@ returns a stream of relative time values starting from 0,
986-- using a clock of granularity 10 ms.
988-- >>> f = Fold.drainMapM print
989-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.relTimes
990-- RelTime64 (NanoSecond64 ...)
991-- RelTime64 (NanoSecond64 ...)
992-- RelTime64 (NanoSecond64 ...)
994-- Note: This API is not safe on 32-bit machines.
998{-# INLINE relTimes #-}
999relTimes :: MonadIO m => Stream m RelTime64
1000relTimes = fmap snd times
1002-- | @durations g@ returns a stream of relative time values measuring the time
1003-- elapsed since the immediate predecessor element of the stream was generated.
1004-- The first element of the stream is always 0. @durations@ uses a clock of
1005-- granularity @g@ specified in seconds. A low granularity clock is more
1006-- expensive in terms of CPU usage. The minimum granularity is 1 millisecond.
1007-- Durations lower than 1 ms will be 0.
1009-- Note: This API is not safe on 32-bit machines.
1013{-# INLINE durations #-}
1014durations :: -- Monad m =>
1015 Double -> t m RelTime64
1016durations = undefined
1018-- | Generate a singleton event at or after the specified absolute time. Note
1019-- that this is different from a threadDelay, a threadDelay starts from the
1020-- time when the action is evaluated, whereas if we use AbsTime based timeout
1021-- it will immediately expire if the action is evaluated too late.
1025{-# INLINE timeout #-}
1026timeout :: -- Monad m =>
1030-------------------------------------------------------------------------------
1032-------------------------------------------------------------------------------
1034{-# INLINE_NORMAL fromIndicesM #-}
1035fromIndicesM :: Monad m => (Int -> m a) -> Stream m a
1036#ifdef USE_UNFOLDS_EVERYWHERE
1037fromIndicesM gen = unfold (Unfold.fromIndicesM gen) 0
1039fromIndicesM gen = Stream step 0
1041 {-# INLINE_LATE step #-}
1044 return $ Yield x (i + 1)
1047{-# INLINE fromIndices #-}
1048fromIndices :: Monad m => (Int -> a) -> Stream m a
1049fromIndices gen = fromIndicesM (return . gen)
1051-- Adapted from the vector package
1052{-# INLINE_NORMAL generateM #-}
1053generateM :: Monad m => Int -> (Int -> m a) -> Stream m a
1054generateM n gen = n `seq` Stream step 0
1056 {-# INLINE_LATE step #-}
1057 step _ i | i < n = do
1059 return $ Yield x (i + 1)
1060 | otherwise = return Stop
1062{-# INLINE generate #-}
1063generate :: Monad m => Int -> (Int -> a) -> Stream m a
1064generate n gen = generateM n (return . gen)
1066-------------------------------------------------------------------------------
1068-------------------------------------------------------------------------------
1070-- | Generate an infinite stream with the first element generated by the action
1071-- @m@ and each successive element derived by applying the monadic function @f@
1072-- on the previous element.
1075-- Stream.iterateM (\x -> print x >> return (x + 1)) (return 0)
1083{-# INLINE_NORMAL iterateM #-}
1084iterateM :: Monad m => (a -> m a) -> m a -> Stream m a
1085#ifdef USE_UNFOLDS_EVERYWHERE
1086iterateM step = unfold (Unfold.iterateM step)
1088iterateM step = Stream (\_ st -> st >>= \(!x) -> return $ Yield x (step x))
1091-- | Generate an infinite stream with @x@ as the first element and each
1092-- successive element derived by applying the function @f@ on the previous
1095-- >>> Stream.toList $ Stream.take 5 $ Stream.iterate (+1) 1
1098{-# INLINE_NORMAL iterate #-}
1099iterate :: Monad m => (a -> a) -> a -> Stream m a
1100iterate step st = iterateM (return . step) (return st)
1102-------------------------------------------------------------------------------
1104-------------------------------------------------------------------------------
1106-- | Convert a list of monadic actions to a 'Stream'
1107{-# INLINE_LATE fromListM #-}
1108fromListM :: Monad m => [m a] -> Stream m a
1109#ifdef USE_UNFOLDS_EVERYWHERE
1110fromListM = unfold Unfold.fromListM
1112fromListM = Stream step
1114 {-# INLINE_LATE step #-}
1115 step _ (m:ms) = m >>= \x -> return $ Yield x ms
1116 step _ [] = return Stop
1120-- >>> fromFoldable = Prelude.foldr Stream.cons Stream.nil
1122-- Construct a stream from a 'Foldable' containing pure values:
1124-- /WARNING: O(n^2), suitable only for a small number of
1125-- elements in the stream/
1127{-# INLINE fromFoldable #-}
1128fromFoldable :: (Monad m, Foldable f) => f a -> Stream m a
1129fromFoldable = Prelude.foldr cons nil
1132-- >>> fromFoldableM = Prelude.foldr Stream.consM Stream.nil
1134-- Construct a stream from a 'Foldable' containing pure values:
1136-- /WARNING: O(n^2), suitable only for a small number of
1137-- elements in the stream/
1139{-# INLINE fromFoldableM #-}
1140fromFoldableM :: (Monad m, Foldable f) => f (m a) -> Stream m a
1141fromFoldableM = Prelude.foldr consM nil
1143-------------------------------------------------------------------------------
1145-------------------------------------------------------------------------------
1147-- | Keep reading 'Storable' elements from an immutable 'Ptr' onwards.
1149-- /Unsafe:/ The caller is responsible for safe addressing.
1152{-# INLINE fromPtr #-}
1153fromPtr :: forall m a. (Monad m, Storable a) => Ptr a -> Stream m a
1154fromPtr = Stream step
1158 {-# INLINE_LATE step #-}
1160 let !x = unsafeInlineIO $ peek p
1161 return $ Yield x (PTR_NEXT(p, a))
1163-- | Take @n@ 'Storable' elements starting from an immutable 'Ptr' onwards.
1165-- >>> fromPtrN n = Stream.take n . Stream.fromPtr
1167-- /Unsafe:/ The caller is responsible for safe addressing.
1170{-# INLINE fromPtrN #-}
1171fromPtrN :: (Monad m, Storable a) => Int -> Ptr a -> Stream m a
1172fromPtrN n = take n . fromPtr
1174-- | Read bytes from an immutable 'Addr#' until a 0 byte is encountered, the 0
1175-- byte is not included in the stream.
1177-- >>> :set -XMagicHash
1178-- >>> fromByteStr# addr = Stream.takeWhile (/= 0) $ Stream.fromPtr $ Ptr addr
1180-- /Unsafe:/ The caller is responsible for safe addressing.
1182-- Note that this is completely safe when reading from Haskell string
1183-- literals because they are guaranteed to be NULL terminated:
1185-- >>> Stream.toList $ Stream.fromByteStr# "\1\2\3\0"#
1188{-# INLINE fromByteStr# #-}
1189fromByteStr# :: Monad m => Addr# -> Stream m Word8
1190fromByteStr# addr = takeWhile (/= 0) $ fromPtr $ Ptr addr
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list