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
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
136import Numeric.Natural
137import Prelude hiding (iterate, repeat, replicate, take, takeWhile)
138import Streamly.Internal.Data.Stream.Type
140#include "DocTestDataStream.hs"
142------------------------------------------------------------------------------
144------------------------------------------------------------------------------
146-- XXX implement in terms of nilM?
148-- | A stream that terminates without producing any output or side effect.
150-- >>> Stream.toList Stream.nil
153{-# INLINE_NORMAL nil #-}
154nil :: Applicative m => Stream m a
155nil = Stream (\_ _ -> pure Stop) ()
157-- XXX implement in terms of consM?
158-- cons x = consM (return x)
159-- From an implementation perspective, StreamK.cons translates into a
160-- functional call whereas fused cons translates into a conditional branch
161-- (jump). However, the overhead of the function call in StreamK.cons only
162-- occurs once, while the overhead of the conditional branch in fused cons is
163-- incurred for each subsequent element in the stream. As a result,
164-- StreamK.cons has a time complexity of O(n), while fused cons has a time
165-- complexity of O(n^2), where @n@ represents the number of 'cons' used.
167-- When composing a few elements together statically, a balanced tree composed
168-- using 'cons' and 'append' is more efficient than a right associated one
169-- composed using 'cons':
171-- >>> s1 = 1 `Stream.cons` 2 `Stream.cons` Stream.nil
172-- >>> s2 = 2 `Stream.cons` 3 `Stream.cons` Stream.nil
173-- >>> s = s1 `Stream.append` s2
175-- However, generating a stream using a case statement or indexing into a
176-- static literal array would be the best. Check if the case statement
177-- translates to a look up table or a binary search.
179-- | WARNING! O(n^2) time complexity wrt number of elements. Use the O(n)
180-- complexity StreamK.'Streamly.Data.StreamK.cons' unless you want to
181-- statically fuse just a few elements.
183-- Fuse a pure value at the head of an existing stream::
185-- >>> s = 1 `Stream.cons` Stream.fromList [2,3]
186-- >>> Stream.toList s
191-- >>> cons x xs = return x `Stream.consM` xs
193{-# INLINE_NORMAL cons #-}
194cons :: Applicative m => a -> Stream m a -> Stream m a
195cons x (Stream step state) = Stream step1 Nothing
197 {-# INLINE_LATE step1 #-}
198 step1 _ Nothing = pure $ Yield x (Just state)
199 step1 gst (Just st) = do
201 Yield a s -> Yield a (Just s)
202 Skip s -> Skip (Just s)
203 Stop -> Stop) <$> step gst st
205------------------------------------------------------------------------------
207------------------------------------------------------------------------------
209-- Adapted from vector package
211-- | Build a stream by unfolding a /monadic/ step function starting from a
212-- seed. The step function returns the next element in the stream and the next
213-- seed value. When it is done it returns 'Nothing' and the stream ends. For
219-- then return Nothing
220-- else return (Just (b, b + 1))
221-- in Stream.toList $ Stream.unfoldrM f 0
225{-# INLINE_NORMAL unfoldrM #-}
226unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
227#ifdef USE_UNFOLDS_EVERYWHERE
228unfoldrM next = unfold (Unfold.unfoldrM next)
230unfoldrM next = Stream step
232 {-# INLINE_LATE step #-}
236 Just (x, s) -> Yield x s
240-- | Build a stream by unfolding a /pure/ step function @step@ starting from a
241-- seed @s@. The step function returns the next element in the stream and the
242-- next seed value. When it is done it returns 'Nothing' and the stream ends.
249-- else Just (b, b + 1)
250-- in Stream.toList $ Stream.unfoldr f 0
254{-# INLINE_LATE unfoldr #-}
255unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
256unfoldr f = unfoldrM (return . f)
258------------------------------------------------------------------------------
260------------------------------------------------------------------------------
263-- >>> repeatM = Stream.sequence . Stream.repeat
265-- Generate a stream by repeatedly executing a monadic action forever.
269-- Stream.repeatM (threadDelay 1000000 >> print 1)
271-- & Stream.fold Fold.drain
274{-# INLINE_NORMAL repeatM #-}
275repeatM :: Monad m => m a -> Stream m a
276#ifdef USE_UNFOLDS_EVERYWHERE
277repeatM = unfold Unfold.repeatM
279repeatM x = Stream (\_ _ -> x >>= \r -> return $ Yield r ()) ()
283-- Generate an infinite stream by repeating a pure value.
285-- >>> repeat x = Stream.repeatM (pure x)
287{-# INLINE_NORMAL repeat #-}
288repeat :: Monad m => a -> Stream m a
289#ifdef USE_UNFOLDS_EVERYWHERE
290repeat x = repeatM (pure x)
292repeat x = Stream (\_ _ -> return $ Yield x ()) ()
295-- Adapted from the vector package
298-- >>> replicateM n = Stream.sequence . Stream.replicate n
300-- Generate a stream by performing a monadic action @n@ times.
301{-# INLINE_NORMAL replicateM #-}
302replicateM :: Monad m => Int -> m a -> Stream m a
303#ifdef USE_UNFOLDS_EVERYWHERE
304replicateM n p = unfold Unfold.replicateM (n, p)
306replicateM n p = Stream step n
308 {-# INLINE_LATE step #-}
310 | i <= 0 = return Stop
313 return $ Yield x (i - 1)
317-- >>> replicate n = Stream.take n . Stream.repeat
318-- >>> replicate n x = Stream.replicateM n (pure x)
320-- Generate a stream of length @n@ by repeating a value @n@ times.
322{-# INLINE_NORMAL replicate #-}
323replicate :: Monad m => Int -> a -> Stream m a
324replicate n x = replicateM n (return x)
326------------------------------------------------------------------------------
328------------------------------------------------------------------------------
330-- | For floating point numbers if the increment is less than the precision then
331-- it just gets lost. Therefore we cannot always increment it correctly by just
333-- 9007199254740992 + 1 + 1 :: Double => 9.007199254740992e15
334-- 9007199254740992 + 2 :: Double => 9.007199254740994e15
336-- Instead we accumulate the increment counter and compute the increment
337-- every time before adding it to the starting number.
339-- This works for Integrals as well as floating point numbers, but
340-- enumerateFromStepIntegral is faster for integrals.
341{-# INLINE_NORMAL enumerateFromStepNum #-}
342enumerateFromStepNum :: (Monad m, Num a) => a -> a -> Stream m a
343#ifdef USE_UNFOLDS_EVERYWHERE
344enumerateFromStepNum from stride =
345 unfold Unfold.enumerateFromStepNum (from, stride)
347enumerateFromStepNum from stride = Stream step 0
349 {-# INLINE_LATE step #-}
350 step _ !i = return $ (Yield $! (from + i * stride)) $! (i + 1)
353{-# INLINE_NORMAL enumerateFromNum #-}
354enumerateFromNum :: (Monad m, Num a) => a -> Stream m a
355enumerateFromNum from = enumerateFromStepNum from 1
357{-# INLINE_NORMAL enumerateFromThenNum #-}
358enumerateFromThenNum :: (Monad m, Num a) => a -> a -> Stream m a
359enumerateFromThenNum from next = enumerateFromStepNum from (next - from)
361------------------------------------------------------------------------------
362-- Enumeration of Integrals
363------------------------------------------------------------------------------
365#ifndef USE_UNFOLDS_EVERYWHERE
366data EnumState a = EnumInit | EnumYield a a a | EnumStop
368{-# INLINE_NORMAL enumerateFromThenToIntegralUp #-}
369enumerateFromThenToIntegralUp
370 :: (Monad m, Integral a)
371 => a -> a -> a -> Stream m a
372enumerateFromThenToIntegralUp from next to = Stream step EnumInit
374 {-# INLINE_LATE step #-}
380 else Yield from EnumStop
381 else -- from <= next <= to
382 let stride = next - from
383 in Skip $ EnumYield from stride (to - stride)
385 step _ (EnumYield x stride toMinus) =
388 then Yield x EnumStop
389 else Yield x $ EnumYield (x + stride) stride toMinus
391 step _ EnumStop = return Stop
393{-# INLINE_NORMAL enumerateFromThenToIntegralDn #-}
394enumerateFromThenToIntegralDn
395 :: (Monad m, Integral a)
396 => a -> a -> a -> Stream m a
397enumerateFromThenToIntegralDn from next to = Stream step EnumInit
399 {-# INLINE_LATE step #-}
401 return $ if to > next
404 else Yield from EnumStop
405 else -- from >= next >= to
406 let stride = next - from
407 in Skip $ EnumYield from stride (to - stride)
409 step _ (EnumYield x stride toMinus) =
412 then Yield x EnumStop
413 else Yield x $ EnumYield (x + stride) stride toMinus
415 step _ EnumStop = return Stop
418-- XXX This can perhaps be simplified and written in terms of
419-- enumeratFromStepIntegral as we have done in unfolds.
421-- | Enumerate an 'Integral' type in steps up to a given limit.
422-- @enumerateFromThenToIntegral from then to@ generates a finite stream whose
423-- first element is @from@, the second element is @then@ and the successive
424-- elements are in increments of @then - from@ up to @to@.
426-- >>> Stream.toList $ Stream.enumerateFromThenToIntegral 0 2 6
429-- >>> Stream.toList $ Stream.enumerateFromThenToIntegral 0 (-2) (-6)
432{-# INLINE_NORMAL enumerateFromThenToIntegral #-}
433enumerateFromThenToIntegral
434 :: (Monad m, Integral a)
435 => a -> a -> a -> Stream m a
436#ifdef USE_UNFOLDS_EVERYWHERE
437enumerateFromThenToIntegral from next to =
438 unfold Unfold.enumerateFromThenToIntegral (from, next, to)
440enumerateFromThenToIntegral from next to
441 | next >= from = enumerateFromThenToIntegralUp from next to
442 | otherwise = enumerateFromThenToIntegralDn from next to
445-- | Enumerate an 'Integral' type in steps. @enumerateFromThenIntegral from
446-- then@ generates a stream whose first element is @from@, the second element
447-- is @then@ and the successive elements are in increments of @then - from@.
448-- The stream is bounded by the size of the 'Integral' type.
450-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) 2
453-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) (-2)
456{-# INLINE_NORMAL enumerateFromThenIntegral #-}
457enumerateFromThenIntegral
458 :: (Monad m, Integral a, Bounded a)
459 => a -> a -> Stream m a
460#ifdef USE_UNFOLDS_EVERYWHERE
461enumerateFromThenIntegral from next =
462 unfold Unfold.enumerateFromThenIntegralBounded (from, next)
464enumerateFromThenIntegral from next =
466 then enumerateFromThenToIntegralUp from next maxBound
467 else enumerateFromThenToIntegralDn from next minBound
470-- | @enumerateFromStepIntegral from step@ generates an infinite stream whose
471-- first element is @from@ and the successive elements are in increments of
474-- CAUTION: This function is not safe for finite integral types. It does not
475-- check for overflow, underflow or bounds.
477-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromStepIntegral 0 2
480-- >>> Stream.toList $ Stream.take 3 $ Stream.enumerateFromStepIntegral 0 (-2)
483{-# INLINE_NORMAL enumerateFromStepIntegral #-}
484enumerateFromStepIntegral :: (Integral a, Monad m) => a -> a -> Stream m a
485#ifdef USE_UNFOLDS_EVERYWHERE
486enumerateFromStepIntegral from stride =
487 unfold Unfold.enumerateFromStepIntegral (from, stride)
489enumerateFromStepIntegral from stride =
490 from `seq` stride `seq` Stream step from
492 {-# INLINE_LATE step #-}
493 step _ !x = return $ Yield x $! (x + stride)
496-- | Enumerate an 'Integral' type up to a given limit.
497-- @enumerateFromToIntegral from to@ generates a finite stream whose first
498-- element is @from@ and successive elements are in increments of @1@ up to
501-- >>> Stream.toList $ Stream.enumerateFromToIntegral 0 4
504{-# INLINE enumerateFromToIntegral #-}
505enumerateFromToIntegral :: (Monad m, Integral a) => a -> a -> Stream m a
506enumerateFromToIntegral from to =
507 takeWhile (<= to) $ enumerateFromStepIntegral from 1
509-- | Enumerate an 'Integral' type. @enumerateFromIntegral from@ generates a
510-- stream whose first element is @from@ and the successive elements are in
511-- increments of @1@. The stream is bounded by the size of the 'Integral' type.
513-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromIntegral (0 :: Int)
516{-# INLINE enumerateFromIntegral #-}
517enumerateFromIntegral :: (Monad m, Integral a, Bounded a) => a -> Stream m a
518enumerateFromIntegral from = enumerateFromToIntegral from maxBound
520------------------------------------------------------------------------------
521-- Enumeration of Fractionals
522------------------------------------------------------------------------------
524-- We cannot write a general function for Num. The only way to write code
525-- portable between the two is to use a 'Real' constraint and convert between
526-- Fractional and Integral using fromRational which is horribly slow.
528-- Even though the underlying implementation of enumerateFromFractional and
529-- enumerateFromThenFractional works for any 'Num' we have restricted these to
530-- 'Fractional' because these do not perform any bounds check, in contrast to
531-- integral versions and are therefore not equivalent substitutes for those.
533-- | Numerically stable enumeration from a 'Fractional' number in steps of size
534-- @1@. @enumerateFromFractional from@ generates a stream whose first element
535-- is @from@ and the successive elements are in increments of @1@. No overflow
536-- or underflow checks are performed.
538-- This is the equivalent to 'enumFrom' for 'Fractional' types. For example:
540-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromFractional 1.1
543{-# INLINE enumerateFromFractional #-}
544enumerateFromFractional :: (Monad m, Fractional a) => a -> Stream m a
545enumerateFromFractional = enumerateFromNum
547-- | Numerically stable enumeration from a 'Fractional' number in steps.
548-- @enumerateFromThenFractional from then@ generates a stream whose first
549-- element is @from@, the second element is @then@ and the successive elements
550-- are in increments of @then - from@. No overflow or underflow checks are
553-- This is the equivalent of 'enumFromThen' for 'Fractional' types. For
556-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 2.1
559-- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 (-2.1)
560-- [1.1,-2.1,-5.300000000000001,-8.500000000000002]
562{-# INLINE enumerateFromThenFractional #-}
563enumerateFromThenFractional
564 :: (Monad m, Fractional a)
565 => a -> a -> Stream m a
566enumerateFromThenFractional = enumerateFromThenNum
568-- | Numerically stable enumeration from a 'Fractional' number to a given
569-- limit. @enumerateFromToFractional from to@ generates a finite stream whose
570-- first element is @from@ and successive elements are in increments of @1@ up
573-- This is the equivalent of 'enumFromTo' for 'Fractional' types. For
576-- >>> Stream.toList $ Stream.enumerateFromToFractional 1.1 4
579-- >>> Stream.toList $ Stream.enumerateFromToFractional 1.1 4.6
580-- [1.1,2.1,3.1,4.1,5.1]
582-- Notice that the last element is equal to the specified @to@ value after
583-- rounding to the nearest integer.
585{-# INLINE_NORMAL enumerateFromToFractional #-}
586enumerateFromToFractional
587 :: (Monad m, Fractional a, Ord a)
588 => a -> a -> Stream m a
589enumerateFromToFractional from to =
590 takeWhile (<= to + 1 / 2) $ enumerateFromStepNum from 1
592-- | Numerically stable enumeration from a 'Fractional' number in steps up to a
593-- given limit. @enumerateFromThenToFractional from then to@ generates a
594-- finite stream whose first element is @from@, the second element is @then@
595-- and the successive elements are in increments of @then - from@ up to @to@.
597-- This is the equivalent of 'enumFromThenTo' for 'Fractional' types. For
600-- >>> Stream.toList $ Stream.enumerateFromThenToFractional 0.1 2 6
601-- [0.1,2.0,3.9,5.799999999999999]
603-- >>> Stream.toList $ Stream.enumerateFromThenToFractional 0.1 (-2) (-6)
604-- [0.1,-2.0,-4.1000000000000005,-6.200000000000001]
606{-# INLINE_NORMAL enumerateFromThenToFractional #-}
607enumerateFromThenToFractional
608 :: (Monad m, Fractional a, Ord a)
609 => a -> a -> a -> Stream m a
610enumerateFromThenToFractional from next to =
611 takeWhile predicate $ enumerateFromThenFractional from next
613 mid = (next - from) / 2
614 predicate | next >= from = (<= to + mid)
615 | otherwise = (>= to + mid)
617-------------------------------------------------------------------------------
618-- Enumeration of Enum types not larger than Int
619-------------------------------------------------------------------------------
621-- | 'enumerateFromTo' for 'Enum' types not larger than 'Int'.
623{-# INLINE enumerateFromToSmall #-}
624enumerateFromToSmall :: (Monad m, Enum a) => a -> a -> Stream m a
625enumerateFromToSmall from to =
627 $ enumerateFromToIntegral (fromEnum from) (fromEnum to)
629-- | 'enumerateFromThenTo' for 'Enum' types not larger than 'Int'.
631{-# INLINE enumerateFromThenToSmall #-}
632enumerateFromThenToSmall :: (Monad m, Enum a)
633 => a -> a -> a -> Stream m a
634enumerateFromThenToSmall from next to =
636 $ enumerateFromThenToIntegral
637 (fromEnum from) (fromEnum next) (fromEnum to)
639-- | 'enumerateFromThen' for 'Enum' types not larger than 'Int'.
641-- Note: We convert the 'Enum' to 'Int' and enumerate the 'Int'. If a
642-- type is bounded but does not have a 'Bounded' instance then we can go on
643-- enumerating it beyond the legal values of the type, resulting in the failure
644-- of 'toEnum' when converting back to 'Enum'. Therefore we require a 'Bounded'
645-- instance for this function to be safely used.
647{-# INLINE enumerateFromThenSmallBounded #-}
648enumerateFromThenSmallBounded :: (Monad m, Enumerable a, Bounded a)
649 => a -> a -> Stream m a
650enumerateFromThenSmallBounded from next =
651 if fromEnum next >= fromEnum from
652 then enumerateFromThenTo from next maxBound
653 else enumerateFromThenTo from next minBound
655-------------------------------------------------------------------------------
656-- Enumerable type class
657-------------------------------------------------------------------------------
659-- NOTE: We would like to rewrite calls to fromList [1..] etc. to stream
660-- enumerations like this:
662-- {-# RULES "fromList enumFrom" [1]
663-- forall (a :: Int). D.fromList (enumFrom a) = D.enumerateFromIntegral a #-}
665-- But this does not work because enumFrom is a class method and GHC rewrites
666-- it quickly, so we do not get a chance to have our rule fired.
668-- | Types that can be enumerated as a stream. The operations in this type
669-- class are equivalent to those in the 'Enum' type class, except that these
670-- generate a stream instead of a list. Use the functions in
671-- "Streamly.Internal.Data.Stream.Enumeration" module to define new instances.
673class Enum a => Enumerable a where
674 -- | @enumerateFrom from@ generates a stream starting with the element
675 -- @from@, enumerating up to 'maxBound' when the type is 'Bounded' or
676 -- generating an infinite stream when the type is not 'Bounded'.
678 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFrom (0 :: Int)
681 -- For 'Fractional' types, enumeration is numerically stable. However, no
682 -- overflow or underflow checks are performed.
684 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFrom 1.1
687 enumerateFrom :: (Monad m) => a -> Stream m a
689 -- | Generate a finite stream starting with the element @from@, enumerating
690 -- the type up to the value @to@. If @to@ is smaller than @from@ then an
691 -- empty stream is returned.
693 -- >>> Stream.toList $ Stream.enumerateFromTo 0 4
696 -- For 'Fractional' types, the last element is equal to the specified @to@
697 -- value after rounding to the nearest integral value.
699 -- >>> Stream.toList $ Stream.enumerateFromTo 1.1 4
702 -- >>> Stream.toList $ Stream.enumerateFromTo 1.1 4.6
703 -- [1.1,2.1,3.1,4.1,5.1]
705 enumerateFromTo :: (Monad m) => a -> a -> Stream m a
707 -- | @enumerateFromThen from then@ generates a stream whose first element
708 -- is @from@, the second element is @then@ and the successive elements are
709 -- in increments of @then - from@. Enumeration can occur downwards or
710 -- upwards depending on whether @then@ comes before or after @from@. For
711 -- 'Bounded' types the stream ends when 'maxBound' is reached, for
712 -- unbounded types it keeps enumerating infinitely.
714 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 2
717 -- >>> Stream.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 (-2)
720 enumerateFromThen :: (Monad m) => a -> a -> Stream m a
722 -- | @enumerateFromThenTo from then to@ generates a finite stream whose
723 -- first element is @from@, the second element is @then@ and the successive
724 -- elements are in increments of @then - from@ up to @to@. Enumeration can
725 -- occur downwards or upwards depending on whether @then@ comes before or
728 -- >>> Stream.toList $ Stream.enumerateFromThenTo 0 2 6
731 -- >>> Stream.toList $ Stream.enumerateFromThenTo 0 (-2) (-6)
734 enumerateFromThenTo :: (Monad m) => a -> a -> a -> Stream m a
736-- MAYBE: Sometimes it is more convenient to know the count rather then the
737-- ending or starting element. For those cases we can define the folllowing
738-- APIs. All of these will work only for bounded types if we represent the
747-------------------------------------------------------------------------------
748-- Convenient functions for bounded types
749-------------------------------------------------------------------------------
752-- > enumerate = enumerateFrom minBound
754-- Enumerate a 'Bounded' type from its 'minBound' to 'maxBound'
756{-# INLINE enumerate #-}
757enumerate :: (Monad m, Bounded a, Enumerable a) => Stream m a
758enumerate = enumerateFrom minBound
761-- >>> enumerateTo = Stream.enumerateFromTo minBound
763-- Enumerate a 'Bounded' type from its 'minBound' to specified value.
765{-# INLINE enumerateTo #-}
766enumerateTo :: (Monad m, Bounded a, Enumerable a) => a -> Stream m a
767enumerateTo = enumerateFromTo minBound
770-- >>> enumerateFromBounded from = Stream.enumerateFromTo from maxBound
772-- 'enumerateFrom' for 'Bounded' 'Enum' types.
774{-# INLINE enumerateFromBounded #-}
775enumerateFromBounded :: (Monad m, Enumerable a, Bounded a)
777enumerateFromBounded from = enumerateFromTo from maxBound
779-------------------------------------------------------------------------------
780-- Enumerable Instances
781-------------------------------------------------------------------------------
783-- For Enum types smaller than or equal to Int size.
784#define ENUMERABLE_BOUNDED_SMALL(SMALL_TYPE) \
785instance Enumerable SMALL_TYPE where { \
786 {-# INLINE enumerateFrom #-}; \
787 enumerateFrom = enumerateFromBounded; \
788 {-# INLINE enumerateFromThen #-}; \
789 enumerateFromThen = enumerateFromThenSmallBounded; \
790 {-# INLINE enumerateFromTo #-}; \
791 enumerateFromTo = enumerateFromToSmall; \
792 {-# INLINE enumerateFromThenTo #-}; \
793 enumerateFromThenTo = enumerateFromThenToSmall }
795ENUMERABLE_BOUNDED_SMALL(())
796ENUMERABLE_BOUNDED_SMALL(Bool)
797ENUMERABLE_BOUNDED_SMALL(Ordering)
798ENUMERABLE_BOUNDED_SMALL(Char)
800-- For bounded Integral Enum types, may be larger than Int.
801#define ENUMERABLE_BOUNDED_INTEGRAL(INTEGRAL_TYPE) \
802instance Enumerable INTEGRAL_TYPE where { \
803 {-# INLINE enumerateFrom #-}; \
804 enumerateFrom = enumerateFromIntegral; \
805 {-# INLINE enumerateFromThen #-}; \
806 enumerateFromThen = enumerateFromThenIntegral; \
807 {-# INLINE enumerateFromTo #-}; \
808 enumerateFromTo = enumerateFromToIntegral; \
809 {-# INLINE enumerateFromThenTo #-}; \
810 enumerateFromThenTo = enumerateFromThenToIntegral }
812ENUMERABLE_BOUNDED_INTEGRAL(Int)
813ENUMERABLE_BOUNDED_INTEGRAL(Int8)
814ENUMERABLE_BOUNDED_INTEGRAL(Int16)
815ENUMERABLE_BOUNDED_INTEGRAL(Int32)
816ENUMERABLE_BOUNDED_INTEGRAL(Int64)
817ENUMERABLE_BOUNDED_INTEGRAL(Word)
818ENUMERABLE_BOUNDED_INTEGRAL(Word8)
819ENUMERABLE_BOUNDED_INTEGRAL(Word16)
820ENUMERABLE_BOUNDED_INTEGRAL(Word32)
821ENUMERABLE_BOUNDED_INTEGRAL(Word64)
823-- For unbounded Integral Enum types.
824#define ENUMERABLE_UNBOUNDED_INTEGRAL(INTEGRAL_TYPE) \
825instance Enumerable INTEGRAL_TYPE where { \
826 {-# INLINE enumerateFrom #-}; \
827 enumerateFrom from = enumerateFromStepIntegral from 1; \
828 {-# INLINE enumerateFromThen #-}; \
829 enumerateFromThen from next = \
830 enumerateFromStepIntegral from (next - from); \
831 {-# INLINE enumerateFromTo #-}; \
832 enumerateFromTo = enumerateFromToIntegral; \
833 {-# INLINE enumerateFromThenTo #-}; \
834 enumerateFromThenTo = enumerateFromThenToIntegral }
836ENUMERABLE_UNBOUNDED_INTEGRAL(Integer)
837ENUMERABLE_UNBOUNDED_INTEGRAL(Natural)
839#define ENUMERABLE_FRACTIONAL(FRACTIONAL_TYPE,CONSTRAINT) \
840instance (CONSTRAINT) => Enumerable FRACTIONAL_TYPE where { \
841 {-# INLINE enumerateFrom #-}; \
842 enumerateFrom = enumerateFromFractional; \
843 {-# INLINE enumerateFromThen #-}; \
844 enumerateFromThen = enumerateFromThenFractional; \
845 {-# INLINE enumerateFromTo #-}; \
846 enumerateFromTo = enumerateFromToFractional; \
847 {-# INLINE enumerateFromThenTo #-}; \
848 enumerateFromThenTo = enumerateFromThenToFractional }
850ENUMERABLE_FRACTIONAL(Float,)
851ENUMERABLE_FRACTIONAL(Double,)
852ENUMERABLE_FRACTIONAL((Fixed a),HasResolution a)
853ENUMERABLE_FRACTIONAL((Ratio a),Integral a)
855instance Enumerable a => Enumerable (Identity a) where
856 {-# INLINE enumerateFrom #-}
857 enumerateFrom (Identity from) =
858 fmap Identity $ enumerateFrom from
859 {-# INLINE enumerateFromThen #-}
860 enumerateFromThen (Identity from) (Identity next) =
861 fmap Identity $ enumerateFromThen from next
862 {-# INLINE enumerateFromTo #-}
863 enumerateFromTo (Identity from) (Identity to) =
864 fmap Identity $ enumerateFromTo from to
865 {-# INLINE enumerateFromThenTo #-}
866 enumerateFromThenTo (Identity from) (Identity next) (Identity to) =
868 $ enumerateFromThenTo from next to
872instance Enumerable a => Enumerable (Last a)
873instance Enumerable a => Enumerable (First a)
874instance Enumerable a => Enumerable (Max a)
875instance Enumerable a => Enumerable (Min a)
876instance Enumerable a => Enumerable (Const a b)
877instance Enumerable (f a) => Enumerable (Alt f a)
878instance Enumerable (f a) => Enumerable (Ap f a)
880------------------------------------------------------------------------------
882------------------------------------------------------------------------------
884-- | @timesWith g@ returns a stream of time value tuples. The first component
885-- of the tuple is an absolute time reference (epoch) denoting the start of the
886-- stream and the second component is a time relative to the reference.
888-- The argument @g@ specifies the granularity of the relative time in seconds.
889-- A lower granularity clock gives higher precision but is more expensive in
890-- terms of CPU usage. Any granularity lower than 1 ms is treated as 1 ms.
892-- >>> import Control.Concurrent (threadDelay)
893-- >>> f = Fold.drainMapM (\x -> print x >> threadDelay 1000000)
894-- >>> Stream.fold f $ Stream.take 3 $ Stream.timesWith 0.01
895-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
896-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
897-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
899-- Note: This API is not safe on 32-bit machines.
903{-# INLINE_NORMAL timesWith #-}
904timesWith :: MonadIO m => Double -> Stream m (AbsTime, RelTime64)
905timesWith g = Stream step Nothing
909 {-# INLINE_LATE step #-}
911 clock <- liftIO $ asyncClock Monotonic g
912 a <- liftIO $ readClock clock
913 return $ Skip $ Just (clock, a)
915 step _ s@(Just (clock, t0)) = do
916 a <- liftIO $ readClock clock
917 -- XXX we can perhaps use an AbsTime64 using a 64 bit Int for
918 -- efficiency. or maybe we can use a representation using Double for
919 -- floating precision time
920 return $ Yield (toAbsTime t0, toRelTime64 (a - t0)) s
922-- | @absTimesWith g@ returns a stream of absolute timestamps using a clock of
923-- granularity @g@ specified in seconds. A low granularity clock is more
924-- expensive in terms of CPU usage. Any granularity lower than 1 ms is treated
927-- >>> f = Fold.drainMapM print
928-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.absTimesWith 0.01
929-- AbsTime (TimeSpec {sec = ..., nsec = ...})
930-- AbsTime (TimeSpec {sec = ..., nsec = ...})
931-- AbsTime (TimeSpec {sec = ..., nsec = ...})
933-- Note: This API is not safe on 32-bit machines.
937{-# INLINE absTimesWith #-}
938absTimesWith :: MonadIO m => Double -> Stream m AbsTime
939absTimesWith = fmap (uncurry addToAbsTime64) . timesWith
941-- | @relTimesWith g@ returns a stream of relative time values starting from 0,
942-- using a clock of granularity @g@ specified in seconds. A low granularity
943-- clock is more expensive in terms of CPU usage. Any granularity lower than 1
944-- ms is treated as 1 ms.
946-- >>> f = Fold.drainMapM print
947-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.relTimesWith 0.01
948-- RelTime64 (NanoSecond64 ...)
949-- RelTime64 (NanoSecond64 ...)
950-- RelTime64 (NanoSecond64 ...)
952-- Note: This API is not safe on 32-bit machines.
956{-# INLINE relTimesWith #-}
957relTimesWith :: MonadIO m => Double -> Stream m RelTime64
958relTimesWith = fmap snd . timesWith
960-- | @times@ returns a stream of time value tuples with clock of 10 ms
961-- granularity. The first component of the tuple is an absolute time reference
962-- (epoch) denoting the start of the stream and the second component is a time
963-- relative to the reference.
965-- >>> f = Fold.drainMapM (\x -> print x >> threadDelay 1000000)
966-- >>> Stream.fold f $ Stream.take 3 $ Stream.times
967-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
968-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
969-- (AbsTime (TimeSpec {sec = ..., nsec = ...}),RelTime64 (NanoSecond64 ...))
971-- Note: This API is not safe on 32-bit machines.
976times :: MonadIO m => Stream m (AbsTime, RelTime64)
977times = timesWith 0.01
979-- | @absTimes@ returns a stream of absolute timestamps using a clock of 10 ms
982-- >>> f = Fold.drainMapM print
983-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.absTimes
984-- AbsTime (TimeSpec {sec = ..., nsec = ...})
985-- AbsTime (TimeSpec {sec = ..., nsec = ...})
986-- AbsTime (TimeSpec {sec = ..., nsec = ...})
988-- Note: This API is not safe on 32-bit machines.
992{-# INLINE absTimes #-}
993absTimes :: MonadIO m => Stream m AbsTime
994absTimes = fmap (uncurry addToAbsTime64) times
996-- | @relTimes@ returns a stream of relative time values starting from 0,
997-- using a clock of granularity 10 ms.
999-- >>> f = Fold.drainMapM print
1000-- >>> Stream.fold f $ Stream.delayPre 1 $ Stream.take 3 $ Stream.relTimes
1001-- RelTime64 (NanoSecond64 ...)
1002-- RelTime64 (NanoSecond64 ...)
1003-- RelTime64 (NanoSecond64 ...)
1005-- Note: This API is not safe on 32-bit machines.
1009{-# INLINE relTimes #-}
1010relTimes :: MonadIO m => Stream m RelTime64
1011relTimes = fmap snd times
1013-- | @durations g@ returns a stream of relative time values measuring the time
1014-- elapsed since the immediate predecessor element of the stream was generated.
1015-- The first element of the stream is always 0. @durations@ uses a clock of
1016-- granularity @g@ specified in seconds. A low granularity clock is more
1017-- expensive in terms of CPU usage. The minimum granularity is 1 millisecond.
1018-- Durations lower than 1 ms will be 0.
1020-- Note: This API is not safe on 32-bit machines.
1024{-# INLINE durations #-}
1025durations :: -- Monad m =>
1026 Double -> t m RelTime64
1027durations = undefined
1029-- | Generate a singleton event at or after the specified absolute time. Note
1030-- that this is different from a threadDelay, a threadDelay starts from the
1031-- time when the action is evaluated, whereas if we use AbsTime based timeout
1032-- it will immediately expire if the action is evaluated too late.
1036{-# INLINE timeout #-}
1037timeout :: -- Monad m =>
1041-------------------------------------------------------------------------------
1043-------------------------------------------------------------------------------
1045{-# INLINE_NORMAL fromIndicesM #-}
1046fromIndicesM :: Monad m => (Int -> m a) -> Stream m a
1047#ifdef USE_UNFOLDS_EVERYWHERE
1048fromIndicesM gen = unfold (Unfold.fromIndicesM gen) 0
1050fromIndicesM gen = Stream step 0
1052 {-# INLINE_LATE step #-}
1055 return $ Yield x (i + 1)
1058{-# INLINE fromIndices #-}
1059fromIndices :: Monad m => (Int -> a) -> Stream m a
1060fromIndices gen = fromIndicesM (return . gen)
1062-- Adapted from the vector package
1063{-# INLINE_NORMAL generateM #-}
1064generateM :: Monad m => Int -> (Int -> m a) -> Stream m a
1065generateM n gen = n `seq` Stream step 0
1067 {-# INLINE_LATE step #-}
1068 step _ i | i < n = do
1070 return $ Yield x (i + 1)
1071 | otherwise = return Stop
1073{-# INLINE generate #-}
1074generate :: Monad m => Int -> (Int -> a) -> Stream m a
1075generate n gen = generateM n (return . gen)
1077-------------------------------------------------------------------------------
1079-------------------------------------------------------------------------------
1081-- | Generate an infinite stream with the first element generated by the action
1082-- @m@ and each successive element derived by applying the monadic function @f@
1083-- on the previous element.
1086-- Stream.iterateM (\x -> print x >> return (x + 1)) (return 0)
1094{-# INLINE_NORMAL iterateM #-}
1095iterateM :: Monad m => (a -> m a) -> m a -> Stream m a
1096#ifdef USE_UNFOLDS_EVERYWHERE
1097iterateM step = unfold (Unfold.iterateM step)
1099iterateM step = Stream (\_ st -> st >>= \(!x) -> return $ Yield x (step x))
1102-- | Generate an infinite stream with @x@ as the first element and each
1103-- successive element derived by applying the function @f@ on the previous
1106-- >>> Stream.toList $ Stream.take 5 $ Stream.iterate (+1) 1
1109{-# INLINE_NORMAL iterate #-}
1110iterate :: Monad m => (a -> a) -> a -> Stream m a
1111iterate step st = iterateM (return . step) (return st)
1113-------------------------------------------------------------------------------
1115-------------------------------------------------------------------------------
1117-- | Convert a list of monadic actions to a 'Stream'
1118{-# INLINE_LATE fromListM #-}
1119fromListM :: Monad m => [m a] -> Stream m a
1120#ifdef USE_UNFOLDS_EVERYWHERE
1121fromListM = unfold Unfold.fromListM
1123fromListM = Stream step
1125 {-# INLINE_LATE step #-}
1126 step _ (m:ms) = m >>= \x -> return $ Yield x ms
1127 step _ [] = return Stop
1131-- >>> fromFoldable = Prelude.foldr Stream.cons Stream.nil
1133-- Construct a stream from a 'Foldable' containing pure values:
1135-- /WARNING: O(n^2), suitable only for a small number of
1136-- elements in the stream/
1138{-# INLINE fromFoldable #-}
1139fromFoldable :: (Monad m, Foldable f) => f a -> Stream m a
1140fromFoldable = Prelude.foldr cons nil
1143-- >>> fromFoldableM = Prelude.foldr Stream.consM Stream.nil
1145-- Construct a stream from a 'Foldable' containing pure values:
1147-- /WARNING: O(n^2), suitable only for a small number of
1148-- elements in the stream/
1150{-# INLINE fromFoldableM #-}
1151fromFoldableM :: (Monad m, Foldable f) => f (m a) -> Stream m a
1152fromFoldableM = Prelude.foldr consM nil
1154-------------------------------------------------------------------------------
1156-------------------------------------------------------------------------------
1158-- | Keep reading 'Storable' elements from an immutable 'Ptr' onwards.
1160-- /Unsafe:/ The caller is responsible for safe addressing.
1163{-# INLINE fromPtr #-}
1164fromPtr :: forall m a. (Monad m, Storable a) => Ptr a -> Stream m a
1165fromPtr = Stream step
1169 {-# INLINE_LATE step #-}
1171 let !x = unsafeInlineIO $ peek p
1172 return $ Yield x (PTR_NEXT(p, a))
1174-- | Take @n@ 'Storable' elements starting from an immutable 'Ptr' onwards.
1176-- >>> fromPtrN n = Stream.take n . Stream.fromPtr
1178-- /Unsafe:/ The caller is responsible for safe addressing.
1181{-# INLINE fromPtrN #-}
1182fromPtrN :: (Monad m, Storable a) => Int -> Ptr a -> Stream m a
1183fromPtrN n = take n . fromPtr
1185-- | Read bytes from an immutable 'Addr#' until a 0 byte is encountered, the 0
1186-- byte is not included in the stream.
1188-- >>> :set -XMagicHash
1189-- >>> fromByteStr# addr = Stream.takeWhile (/= 0) $ Stream.fromPtr $ Ptr addr
1191-- /Unsafe:/ The caller is responsible for safe addressing.
1193-- Note that this is completely safe when reading from Haskell string
1194-- literals because they are guaranteed to be NULL terminated:
1196-- >>> Stream.toList $ Stream.fromByteStr# "\1\2\3\0"#
1199{-# INLINE fromByteStr# #-}
1200fromByteStr# :: Monad m => Addr# -> Stream m Word8
1201fromByteStr# 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