2-- Module : Streamly.Internal.Data.Stream.Enumerate
3-- Copyright : (c) 2018 Composewell Technologies
6-- Maintainer : streamly@composewell.com
7-- Stability : experimental
10-- The functions defined in this module should be rarely needed for direct use,
11-- try to use the operations from the 'Enumerable' type class
14-- This module provides an 'Enumerable' type class to enumerate 'Enum' types
15-- into a stream. The operations in this type class correspond to similar
16-- perations in the 'Enum' type class, the only difference is that they produce
17-- a stream instead of a list. These operations cannot be defined generically
18-- based on the 'Enum' type class. We provide instances for commonly used
19-- types. If instances for other types are needed convenience functions defined
20-- in this module can be used to define them. Alternatively, these functions
21-- can be used directly.
23-- XXX The Unfold.Enumeration module is more modular, check the differences and
26module Streamly.Internal.Data.Stream.Enumerate
30 -- ** Enumerating 'Bounded' 'Enum' Types
33 , enumerateFromBounded
35 -- ** Enumerating 'Enum' Types not larger than 'Int'
36 , enumerateFromToSmall
37 , enumerateFromThenToSmall
38 , enumerateFromThenSmallBounded
40 -- ** Enumerating 'Bounded' 'Integral' Types
41 , enumerateFromIntegral
42 , enumerateFromThenIntegral
44 -- ** Enumerating 'Integral' Types
45 , enumerateFromToIntegral
46 , enumerateFromThenToIntegral
48 -- ** Enumerating unbounded 'Integral' Types
49 , enumerateFromStepIntegral
51 -- ** Enumerating 'Fractional' Types
52 , enumerateFromFractional
53 , enumerateFromToFractional
54 , enumerateFromThenFractional
55 , enumerateFromThenToFractional
64import Data.Functor.Identity (Identity(..))
66import Streamly.Internal.Data.Stream.Type (Stream, fromStreamD)
68import qualified Streamly.Internal.Data.Stream.StreamD.Generate as D
71-- >>> import Streamly.Data.Fold as Fold
72-- >>> import Streamly.Internal.Data.Stream as Stream
73-- >>> import Streamly.Internal.Data.Stream.Enumerate as Stream
75-------------------------------------------------------------------------------
76-- Enumeration of Integral types
77-------------------------------------------------------------------------------
79-- | @enumerateFromStepIntegral from step@ generates an infinite stream whose
80-- first element is @from@ and the successive elements are in increments of
83-- CAUTION: This function is not safe for finite integral types. It does not
84-- check for overflow, underflow or bounds.
87-- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromStepIntegral 0 2
90-- >>> Stream.fold Fold.toList $ Stream.take 3 $ Stream.enumerateFromStepIntegral 0 (-2)
96{-# INLINE enumerateFromStepIntegral #-}
97enumerateFromStepIntegral
98 :: (Monad m, Integral a)
99 => a -> a -> Stream m a
100enumerateFromStepIntegral from stride =
101 fromStreamD $ D.enumerateFromStepIntegral from stride
103-- | Enumerate an 'Integral' type. @enumerateFromIntegral from@ generates a
104-- stream whose first element is @from@ and the successive elements are in
105-- increments of @1@. The stream is bounded by the size of the 'Integral' type.
108-- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromIntegral (0 :: Int)
114{-# INLINE enumerateFromIntegral #-}
116 :: (Monad m, Integral a, Bounded a)
118enumerateFromIntegral from = fromStreamD $ D.enumerateFromIntegral from
120-- | Enumerate an 'Integral' type in steps. @enumerateFromThenIntegral from
121-- then@ generates a stream whose first element is @from@, the second element
122-- is @then@ and the successive elements are in increments of @then - from@.
123-- The stream is bounded by the size of the 'Integral' type.
126-- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) 2
129-- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromThenIntegral (0 :: Int) (-2)
135{-# INLINE enumerateFromThenIntegral #-}
136enumerateFromThenIntegral
137 :: (Monad m, Integral a, Bounded a)
138 => a -> a -> Stream m a
139enumerateFromThenIntegral from next =
140 fromStreamD $ D.enumerateFromThenIntegral from next
142-- | Enumerate an 'Integral' type up to a given limit.
143-- @enumerateFromToIntegral from to@ generates a finite stream whose first
144-- element is @from@ and successive elements are in increments of @1@ up to
148-- >>> Stream.fold Fold.toList $ Stream.enumerateFromToIntegral 0 4
154{-# INLINE enumerateFromToIntegral #-}
155enumerateFromToIntegral :: (Monad m, Integral a) => a -> a -> Stream m a
156enumerateFromToIntegral from to =
157 fromStreamD $ D.enumerateFromToIntegral from to
159-- | Enumerate an 'Integral' type in steps up to a given limit.
160-- @enumerateFromThenToIntegral from then to@ generates a finite stream whose
161-- first element is @from@, the second element is @then@ and the successive
162-- elements are in increments of @then - from@ up to @to@.
165-- >>> Stream.fold Fold.toList $ Stream.enumerateFromThenToIntegral 0 2 6
168-- >>> Stream.fold Fold.toList $ Stream.enumerateFromThenToIntegral 0 (-2) (-6)
174{-# INLINE enumerateFromThenToIntegral #-}
175enumerateFromThenToIntegral
176 :: (Monad m, Integral a)
177 => a -> a -> a -> Stream m a
178enumerateFromThenToIntegral from next to =
179 fromStreamD $ D.enumerateFromThenToIntegral from next to
181-------------------------------------------------------------------------------
182-- Enumeration of Fractional types
183-------------------------------------------------------------------------------
185-- Even though the underlying implementation of enumerateFromFractional and
186-- enumerateFromThenFractional works for any 'Num' we have restricted these to
187-- 'Fractional' because these do not perform any bounds check, in contrast to
188-- integral versions and are therefore not equivalent substitutes for those.
190-- | Numerically stable enumeration from a 'Fractional' number in steps of size
191-- @1@. @enumerateFromFractional from@ generates a stream whose first element
192-- is @from@ and the successive elements are in increments of @1@. No overflow
193-- or underflow checks are performed.
195-- This is the equivalent to 'enumFrom' for 'Fractional' types. For example:
198-- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromFractional 1.1
205{-# INLINE enumerateFromFractional #-}
206enumerateFromFractional :: (Monad m, Fractional a) => a -> Stream m a
207enumerateFromFractional from = fromStreamD $ D.enumerateFromNum from
209-- | Numerically stable enumeration from a 'Fractional' number in steps.
210-- @enumerateFromThenFractional from then@ generates a stream whose first
211-- element is @from@, the second element is @then@ and the successive elements
212-- are in increments of @then - from@. No overflow or underflow checks are
215-- This is the equivalent of 'enumFromThen' for 'Fractional' types. For
219-- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 2.1
222-- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromThenFractional 1.1 (-2.1)
223-- [1.1,-2.1,-5.300000000000001,-8.500000000000002]
228{-# INLINE enumerateFromThenFractional #-}
229enumerateFromThenFractional
230 :: (Monad m, Fractional a)
231 => a -> a -> Stream m a
232enumerateFromThenFractional from next = fromStreamD $ D.enumerateFromThenNum from next
234-- | Numerically stable enumeration from a 'Fractional' number to a given
235-- limit. @enumerateFromToFractional from to@ generates a finite stream whose
236-- first element is @from@ and successive elements are in increments of @1@ up
239-- This is the equivalent of 'enumFromTo' for 'Fractional' types. For
243-- >>> Stream.fold Fold.toList $ Stream.enumerateFromToFractional 1.1 4
246-- >>> Stream.fold Fold.toList $ Stream.enumerateFromToFractional 1.1 4.6
247-- [1.1,2.1,3.1,4.1,5.1]
251-- Notice that the last element is equal to the specified @to@ value after
252-- rounding to the nearest integer.
255{-# INLINE enumerateFromToFractional #-}
256enumerateFromToFractional
257 :: (Monad m, Fractional a, Ord a)
258 => a -> a -> Stream m a
259enumerateFromToFractional from to =
260 fromStreamD $ D.enumerateFromToFractional from to
262-- | Numerically stable enumeration from a 'Fractional' number in steps up to a
263-- given limit. @enumerateFromThenToFractional from then to@ generates a
264-- finite stream whose first element is @from@, the second element is @then@
265-- and the successive elements are in increments of @then - from@ up to @to@.
267-- This is the equivalent of 'enumFromThenTo' for 'Fractional' types. For
271-- >>> Stream.fold Fold.toList $ Stream.enumerateFromThenToFractional 0.1 2 6
272-- [0.1,2.0,3.9,5.799999999999999]
274-- >>> Stream.fold Fold.toList $ Stream.enumerateFromThenToFractional 0.1 (-2) (-6)
275-- [0.1,-2.0,-4.1000000000000005,-6.200000000000001]
281{-# INLINE enumerateFromThenToFractional #-}
282enumerateFromThenToFractional
283 :: (Monad m, Fractional a, Ord a)
284 => a -> a -> a -> Stream m a
285enumerateFromThenToFractional from next to =
286 fromStreamD $ D.enumerateFromThenToFractional from next to
288-------------------------------------------------------------------------------
289-- Enumeration of Enum types not larger than Int
290-------------------------------------------------------------------------------
292-- | 'enumerateFromTo' for 'Enum' types not larger than 'Int'.
295{-# INLINE enumerateFromToSmall #-}
296enumerateFromToSmall :: (Monad m, Enum a) => a -> a -> Stream m a
297enumerateFromToSmall from to =
299 $ enumerateFromToIntegral (fromEnum from) (fromEnum to)
301-- | 'enumerateFromThenTo' for 'Enum' types not larger than 'Int'.
304{-# INLINE enumerateFromThenToSmall #-}
305enumerateFromThenToSmall :: (Monad m, Enum a)
306 => a -> a -> a -> Stream m a
307enumerateFromThenToSmall from next to =
309 $ enumerateFromThenToIntegral
310 (fromEnum from) (fromEnum next) (fromEnum to)
312-- | 'enumerateFromThen' for 'Enum' types not larger than 'Int'.
314-- Note: We convert the 'Enum' to 'Int' and enumerate the 'Int'. If a
315-- type is bounded but does not have a 'Bounded' instance then we can go on
316-- enumerating it beyond the legal values of the type, resulting in the failure
317-- of 'toEnum' when converting back to 'Enum'. Therefore we require a 'Bounded'
318-- instance for this function to be safely used.
321{-# INLINE enumerateFromThenSmallBounded #-}
322enumerateFromThenSmallBounded :: (Monad m, Enumerable a, Bounded a)
323 => a -> a -> Stream m a
324enumerateFromThenSmallBounded from next =
325 if fromEnum next >= fromEnum from
326 then enumerateFromThenTo from next maxBound
327 else enumerateFromThenTo from next minBound
329-------------------------------------------------------------------------------
330-- Enumerable type class
331-------------------------------------------------------------------------------
333-- NOTE: We would like to rewrite calls to fromList [1..] etc. to stream
334-- enumerations like this:
336-- {-# RULES "fromList enumFrom" [1]
337-- forall (a :: Int). D.fromList (enumFrom a) = D.enumerateFromIntegral a #-}
339-- But this does not work because enumFrom is a class method and GHC rewrites
340-- it quickly, so we do not get a chance to have our rule fired.
342-- | Types that can be enumerated as a stream. The operations in this type
343-- class are equivalent to those in the 'Enum' type class, except that these
344-- generate a stream instead of a list. Use the functions in
345-- "Streamly.Internal.Data.Stream.Enumeration" module to define new instances.
348class Enum a => Enumerable a where
349 -- | @enumerateFrom from@ generates a stream starting with the element
350 -- @from@, enumerating up to 'maxBound' when the type is 'Bounded' or
351 -- generating an infinite stream when the type is not 'Bounded'.
354 -- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFrom (0 :: Int)
359 -- For 'Fractional' types, enumeration is numerically stable. However, no
360 -- overflow or underflow checks are performed.
363 -- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFrom 1.1
369 enumerateFrom :: (Monad m) => a -> Stream m a
371 -- | Generate a finite stream starting with the element @from@, enumerating
372 -- the type up to the value @to@. If @to@ is smaller than @from@ then an
373 -- empty stream is returned.
376 -- >>> Stream.fold Fold.toList $ Stream.enumerateFromTo 0 4
381 -- For 'Fractional' types, the last element is equal to the specified @to@
382 -- value after rounding to the nearest integral value.
385 -- >>> Stream.fold Fold.toList $ Stream.enumerateFromTo 1.1 4
388 -- >>> Stream.fold Fold.toList $ Stream.enumerateFromTo 1.1 4.6
389 -- [1.1,2.1,3.1,4.1,5.1]
394 enumerateFromTo :: (Monad m) => a -> a -> Stream m a
396 -- | @enumerateFromThen from then@ generates a stream whose first element
397 -- is @from@, the second element is @then@ and the successive elements are
398 -- in increments of @then - from@. Enumeration can occur downwards or
399 -- upwards depending on whether @then@ comes before or after @from@. For
400 -- 'Bounded' types the stream ends when 'maxBound' is reached, for
401 -- unbounded types it keeps enumerating infinitely.
404 -- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 2
407 -- >>> Stream.fold Fold.toList $ Stream.take 4 $ Stream.enumerateFromThen 0 (-2)
413 enumerateFromThen :: (Monad m) => a -> a -> Stream m a
415 -- | @enumerateFromThenTo from then to@ generates a finite stream whose
416 -- first element is @from@, the second element is @then@ and the successive
417 -- elements are in increments of @then - from@ up to @to@. Enumeration can
418 -- occur downwards or upwards depending on whether @then@ comes before or
422 -- >>> Stream.fold Fold.toList $ Stream.enumerateFromThenTo 0 2 6
425 -- >>> Stream.fold Fold.toList $ Stream.enumerateFromThenTo 0 (-2) (-6)
431 enumerateFromThenTo :: (Monad m) => a -> a -> a -> Stream m a
433-- MAYBE: Sometimes it is more convenient to know the count rather then the
434-- ending or starting element. For those cases we can define the folllowing
435-- APIs. All of these will work only for bounded types if we represent the
444-------------------------------------------------------------------------------
445-- Convenient functions for bounded types
446-------------------------------------------------------------------------------
449-- > enumerate = enumerateFrom minBound
451-- Enumerate a 'Bounded' type from its 'minBound' to 'maxBound'
454{-# INLINE enumerate #-}
455enumerate :: (Monad m, Bounded a, Enumerable a) => Stream m a
456enumerate = enumerateFrom minBound
459-- > enumerateTo = enumerateFromTo minBound
461-- Enumerate a 'Bounded' type from its 'minBound' to specified value.
464{-# INLINE enumerateTo #-}
465enumerateTo :: (Monad m, Bounded a, Enumerable a) => a -> Stream m a
466enumerateTo = enumerateFromTo minBound
469-- > enumerateFromBounded = enumerateFromTo from maxBound
471-- 'enumerateFrom' for 'Bounded' 'Enum' types.
474{-# INLINE enumerateFromBounded #-}
475enumerateFromBounded :: (Monad m, Enumerable a, Bounded a)
477enumerateFromBounded from = enumerateFromTo from maxBound
479-------------------------------------------------------------------------------
480-- Enumerable Instances
481-------------------------------------------------------------------------------
483-- For Enum types smaller than or equal to Int size.
484#define ENUMERABLE_BOUNDED_SMALL(SMALL_TYPE) \
485instance Enumerable SMALL_TYPE where { \
486 {-# INLINE enumerateFrom #-}; \
487 enumerateFrom = enumerateFromBounded; \
488 {-# INLINE enumerateFromThen #-}; \
489 enumerateFromThen = enumerateFromThenSmallBounded; \
490 {-# INLINE enumerateFromTo #-}; \
491 enumerateFromTo = enumerateFromToSmall; \
492 {-# INLINE enumerateFromThenTo #-}; \
493 enumerateFromThenTo = enumerateFromThenToSmall }
496ENUMERABLE_BOUNDED_SMALL(())
497ENUMERABLE_BOUNDED_SMALL(Bool)
498ENUMERABLE_BOUNDED_SMALL(Ordering)
499ENUMERABLE_BOUNDED_SMALL(Char)
501-- For bounded Integral Enum types, may be larger than Int.
502#define ENUMERABLE_BOUNDED_INTEGRAL(INTEGRAL_TYPE) \
503instance Enumerable INTEGRAL_TYPE where { \
504 {-# INLINE enumerateFrom #-}; \
505 enumerateFrom = enumerateFromIntegral; \
506 {-# INLINE enumerateFromThen #-}; \
507 enumerateFromThen = enumerateFromThenIntegral; \
508 {-# INLINE enumerateFromTo #-}; \
509 enumerateFromTo = enumerateFromToIntegral; \
510 {-# INLINE enumerateFromThenTo #-}; \
511 enumerateFromThenTo = enumerateFromThenToIntegral }
513ENUMERABLE_BOUNDED_INTEGRAL(Int)
514ENUMERABLE_BOUNDED_INTEGRAL(Int8)
515ENUMERABLE_BOUNDED_INTEGRAL(Int16)
516ENUMERABLE_BOUNDED_INTEGRAL(Int32)
517ENUMERABLE_BOUNDED_INTEGRAL(Int64)
518ENUMERABLE_BOUNDED_INTEGRAL(Word)
519ENUMERABLE_BOUNDED_INTEGRAL(Word8)
520ENUMERABLE_BOUNDED_INTEGRAL(Word16)
521ENUMERABLE_BOUNDED_INTEGRAL(Word32)
522ENUMERABLE_BOUNDED_INTEGRAL(Word64)
524-- For unbounded Integral Enum types.
525#define ENUMERABLE_UNBOUNDED_INTEGRAL(INTEGRAL_TYPE) \
526instance Enumerable INTEGRAL_TYPE where { \
527 {-# INLINE enumerateFrom #-}; \
528 enumerateFrom from = enumerateFromStepIntegral from 1; \
529 {-# INLINE enumerateFromThen #-}; \
530 enumerateFromThen from next = \
531 enumerateFromStepIntegral from (next - from); \
532 {-# INLINE enumerateFromTo #-}; \
533 enumerateFromTo = enumerateFromToIntegral; \
534 {-# INLINE enumerateFromThenTo #-}; \
535 enumerateFromThenTo = enumerateFromThenToIntegral }
537ENUMERABLE_UNBOUNDED_INTEGRAL(Integer)
538ENUMERABLE_UNBOUNDED_INTEGRAL(Natural)
540#define ENUMERABLE_FRACTIONAL(FRACTIONAL_TYPE,CONSTRAINT) \
541instance (CONSTRAINT) => Enumerable FRACTIONAL_TYPE where { \
542 {-# INLINE enumerateFrom #-}; \
543 enumerateFrom = enumerateFromFractional; \
544 {-# INLINE enumerateFromThen #-}; \
545 enumerateFromThen = enumerateFromThenFractional; \
546 {-# INLINE enumerateFromTo #-}; \
547 enumerateFromTo = enumerateFromToFractional; \
548 {-# INLINE enumerateFromThenTo #-}; \
549 enumerateFromThenTo = enumerateFromThenToFractional }
551ENUMERABLE_FRACTIONAL(Float,)
552ENUMERABLE_FRACTIONAL(Double,)
553ENUMERABLE_FRACTIONAL((Fixed a),HasResolution a)
554ENUMERABLE_FRACTIONAL((Ratio a),Integral a)
556instance Enumerable a => Enumerable (Identity a) where
557 {-# INLINE enumerateFrom #-}
558 enumerateFrom (Identity from) =
559 fmap Identity $ enumerateFrom from
560 {-# INLINE enumerateFromThen #-}
561 enumerateFromThen (Identity from) (Identity next) =
562 fmap Identity $ enumerateFromThen from next
563 {-# INLINE enumerateFromTo #-}
564 enumerateFromTo (Identity from) (Identity to) =
565 fmap Identity $ enumerateFromTo from to
566 {-# INLINE enumerateFromThenTo #-}
567 enumerateFromThenTo (Identity from) (Identity next) (Identity to) =
569 $ enumerateFromThenTo from next to
573instance Enumerable a => Enumerable (Last a)
574instance Enumerable a => Enumerable (First a)
575instance Enumerable a => Enumerable (Max a)
576instance Enumerable a => Enumerable (Min a)
577instance Enumerable a => Enumerable (Const a b)
578instance Enumerable (f a) => Enumerable (Alt f a)
579instance Enumerable (f a) => Enumerable (Ap f a)
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