3-- Module : Streamly.Internal.Data.Stream.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.Generate
32 -- ** Enumerating 'Num' Types
33 , enumerateFromStepNum
35 , enumerateFromThenNum
37 -- ** Enumerating 'Bounded' 'Enum' Types
40 , enumerateFromBounded
42 -- ** Enumerating 'Enum' Types not larger than 'Int'
43 , enumerateFromToSmall
44 , enumerateFromThenToSmall
45 , enumerateFromThenSmallBounded
47 -- ** Enumerating 'Bounded' 'Integral' Types
48 , enumerateFromIntegral
49 , enumerateFromThenIntegral
51 -- ** Enumerating 'Integral' Types
52 , enumerateFromToIntegral
53 , enumerateFromThenToIntegral
55 -- ** Enumerating unbounded 'Integral' Types
56 , enumerateFromStepIntegral
58 -- ** Enumerating 'Fractional' Types
59 , enumerateFromFractional
60 , enumerateFromToFractional
61 , enumerateFromThenFractional
62 , enumerateFromThenToFractional
64 -- ** Enumerable Type Class
78 -- | Generate a monadic stream from a seed.
89 -- | Transform an input structure into a stream.
103#include "ArrayMacros.h"
105import Control.Monad.IO.Class (MonadIO(..))
106import Data.Functor.Identity (Identity(..))
107import Foreign.Ptr (Ptr, plusPtr)
108import Foreign.Storable (Storable (peek), sizeOf)
109import GHC.Exts (Addr#, Ptr (Ptr))
110import Streamly.Internal.Data.Time.Clock
111 (Clock(Monotonic), asyncClock, readClock)
112import Streamly.Internal.Data.Time.Units
113 (toAbsTime, AbsTime, toRelTime64, RelTime64, addToAbsTime64)
114import Streamly.Internal.System.IO (unsafeInlineIO)
116#ifdef USE_UNFOLDS_EVERYWHERE
117import qualified Streamly.Internal.Data.Unfold as Unfold
124import Numeric.Natural
125import Prelude hiding (iterate, repeat, replicate, take, takeWhile)
126import Streamly.Internal.Data.Stream.Type
128#include "DocTestDataStream.hs"
130------------------------------------------------------------------------------
132------------------------------------------------------------------------------
134-- XXX implement in terms of nilM?
136-- | A stream that terminates without producing any output or side effect.
138-- >>> Stream.toList Stream.nil
141{-# INLINE_NORMAL nil #-}
142nil :: Applicative m => Stream m a
143nil = Stream (\_ _ -> pure Stop) ()
147-- XXX implement in terms of consM?
148-- cons x = consM (return x)
149-- From an implementation perspective, StreamK.cons translates into a
150-- functional call whereas fused cons translates into a conditional branch
151-- (jump). However, the overhead of the function call in StreamK.cons only
152-- occurs once, while the overhead of the conditional branch in fused cons is
153-- incurred for each subsequent element in the stream. As a result,
154-- StreamK.cons has a time complexity of O(n), while fused cons has a time
155-- complexity of O(n^2), where @n@ represents the number of 'cons' used.
157-- When composing a few elements together statically, a balanced tree composed
158-- using 'cons' and 'append' is more efficient than a right associated one
159-- composed using 'cons':
161-- >>> s1 = 1 `Stream.cons` 2 `Stream.cons` Stream.nil
162-- >>> s2 = 2 `Stream.cons` 3 `Stream.cons` Stream.nil
163-- >>> s = s1 `Stream.append` s2
165-- However, generating a stream using a case statement or indexing into a
166-- static literal array would be the best. Check if the case statement
167-- translates to a look up table or a binary search.
169-- | WARNING! O(n^2) time complexity wrt number of elements. Use the O(n)
170-- complexity StreamK.'Streamly.Data.StreamK.cons' unless you want to
171-- statically fuse just a few elements.
173-- Fuse a pure value at the head of an existing stream::
175-- >>> s = 1 `Stream.cons` Stream.fromList [2,3]
176-- >>> Stream.toList s
181-- >>> cons x xs = return x `Stream.consM` xs
183{-# INLINE_NORMAL cons #-}
184cons :: Applicative m => a -> Stream m a -> Stream m a
185cons x (Stream step state) = Stream step1 Nothing
187 {-# INLINE_LATE step1 #-}
188 step1 _ Nothing = pure $ Yield x (Just state)
189 step1 gst (Just st) = do
191 Yield a s -> Yield a (Just s)
192 Skip s -> Skip (Just s)
193 Stop -> Stop) <$> step gst st
195------------------------------------------------------------------------------
197------------------------------------------------------------------------------
199-- Adapted from vector package
201-- | Build a stream by unfolding a /monadic/ step function starting from a
202-- seed. The step function returns the next element in the stream and the next
203-- seed value. When it is done it returns 'Nothing' and the stream ends. For
209-- then return Nothing
210-- else return (Just (b, b + 1))
211-- in Stream.toList $ Stream.unfoldrM f 0
215{-# INLINE_NORMAL unfoldrM #-}
216unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
217#ifdef USE_UNFOLDS_EVERYWHERE
218unfoldrM next = unfold (Unfold.unfoldrM next)
220unfoldrM next = Stream step
222 {-# INLINE_LATE step #-}
226 Just (x, s) -> Yield x s
230-- | Build a stream by unfolding a /pure/ step function @step@ starting from a
231-- seed @s@. The step function returns the next element in the stream and the
232-- next seed value. When it is done it returns 'Nothing' and the stream ends.
239-- else Just (b, b + 1)
240-- in Stream.toList $ Stream.unfoldr f 0
244{-# INLINE_LATE unfoldr #-}
245unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
246unfoldr f = unfoldrM (return . f)
248------------------------------------------------------------------------------
250------------------------------------------------------------------------------
253-- >>> repeatM = Stream.sequence . Stream.repeat
255-- Generate a stream by repeatedly executing a monadic action forever.
259-- Stream.repeatM (threadDelay 1000000 >> print 1)
261-- & Stream.fold Fold.drain
264{-# INLINE_NORMAL repeatM #-}
265repeatM :: Monad m => m a -> Stream m a
266#ifdef USE_UNFOLDS_EVERYWHERE
267repeatM = unfold Unfold.repeatM
269repeatM x = Stream (\_ _ -> x >>= \r -> return $ Yield r ()) ()
273-- Generate an infinite stream by repeating a pure value.
275-- >>> repeat x = Stream.repeatM (pure x)
277{-# INLINE_NORMAL repeat #-}
278repeat :: Monad m => a -> Stream m a
279#ifdef USE_UNFOLDS_EVERYWHERE
280repeat x = repeatM (pure x)
282repeat x = Stream (\_ _ -> return $ Yield x ()) ()
285-- Adapted from the vector package
288-- >>> replicateM n = Stream.sequence . Stream.replicate n
290-- Generate a stream by performing a monadic action @n@ times.
291{-# INLINE_NORMAL replicateM #-}
292replicateM :: Monad m => Int -> m a -> Stream m a
293#ifdef USE_UNFOLDS_EVERYWHERE
294replicateM n p = unfold Unfold.replicateM (n, p)
296replicateM n p = Stream step n
298 {-# INLINE_LATE step #-}
300 | i <= 0 = return Stop
303 return $ Yield x (i - 1)
307-- >>> replicate n = Stream.take n . Stream.repeat
308-- >>> replicate n x = Stream.replicateM n (pure x)
310-- Generate a stream of length @n@ by repeating a value @n@ times.
312{-# INLINE_NORMAL replicate #-}
313replicate :: Monad m => Int -> a -> Stream m a
314replicate n x = replicateM n (return x)
316------------------------------------------------------------------------------
318------------------------------------------------------------------------------
320-- | For floating point numbers if the increment is less than the precision then
321-- it just gets lost. Therefore we cannot always increment it correctly by just
323-- 9007199254740992 + 1 + 1 :: Double => 9.007199254740992e15
324-- 9007199254740992 + 2 :: Double => 9.007199254740994e15
326-- Instead we accumulate the increment counter and compute the increment
327-- every time before adding it to the starting number.
329-- This works for Integrals as well as floating point numbers, but
330-- enumerateFromStepIntegral is faster for integrals.
331{-# INLINE_NORMAL enumerateFromStepNum #-}
332enumerateFromStepNum :: (Monad m, Num a) => a -> a -> Stream m a
333#ifdef USE_UNFOLDS_EVERYWHERE
334enumerateFromStepNum from stride =
335 unfold Unfold.enumerateFromStepNum (from, stride)
337enumerateFromStepNum from stride = Stream step 0
339 {-# INLINE_LATE step #-}
340 step _ !i = return $ (Yield $! (from + i * stride)) $! (i + 1)
343{-# INLINE_NORMAL enumerateFromNum #-}
344enumerateFromNum :: (Monad m, Num a) => a -> Stream m a
345enumerateFromNum from = enumerateFromStepNum from 1
347{-# INLINE_NORMAL enumerateFromThenNum #-}
348enumerateFromThenNum :: (Monad m, Num a) => a -> a -> Stream m a
349enumerateFromThenNum from next = enumerateFromStepNum from (next - from)
351------------------------------------------------------------------------------
352-- Enumeration of Integrals
353------------------------------------------------------------------------------
355#ifndef USE_UNFOLDS_EVERYWHERE
356data EnumState a = EnumInit | EnumYield a a a | EnumStop
358{-# INLINE_NORMAL enumerateFromThenToIntegralUp #-}
359enumerateFromThenToIntegralUp
360 :: (Monad m, Integral a)
361 => a -> a -> a -> Stream m a
362enumerateFromThenToIntegralUp from next to = Stream step EnumInit
364 {-# INLINE_LATE step #-}
370 else Yield from EnumStop
371 else -- from <= next <= to
372 let stride = next - from
373 in Skip $ EnumYield from stride (to - stride)
375 step _ (EnumYield x stride toMinus) =
378 then Yield x EnumStop
379 else Yield x $ EnumYield (x + stride) stride toMinus
381 step _ EnumStop = return Stop
383{-# INLINE_NORMAL enumerateFromThenToIntegralDn #-}
384enumerateFromThenToIntegralDn
385 :: (Monad m, Integral a)
386 => a -> a -> a -> Stream m a
387enumerateFromThenToIntegralDn from next to = Stream step EnumInit
389 {-# INLINE_LATE step #-}
391 return $ if to > next
394 else Yield from EnumStop
395 else -- from >= next >= to
396 let stride = next - from
397 in Skip $ EnumYield from stride (to - stride)
399 step _ (EnumYield x stride toMinus) =
402 then Yield x EnumStop
403 else Yield x $ EnumYield (x + stride) stride toMinus
405 step _ EnumStop = return Stop
408-- XXX This can perhaps be simplified and written in terms of
409-- enumeratFromStepIntegral as we have done in unfolds.
411-- | Enumerate an 'Integral' type in steps up to a given limit.
412-- @enumerateFromThenToIntegral from then to@ generates a finite stream whose
413-- first element is @from@, the second element is @then@ and the successive
414-- elements are in increments of @then - from@ up to @to@.
416-- >>> Stream.toList $ Stream.enumerateFromThenToIntegral 0 2 6
419-- >>> Stream.toList $ Stream.enumerateFromThenToIntegral 0 (-2) (-6)
422{-# INLINE_NORMAL enumerateFromThenToIntegral #-}
423enumerateFromThenToIntegral
424 :: (Monad m, Integral a)
425 => a -> a -> a -> Stream m a
426#ifdef USE_UNFOLDS_EVERYWHERE
427enumerateFromThenToIntegral from next to =
428 unfold Unfold.enumerateFromThenToIntegral (from, next, to)
430enumerateFromThenToIntegral from next to
431 | next >= from = enumerateFromThenToIntegralUp from next to
432 | otherwise = enumerateFromThenToIntegralDn from next to
435-- | Enumerate an 'Integral' type in steps. @enumerateFromThenIntegral from
436-- then@ generates a stream whose first element is @from@, the second element
437-- is @then@ and the successive elements are in increments of @then - from@.
438-- The stream is bounded by the size of the 'Integral' type.
440-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) 2
443-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) (-2)
446{-# INLINE_NORMAL enumerateFromThenIntegral #-}
447enumerateFromThenIntegral
448 :: (Monad m, Integral a, Bounded a)
449 => a -> a -> Stream m a
450#ifdef USE_UNFOLDS_EVERYWHERE
451enumerateFromThenIntegral from next =
452 unfold Unfold.enumerateFromThenIntegralBounded (from, next)
454enumerateFromThenIntegral from next =
456 then enumerateFromThenToIntegralUp from next maxBound
457 else enumerateFromThenToIntegralDn from next minBound
460-- | @enumerateFromStepIntegral from step@ generates an infinite stream whose
461-- first element is @from@ and the successive elements are in increments of
464-- CAUTION: This function is not safe for finite integral types. It does not
465-- check for overflow, underflow or bounds.
467-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromStepIntegral 0 2
470-- >>> Stream.toList $ Stream.take 3 $ Stream.enumerateFromStepIntegral 0 (-2)
473{-# INLINE_NORMAL enumerateFromStepIntegral #-}
474enumerateFromStepIntegral :: (Integral a, Monad m) => a -> a -> Stream m a
475#ifdef USE_UNFOLDS_EVERYWHERE
476enumerateFromStepIntegral from stride =
477 unfold Unfold.enumerateFromStepIntegral (from, stride)
479enumerateFromStepIntegral from stride =
480 from `seq` stride `seq` Stream step from
482 {-# INLINE_LATE step #-}
483 step _ !x = return $ Yield x $! (x + stride)
486-- | Enumerate an 'Integral' type up to a given limit.
487-- @enumerateFromToIntegral from to@ generates a finite stream whose first
488-- element is @from@ and successive elements are in increments of @1@ up to
491-- >>> Stream.toList $ Stream.enumerateFromToIntegral 0 4
494{-# INLINE enumerateFromToIntegral #-}
495enumerateFromToIntegral :: (Monad m, Integral a) => a -> a -> Stream m a
496enumerateFromToIntegral from to =
497 takeWhile (<= to) $ enumerateFromStepIntegral from 1
499-- | Enumerate an 'Integral' type. @enumerateFromIntegral from@ generates a
500-- stream whose first element is @from@ and the successive elements are in
501-- increments of @1@. The stream is bounded by the size of the 'Integral' type.
503-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromIntegral (0 :: Int)
506{-# INLINE enumerateFromIntegral #-}
507enumerateFromIntegral :: (Monad m, Integral a, Bounded a) => a -> Stream m a
508enumerateFromIntegral from = enumerateFromToIntegral from maxBound
510------------------------------------------------------------------------------
511-- Enumeration of Fractionals
512------------------------------------------------------------------------------
514-- We cannot write a general function for Num. The only way to write code
515-- portable between the two is to use a 'Real' constraint and convert between
516-- Fractional and Integral using fromRational which is horribly slow.
518-- Even though the underlying implementation of enumerateFromFractional and
519-- enumerateFromThenFractional works for any 'Num' we have restricted these to
520-- 'Fractional' because these do not perform any bounds check, in contrast to
521-- integral versions and are therefore not equivalent substitutes for those.
523-- | Numerically stable enumeration from a 'Fractional' number in steps of size
524-- @1@. @enumerateFromFractional from@ generates a stream whose first element
525-- is @from@ and the successive elements are in increments of @1@. No overflow
526-- or underflow checks are performed.
528-- This is the equivalent to 'enumFrom' for 'Fractional' types. For example:
530-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromFractional 1.1
533{-# INLINE enumerateFromFractional #-}
534enumerateFromFractional :: (Monad m, Fractional a) => a -> Stream m a
535enumerateFromFractional = enumerateFromNum
537-- | Numerically stable enumeration from a 'Fractional' number in steps.
538-- @enumerateFromThenFractional from then@ generates a stream whose first
539-- element is @from@, the second element is @then@ and the successive elements
540-- are in increments of @then - from@. No overflow or underflow checks are
543-- This is the equivalent of 'enumFromThen' for 'Fractional' types. For
546-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 2.1
549-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 (-2.1)
550-- [1.1,-2.1,-5.300000000000001,-8.500000000000002]
552{-# INLINE enumerateFromThenFractional #-}
553enumerateFromThenFractional
554 :: (Monad m, Fractional a)
555 => a -> a -> Stream m a
556enumerateFromThenFractional = enumerateFromThenNum
558-- | Numerically stable enumeration from a 'Fractional' number to a given
559-- limit. @enumerateFromToFractional from to@ generates a finite stream whose
560-- first element is @from@ and successive elements are in increments of @1@ up
563-- This is the equivalent of 'enumFromTo' for 'Fractional' types. For
566-- >>> Stream.toList $ Stream.enumerateFromToFractional 1.1 4
569-- >>> Stream.toList $ Stream.enumerateFromToFractional 1.1 4.6
570-- [1.1,2.1,3.1,4.1,5.1]
572-- Notice that the last element is equal to the specified @to@ value after
573-- rounding to the nearest integer.
575{-# INLINE_NORMAL enumerateFromToFractional #-}
576enumerateFromToFractional
577 :: (Monad m, Fractional a, Ord a)
578 => a -> a -> Stream m a
579enumerateFromToFractional from to =
580 takeWhile (<= to + 1 / 2) $ enumerateFromStepNum from 1
582-- | Numerically stable enumeration from a 'Fractional' number in steps up to a
583-- given limit. @enumerateFromThenToFractional from then to@ generates a
584-- finite stream whose first element is @from@, the second element is @then@
585-- and the successive elements are in increments of @then - from@ up to @to@.
587-- This is the equivalent of 'enumFromThenTo' for 'Fractional' types. For
590-- >>> Stream.toList $ Stream.enumerateFromThenToFractional 0.1 2 6
591-- [0.1,2.0,3.9,5.799999999999999]
593-- >>> Stream.toList $ Stream.enumerateFromThenToFractional 0.1 (-2) (-6)
594-- [0.1,-2.0,-4.1000000000000005,-6.200000000000001]
596{-# INLINE_NORMAL enumerateFromThenToFractional #-}
597enumerateFromThenToFractional
598 :: (Monad m, Fractional a, Ord a)
599 => a -> a -> a -> Stream m a
600enumerateFromThenToFractional from next to =
601 takeWhile predicate $ enumerateFromThenFractional from next
603 mid = (next - from) / 2
604 predicate | next >= from = (<= to + mid)
605 | otherwise = (>= to + mid)
607-------------------------------------------------------------------------------
608-- Enumeration of Enum types not larger than Int
609-------------------------------------------------------------------------------
611-- | 'enumerateFromTo' for 'Enum' types not larger than 'Int'.
613{-# INLINE enumerateFromToSmall #-}
614enumerateFromToSmall :: (Monad m, Enum a) => a -> a -> Stream m a
615enumerateFromToSmall from to =
617 $ enumerateFromToIntegral (fromEnum from) (fromEnum to)
619-- | 'enumerateFromThenTo' for 'Enum' types not larger than 'Int'.
621{-# INLINE enumerateFromThenToSmall #-}
622enumerateFromThenToSmall :: (Monad m, Enum a)
623 => a -> a -> a -> Stream m a
624enumerateFromThenToSmall from next to =
626 $ enumerateFromThenToIntegral
627 (fromEnum from) (fromEnum next) (fromEnum to)
629-- | 'enumerateFromThen' for 'Enum' types not larger than 'Int'.
631-- Note: We convert the 'Enum' to 'Int' and enumerate the 'Int'. If a
632-- type is bounded but does not have a 'Bounded' instance then we can go on
633-- enumerating it beyond the legal values of the type, resulting in the failure
634-- of 'toEnum' when converting back to 'Enum'. Therefore we require a 'Bounded'
635-- instance for this function to be safely used.
637{-# INLINE enumerateFromThenSmallBounded #-}
638enumerateFromThenSmallBounded :: (Monad m, Enumerable a, Bounded a)
639 => a -> a -> Stream m a
640enumerateFromThenSmallBounded from next =
641 if fromEnum next >= fromEnum from
642 then enumerateFromThenTo from next maxBound
643 else enumerateFromThenTo from next minBound
645-------------------------------------------------------------------------------
646-- Enumerable type class
647-------------------------------------------------------------------------------
649-- NOTE: We would like to rewrite calls to fromList [1..] etc. to stream
650-- enumerations like this:
652-- {-# RULES "fromList enumFrom" [1]
653-- forall (a :: Int). D.fromList (enumFrom a) = D.enumerateFromIntegral a #-}
655-- But this does not work because enumFrom is a class method and GHC rewrites
656-- it quickly, so we do not get a chance to have our rule fired.
658-- | Types that can be enumerated as a stream. The operations in this type
659-- class are equivalent to those in the 'Enum' type class, except that these
660-- generate a stream instead of a list. Use the functions in
661-- "Streamly.Internal.Data.Stream.Enumeration" module to define new instances.
663class Enum a => Enumerable a where
664 -- | @enumerateFrom from@ generates a stream starting with the element
665 -- @from@, enumerating up to 'maxBound' when the type is 'Bounded' or
666 -- generating an infinite stream when the type is not 'Bounded'.
668 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFrom (0 :: Int)
671 -- For 'Fractional' types, enumeration is numerically stable. However, no
672 -- overflow or underflow checks are performed.
674 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFrom 1.1
677 enumerateFrom :: (Monad m) => a -> Stream m a
679 -- | Generate a finite stream starting with the element @from@, enumerating
680 -- the type up to the value @to@. If @to@ is smaller than @from@ then an
681 -- empty stream is returned.
683 -- >>> Stream.toList $ Stream.enumerateFromTo 0 4
686 -- For 'Fractional' types, the last element is equal to the specified @to@
687 -- value after rounding to the nearest integral value.
689 -- >>> Stream.toList $ Stream.enumerateFromTo 1.1 4
692 -- >>> Stream.toList $ Stream.enumerateFromTo 1.1 4.6
693 -- [1.1,2.1,3.1,4.1,5.1]
695 enumerateFromTo :: (Monad m) => a -> a -> Stream m a
697 -- | @enumerateFromThen from then@ generates a stream whose first element
698 -- is @from@, the second element is @then@ and the successive elements are
699 -- in increments of @then - from@. Enumeration can occur downwards or
700 -- upwards depending on whether @then@ comes before or after @from@. For
701 -- 'Bounded' types the stream ends when 'maxBound' is reached, for
702 -- unbounded types it keeps enumerating infinitely.
704 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 2
707 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 (-2)
710 enumerateFromThen :: (Monad m) => a -> a -> Stream m a
712 -- | @enumerateFromThenTo from then to@ generates a finite stream whose
713 -- first element is @from@, the second element is @then@ and the successive
714 -- elements are in increments of @then - from@ up to @to@. Enumeration can
715 -- occur downwards or upwards depending on whether @then@ comes before or
718 -- >>> Stream.toList $ Stream.enumerateFromThenTo 0 2 6
721 -- >>> Stream.toList $ Stream.enumerateFromThenTo 0 (-2) (-6)
724 enumerateFromThenTo :: (Monad m) => a -> a -> a -> Stream m a
726-- MAYBE: Sometimes it is more convenient to know the count rather then the
727-- ending or starting element. For those cases we can define the folllowing
728-- APIs. All of these will work only for bounded types if we represent the
737-------------------------------------------------------------------------------
738-- Convenient functions for bounded types
739-------------------------------------------------------------------------------
742-- > enumerate = enumerateFrom minBound
744-- Enumerate a 'Bounded' type from its 'minBound' to 'maxBound'
746{-# INLINE enumerate #-}
747enumerate :: (Monad m, Bounded a, Enumerable a) => Stream m a
748enumerate = enumerateFrom minBound
751-- >>> enumerateTo = Stream.enumerateFromTo minBound
753-- Enumerate a 'Bounded' type from its 'minBound' to specified value.
755{-# INLINE enumerateTo #-}
756enumerateTo :: (Monad m, Bounded a, Enumerable a) => a -> Stream m a
757enumerateTo = enumerateFromTo minBound
760-- >>> enumerateFromBounded from = Stream.enumerateFromTo from maxBound
762-- 'enumerateFrom' for 'Bounded' 'Enum' types.
764{-# INLINE enumerateFromBounded #-}
765enumerateFromBounded :: (Monad m, Enumerable a, Bounded a)
767enumerateFromBounded from = enumerateFromTo from maxBound
769-------------------------------------------------------------------------------
770-- Enumerable Instances
771-------------------------------------------------------------------------------
773-- For Enum types smaller than or equal to Int size.
774#define ENUMERABLE_BOUNDED_SMALL(SMALL_TYPE) \
775instance Enumerable SMALL_TYPE where { \
776 {-# INLINE enumerateFrom #-}; \
777 enumerateFrom = enumerateFromBounded; \
778 {-# INLINE enumerateFromThen #-}; \
779 enumerateFromThen = enumerateFromThenSmallBounded; \
780 {-# INLINE enumerateFromTo #-}; \
781 enumerateFromTo = enumerateFromToSmall; \
782 {-# INLINE enumerateFromThenTo #-}; \
783 enumerateFromThenTo = enumerateFromThenToSmall }
785ENUMERABLE_BOUNDED_SMALL(())
786ENUMERABLE_BOUNDED_SMALL(Bool)
787ENUMERABLE_BOUNDED_SMALL(Ordering)
788ENUMERABLE_BOUNDED_SMALL(Char)
790-- For bounded Integral Enum types, may be larger than Int.
791#define ENUMERABLE_BOUNDED_INTEGRAL(INTEGRAL_TYPE) \
792instance Enumerable INTEGRAL_TYPE where { \
793 {-# INLINE enumerateFrom #-}; \
794 enumerateFrom = enumerateFromIntegral; \
795 {-# INLINE enumerateFromThen #-}; \
796 enumerateFromThen = enumerateFromThenIntegral; \
797 {-# INLINE enumerateFromTo #-}; \
798 enumerateFromTo = enumerateFromToIntegral; \
799 {-# INLINE enumerateFromThenTo #-}; \
800 enumerateFromThenTo = enumerateFromThenToIntegral }
802ENUMERABLE_BOUNDED_INTEGRAL(Int)
803ENUMERABLE_BOUNDED_INTEGRAL(Int8)
804ENUMERABLE_BOUNDED_INTEGRAL(Int16)
805ENUMERABLE_BOUNDED_INTEGRAL(Int32)
806ENUMERABLE_BOUNDED_INTEGRAL(Int64)
807ENUMERABLE_BOUNDED_INTEGRAL(Word)
808ENUMERABLE_BOUNDED_INTEGRAL(Word8)
809ENUMERABLE_BOUNDED_INTEGRAL(Word16)
810ENUMERABLE_BOUNDED_INTEGRAL(Word32)
811ENUMERABLE_BOUNDED_INTEGRAL(Word64)
813-- For unbounded Integral Enum types.
814#define ENUMERABLE_UNBOUNDED_INTEGRAL(INTEGRAL_TYPE) \
815instance Enumerable INTEGRAL_TYPE where { \
816 {-# INLINE enumerateFrom #-}; \
817 enumerateFrom from = enumerateFromStepIntegral from 1; \
818 {-# INLINE enumerateFromThen #-}; \
819 enumerateFromThen from next = \
820 enumerateFromStepIntegral from (next - from); \
821 {-# INLINE enumerateFromTo #-}; \
822 enumerateFromTo = enumerateFromToIntegral; \
823 {-# INLINE enumerateFromThenTo #-}; \
824 enumerateFromThenTo = enumerateFromThenToIntegral }
826ENUMERABLE_UNBOUNDED_INTEGRAL(Integer)
827ENUMERABLE_UNBOUNDED_INTEGRAL(Natural)
829#define ENUMERABLE_FRACTIONAL(FRACTIONAL_TYPE,CONSTRAINT) \
830instance (CONSTRAINT) => Enumerable FRACTIONAL_TYPE where { \
831 {-# INLINE enumerateFrom #-}; \
832 enumerateFrom = enumerateFromFractional; \
833 {-# INLINE enumerateFromThen #-}; \
834 enumerateFromThen = enumerateFromThenFractional; \
835 {-# INLINE enumerateFromTo #-}; \
836 enumerateFromTo = enumerateFromToFractional; \
837 {-# INLINE enumerateFromThenTo #-}; \
838 enumerateFromThenTo = enumerateFromThenToFractional }
840ENUMERABLE_FRACTIONAL(Float,)
841ENUMERABLE_FRACTIONAL(Double,)
842ENUMERABLE_FRACTIONAL((Fixed a),HasResolution a)
843ENUMERABLE_FRACTIONAL((Ratio a),Integral a)
845instance Enumerable a => Enumerable (Identity a) where
846 {-# INLINE enumerateFrom #-}
847 enumerateFrom (Identity from) =
848 fmap Identity $ enumerateFrom from
849 {-# INLINE enumerateFromThen #-}
850 enumerateFromThen (Identity from) (Identity next) =
851 fmap Identity $ enumerateFromThen from next
852 {-# INLINE enumerateFromTo #-}
853 enumerateFromTo (Identity from) (Identity to) =
854 fmap Identity $ enumerateFromTo from to
855 {-# INLINE enumerateFromThenTo #-}
856 enumerateFromThenTo (Identity from) (Identity next) (Identity to) =
858 $ enumerateFromThenTo from next to
862instance Enumerable a => Enumerable (Last a)
863instance Enumerable a => Enumerable (First a)
864instance Enumerable a => Enumerable (Max a)
865instance Enumerable a => Enumerable (Min a)
866instance Enumerable a => Enumerable (Const a b)
867instance Enumerable (f a) => Enumerable (Alt f a)
868instance Enumerable (f a) => Enumerable (Ap f a)
870------------------------------------------------------------------------------
872------------------------------------------------------------------------------
874-- | @timesWith g@ returns a stream of time value tuples. The first component
875-- of the tuple is an absolute time reference (epoch) denoting the start of the
876-- stream and the second component is a time relative to the reference.
878-- The argument @g@ specifies the granularity of the relative time in seconds.
879-- A lower granularity clock gives higher precision but is more expensive in
880-- terms of CPU usage. Any granularity lower than 1 ms is treated as 1 ms.
882-- >>> import Control.Concurrent (threadDelay)
883-- >>> f = Fold.drainMapM (\x -> print x >> threadDelay 1000000)
884-- >>> Stream.fold f $ Stream.take 3 $ Stream.timesWith 0.01
885-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
886-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
887-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
889-- Note: This API is not safe on 32-bit machines.
893{-# INLINE_NORMAL timesWith #-}
894timesWith :: MonadIO m => Double -> Stream m (AbsTime, RelTime64)
895timesWith g = Stream step Nothing
899 {-# INLINE_LATE step #-}
901 clock <- liftIO $ asyncClock Monotonic g
902 a <- liftIO $ readClock clock
903 return $ Skip $ Just (clock, a)
905 step _ s@(Just (clock, t0)) = do
906 a <- liftIO $ readClock clock
907 -- XXX we can perhaps use an AbsTime64 using a 64 bit Int for
908 -- efficiency. or maybe we can use a representation using Double for
909 -- floating precision time
910 return $ Yield (toAbsTime t0, toRelTime64 (a - t0)) s
912-- | @absTimesWith g@ returns a stream of absolute timestamps using a clock of
913-- granularity @g@ specified in seconds. A low granularity clock is more
914-- expensive in terms of CPU usage. Any granularity lower than 1 ms is treated
917-- >>> f = Fold.drainMapM print
918-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.absTimesWith 0.01
919-- AbsTime (TimeSpec {sec = ..., nsec = ...})
920-- AbsTime (TimeSpec {sec = ..., nsec = ...})
921-- AbsTime (TimeSpec {sec = ..., nsec = ...})
923-- Note: This API is not safe on 32-bit machines.
927{-# INLINE absTimesWith #-}
928absTimesWith :: MonadIO m => Double -> Stream m AbsTime
929absTimesWith = fmap (uncurry addToAbsTime64) . timesWith
931-- | @relTimesWith g@ returns a stream of relative time values starting from 0,
932-- using a clock of granularity @g@ specified in seconds. A low granularity
933-- clock is more expensive in terms of CPU usage. Any granularity lower than 1
934-- ms is treated as 1 ms.
936-- >>> f = Fold.drainMapM print
937-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.relTimesWith 0.01
938-- RelTime64 (NanoSecond64 ...)
939-- RelTime64 (NanoSecond64 ...)
940-- RelTime64 (NanoSecond64 ...)
942-- Note: This API is not safe on 32-bit machines.
946{-# INLINE relTimesWith #-}
947relTimesWith :: MonadIO m => Double -> Stream m RelTime64
948relTimesWith = fmap snd . timesWith
950-- | @times@ returns a stream of time value tuples with clock of 10 ms
951-- granularity. The first component of the tuple is an absolute time reference
952-- (epoch) denoting the start of the stream and the second component is a time
953-- relative to the reference.
955-- >>> f = Fold.drainMapM (\x -> print x >> threadDelay 1000000)
956-- >>> Stream.fold f $ Stream.take 3 $ Stream.times
957-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
958-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
959-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
961-- Note: This API is not safe on 32-bit machines.
966times :: MonadIO m => Stream m (AbsTime, RelTime64)
967times = timesWith 0.01
969-- | @absTimes@ returns a stream of absolute timestamps using a clock of 10 ms
972-- >>> f = Fold.drainMapM print
973-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.absTimes
974-- AbsTime (TimeSpec {sec = ..., nsec = ...})
975-- AbsTime (TimeSpec {sec = ..., nsec = ...})
976-- AbsTime (TimeSpec {sec = ..., nsec = ...})
978-- Note: This API is not safe on 32-bit machines.
982{-# INLINE absTimes #-}
983absTimes :: MonadIO m => Stream m AbsTime
984absTimes = fmap (uncurry addToAbsTime64) times
986-- | @relTimes@ returns a stream of relative time values starting from 0,
987-- using a clock of granularity 10 ms.
989-- >>> f = Fold.drainMapM print
990-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.relTimes
991-- RelTime64 (NanoSecond64 ...)
992-- RelTime64 (NanoSecond64 ...)
993-- RelTime64 (NanoSecond64 ...)
995-- Note: This API is not safe on 32-bit machines.
999{-# INLINE relTimes #-}
1000relTimes :: MonadIO m => Stream m RelTime64
1001relTimes = fmap snd times
1003-- | @durations g@ returns a stream of relative time values measuring the time
1004-- elapsed since the immediate predecessor element of the stream was generated.
1005-- The first element of the stream is always 0. @durations@ uses a clock of
1006-- granularity @g@ specified in seconds. A low granularity clock is more
1007-- expensive in terms of CPU usage. The minimum granularity is 1 millisecond.
1008-- Durations lower than 1 ms will be 0.
1010-- Note: This API is not safe on 32-bit machines.
1014{-# INLINE durations #-}
1015durations :: -- Monad m =>
1016 Double -> t m RelTime64
1017durations = undefined
1019-- | Generate a singleton event at or after the specified absolute time. Note
1020-- that this is different from a threadDelay, a threadDelay starts from the
1021-- time when the action is evaluated, whereas if we use AbsTime based timeout
1022-- it will immediately expire if the action is evaluated too late.
1026{-# INLINE timeout #-}
1027timeout :: -- Monad m =>
1031-------------------------------------------------------------------------------
1033-------------------------------------------------------------------------------
1035{-# INLINE_NORMAL fromIndicesM #-}
1036fromIndicesM :: Monad m => (Int -> m a) -> Stream m a
1037#ifdef USE_UNFOLDS_EVERYWHERE
1038fromIndicesM gen = unfold (Unfold.fromIndicesM gen) 0
1040fromIndicesM gen = Stream step 0
1042 {-# INLINE_LATE step #-}
1045 return $ Yield x (i + 1)
1048{-# INLINE fromIndices #-}
1049fromIndices :: Monad m => (Int -> a) -> Stream m a
1050fromIndices gen = fromIndicesM (return . gen)
1052-- Adapted from the vector package
1053{-# INLINE_NORMAL generateM #-}
1054generateM :: Monad m => Int -> (Int -> m a) -> Stream m a
1055generateM n gen = n `seq` Stream step 0
1057 {-# INLINE_LATE step #-}
1058 step _ i | i < n = do
1060 return $ Yield x (i + 1)
1061 | otherwise = return Stop
1063{-# INLINE generate #-}
1064generate :: Monad m => Int -> (Int -> a) -> Stream m a
1065generate n gen = generateM n (return . gen)
1067-------------------------------------------------------------------------------
1069-------------------------------------------------------------------------------
1071-- | Generate an infinite stream with the first element generated by the action
1072-- @m@ and each successive element derived by applying the monadic function @f@
1073-- on the previous element.
1076-- Stream.iterateM (\x -> print x >> return (x + 1)) (return 0)
1084{-# INLINE_NORMAL iterateM #-}
1085iterateM :: Monad m => (a -> m a) -> m a -> Stream m a
1086#ifdef USE_UNFOLDS_EVERYWHERE
1087iterateM step = unfold (Unfold.iterateM step)
1089iterateM step = Stream (\_ st -> st >>= \(!x) -> return $ Yield x (step x))
1092-- | Generate an infinite stream with @x@ as the first element and each
1093-- successive element derived by applying the function @f@ on the previous
1096-- >>> Stream.toList $ Stream.take 5 $ Stream.iterate (+1) 1
1099{-# INLINE_NORMAL iterate #-}
1100iterate :: Monad m => (a -> a) -> a -> Stream m a
1101iterate step st = iterateM (return . step) (return st)
1103-------------------------------------------------------------------------------
1105-------------------------------------------------------------------------------
1107-- | Convert a list of monadic actions to a 'Stream'
1108{-# INLINE_LATE fromListM #-}
1109fromListM :: Monad m => [m a] -> Stream m a
1110#ifdef USE_UNFOLDS_EVERYWHERE
1111fromListM = unfold Unfold.fromListM
1113fromListM = Stream step
1115 {-# INLINE_LATE step #-}
1116 step _ (m:ms) = m >>= \x -> return $ Yield x ms
1117 step _ [] = return Stop
1121-- >>> fromFoldable = Prelude.foldr Stream.cons Stream.nil
1123-- Construct a stream from a 'Foldable' containing pure values:
1125-- /WARNING: O(n^2), suitable only for a small number of
1126-- elements in the stream/
1128{-# INLINE fromFoldable #-}
1129fromFoldable :: (Monad m, Foldable f) => f a -> Stream m a
1130fromFoldable = Prelude.foldr cons nil
1133-- >>> fromFoldableM = Prelude.foldr Stream.consM Stream.nil
1135-- Construct a stream from a 'Foldable' containing pure values:
1137-- /WARNING: O(n^2), suitable only for a small number of
1138-- elements in the stream/
1140{-# INLINE fromFoldableM #-}
1141fromFoldableM :: (Monad m, Foldable f) => f (m a) -> Stream m a
1142fromFoldableM = Prelude.foldr consM nil
1144-------------------------------------------------------------------------------
1146-------------------------------------------------------------------------------
1148-- | Keep reading 'Storable' elements from an immutable 'Ptr' onwards.
1150-- /Unsafe:/ The caller is responsible for safe addressing.
1153{-# INLINE fromPtr #-}
1154fromPtr :: forall m a. (Monad m, Storable a) => Ptr a -> Stream m a
1155fromPtr = Stream step
1159 {-# INLINE_LATE step #-}
1161 let !x = unsafeInlineIO $ peek p
1162 return $ Yield x (PTR_NEXT(p, a))
1164-- | Take @n@ 'Storable' elements starting from an immutable 'Ptr' onwards.
1166-- >>> fromPtrN n = Stream.take n . Stream.fromPtr
1168-- /Unsafe:/ The caller is responsible for safe addressing.
1171{-# INLINE fromPtrN #-}
1172fromPtrN :: (Monad m, Storable a) => Int -> Ptr a -> Stream m a
1173fromPtrN n = take n . fromPtr
1175-- | Read bytes from an immutable 'Addr#' until a 0 byte is encountered, the 0
1176-- byte is not included in the stream.
1178-- >>> :set -XMagicHash
1179-- >>> fromByteStr# addr = Stream.takeWhile (/= 0) $ Stream.fromPtr $ Ptr addr
1181-- /Unsafe:/ The caller is responsible for safe addressing.
1183-- Note that this is completely safe when reading from Haskell string
1184-- literals because they are guaranteed to be NULL terminated:
1186-- >>> Stream.toList $ Stream.fromByteStr# "\1\2\3\0"#
1189{-# INLINE fromByteStr# #-}
1190fromByteStr# :: Monad m => Addr# -> Stream m Word8
1191fromByteStr# 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