1{-# OPTIONS_GHC -Wno-orphans #-}
6-- Module : Streamly.Prelude
7-- Copyright : (c) 2017 Composewell Technologies
10-- Maintainer : streamly@composewell.com
11-- Stability : experimental
14-- This module is designed to be imported qualified:
17-- import qualified Streamly.Prelude as S
20-- Functions with the suffix @M@ are general functions that work on monadic
21-- arguments. The corresponding functions without the suffix @M@ work on pure
22-- arguments and can in general be derived from their monadic versions but are
23-- provided for convenience and for consistency with other pure APIs in the
26-- In many cases, short definitions of the combinators are provided in the
27-- documentation for illustration. The actual implementation may differ for
28-- performance reasons.
30-- Functions having a 'MonadAsync' constraint work concurrently when used with
31-- appropriate stream type combinator. Please be careful to not use 'parallely'
32-- with infinite streams.
34-- Deconstruction and folds accept a 'SerialT' type instead of a polymorphic
35-- type to ensure that streams always have a concrete monomorphic type by
36-- default, reducing type errors. In case you want to use any other type of
37-- stream you can use one of the type combinators provided to convert the
40module Streamly.Prelude
50 -- ** Speculative Streams
54 -- ** Asynchronous Streams
79 -- * Stream Type Adapters
95 -- | Primitives to construct a stream from pure values or monadic actions.
96 -- All other stream construction and generation combinators described later
97 -- can be expressed in terms of these primitives. However, the special
98 -- versions provided in this module can be much more efficient in most
99 -- cases. Users can create custom combinators using these primitives.
109 -- | Generate a monadic stream from a seed value or values.
117 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
118 -- to be slightly faster than the idioms like @[from, then..]@.
121 -- | We can use the 'Enum' type class to enumerate a type producing a list
122 -- and then convert it to a stream:
125 -- 'fromList' $ 'Prelude.enumFromThen' from then
128 -- However, this is not particularly efficient.
129 -- The 'Enumerable' type class provides corresponding functions that
130 -- generate a stream instead of a list, efficiently.
136 -- ** From Generators
137 -- | Generate a monadic stream from a seed value and a generator function.
146 -- ** From Containers
147 -- | Convert an input structure, container or source into a stream. All of
148 -- these can be expressed in terms of primitives.
157 -- | It is easy to express all the folds in terms of the 'uncons' primitive,
158 -- however the specific implementations provided later are generally more
166-- | In imperative terms a fold can be considered as a loop over the stream
167-- that reduces the stream to a single value.
168-- Left and right folds both use a fold function @f@ and an identity element
169-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
170-- new data structure. The new structure may be a recursive construction (a
171-- container) or a non-recursive single value reduction of the original
174-- Both right and left folds are mathematical duals of each other, they are
175-- functionally equivalent. Operationally, a left fold on a left associated
176-- structure behaves exactly in the same way as a right fold on a right
177-- associated structure. Similarly, a left fold on a right associated structure
178-- behaves in the same way as a right fold on a left associated structure.
179-- However, the behavior of a right fold on a right associated structure is
180-- operationally different (even though functionally equivalent) than a left
181-- fold on the same structure.
183-- On right associated structures like Haskell @cons@ lists or Streamly
184-- streams, a lazy right fold is naturally suitable for lazy recursive
185-- reconstruction of a new structure, while a strict left fold is naturally
186-- suitable for efficient reduction. In right folds control is in the hand of
187-- the @puller@ whereas in left folds the control is in the hand of the
190-- The behavior of right and left folds are described in detail in the
191-- individual fold's documentation. To illustrate the two folds for right
192-- associated @cons@ lists:
194-- > foldr :: (a -> b -> b) -> b -> [a] -> b
196-- > foldr f z (x:xs) = x `f` foldr f z xs
198-- > foldl :: (b -> a -> b) -> b -> [a] -> b
200-- > foldl f z (x:xs) = foldl f (z `f` x) xs
202-- @foldr@ is conceptually equivalent to:
205-- > foldr f z [x] = f x z
206-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
208-- @foldl@ is conceptually equivalent to:
211-- > foldl f z [x] = f z x
212-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
214-- Left and right folds are duals of each other.
217-- foldr f z xs = foldl (flip f) z (reverse xs)
218-- foldl f z xs = foldr (flip f) z (reverse xs)
224-- foldr f z xs = foldl g id xs z where g k x = k . f x
225-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
229-- As a general rule, foldr cannot have state and foldl cannot have control.
231-- NOTE: Folds are inherently serial as each step needs to use the result of
232-- the previous step. However, it is possible to fold parts of the stream in
233-- parallel and then combine the results using a monoid.
246 -- ** Composable Left Folds
252 -- | Folds that are guaranteed to evaluate the whole stream.
254 -- -- ** To Summary (Full Folds)
255 -- -- | Folds that summarize the stream to a single value.
262 -- -- ** To Summary (Maybe) (Full Folds)
263 -- -- | Folds that summarize a non-empty stream to a 'Just' value and return
264 -- 'Nothing' for an empty stream.
273 -- | Folds that generate a lazy structure. Note that the generated
274 -- structure may not be lazy if the underlying monad is strict.
276 -- -- ** To Containers (Full Folds)
277 -- -- | Convert or divert a stream into an output structure, container or
282 -- | Folds that may terminate before evaluating the whole stream. These
283 -- folds strictly evaluate the stream until the result is determined.
285 -- -- ** To Elements (Partial Folds)
289 -- -- | Folds that extract selected elements of a stream or their properties.
298 -- -- ** To Boolean (Partial Folds)
299 -- -- | Folds that summarize the stream to a boolean value.
308 -- ** Multi-Stream folds
314 -- trimming sequences
317 -- * Parallel Function Application
327 -- | In imperative terms a map operation can be considered as a loop over
328 -- the stream that transforms the stream into another stream by performing
329 -- an operation on each element of the stream.
331 -- 'map' is the least powerful transformation operation with strictest
332 -- guarantees. A map, (1) is a stateless loop which means that no state is
333 -- allowed to be carried from one iteration to another, therefore,
334 -- operations on different elements are guaranteed to not affect each
335 -- other, (2) is a strictly one-to-one transformation of stream elements
336 -- which means it guarantees that no elements can be added or removed from
337 -- the stream, it can merely transform them.
349 -- | A scan is more powerful than map. While a 'map' is a stateless loop, a
350 -- @scan@ is a stateful loop which means that a state can be shared across
351 -- all the loop iterations, therefore, future iterations can be impacted by
352 -- the state changes made by the past iterations. A scan yields the state
353 -- of the loop after each iteration. Like a map, a @postscan@ or @prescan@
354 -- does not add or remove elements in the stream, it just transforms them.
355 -- However, a @scan@ adds one extra element to the stream.
357 -- A left associative scan, also known as a prefix sum, can be thought of
358 -- as a stream transformation consisting of left folds of all prefixes of a
359 -- stream. Another way of thinking about it is that it streams all the
360 -- intermediate values of the accumulator while applying a left fold on the
361 -- input stream. A right associative scan, on the other hand, can be
362 -- thought of as a stream consisting of right folds of all the suffixes of
365 -- The following equations hold for lists:
367 -- > scanl f z xs == map (foldl f z) $ inits xs
368 -- > scanr f z xs == map (foldr f z) $ tails xs
371 -- > scanl (+) 0 [1,2,3,4]
376 -- 0 + 1 + 2 + 3 + 4 = 10
378 -- > scanr (+) 0 [1,2,3,4]
379 -- 1 + 2 + 3 + 4 + 0 = 10
386 -- Left and right scans are duals:
388 -- > scanr f z xs == reverse $ scanl (flip f) z (reverse xs)
389 -- > scanl f z xs == reverse $ scanr (flip f) z (reverse xs)
391 -- A scan is a stateful map i.e. a combination of map and fold:
393 -- > map f xs = tail $ scanl (\_ x -> f x) z xs
394 -- > map f xs = reverse $ head $ scanr (\_ x -> f x) z xs
396 -- > foldl f z xs = last $ scanl f z xs
397 -- > foldr f z xs = head $ scanr f z xs
407 -- ** Scan Using Fold
412 -- | Remove some elements from the stream based on a predicate. In
413 -- imperative terms a filter over a stream corresponds to a loop with a
414 -- @continue@ clause for the cases when the predicate fails.
419 -- ** Mapping Filters
420 -- | Mapping along with filtering
425 -- ** Deleting Elements
426 -- | Deleting elements is a special case of de-interleaving streams.
430 -- ** Inserting Elements
431 -- | Inserting elements is a special case of interleaving/merging streams.
438 -- | Indexing can be considered as a special type of zipping where we zip a
439 -- stream with an index stream.
443 -- ** Reordering Elements
447 -- | Take or remove elements from one or both ends of a stream.
461 -- | Finding the presence or location of an element, a sequence of elements
462 -- or another stream within a stream.
464 -- -- ** Searching Elements
469 -- | In general we can express splitting in terms of parser combinators.
470 -- These are some common use functions for convenience and efficiency.
471 -- While parsers can fail these functions are designed to transform a
472 -- stream without failure with a predefined behavior for all cases.
474 -- In general, there are three possible ways of combining stream segments
475 -- with a separator. The separator could be prefixed to each segment,
476 -- suffixed to each segment, or it could be infixed between segments.
477 -- 'intersperse' and 'intercalate' operations are examples of infixed
478 -- combining whereas 'unlines' is an example of suffixed combining. When we
479 -- split a stream with separators we can split in three different ways,
480 -- each being an opposite of the three ways of combining.
482 -- Splitting may keep the separator or drop it. Depending on how we split,
483 -- the separator may be kept attached to the stream segments in prefix or
484 -- suffix position or as a separate element in infix position. Combinators
485 -- like 'splitOn' that use @On@ in their names drop the separator and
486 -- combinators that use 'With' in their names keep the separator. When a
487 -- segment is missing it is considered as empty, therefore, we never
488 -- encounter an error in parsing.
490 -- -- ** Splitting By Elements
495 , wordsBy -- strip, compact and split
498 -- | Splitting a stream by combining multiple contiguous elements into
499 -- groups using some criterion.
504 -- * Combining Streams
505 -- | New streams can be constructed by appending, merging or zipping
509 -- | Streams form a 'Semigroup' and a 'Monoid' under the append
510 -- operation. Appending can be considered as a generalization of the `cons`
511 -- operation to consing a stream to a stream.
515 -- -------Stream m a------|-------Stream m a------|=>----Stream m a---
520 -- >> S.toList $ S.fromList [1,2] \<> S.fromList [3,4]
522 -- >> S.toList $ fold $ [S.fromList [1,2], S.fromList [3,4]]
537 -- | Streams form a commutative semigroup under the merge
538 -- operation. Merging can be considered as a generalization of inserting an
539 -- element in a stream to interleaving a stream with another stream.
543 -- -------Stream m a------|
544 -- |=>----Stream m a---
545 -- -------Stream m a------|
559 -- -------Stream m a------|
560 -- |=>----Stream m c---
561 -- -------Stream m b------|
569 -- ** Folding Streams of Streams
570 -- | Stream operations like map and filter represent loop processing in
571 -- imperative programming terms. Similarly, the imperative concept of
572 -- nested loops are represented by streams of streams. The 'concatMap'
573 -- operation represents nested looping.
574 -- A 'concatMap' operation loops over the input stream and then for each
575 -- element of the input stream generates another stream and then loops over
576 -- that inner stream as well producing effects and generating a single
578 -- The 'Monad' instances of different stream types provide a more
579 -- convenient way of writing nested loops. Note that the monad bind
580 -- operation is just @flip concatMap@.
582 -- One dimension loops are just a special case of nested loops. For
583 -- example, 'concatMap' can degenerate to a simple map operation:
585 -- > map f m = S.concatMap (\x -> S.yield (f x)) m
587 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
590 -- > filter p m = S.concatMap (\x -> if p x then S.yield x else S.nil) m
598 -- ** Folding Containers of Streams
599 -- | These are variants of standard 'Foldable' fold functions that use a
600 -- polymorphic stream sum operation (e.g. 'async' or 'wSerial') to fold a
601 -- finite container of streams. Note that these are just special cases of
602 -- the more general 'concatMapWith' operation.
605 , concatMapFoldableWith
606 , concatForFoldableWith
609 -- | Most of these combinators inhibit stream fusion, therefore, when
610 -- possible, they should be called in an outer loop to mitigate the cost.
611 -- For example, instead of calling them on a stream of chars call them on a
612 -- stream of arrays before flattening it to a stream of chars.
621 -- * Concurrency Control
650 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
651 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
652 notElem, maximum, minimum, head, last, tail, length, null,
653 reverse, iterate, init, and, or, lookup, foldr1, (!!),
654 scanl, scanl1, repeat, replicate, concatMap, span)
656import Streamly.Internal.Data.Stream.IsStream
660-- The basic stream type is 'Serial', it represents a sequence of IO actions,
661-- and is a 'Monad'. The type 'SerialT' is a monad transformer that can
662-- represent a sequence of actions in an arbitrary monad. The type 'Serial' is
663-- in fact a synonym for @SerialT IO@. There are a few more types similar to
664-- 'SerialT', all of them represent a stream and differ only in the
665-- 'Semigroup', 'Applicative' and 'Monad' compositions of the stream. 'Serial'
666-- and 'WSerial' types compose serially whereas 'Async' and 'WAsync'
667-- types compose concurrently. All these types can be freely inter-converted
668-- using type combinators without any cost. You can freely switch to any type
669-- of composition at any point in the program. When no type annotation or
670-- explicit stream type combinators are used, the default stream type is
671-- inferred as 'Serial'.
675-- When a stream consumer demands an element from a serial stream constructed
676-- as @a \`consM` b \`consM` ... nil@, the action @a@ at the head of the stream
677-- sequence is executed and the result is supplied to the consumer. When the
678-- next element is demanded, the action @b@ is executed and its result is
679-- supplied. Thus, the effects are performed and results are consumed strictly
680-- in a serial order. Serial streams can be considered as /spatially ordered/
681-- streams as the order of execution and consumption is the same as the spatial
682-- order in which the actions are composed by the programmer.
684-- Serial streams enforce the side effects as well as the results of the
685-- actions to be in the same order in which the actions are added to the
686-- stream. Therefore, the semigroup operation for serial streams is not
690-- a <> b is not the same as b <> a
693-- There are two serial stream types 'SerialT' and 'WSerialT'. The stream
694-- evaluation of both the variants works in the same way as described above,
695-- they differ only in the 'Semigroup' and 'Monad' implementaitons.
699-- When a stream consumer demands an element from a speculative stream
700-- constructed as @a \`consM` b \`consM` ... nil@, the action @a@ at the head
701-- of the stream is executed and the output of the action is supplied to the
702-- consumer. However, in addition to the action at the head multiple actions
703-- following it may also be executed concurrently and the results buffered.
704-- When the next element is demanded it may be served from the buffer and we
705-- may execute the next action in the sequence to keep the buffer adequately
706-- filled. Thus, the actions are executed concurrently but results consumed in
707-- serial order just like serial streams. `consM` can be used to fold an
708-- infinite lazy container of effects, as the number of concurrent executions
711-- Similar to 'consM', the monadic stream generation (e.g. replicateM) and
712-- transformation operations (e.g. mapM) on speculative streams can execute
713-- multiple effects concurrently in a speculative manner.
715-- How many effects can be executed concurrently and how many results can be
716-- buffered are controlled by 'maxThreads' and 'maxBuffer' combinators
717-- respectively. The actual number of concurrent threads is adjusted according
718-- to the rate at which the consumer is consuming the stream. It may even
719-- execute actions serially in a single thread if that is enough to match the
722-- Speculative streams enforce ordering of the results of actions in the stream
723-- but the side effects are only partially ordered. Therefore, the semigroup
724-- operation for speculative streams is not commutative from the pure outputs
725-- perspective but commutative from side effects perspective.
729-- /Scheduling and execution:/ In an asynchronous stream @a \`consM` b \`consM`
730-- c ...@, the actions @a@, @b@, and @c@ are executed concurrently with the
731-- consumer of the stream. The actions are /scheduled/ for execution in the
732-- same order as they are specified in the stream. Multiple scheduled actions
733-- may be /executed/ concurrently in parallel threads of execution. The
734-- actions may be executed out of order and they may complete at arbitrary
735-- times. Therefore, the /effects/ of the actions may be observed out of
738-- /Buffering:/ The /results/ from multiple threads of execution are queued in
739-- a buffer as soon as they become available. The consumer of the stream is
740-- served from this buffer. Therefore, the consumer may observe the results to
741-- be out of order. In other words, an asynchronous stream is an unordered
742-- stream i.e. order does not matter.
744-- /Concurrency control:/ Threads are suspended if the `maxBuffer` limit is
745-- reached, and resumed when the consumer makes space in the buffer. The
746-- maximum number of concurrent threads depends on `maxThreads`. Number of
747-- threads is increased or decreased based on the speed of the consumer.
749-- /Generation operations:/ Concurrent stream generation operations e.g.
750-- 'Streamly.Prelude.replicateM' when used in async style schedule and execute
751-- the stream generating actions in the manner described above. The generation
752-- actions run concurrently, effects and results of the actions as observed by
753-- the consumer of the stream may be out of order.
755-- /Transformation operations:/ Concurrent stream transformation operations
756-- e.g. 'Streamly.Prelude.mapM', when used in async style, schedule and
757-- execute transformation actions in the manner described above. Transformation
758-- actions run concurrently, effects and results of the actions may be
759-- observed by the consumer out of order.
761-- /Variants:/ There are two asynchronous stream types 'AsyncT' and 'WAsyncT'.
762-- They are identical with respect to single stream evaluation behavior. Their
763-- behaviors differ in how they combine multiple streams using 'Semigroup' or
764-- 'Monad' composition. Since the order of elements does not matter in
765-- asynchronous streams the 'Semigroup' operation is effectively commutative.
769-- 'ZipSerialM' and 'ZipAsyncM', provide 'Applicative' instances for zipping the
770-- corresponding elements of two streams together. Note that these types are
775-- Let's take a closer look at the @foldr@ definition for lists, as given3
779-- foldr f z (x:xs) = x \`f` foldr f z xs
782-- @foldr@ invokes the fold step function @f@ as @f x (foldr f z xs)@. At each
783-- invocation of @f@, @foldr@ gives us the next element in the input container
784-- @x@ and a recursive expression @foldr f z xs@ representing the yet unbuilt
785-- (lazy thunk) part of the output.
787-- When @f x xs@ is lazy in @xs@ it can consume the input one element at a time
788-- in FIFO order to build a lazy output expression. For example,
790-- > f x remaining = show x : remaining
792-- @take 2 $ foldr f [] (1:2:undefined)@ would consume the input lazily on
793-- demand, consuming only first two elements and resulting in ["1", "2"]. @f@
794-- can terminate recursion by not evaluating the @remaining@ part:
796-- > f 2 remaining = show 2 : []
797-- > f x remaining = show x : remaining
799-- @f@ would terminate recursion whenever it sees element @2@ in the input.
800-- Therefore, @take 2 $ foldr f [] (1:2:undefined)@ would work without any
803-- On the other hand, if @f a b@ is strict in @b@ it would end up consuming the
804-- whole input right away and expanding the recursive expression @b@ (i.e.
805-- @foldr f z xs@) fully before it yields an output expression, resulting in
806-- the following /right associated expression/:
809-- foldr f z xs == x1 \`f` (x2 \`f` ...(xn \`f` z))
814-- > f x remaining = x + remaining
816-- With this definition, @foldr f 0 [1..1000]@, would recurse completely until
817-- it reaches the terminating case @... `f` (1000 `f` 0)@, and then
818-- start reducing the whole expression from right to left, therefore, consuming
819-- the input elements in LIFO order. Thus, such an evaluation would require
820-- memory proportional to the size of input. Try out @foldr (+) 0 (map (\\x ->
821-- trace (show x) x) [1..10])@.
823-- Notice the order of the arguments to the step function @f a b@. It follows
824-- the order of @a@ and @b@ in the right associative recursive expression
825-- generated by expanding @a \`f` b@.
827-- A right fold is a pull fold, the step function is the puller, it can pull
828-- more data from the input container by using its second argument in the
829-- output expression or terminate pulling by not using it. As a corollary:
831-- 1. a step function which is lazy in its second argument (usually functions
832-- or constructors that build a lazy structure e.g. @(:)@) can pull lazily on
834-- 2. a step function strict in its second argument (usually reducers e.g.
835-- (+)) would end up pulling all of its input and buffer it in memory before
836-- potentially reducing it.
838-- A right fold is suitable for lazy reconstructions e.g. transformation,
839-- mapping, filtering of /right associated input structures/ (e.g. cons lists).
840-- Whereas a left fold is suitable for reductions (e.g. summing a stream of
841-- numbers) of right associated structures. Note that these roles will reverse
842-- for left associated structures (e.g. snoc lists). Most of our observations
843-- here assume right associated structures, lists being the canonical example.
845-- 1. A lazy FIFO style pull using a right fold allows pulling a potentially
846-- /infinite/ input stream lazily, perform transformations on it, and
847-- reconstruct a new structure without having to buffer the whole structure. In
848-- contrast, a left fold would buffer the entire structure before the
849-- reconstructed structure can be consumed.
850-- 2. Even if buffering the entire input structure is ok, we need to keep in
851-- mind that a right fold reconstructs structures in a FIFO style, whereas a
852-- left fold reconstructs in a LIFO style, thereby reversing the order of
854-- 3. A right fold has termination control and therefore can terminate early
855-- without going through the entire input, a left fold cannot terminate
856-- without consuming all of its input. For example, a right fold
857-- implementation of 'or' can terminate as soon as it finds the first 'True'
858-- element, whereas a left fold would necessarily go through the entire input
859-- irrespective of that.
860-- 4. Reduction (e.g. using (+) on a stream of numbers) using a right fold
861-- occurs in a LIFO style, which means that the entire input gets buffered
862-- before reduction starts. Whereas with a strict left fold reductions occur
863-- incrementally in FIFO style. Therefore, a strict left fold is more suitable
869-- Note that the observations below about the behavior of a left fold assume
870-- that we are working on a right associated structure like cons lists and
871-- streamly streams. If we are working on a left associated structure (e.g.
872-- snoc lists) the roles of right and left folds would reverse.
874-- Let's take a closer look at the @foldl@ definition for lists given above:
877-- foldl f z (x:xs) = foldl f (z \`f` x) xs
880-- @foldl@ calls itself recursively, in each call it invokes @f@ as @f z x@
881-- providing it with the result accumulated till now @z@ (the state) and the
882-- next element from the input container. First call to @f@ is supplied with
883-- the initial value of the accumulator @z@ and each subsequent call uses the
884-- output of the previous call to @f z x@.
886-- >> foldl' (+) 0 [1,2,3]
889-- The recursive call at the head of the output expression is bound to be
890-- evaluated until recursion terminates, therefore, a left fold always
891-- /consumes the whole input container/. The following would result in an
892-- error, even though the fold is not using the values at all:
894-- >> foldl' (\_ _ -> 0) 0 (1:undefined)
895-- > *** Exception: Prelude.undefined
897-- As @foldl@ recurses, it builds the left associated expression shown below.
898-- Notice, the order of the arguments to the step function @f b a@. It follows
899-- the left associative recursive expression generated by expanding @b \`f` a@.
902-- foldl f z xs == (((z \`f` x1) \`f` x2) ...) \`f` xn
906-- The strict left fold @foldl'@ forces the reduction of its argument @z \`f`
907-- x@ before using it, therefore it never builds the whole expression in
908-- memory. Thus, @z \`f` x1@ would get reduced to @z1@ and then @z1 \`f` x2@
909-- would get reduced to @z2@ and so on, incrementally reducing the expression
910-- from left to right as it recurses, consuming the input in FIFO order. Try
911-- out @foldl' (+) 0 (map (\\x -> trace (show x) x) [1..10])@ to see how it
912-- works. For example:
915-- > S.foldl' (+) 0 $ S.fromList [1,2,3,4]
926-- However, @foldl'@ evaluates the accumulator only to WHNF. It may further
927-- help if the step function uses a strict data structure as accumulator to
928-- improve performance and to keep the expression fully reduced at all times
931-- A left fold can also build a new structure instead of reducing one if a
932-- constructor is used as a fold step. However, it may not be very useful
933-- because it will consume the whole input and construct the new structure in
934-- memory before we can consume it. Thus the whole structure gets buffered in
935-- memory. When the list constructor is used it would build a new list in
936-- reverse (LIFO) order:
939-- > S.foldl' (flip (:)) [] $ S.fromList [1,2,3,4]
943-- A left fold is a push fold. The producer pushes its contents to the step
944-- function of the fold. The step function therefore has no control to stop the
945-- input, it can only discard it if it does not need it. We can also consider a
946-- left fold as a state machine where the state is store in the accumulator,
947-- the state can be modified based on new inputs that are pushed to the fold.
949-- In general, a strict left fold is a reducing fold, whereas a right fold is a
950-- constructing fold. A strict left fold reduces in a FIFO order whereas it
951-- constructs in a LIFO order, and vice-versa for the right fold. See the
952-- documentation of 'foldrM' for a discussion on where a left or right fold is
955-- To perform a left fold lazily without having to consume all the input one
956-- can use @scanl@ to stream the intermediate results of the fold and consume
957-- the resulting stream lazily.
962-- "Streamly.Data.Fold" module defines composable left folds which can be combined
963-- together in many interesting ways. Those folds can be run using 'fold'.
964-- The following two ways of folding are equivalent in functionality and
967-- >>> S.fold FL.sum (S.enumerateFromTo 1 100)
969-- >>> S.sum (S.enumerateFromTo 1 100)
972-- However, left folds cannot terminate early even if it does not need to
973-- consume more input to determine the result. Therefore, the performance is
974-- equivalent only for full folds like 'sum' and 'length'. For partial folds
975-- like 'head' or 'any' the the folds defined in this module may be much more
976-- efficient because they are implemented as right folds that terminate as soon
977-- as we get the result. Note that when a full fold is composed with a partial
978-- fold in parallel the performance is not impacted as we anyway have to
979-- consume the whole stream due to the full fold.
981-- >>> S.head (1 `S.cons` undefined)
983-- >>> S.fold FL.head (1 `S.cons` undefined)
984-- *** Exception: Prelude.undefined
986-- However, we can wrap the fold in a scan to convert it into a lazy stream of
987-- fold steps. We can then terminate the stream whenever we want. For example,
989-- >>> S.toList $ S.take 1 $ S.scan FL.head (1 `S.cons` undefined)
992-- The following example extracts the input stream up to a point where the
993-- running average of elements is no more than 10:
997-- $ S.map (fromJust . fst)
998-- $ S.takeWhile (\\(_,x) -> x <= 10)
999-- $ S.postscan ((,) \<$> FL.last \<*> avg) (S.enumerateFromTo 1.0 100.0)
1002-- [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0,16.0,17.0,18.0,19.0]
1007-- Stream processing functions can be composed in a chain using function
1008-- application with or without the '$' operator, or with reverse function
1009-- application operator '&'. Streamly provides concurrent versions of these
1010-- operators applying stream processing functions such that each stage of the
1011-- stream can run in parallel. The operators start with a @|@; we can read '|$'
1012-- as "@parallel dollar@" to remember that @|@ comes before '$'.
1014-- Imports for the code snippets below:
1017-- import qualified Streamly.Prelude as S
1018-- import Control.Concurrent
1023-- These combinators can be used at any point in a stream composition to set
1024-- parameters to control the concurrency of the /argument stream/. A control
1025-- parameter set at any point remains effective for any concurrent combinators
1026-- used in the argument stream until it is reset by using the combinator again.
1027-- These control parameters have no effect on non-concurrent combinators in the
1028-- stream, or on non-concurrent streams.
1030-- /Pitfall:/ Remember that 'maxBuffer' in the following example applies to
1031-- 'mapM' and any other combinators that may follow it, and it does not apply
1032-- to the combinators before it:
1041-- If we use '&' instead of '$' the situation will reverse, in the following
1042-- example, 'maxBuffer' does not apply to 'mapM', it applies to combinators
1043-- that come before it, because those are the arguments to 'maxBuffer':
1054-- You may want to use different stream composition styles at different points
1055-- in your program. Stream types can be freely converted or adapted from one
1056-- type to another. The 'IsStream' type class facilitates type conversion of
1057-- one stream type to another. It is not used directly, instead the type
1058-- combinators provided below are used for conversions.
1060-- To adapt from one monomorphic type (e.g. 'AsyncT') to another monomorphic
1061-- type (e.g. 'SerialT') use the 'adapt' combinator. To give a polymorphic code
1062-- a specific interpretation or to adapt a specific type to a polymorphic type
1063-- use the type specific combinators e.g. 'asyncly' or 'wSerially'. You
1064-- cannot adapt polymorphic code to polymorphic code, as the compiler would not know
1065-- which specific type you are converting from or to. If you see a an
1066-- @ambiguous type variable@ error then most likely you are using 'adapt'
1067-- unnecessarily on polymorphic code.
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