1{-# OPTIONS_GHC -Wno-deprecations #-}
6-- Module : Streamly.Prelude
7-- Copyright : (c) 2017 Composewell Technologies
10-- Maintainer : streamly@composewell.com
11-- Stability : released
14-- To run examples in this module:
16-- >>> import qualified Streamly.Data.Fold as Fold
17-- >>> import qualified Streamly.Prelude as Stream
19-- We will add some more imports in the examples as needed.
21-- For effectful streams we will use the following IO action that blocks for
24-- >>> import Control.Concurrent (threadDelay)
27-- threadDelay (n * 1000000) -- sleep for n seconds
28-- putStrLn (show n ++ " sec") -- print "n sec"
38-- Streamly is a framework for modular data flow based programming and
39-- declarative concurrency. Powerful stream fusion framework in streamly
40-- allows high performance combinatorial programming even when using byte level
41-- streams. Streamly API is similar to Haskell lists.
43-- The basic stream type is 'SerialT'. The type @SerialT IO a@ is an effectful
44-- equivalent of a list @[a]@ using the IO monad. Streams can be constructed
45-- like lists, except that they use 'nil' instead of '[]' and 'cons' instead of
48-- `cons` constructs a pure stream which is more or less the same as a list:
50-- >>> import Streamly.Prelude (SerialT, cons, consM, nil)
51-- >>> stream = 1 `cons` 2 `cons` nil :: SerialT IO Int
52-- >>> Stream.toList stream -- IO [Int]
55-- 'consM' constructs a stream from effectful actions:
57-- >>> stream = delay 1 `consM` delay 2 `consM` nil
58-- >>> Stream.toList stream
63-- == Console Echo Program
65-- In the following example, 'repeatM' generates an infinite stream of 'String'
66-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
67-- 'putStrLn' on each element in the stream converting it to stream of '()'.
68-- Finally, 'drain' folds the stream to IO discarding the () values, thus
69-- producing only effects.
71-- >>> import Data.Function ((&))
75-- Stream.repeatM getLine -- SerialT IO String
76-- & Stream.mapM putStrLn -- SerialT IO ()
77-- & Stream.drain -- IO ()
81-- This is a console echo program. It is an example of a declarative loop
82-- written using streaming combinators. Compare it with an imperative @while@
85-- Hopefully, this gives you an idea how we can program declaratively by
86-- representing loops using streams. In this module, you can find all
87-- "Data.List" like functions and many more powerful combinators to perform
88-- common programming tasks. Also see "Streamly.Internal.Data.Stream.IsStream"
89-- module for many more @Pre-release@ combinators. See the
90-- <https://github.com/composewell/streamly-examples> repository for many more
91-- real world examples of stream programming.
93-- == Polymorphic Combinators
95-- Streamly has several stream types, 'SerialT' is one type of stream with
96-- serial execution of actions, 'AsyncT' is another with concurrent execution.
97-- The combinators in this module are polymorphic in stream type. For example,
100-- repeatM :: (IsStream t, MonadAsync m) => m a -> t m a
103-- @t@ is the stream type, @m@ is the underlying 'Monad' of the stream (e.g.
104-- IO) and @a@ is the type of elements in the stream (e.g. Int).
106-- Stream elimination combinators accept a 'SerialT' type instead of a
107-- polymorphic type to force a concrete monomorphic type by default, reducing
108-- type errors. That's why in the console echo example above the stream type is
112-- drain :: Monad m => SerialT m a -> m ()
115-- We can force a certain stream type in polymorphic code by using "Stream Type
116-- Adaptors". For example, to force 'AsyncT':
118-- >>> Stream.drain $ Stream.fromAsync $ Stream.replicateM 10 $ delay 1
121-- == Combining two streams
123-- Two streams can be combined to form a single stream in various interesting
124-- ways. 'serial' (append), 'wSerial' (interleave), 'ahead' (concurrent,
125-- ordered append), 'async' (lazy concurrent, unordered append) , 'wAsync'
126-- (lazy concurrent, unordered interleave), 'parallel' (strict concurrent
127-- merge), 'zipWith', 'zipAsyncWith' (concurrent zip), 'mergeBy',
128-- 'mergeAsyncBy' (concurrent merge) are some ways of combining two streams.
130-- For example, the `parallel` combinator schedules both the streams
133-- >>> stream1 = Stream.fromListM [delay 3, delay 4]
134-- >>> stream2 = Stream.fromListM [delay 1, delay 2]
135-- >>> Stream.toList $ stream1 `parallel` stream2
138-- We can chain the operations to combine more than two streams:
140-- >>> stream3 = Stream.fromListM [delay 1, delay 2]
141-- >>> Stream.toList $ stream1 `parallel` stream2 `parallel` stream3
144-- Concurrent generation ('consM') and concurrent merging of streams is the
145-- fundamental basis of all concurrency in streamly.
147-- == Combining many streams
149-- The 'concatMapWith' combinator can be used to generalize the two stream
150-- combining combinators to @n@ streams. For example, we can use
151-- @concatMapWith parallel@ to read concurrently from all incoming network
152-- connections and combine the input streams into a single output stream:
155-- import qualified Streamly.Network.Inet.TCP as TCP
156-- import qualified Streamly.Network.Socket as Socket
158-- Stream.unfold TCP.acceptOnPort 8090
159-- & Stream.concatMapWith Stream.parallel (Stream.unfold Socket.read)
162-- See the @streamly-examples@ repository for a full working example.
164-- == Concurrent Nested Loops
166-- The Monad instance of 'SerialT' is an example of nested looping. It is in
167-- fact a list transformer. Different stream types provide different variants
168-- of nested looping. For example, the 'Monad' instance of 'ParallelT' uses
169-- @concatMapWith parallel@ as its bind operation. Therefore, each iteration of
170-- the loop for 'ParallelT' stream can run concurrently. See the documentation
171-- for individual stream types for the specific execution behavior of the
172-- stream as well as the behavior of 'Semigroup' and 'Monad' instances.
176-- Streamly has several stream types. These types differ in three fundamental
177-- operations, 'consM' ('IsStream' instance), '<>' ('Semigroup' instance) and
178-- '>>=' ('Monad' instance). Below we will see how 'consM' behaves for
179-- 'SerialT', 'AsyncT' and 'AheadT' stream types.
181-- 'SerialT' executes actions serially, so the total delay in the following
182-- example is @2 + 1 = 3@ seconds:
184-- >>> stream = delay 2 `consM` delay 1 `consM` nil
185-- >>> Stream.toList stream -- IO [Int]
190-- 'AsyncT' executes the actions concurrently, so the total delay is @max 2 1 =
193-- >>> Stream.toList $ Stream.fromAsync stream -- IO [Int]
198-- 'AsyncT' produces the results in the order in which execution finishes.
199-- Notice the order of elements in the list above, it is not the same as the
200-- order of actions in the stream.
202-- 'AheadT' is similar to 'AsyncT' but the order of results is the same as the
203-- order of actions, even though they execute concurrently:
205-- >>> Stream.toList $ Stream.fromAhead stream -- IO [Int]
210-- == Semigroup Instance
212-- Earlier we distinguished stream types based on the execution behavior of
213-- actions within a stream. Stream types are also distinguished based on how
214-- actions from different streams are scheduled for execution when two streams
215-- are combined together.
217-- For example, both 'SerialT' and 'WSerialT' execute actions within the stream
218-- serially, however, they differ in how actions from individual streams are
219-- executed when two streams are combined with '<>' (the 'Semigroup' instance).
221-- For 'SerialT', '<>' has an appending behavior i.e. it executes the actions
222-- from the second stream after executing actions from the first stream:
224-- >>> stream1 = Stream.fromListM [delay 1, delay 2]
225-- >>> stream2 = Stream.fromListM [delay 3, delay 4]
226-- >>> Stream.toList $ stream1 <> stream2
233-- For 'WSerialT', '<>' has an interleaving behavior i.e. it executes one
234-- action from the first stream and then one action from the second stream and
237-- >>> Stream.toList $ Stream.fromWSerial $ stream1 <> stream2
244-- The '<>' operation of 'SerialT' and 'WSerialT' is the same as 'serial' and
245-- 'wSerial' respectively. The 'serial' combinator combines two streams of any
246-- type in the same way as a serial stream combines.
248-- == Concurrent Combinators
250-- Like 'consM', there are several other stream generation operations whose
251-- execution behavior depends on the stream type, they all follow behavior
252-- similar to 'consM'.
254-- By default, folds like 'drain' force the stream type to be 'SerialT', so
255-- 'replicateM' in the following code runs serially, and takes 10 seconds:
257-- >>> Stream.drain $ Stream.replicateM 10 $ delay 1
260-- We can use the 'fromAsync' combinator to force the argument stream to be of
261-- 'AsyncT' type, 'replicateM' in the following example executes the replicated
262-- actions concurrently, thus taking only 1 second:
264-- >>> Stream.drain $ Stream.fromAsync $ Stream.replicateM 10 $ delay 1
267-- We can use 'mapM' to map an action concurrently:
269-- >>> f x = delay 1 >> return (x + 1)
270-- >>> Stream.toList $ Stream.fromAhead $ Stream.mapM f $ Stream.fromList [1..3]
274-- 'fromAhead' forces mapM to happen in 'AheadT' style, thus all three actions
275-- take only one second even though each individual action blocks for a second.
277-- See the documentation of individual combinators to check if it is concurrent
278-- or not. The concurrent combinators necessarily have a @MonadAsync m@
279-- constraint. However, a @MonadAsync m@ constraint does not necessarily mean
280-- that the combinator is concurrent.
282-- == Automatic Concurrency Control
284-- 'SerialT' (and 'WSerialT') runs all tasks serially whereas 'ParallelT' runs
285-- all tasks concurrently i.e. one thread per task. The stream types 'AsyncT',
286-- 'WAsyncT', and 'AheadT' provide demand driven concurrency. It means that
287-- based on the rate at which the consumer is consuming the stream, it
288-- maintains the optimal number of threads to increase or decrease parallelism.
290-- However, the programmer can control the maximum number of threads using
291-- 'maxThreads'. It provides an upper bound on the concurrent IO requests or
292-- CPU cores that can be used. 'maxBuffer' limits the number of evaluated
293-- stream elements that we can buffer. See the "Concurrency Control" section
298-- When we use combinators like 'fromAsync' on a piece of code, all combinators
299-- inside the argument of fromAsync become concurrent which is often counter
300-- productive. Therefore, we recommend that in a pipeline, you identify the
301-- combinators that you really want to be concurrent and add a 'fromSerial' after
302-- those combinators so that the code following the combinator remains serial:
305-- Stream.fromAsync $ ... concurrent combinator here ... $ Stream.fromSerial $ ...
310-- Functions with the suffix @M@ are general functions that work on monadic
311-- arguments. The corresponding functions without the suffix @M@ work on pure
312-- arguments and can in general be derived from their monadic versions but are
313-- provided for convenience and for consistency with other pure APIs in the
316-- In many cases, short definitions of the combinators are provided in the
317-- documentation for illustration. The actual implementation may differ for
318-- performance reasons.
320module Streamly.Prelude
321{-# DEPRECATED "Please use \"Streamly.Data.Stream.Prelude\" from streamly package and \"Streamly.Data.Fold\" from streamly-core package instead." #-}
324 -- | Functions ending in the general shape @b -> t m a@.
326 -- See also: "Streamly.Internal.Data.Stream.IsStream.Generate" for
327 -- @Pre-release@ functions.
330 -- | Primitives to construct a stream from pure values or monadic actions.
331 -- All other stream construction and generation combinators described later
332 -- can be expressed in terms of these primitives. However, the special
333 -- versions provided in this module can be much more efficient in most
334 -- cases. Users can create custom combinators using these primitives.
344 -- | Generalized way of generating a stream efficiently.
350 -- | Generate a monadic stream from a seed value or values.
358 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
359 -- to be slightly faster than the idioms like @[from, then..]@.
362 -- | We can use the 'Enum' type class to enumerate a type producing a list
363 -- and then convert it to a stream:
366 -- 'fromList' $ 'Prelude.enumFromThen' from then
369 -- However, this is not particularly efficient.
370 -- The 'Enumerable' type class provides corresponding functions that
371 -- generate a stream instead of a list, efficiently.
381 -- ** From Generators
382 -- | Generate a monadic stream from a seed value and a generator function.
386 -- ** From Containers
387 -- | Convert an input structure, container or source into a stream. All of
388 -- these can be expressed in terms of primitives.
395 -- | Functions ending in the general shape @t m a -> m b@
397 -- See also: "Streamly.Internal.Data.Stream.IsStream.Eliminate" for
398 -- @Pre-release@ functions.
400 -- ** Running a 'Fold'
406 -- | Functions ending in the general shape @t m a -> m (b, t m a)@
413-- | In imperative terms a fold can be considered as a loop over the stream
414-- that reduces the stream to a single value.
415-- Left and right folds both use a fold function @f@ and an identity element
416-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
417-- new data structure. The new structure may be a recursive construction (a
418-- container) or a non-recursive single value reduction of the original
421-- Both right and left folds are mathematical duals of each other, they are
422-- functionally equivalent. Operationally, a left fold on a left associated
423-- structure behaves exactly in the same way as a right fold on a right
424-- associated structure. Similarly, a left fold on a right associated structure
425-- behaves in the same way as a right fold on a left associated structure.
426-- However, the behavior of a right fold on a right associated structure is
427-- operationally different (even though functionally equivalent) than a left
428-- fold on the same structure.
430-- On right associated structures like Haskell @cons@ lists or Streamly
431-- streams, a lazy right fold is naturally suitable for lazy recursive
432-- reconstruction of a new structure, while a strict left fold is naturally
433-- suitable for efficient reduction. In right folds control is in the hand of
434-- the @puller@ whereas in left folds the control is in the hand of the
437-- The behavior of right and left folds are described in detail in the
438-- individual fold's documentation. To illustrate the two folds for right
439-- associated @cons@ lists:
441-- > foldr :: (a -> b -> b) -> b -> [a] -> b
443-- > foldr f z (x:xs) = x `f` foldr f z xs
445-- > foldl :: (b -> a -> b) -> b -> [a] -> b
447-- > foldl f z (x:xs) = foldl f (z `f` x) xs
449-- @foldr@ is conceptually equivalent to:
452-- > foldr f z [x] = f x z
453-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
455-- @foldl@ is conceptually equivalent to:
458-- > foldl f z [x] = f z x
459-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
461-- Left and right folds are duals of each other.
464-- foldr f z xs = foldl (flip f) z (reverse xs)
465-- foldl f z xs = foldr (flip f) z (reverse xs)
471-- foldr f z xs = foldl g id xs z where g k x = k . f x
472-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
476-- As a general rule, foldr cannot have state and foldl cannot have control.
478-- NOTE: Folds are inherently serial as each step needs to use the result of
479-- the previous step. However, it is possible to fold parts of the stream in
480-- parallel and then combine the results using a monoid.
495 -- | Folds that are guaranteed to evaluate the whole stream.
497 -- -- ** To Summary (Full Folds)
498 -- -- | Folds that summarize the stream to a single value.
505 -- -- ** To Summary (Maybe) (Full Folds)
506 -- -- | Folds that summarize a non-empty stream to a 'Just' value and return
507 -- 'Nothing' for an empty stream.
515 -- | Folds that may terminate before evaluating the whole stream. These
516 -- folds strictly evaluate the stream until the result is determined.
518 -- -- ** To Elements (Partial Folds)
522 -- -- | Folds that extract selected elements of a stream or their properties.
531 -- -- ** To Boolean (Partial Folds)
532 -- -- | Folds that summarize the stream to a boolean value.
542 -- | Convert a stream into a container holding all the values.
545 -- ** Folding Concurrently
549 -- ** Multi-Stream folds
555 -- trimming sequences
559 -- | See also: "Streamly.Internal.Data.Stream.IsStream.Transform" for
560 -- @Pre-release@ functions.
563 -- | In imperative terms a map operation can be considered as a loop over
564 -- the stream that transforms the stream into another stream by performing
565 -- an operation on each element of the stream.
567 -- 'map' is the least powerful transformation operation with strictest
568 -- guarantees. A map, (1) is a stateless loop which means that no state is
569 -- allowed to be carried from one iteration to another, therefore,
570 -- operations on different elements are guaranteed to not affect each
571 -- other, (2) is a strictly one-to-one transformation of stream elements
572 -- which means it guarantees that no elements can be added or removed from
573 -- the stream, it can merely transform them.
578 -- ** Mapping Side Effects
586 -- | A scan is more powerful than map. While a 'map' is a stateless loop, a
587 -- @scan@ is a stateful loop which means that a state can be shared across
588 -- all the loop iterations, therefore, future iterations can be impacted by
589 -- the state changes made by the past iterations. A scan yields the state
590 -- of the loop after each iteration. Like a map, a @postscan@ or @prescan@
591 -- does not add or remove elements in the stream, it just transforms them.
592 -- However, a @scan@ adds one extra element to the stream.
594 -- A left associative scan, also known as a prefix sum, can be thought of
595 -- as a stream transformation consisting of left folds of all prefixes of a
596 -- stream. Another way of thinking about it is that it streams all the
597 -- intermediate values of the accumulator while applying a left fold on the
598 -- input stream. A right associative scan, on the other hand, can be
599 -- thought of as a stream consisting of right folds of all the suffixes of
602 -- The following equations hold for lists:
604 -- > scanl f z xs == map (foldl f z) $ inits xs
605 -- > scanr f z xs == map (foldr f z) $ tails xs
608 -- > scanl (+) 0 [1,2,3,4]
613 -- 0 + 1 + 2 + 3 + 4 = 10
615 -- > scanr (+) 0 [1,2,3,4]
616 -- 1 + 2 + 3 + 4 + 0 = 10
623 -- Left and right scans are duals:
625 -- > scanr f z xs == reverse $ scanl (flip f) z (reverse xs)
626 -- > scanl f z xs == reverse $ scanr (flip f) z (reverse xs)
628 -- A scan is a stateful map i.e. a combination of map and fold:
630 -- > map f xs = tail $ scanl (\_ x -> f x) z xs
631 -- > map f xs = reverse $ head $ scanr (\_ x -> f x) z xs
633 -- > foldl f z xs = last $ scanl f z xs
634 -- > foldr f z xs = head $ scanr f z xs
644 -- ** Scanning By 'Fold'
649 -- | Remove some elements from the stream based on a predicate. In
650 -- imperative terms a filter over a stream corresponds to a loop with a
651 -- @continue@ clause for the cases when the predicate fails.
659 -- | Take or remove elements from one or both ends of a stream.
667 -- ** Inserting Elements
668 -- | Inserting elements is a special case of interleaving/merging streams.
674 -- ** Reordering Elements
678 -- | Indexing can be considered as a special type of zipping where we zip a
679 -- stream with an index stream.
684 -- | Finding the presence or location of an element, a sequence of elements
685 -- or another stream within a stream.
687 -- -- ** Searching Elements
695 -- * Concurrent Transformation
696 -- ** Concurrent Pipelines
702 -- ** Concurrency Control
715 -- * Combining Streams
716 -- | New streams can be constructed by appending, merging or zipping
719 -- Any exceptions generated by concurrent evaluation are propagated to
720 -- the consumer of the stream as soon as they occur. Exceptions from a
721 -- particular stream are guaranteed to arrive in the same order in the
722 -- output stream as they were generated in the input stream.
724 -- See 'maxThreads' and 'maxBuffer' to control the concurrency of the
725 -- concurrent combinators.
727 -- See also: "Streamly.Internal.Data.Stream.IsStream.Expand" for
728 -- @Pre-release@ functions.
730 -- ** Linear combinators
731 -- | These functions have O(n) append performance. They can be used
732 -- efficiently with 'concatMapWith' et. al.
741 -- ** PairWise combinators
742 -- | These functions have O(n^2) append performance when used linearly e.g.
743 -- using 'concatMapWith'. However, they can be combined pair wise using
744 -- 'Streamly.Internal.Data.Stream.IsStream.Expand.concatPairsWith' to give
745 -- O(n * log n) complexity.
764 -- | Stream operations like map and filter represent loop processing in
765 -- imperative programming terms. Similarly, the imperative concept of
766 -- nested loops are represented by streams of streams. The 'concatMap'
767 -- operation represents nested looping.
768 -- A 'concatMap' operation loops over the input stream and then for each
769 -- element of the input stream generates another stream and then loops over
770 -- that inner stream as well producing effects and generating a single
772 -- The 'Monad' instances of different stream types provide a more
773 -- convenient way of writing nested loops. Note that the monad bind
774 -- operation is just @flip concatMap@.
776 -- One dimension loops are just a special case of nested loops. For
777 -- example, 'concatMap' can degenerate to a simple map operation:
779 -- > map f m = S.concatMap (\x -> S.fromPure (f x)) m
781 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
784 -- > filter p m = S.concatMap (\x -> if p x then S.fromPure x else S.nil) m
791 -- ** Containers of Streams
792 -- | These are variants of standard 'Foldable' fold functions that use a
793 -- polymorphic stream sum operation (e.g. 'async' or 'wSerial') to fold a
794 -- finite container of streams. Note that these are just special cases of
795 -- the more general 'concatMapWith' operation.
798 , concatMapFoldableWith
799 , concatForFoldableWith
803 -- See also: "Streamly.Internal.Data.Stream.IsStream.Reduce" for
804 -- @Pre-release@ functions.
812 -- | In general we can express splitting in terms of parser combinators.
813 -- These are some common use functions for convenience and efficiency.
814 -- While parsers can fail these functions are designed to transform a
815 -- stream without failure with a predefined behavior for all cases.
817 -- In general, there are three possible ways of combining stream segments
818 -- with a separator. The separator could be prefixed to each segment,
819 -- suffixed to each segment, or it could be infixed between segments.
820 -- 'intersperse' and 'intercalate' operations are examples of infixed
821 -- combining whereas 'unlines' is an example of suffixed combining. When we
822 -- split a stream with separators we can split in three different ways,
823 -- each being an opposite of the three ways of combining.
825 -- Splitting may keep the separator or drop it. Depending on how we split,
826 -- the separator may be kept attached to the stream segments in prefix or
827 -- suffix position or as a separate element in infix position. Combinators
828 -- like 'splitOn' that use @On@ in their names drop the separator and
829 -- combinators that use 'With' in their names keep the separator. When a
830 -- segment is missing it is considered as empty, therefore, we never
831 -- encounter an error in parsing.
833 -- -- ** Splitting By Elements
838 , wordsBy -- strip, compact and split
841 -- | Splitting a stream by combining multiple contiguous elements into
842 -- groups using some criterion.
848 -- | Most of these combinators inhibit stream fusion, therefore, when
849 -- possible, they should be called in an outer loop to mitigate the cost.
850 -- For example, instead of calling them on a stream of chars call them on a
851 -- stream of arrays before flattening it to a stream of chars.
853 -- See also: "Streamly.Internal.Data.Stream.IsStream.Exception" for
854 -- @Pre-release@ functions.
863 -- * Lifting Inner Monad
864 -- | See also: "Streamly.Internal.Data.Stream.IsStream.Lift" for
865 -- @Pre-release@ functions.
872 -- | Stream types that end with a @T@ (e.g. 'SerialT') are monad
880 -- ** Speculative Streams
884 -- ** Asynchronous Streams
890 -- ** Zipping Streams
908 -- * Converting from/to Stream/StreamK types
914 -- * Stream Type Adapters
944import Streamly.Internal.Control.Concurrent (MonadAsync)
946 hiding (Foldable(..), filter, drop, dropWhile, take, takeWhile, zipWith,
947 map, mapM, mapM_, sequence, all, any,
948 notElem, head, last, tail,
949 reverse, iterate, init, and, or, lookup, (!!),
950 scanl, scanl1, repeat, replicate, concatMap, span)
952import Streamly.Internal.Data.Stream.IsStream
955-- >>> :set -fno-warn-deprecations
956-- >>> import qualified Streamly.Data.Fold as Fold
957-- >>> import qualified Streamly.Prelude as Stream
961-- Serial streams are /spatially ordered/, they execute the actions in the
962-- stream strictly one after the other.
964-- There are two serial stream types 'SerialT' and 'WSerialT'. They differ
965-- only in the 'Semigroup' and 'Monad' instance behavior.
969-- Speculative streams evaluate some future actions speculatively and
970-- concurrently, and keep the results ready for consumption. As in serial
971-- streams, results are consumed in the same order as the actions in the
974-- Even though the results of actions are ordered, the side effects are only
975-- partially ordered. Therefore, the semigroup operation is not commutative
976-- from the pure outputs perspective but commutative from side effects
981-- Asynchronous streams evaluate some future actions concurrently, the results
982-- are given to the consumer as soon as they become available, they may not be
983-- in the same order as the actions in the stream.
985-- The results of the actions as well as their side effects are partially
986-- ordered. Since the order of elements does not matter the 'Semigroup'
987-- operation is effectively commutative.
989-- There are two asynchronous stream types 'AsyncT' and 'WAsyncT'. They differ
990-- only in the 'Semigroup' and 'Monad' instance behavior.
994-- 'ZipSerialM' and 'ZipAsyncM', provide 'Applicative' instances for zipping the
995-- corresponding elements of two streams together. Note that these types are
1000-- Let's take a closer look at the @foldr@ definition for lists, as given
1004-- foldr f z (x:xs) = x \`f` foldr f z xs
1007-- @foldr@ invokes the fold step function @f@ as @f x (foldr f z xs)@. At each
1008-- invocation of @f@, @foldr@ gives us the next element in the input container
1009-- @x@ and a recursive expression @foldr f z xs@ representing the yet unbuilt
1010-- (lazy thunk) part of the output.
1012-- When @f x xs@ is lazy in @xs@ it can consume the input one element at a time
1013-- in FIFO order to build a lazy output expression. For example,
1015-- > f x remaining = show x : remaining
1017-- @take 2 $ foldr f [] (1:2:undefined)@ would consume the input lazily on
1018-- demand, consuming only first two elements and resulting in ["1", "2"]. @f@
1019-- can terminate recursion by not evaluating the @remaining@ part:
1021-- > f 2 remaining = show 2 : []
1022-- > f x remaining = show x : remaining
1024-- @f@ would terminate recursion whenever it sees element @2@ in the input.
1025-- Therefore, @take 2 $ foldr f [] (1:2:undefined)@ would work without any
1028-- On the other hand, if @f a b@ is strict in @b@ it would end up consuming the
1029-- whole input right away and expanding the recursive expression @b@ (i.e.
1030-- @foldr f z xs@) fully before it yields an output expression, resulting in
1031-- the following /right associated expression/:
1034-- foldr f z xs == x1 \`f` (x2 \`f` ...(xn \`f` z))
1039-- > f x remaining = x + remaining
1041-- With this definition, @foldr f 0 [1..1000]@, would recurse completely until
1042-- it reaches the terminating case @... `f` (1000 `f` 0)@, and then
1043-- start reducing the whole expression from right to left, therefore, consuming
1044-- the input elements in LIFO order. Thus, such an evaluation would require
1045-- memory proportional to the size of input. Try out @foldr (+) 0 (map (\\x ->
1046-- trace (show x) x) [1..10])@.
1048-- Notice the order of the arguments to the step function @f a b@. It follows
1049-- the order of @a@ and @b@ in the right associative recursive expression
1050-- generated by expanding @a \`f` b@.
1052-- A right fold is a pull fold, the step function is the puller, it can pull
1053-- more data from the input container by using its second argument in the
1054-- output expression or terminate pulling by not using it. As a corollary:
1056-- 1. a step function which is lazy in its second argument (usually functions
1057-- or constructors that build a lazy structure e.g. @(:)@) can pull lazily on
1059-- 2. a step function strict in its second argument (usually reducers e.g.
1060-- (+)) would end up pulling all of its input and buffer it in memory before
1061-- potentially reducing it.
1063-- A right fold is suitable for lazy reconstructions e.g. transformation,
1064-- mapping, filtering of /right associated input structures/ (e.g. cons lists).
1065-- Whereas a left fold is suitable for reductions (e.g. summing a stream of
1066-- numbers) of right associated structures. Note that these roles will reverse
1067-- for left associated structures (e.g. snoc lists). Most of our observations
1068-- here assume right associated structures, lists being the canonical example.
1070-- 1. A lazy FIFO style pull using a right fold allows pulling a potentially
1071-- /infinite/ input stream lazily, perform transformations on it, and
1072-- reconstruct a new structure without having to buffer the whole structure. In
1073-- contrast, a left fold would buffer the entire structure before the
1074-- reconstructed structure can be consumed.
1075-- 2. Even if buffering the entire input structure is ok, we need to keep in
1076-- mind that a right fold reconstructs structures in a FIFO style, whereas a
1077-- left fold reconstructs in a LIFO style, thereby reversing the order of
1079-- 3. A right fold has termination control and therefore can terminate early
1080-- without going through the entire input, a left fold cannot terminate
1081-- without consuming all of its input. For example, a right fold
1082-- implementation of 'or' can terminate as soon as it finds the first 'True'
1083-- element, whereas a left fold would necessarily go through the entire input
1084-- irrespective of that.
1085-- 4. Reduction (e.g. using (+) on a stream of numbers) using a right fold
1086-- occurs in a LIFO style, which means that the entire input gets buffered
1087-- before reduction starts. Whereas with a strict left fold reductions occur
1088-- incrementally in FIFO style. Therefore, a strict left fold is more suitable
1094-- Note that the observations below about the behavior of a left fold assume
1095-- that we are working on a right associated structure like cons lists and
1096-- streamly streams. If we are working on a left associated structure (e.g.
1097-- snoc lists) the roles of right and left folds would reverse.
1099-- Let's take a closer look at the @foldl@ definition for lists given above:
1102-- foldl f z (x:xs) = foldl f (z \`f` x) xs
1105-- @foldl@ calls itself recursively, in each call it invokes @f@ as @f z x@
1106-- providing it with the result accumulated till now @z@ (the state) and the
1107-- next element from the input container. First call to @f@ is supplied with
1108-- the initial value of the accumulator @z@ and each subsequent call uses the
1109-- output of the previous call to @f z x@.
1111-- >> foldl' (+) 0 [1,2,3]
1114-- The recursive call at the head of the output expression is bound to be
1115-- evaluated until recursion terminates, therefore, a left fold always
1116-- /consumes the whole input container/. The following would result in an
1117-- error, even though the fold is not using the values at all:
1119-- >> foldl' (\_ _ -> 0) 0 (1:undefined)
1120-- > *** Exception: Prelude.undefined
1122-- As @foldl@ recurses, it builds the left associated expression shown below.
1123-- Notice, the order of the arguments to the step function @f b a@. It follows
1124-- the left associative recursive expression generated by expanding @b \`f` a@.
1127-- foldl f z xs == (((z \`f` x1) \`f` x2) ...) \`f` xn
1131-- The strict left fold @foldl'@ forces the reduction of its argument @z \`f`
1132-- x@ before using it, therefore it never builds the whole expression in
1133-- memory. Thus, @z \`f` x1@ would get reduced to @z1@ and then @z1 \`f` x2@
1134-- would get reduced to @z2@ and so on, incrementally reducing the expression
1135-- from left to right as it recurses, consuming the input in FIFO order. Try
1136-- out @foldl' (+) 0 (map (\\x -> trace (show x) x) [1..10])@ to see how it
1137-- works. For example:
1140-- >>> Stream.foldl' (+) 0 $ Stream.fromList [1,2,3,4]
1152-- However, @foldl'@ evaluates the accumulator only to WHNF. It may further
1153-- help if the step function uses a strict data structure as accumulator to
1154-- improve performance and to keep the expression fully reduced at all times
1157-- A left fold can also build a new structure instead of reducing one if a
1158-- constructor is used as a fold step. However, it may not be very useful
1159-- because it will consume the whole input and construct the new structure in
1160-- memory before we can consume it. Thus the whole structure gets buffered in
1161-- memory. When the list constructor is used it would build a new list in
1162-- reverse (LIFO) order:
1165-- >>> Stream.foldl' (flip (:)) [] $ Stream.fromList [1,2,3,4]
1170-- A left fold is a push fold. The producer pushes its contents to the step
1171-- function of the fold. The step function therefore has no control to stop the
1172-- input, it can only discard it if it does not need it. We can also consider a
1173-- left fold as a state machine where the state is store in the accumulator,
1174-- the state can be modified based on new inputs that are pushed to the fold.
1176-- In general, a strict left fold is a reducing fold, whereas a right fold is a
1177-- constructing fold. A strict left fold reduces in a FIFO order whereas it
1178-- constructs in a LIFO order, and vice-versa for the right fold. See the
1179-- documentation of 'foldrM' for a discussion on where a left or right fold is
1182-- To perform a left fold lazily without having to consume all the input one
1183-- can use @scanl@ to stream the intermediate results of the fold and consume
1184-- the resulting stream lazily.
1189-- See "Streamly.Data.Fold" for an overview of composable folds. All folds in
1190-- this module can be expressed in terms of composable folds using 'fold'.
1194-- Stream processing functions can be composed in a chain using function
1195-- application with or without the '$' operator, or with reverse function
1196-- application operator '&'. Streamly provides concurrent versions of these
1197-- operators applying stream processing functions such that each stage of the
1198-- stream can run in parallel. The operators start with a @|@; we can read '|$'
1199-- as "@parallel dollar@" to remember that @|@ comes before '$'.
1203-- These combinators can be used at any point in a stream composition to set
1204-- parameters to control the concurrency of the /argument stream/. A control
1205-- parameter set at any point remains effective for any concurrent combinators
1206-- used in the argument stream until it is reset by using the combinator again.
1207-- These control parameters have no effect on non-concurrent combinators in the
1208-- stream, or on non-concurrent streams.
1210-- /Pitfall:/ Remember that 'maxBuffer' in the following example applies to
1211-- 'mapM' and any other combinators that may follow it, and it does not apply
1212-- to the combinators before it:
1216-- $ Stream.maxBuffer 10
1221-- If we use '&' instead of '$' the situation will reverse, in the following
1222-- example, 'maxBuffer' does not apply to 'mapM', it applies to combinators
1223-- that come before it, because those are the arguments to 'maxBuffer':
1227-- & Stream.maxBuffer 10
1234-- You may want to use different stream composition styles at different points
1235-- in your program. Stream types can be freely converted or adapted from one
1236-- type to another. The 'IsStream' type class facilitates type conversion of
1237-- one stream type to another. It is not used directly, instead the type
1238-- combinators provided below are used for conversions.
1240-- To adapt from one monomorphic type (e.g. 'AsyncT') to another monomorphic
1241-- type (e.g. 'SerialT') use the 'adapt' combinator. To give a polymorphic code
1242-- a specific interpretation or to adapt a specific type to a polymorphic type
1243-- use the type specific combinators e.g. 'fromAsync' or 'fromWSerial'. You
1244-- cannot adapt polymorphic code to polymorphic code, as the compiler would not know
1245-- which specific type you are converting from or to. If you see a an
1246-- @ambiguous type variable@ error then most likely you are using 'adapt'
1247-- 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