3-- Module : Streamly.Data.Stream
4-- Copyright : (c) 2017 Composewell Technologies
7-- Maintainer : streamly@composewell.com
11-- Fast, composable stream producers with ability to terminate, supporting
14-- Please refer to "Streamly.Internal.Data.Stream" for more functions that have
15-- not yet been released.
17-- For continuation passing style (CPS) stream type, please refer to
18-- the "Streamly.Data.StreamK" module.
20-- Checkout the <https://github.com/composewell/streamly-examples>
21-- repository for many more real world examples of stream programming.
23module Streamly.Data.Stream
26 -- | To execute the code examples provided in this module in ghci, please
27 -- run the following commands first.
38 -- | Functions ending in the general shape @b -> Stream m a@.
40 -- See also: "Streamly.Internal.Data.Stream.Generate" for
41 -- @Pre-release@ functions.
45 -- >>> fromIndices f = fmap f $ Stream.enumerateFrom 0
46 -- >>> fromIndicesM f = Stream.mapM f $ Stream.enumerateFrom 0
47 -- >>> fromListM = Stream.sequence . Stream.fromList
48 -- >>> fromFoldable = StreamK.toStream . StreamK.fromFoldable
49 -- >>> fromFoldableM = Stream.sequence . fromFoldable
52 -- | A fused 'Stream' is never constructed using 'cons', we always convert
53 -- other type of containers like list into streams, or generate it using
54 -- custom functions provided in this module. The 'cons' primitive has a
55 -- rare use in fusing a small number of elements. On the other hand, it is
56 -- common to construct 'StreamK' stream using the 'StreamK.cons' primitive.
63 -- | 'unfoldrM' is the most general way of generating a stream efficiently.
64 -- All other generation operations can be expressed using it.
69 -- | Generate a monadic stream from a seed value or values.
77 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
78 -- to be slightly faster than the idioms like @[from, then..]@.
81 -- | We can use the 'Enum' type class to enumerate a type producing a list
82 -- and then convert it to a stream:
85 -- 'fromList' $ 'Prelude.enumFromThen' from then
88 -- However, this is not particularly efficient.
89 -- The 'Enumerable' type class provides corresponding functions that
90 -- generate a stream instead of a list, efficiently.
100 -- ** From Containers
101 -- | Convert an input structure, container or source into a stream. All of
102 -- these can be expressed in terms of primitives.
106 -- | Most of the above stream generation operations can also be expressed
107 -- using the corresponding unfolds in the "Streamly.Data.Unfold" module.
108 , unfold -- XXX rename to fromUnfold?
111 -- | Functions ending in the general shape @Stream m a -> m b@ or @Stream m
112 -- a -> m (b, Stream m a)@
114 -- See also: "Streamly.Internal.Data.Stream.Eliminate" for @Pre-release@
117-- EXPLANATION: In imperative terms a fold can be considered as a loop over the stream
118-- that reduces the stream to a single value.
119-- Left and right folds both use a fold function @f@ and an identity element
120-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
121-- new data structure. The new structure may be a recursive construction (a
122-- container) or a non-recursive single value reduction of the original
125-- Both right and left folds are mathematical duals of each other, they are
126-- functionally equivalent. Operationally, a left fold on a left associated
127-- structure behaves exactly in the same way as a right fold on a right
128-- associated structure. Similarly, a left fold on a right associated structure
129-- behaves in the same way as a right fold on a left associated structure.
130-- However, the behavior of a right fold on a right associated structure is
131-- operationally different (even though functionally equivalent) than a left
132-- fold on the same structure.
134-- On right associated structures like Haskell @cons@ lists or Streamly
135-- streams, a lazy right fold is naturally suitable for lazy recursive
136-- reconstruction of a new structure, while a strict left fold is naturally
137-- suitable for efficient reduction. In right folds control is in the hand of
138-- the @puller@ whereas in left folds the control is in the hand of the
141-- The behavior of right and left folds are described in detail in the
142-- individual fold's documentation. To illustrate the two folds for right
143-- associated @cons@ lists:
145-- > foldr :: (a -> b -> b) -> b -> [a] -> b
147-- > foldr f z (x:xs) = x `f` foldr f z xs
149-- > foldl :: (b -> a -> b) -> b -> [a] -> b
151-- > foldl f z (x:xs) = foldl f (z `f` x) xs
153-- @foldr@ is conceptually equivalent to:
156-- > foldr f z [x] = f x z
157-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
159-- @foldl@ is conceptually equivalent to:
162-- > foldl f z [x] = f z x
163-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
165-- Left and right folds are duals of each other.
168-- foldr f z xs = foldl (flip f) z (reverse xs)
169-- foldl f z xs = foldr (flip f) z (reverse xs)
175-- foldr f z xs = foldl g id xs z where g k x = k . f x
176-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
180-- NOTE: Folds are inherently serial as each step needs to use the result of
181-- the previous step. However, it is possible to fold parts of the stream in
182-- parallel and then combine the results using a monoid.
185 -- Consuming a part of the stream and returning the rest. Functions
186 -- ending in the general shape @Stream m a -> m (b, Stream m a)@
189 -- ** Strict Left Folds
190 -- XXX Need to have a general parse operation here which can be used to
191 -- express all others.
192 , fold -- XXX rename to run? We can have a Stream.run and Fold.run.
193 -- XXX fold1 can be achieved using Monoids or Refolds.
194 -- XXX We can call this just "break" and parseBreak as "munch"
197 -- XXX should we have a Fold returning function in stream module?
205 -- ** Lazy Right Folds
206 -- | Consuming a stream to build a right associated expression, suitable
207 -- for lazy evaluation. Evaluation of the input happens when the output of
208 -- the fold is evaluated, the fold output is a lazy thunk.
210 -- This is suitable for stream transformation operations, for example,
211 -- operations like mapping a function over the stream.
216 -- | Usually you can use the folds in "Streamly.Data.Fold". However, some
217 -- folds that may be commonly used or may have an edge in performance in
218 -- some cases are provided here.
223 -- | Stateless one-to-one transformations. Use 'fmap' for mapping a pure
224 -- function on a stream.
227 -- In imperative terms a map operation can be considered as a loop over
228 -- the stream that transforms the stream into another stream by performing
229 -- an operation on each element of the stream.
231 -- 'map' is the least powerful transformation operation with strictest
232 -- guarantees. A map, (1) is a stateless loop which means that no state is
233 -- allowed to be carried from one iteration to another, therefore,
234 -- operations on different elements are guaranteed to not affect each
235 -- other, (2) is a strictly one-to-one transformation of stream elements
236 -- which means it guarantees that no elements can be added or removed from
237 -- the stream, it can merely transform them.
245 -- | Stateful one-to-one transformations.
247 -- See also: "Streamly.Internal.Data.Stream.Transform" for
248 -- @Pre-release@ functions.
252 -- | We can perform scans using folds with the 'scan' combinator in the
253 -- next section. However, the combinators supplied in this section are
254 -- better amenable to stream fusion when combined with other operations.
255 -- Note that 'postscan' using folds fuses well and does not require custom
256 -- combinators like these.
263 -- ** Scanning By 'Fold'
266 -- >>> scanl' f z = Stream.scan (Fold.foldl' f z)
267 -- >>> scanlM' f z = Stream.scan (Fold.foldlM' f z)
268 -- >>> postscanl' f z = Stream.postscan (Fold.foldl' f z)
269 -- >>> postscanlM' f z = Stream.postscan (Fold.foldlM' f z)
270 -- >>> scanl1' f = Stream.catMaybes . Stream.scan (Fold.foldl1' f)
271 -- >>> scanl1M' f = Stream.catMaybes . Stream.scan (Fold.foldlM1' f)
274 -- XXX postscan1 can be implemented using Monoids or Refolds.
277 -- Indexing can be considered as a special type of zipping where we zip a
278 -- stream with an index stream.
282 -- | Add elements to the stream.
284 -- Inserting elements is a special case of interleaving/merging streams.
291 -- | Remove elements from the stream.
293 -- ** Stateless Filters
294 -- | 'mapMaybeM' is the most general stateless filtering operation. All
295 -- other filtering operations can be expressed using it.
298 -- In imperative terms a filter over a stream corresponds to a loop with a
299 -- @continue@ clause for the cases when the predicate fails.
312 -- ** Stateful Filters
313 -- | 'scanMaybe' is the most general stateful filtering operation. The
314 -- filtering folds (folds returning a 'Maybe' type) in
315 -- "Streamly.Internal.Data.Fold" can be used along with 'scanMaybe' to
316 -- perform stateful filtering operations in general.
320 -- >>> deleteBy cmp x = Stream.scanMaybe (Fold.deleteBy cmp x)
321 -- >>> findIndices p = Stream.scanMaybe (Fold.findIndices p)
322 -- >>> elemIndices a = findIndices (== a)
323 -- >>> uniq = Stream.scanMaybe (Fold.uniqBy (==))
332 -- XXX These are available as scans in folds. We need to check the
333 -- performance though. If these are common and we need convenient stream
334 -- ops then we can expose these.
344 -- Finding the presence or location of an element, a sequence of elements
345 -- or another stream within a stream.
347 -- -- ** Searching Elements
351 -- * Combining Two Streams
356 -- | When interleaving more than two streams you may want to interleave
357 -- them pairwise creating a balanced binary merge tree.
361 -- | When merging more than two streams you may want to merging them
362 -- pairwise creating a balanced binary merge tree.
364 -- Merging of @n@ streams can be performed by combining the streams pair
365 -- wise using 'mergeMapWith' to give O(n * log n) time complexity. If used
366 -- with 'concatMapWith' it will have O(n^2) performance.
372 -- | When zipping more than two streams you may want to zip them
373 -- pairwise creating a balanced binary tree.
375 -- Zipping of @n@ streams can be performed by combining the streams pair
376 -- wise using 'mergeMapWith' with O(n * log n) time complexity. If used
377 -- with 'concatMapWith' it will have O(n^2) performance.
383 -- XXX The argument order in this operation is such that it seems we are
384 -- transforming the first stream using the second stream because the second
385 -- stream is evaluated many times or buffered and better be finite, first
386 -- stream could potentially be infinite. In the tradition of using the
387 -- transformed stream at the end we can have a flipped version called
388 -- "crossMap" or "nestWith".
392 -- , CrossStream (..)
399 -- * Stream of streams
400 -- | Stream operations like map and filter represent loop processing in
401 -- imperative programming terms. Similarly, the imperative concept of
402 -- nested loops are represented by streams of streams. The 'concatMap'
403 -- operation represents nested looping.
404 -- A 'concatMap' operation loops over the input stream and then for each
405 -- element of the input stream generates another stream and then loops over
406 -- that inner stream as well producing effects and generating a single
409 -- One dimension loops are just a special case of nested loops. For
410 -- example, 'concatMap' can degenerate to a simple map operation:
412 -- > map f m = S.concatMap (\x -> S.fromPure (f x)) m
414 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
417 -- > filter p m = S.concatMap (\x -> if p x then S.fromPure x else S.nil) m
427 -- >>> splitWithSuffix p f = Stream.foldMany (Fold.takeEndBy p f)
428 -- >>> splitOnSuffix p f = Stream.foldMany (Fold.takeEndBy_ p f)
429 -- >>> groupsBy eq f = Stream.parseMany (Parser.groupBy eq f)
430 -- >>> groupsByRolling eq f = Stream.parseMany (Parser.groupByRolling eq f)
431 -- >>> wordsBy p f = Stream.parseMany (Parser.wordBy p f)
432 -- >>> groupsOf n f = Stream.foldMany (Fold.take n f)
433 , foldMany -- XXX Rename to foldRepeat
437 -- * Buffered Operations
438 -- | Operations that require buffering of the stream.
439 -- Reverse is essentially a left fold followed by an unfold.
442 -- * Multi-Stream folds
443 -- | Operations that consume multiple streams at the same time.
449 -- trimming sequences
452 -- Exceptions and resource management depend on the "exceptions" package
453 -- XXX We can have IO Stream operations not depending on "exceptions"
457 -- | Most of these combinators inhibit stream fusion, therefore, when
458 -- possible, they should be called in an outer loop to mitigate the cost.
459 -- For example, instead of calling them on a stream of chars call them on a
460 -- stream of arrays before flattening it to a stream of chars.
462 -- See also: "Streamly.Internal.Data.Stream.Exception" for
463 -- @Pre-release@ functions.
468 -- * Resource Management
469 -- | 'bracket' is the most general resource management operation, all other
470 -- operations can be expressed using it. These functions have IO suffix
471 -- because the allocation and cleanup functions are IO actions. For
472 -- generalized allocation and cleanup functions see the functions without
473 -- the IO suffix in the "streamly" package.
480 -- * Transforming Inner Monad
494import qualified Streamly.Internal.Data.Array.Type as Array
495import Streamly.Internal.Data.Stream.StreamD
497 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
498 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
499 notElem, maximum, minimum, head, last, tail, length, null,
500 reverse, iterate, init, and, or, lookup, foldr1, (!!),
501 scanl, scanl1, repeat, replicate, concatMap, span)
503#include "DocTestDataStream.hs"
507-- Streamly is a framework for modular data flow based programming and
508-- declarative concurrency. Powerful stream fusion framework in streamly
509-- allows high performance combinatorial programming even when using byte level
510-- streams. Streamly API is similar to Haskell lists.
512-- == Console Echo Example
514-- In the following example, 'repeatM' generates an infinite stream of 'String'
515-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
516-- 'putStrLn' on each element in the stream converting it to stream of '()'.
517-- Finally, 'drain' folds the stream to IO discarding the () values, thus
518-- producing only effects.
520-- >>> import Data.Function ((&))
524-- Stream.repeatM getLine -- Stream IO String
525-- & Stream.mapM putStrLn -- Stream IO ()
526-- & Stream.fold Fold.drain -- IO ()
529-- This is a console echo program. It is an example of a declarative loop
530-- written using streaming combinators. Compare it with an imperative @while@
533-- Hopefully, this gives you an idea how we can program declaratively by
534-- representing loops using streams. In this module, you can find all
535-- "Data.List" like functions and many more powerful combinators to perform
536-- common programming tasks.
540-- The fused 'Stream' type employs stream fusion for C-like performance when
541-- looping over data. It represents a stream source or transformation by
542-- defining a state machine with explicit state, and a step function working on
543-- the state. A typical stream operation consumes elements from the previous
544-- state machine in the pipeline, transforms them and yields new values for the
545-- next stage to consume. The stream operations are modular and represent a
546-- single task, they have no knowledge of previous or next operation on the
549-- A typical stream pipeline consists of a stream producer, several stream
550-- transformation operations and a stream consumer. All these operations taken
551-- together form a closed loop processing the stream elements. Elements are
552-- transferred between stages using a boxed data constructor. However, all the
553-- stages of the pipeline are fused together by GHC, eliminating the
554-- intermediate constructors, and thus forming a tight C like loop without any
555-- boxed data being used in the loop.
557-- Stream fusion works effectively when:
559-- * the stream pipeline is composed statically (known at compile time)
560-- * all the operations forming the loop are inlined
561-- * the loop is not recursively defined, recursion breaks inlining
563-- If these conditions cannot be met, the CPS style stream type 'StreamK' may
564-- turn out to be a better choice than the fused stream type 'Stream'.
566-- == Stream vs StreamK
568-- The fused stream model avoids constructor allocations or function call
569-- overheads. However, the stream is represented as a state machine and to
570-- generate elements it has to navigate the decision tree of the state machine.
571-- Moreover, the state machine is cranked for each element in the stream. This
572-- performs extremely well when the number of states are limited. The state
573-- machine starts getting expensive as the number of states increase. For
574-- example, generating a million element stream from a list requires a single
575-- state and is very efficient. However, using fused 'cons' to generate a
576-- million element stream would be a disaster.
578-- A typical worst case scenario for fused stream model is a large number of
579-- `cons` or `append` operations. A few static `cons` or `append` operations
580-- are very fast and much faster than a CPS style stream. However, if we
581-- construct a large stream using `cons` it introduces as many states in the
582-- state machine as the number of elements. If we compose the `cons` as a
583-- binary tree it will take @n * log n@ time to navigate the tree, and @n * n@
584-- if it is a right associative composition.
586-- For quadratic cases of fused stream, after a certain threshold the CPS
587-- stream would perform much better and exhibit linear performance behavior.
588-- Operations like 'cons' or 'append'; are typically recursively called to
589-- construct a lazy infinite stream. For such use cases the CPS style 'StreamK'
590-- type is provided. CPS streams do not have a state machine that needs to be
591-- cranked for each element, past state has no effect on the future element
592-- processing. However, it incurs a function call overhead for each operation
593-- for each element, which could be very large overhead compared to fused state
594-- machines even if it has many states and cranks it for each element. But in
595-- some cases scales tip in favor of the CPS stream. In those cases even though
596-- CPS has a large constant overhead, it has a linear performance rather than
599-- As a general guideline, if you have to use 'cons' or 'append' or operations
600-- of similar nature, at a large scale, then 'StreamK' should be used. When you
601-- need to compose the stream dynamically or recursively, then 'StreamK' should
602-- be used. Typically you would use a dynamically generated 'StreamK' with
603-- chunks of data which can then be processed by statically fused stream
604-- pipeline operations.
606-- 'Stream' and 'StreamK' types can be interconverted. See
607-- "Streamly.Data.StreamK" module for conversion operations.
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