3-- Module : Streamly.Data.Stream
4-- Copyright : (c) 2017 Composewell Technologies
7-- Maintainer : streamly@composewell.com
11-- Streams represented as state machines, that fuse together when composed
12-- statically, eliminating function calls or intermediate constructor
13-- allocations - generating tight, efficient loops. Suitable for high
14-- performance looping operations.
16-- If you need to call these operations recursively in a loop (i.e. composed
17-- dynamically) then it is recommended to use the continuation passing style
18-- (CPS) stream operations from the "Streamly.Data.StreamK" module. 'Stream'
19-- and 'StreamK' types are interconvertible. See more details in the
20-- documentation below regarding 'Stream' vs 'StreamK'.
22-- Please refer to "Streamly.Internal.Data.Stream" for more functions that have
23-- not yet been released.
25-- Checkout the <https://github.com/composewell/streamly-examples>
26-- repository for many more real world examples of stream programming.
28module Streamly.Data.Stream
31 -- | To execute the code examples provided in this module in ghci, please
32 -- run the following commands first.
43 -- | Functions ending in the general shape @b -> Stream m a@.
47 -- >>> fromIndices f = fmap f $ Stream.enumerateFrom 0
48 -- >>> fromIndicesM f = Stream.mapM f $ Stream.enumerateFrom 0
49 -- >>> fromListM = Stream.sequence . Stream.fromList
50 -- >>> fromFoldable = StreamK.toStream . StreamK.fromFoldable
51 -- >>> fromFoldableM = Stream.sequence . fromFoldable
54 -- | A fused 'Stream' is never constructed using these primitives, they are
55 -- typically generated by converting containers like list into streams, or
56 -- generated using custom functions provided in this module. The 'cons'
57 -- primitive in this module has a rare use in fusing a small number of
58 -- elements. On the other hand, it is common to construct 'StreamK' stream
59 -- using the StreamK.'StreamK.cons' primitive.
66 -- | 'unfoldrM' is the most general way of generating a stream efficiently.
67 -- All other generation operations can be expressed using it.
72 -- | Generate a monadic stream from a seed value or values.
80 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
81 -- to be slightly faster than the idioms like @[from, then..]@.
84 -- | We can use the 'Enum' type class to enumerate a type producing a list
85 -- and then convert it to a stream:
88 -- 'fromList' $ 'Prelude.enumFromThen' from then
91 -- However, this is not particularly efficient.
92 -- The 'Enumerable' type class provides corresponding functions that
93 -- generate a stream instead of a list, efficiently.
103 -- ** From Containers
104 -- | Convert an input structure, container or source into a stream. All of
105 -- these can be expressed in terms of primitives.
109 -- | Most of the above stream generation operations can also be expressed
110 -- using the corresponding unfolds in the "Streamly.Data.Unfold" module.
111 , unfold -- XXX rename to fromUnfold?
114 -- | Functions ending in the general shape @Stream m a -> m b@ or @Stream m
115 -- a -> m (b, Stream m a)@
118-- EXPLANATION: In imperative terms a fold can be considered as a loop over the stream
119-- that reduces the stream to a single value.
120-- Left and right folds both use a fold function @f@ and an identity element
121-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
122-- new data structure. The new structure may be a recursive construction (a
123-- container) or a non-recursive single value reduction of the original
126-- Both right and left folds are mathematical duals of each other, they are
127-- functionally equivalent. Operationally, a left fold on a left associated
128-- structure behaves exactly in the same way as a right fold on a right
129-- associated structure. Similarly, a left fold on a right associated structure
130-- behaves in the same way as a right fold on a left associated structure.
131-- However, the behavior of a right fold on a right associated structure is
132-- operationally different (even though functionally equivalent) than a left
133-- fold on the same structure.
135-- On right associated structures like Haskell @cons@ lists or Streamly
136-- streams, a lazy right fold is naturally suitable for lazy recursive
137-- reconstruction of a new structure, while a strict left fold is naturally
138-- suitable for efficient reduction. In right folds control is in the hand of
139-- the @puller@ whereas in left folds the control is in the hand of the
142-- The behavior of right and left folds are described in detail in the
143-- individual fold's documentation. To illustrate the two folds for right
144-- associated @cons@ lists:
146-- > foldr :: (a -> b -> b) -> b -> [a] -> b
148-- > foldr f z (x:xs) = x `f` foldr f z xs
150-- > foldl :: (b -> a -> b) -> b -> [a] -> b
152-- > foldl f z (x:xs) = foldl f (z `f` x) xs
154-- @foldr@ is conceptually equivalent to:
157-- > foldr f z [x] = f x z
158-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
160-- @foldl@ is conceptually equivalent to:
163-- > foldl f z [x] = f z x
164-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
166-- Left and right folds are duals of each other.
169-- foldr f z xs = foldl (flip f) z (reverse xs)
170-- foldl f z xs = foldr (flip f) z (reverse xs)
176-- foldr f z xs = foldl g id xs z where g k x = k . f x
177-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
181-- NOTE: Folds are inherently serial as each step needs to use the result of
182-- the previous step. However, it is possible to fold parts of the stream in
183-- parallel and then combine the results using a monoid.
186 -- Consuming a part of the stream and returning the rest. Functions
187 -- ending in the general shape @Stream m a -> m (b, Stream m a)@
190 -- ** Strict Left Folds
191 -- XXX Need to have a general parse operation here which can be used to
192 -- express all others.
193 , fold -- XXX rename to run? We can have a Stream.run and Fold.run.
194 -- XXX fold1 can be achieved using Monoids or Refolds.
195 -- XXX We can call this just "break" and parseBreak as "munch"
198 -- XXX should we have a Fold returning function in stream module?
206 -- ** Lazy Right Folds
207 -- | Consuming a stream to build a right associated expression, suitable
208 -- for lazy evaluation. Evaluation of the input happens when the output of
209 -- the fold is evaluated, the fold output is a lazy thunk.
211 -- This is suitable for stream transformation operations, for example,
212 -- operations like mapping a function over the stream.
217 -- | Usually you can use the folds in "Streamly.Data.Fold". However, some
218 -- folds that may be commonly used or may have an edge in performance in
219 -- some cases are provided here.
223 -- >>> foldlM' f a = Stream.fold (Fold.foldlM' f a)
224 -- >>> foldl1 f = Stream.fold (Fold.foldl1' f)
225 -- >>> foldl' f a = Stream.fold (Fold.foldl' f a)
226 -- >>> drain = Stream.fold Fold.drain
227 -- >>> mapM_ f = Stream.fold (Fold.drainMapM f)
228 -- >>> length = Stream.fold Fold.length
229 -- >>> head = Stream.fold Fold.one
233 -- | Stateless one-to-one transformations. Use 'fmap' for mapping a pure
234 -- function on a stream.
237 -- In imperative terms a map operation can be considered as a loop over
238 -- the stream that transforms the stream into another stream by performing
239 -- an operation on each element of the stream.
241 -- 'map' is the least powerful transformation operation with strictest
242 -- guarantees. A map, (1) is a stateless loop which means that no state is
243 -- allowed to be carried from one iteration to another, therefore,
244 -- operations on different elements are guaranteed to not affect each
245 -- other, (2) is a strictly one-to-one transformation of stream elements
246 -- which means it guarantees that no elements can be added or removed from
247 -- the stream, it can merely transform them.
255 -- | Stateful one-to-one transformations.
260 -- | We can perform scans using folds with the 'scan' combinator in the
261 -- next section. However, the combinators supplied in this section are
262 -- better amenable to stream fusion when combined with other operations.
263 -- Note that 'postscan' using folds fuses well and does not require custom
264 -- combinators like these.
271 -- ** Scanning By 'Fold'
274 -- >>> scanl' f z = Stream.scan (Fold.foldl' f z)
275 -- >>> scanlM' f z = Stream.scan (Fold.foldlM' f z)
276 -- >>> postscanl' f z = Stream.postscan (Fold.foldl' f z)
277 -- >>> postscanlM' f z = Stream.postscan (Fold.foldlM' f z)
278 -- >>> scanl1' f = Stream.catMaybes . Stream.scan (Fold.foldl1' f)
279 -- >>> scanl1M' f = Stream.catMaybes . Stream.scan (Fold.foldlM1' f)
282 -- XXX postscan1 can be implemented using Monoids or Refolds.
285 -- Indexing can be considered as a special type of zipping where we zip a
286 -- stream with an index stream.
290 -- | Add elements to the stream.
292 -- Inserting elements is a special case of interleaving/merging streams.
299 -- | Remove elements from the stream.
301 -- ** Stateless Filters
302 -- | 'mapMaybeM' is the most general stateless filtering operation. All
303 -- other filtering operations can be expressed using it.
306 -- In imperative terms a filter over a stream corresponds to a loop with a
307 -- @continue@ clause for the cases when the predicate fails.
320 -- ** Stateful Filters
321 -- | 'scanMaybe' is the most general stateful filtering operation. The
322 -- filtering folds (folds returning a 'Maybe' type) in
323 -- "Streamly.Internal.Data.Fold" can be used along with 'scanMaybe' to
324 -- perform stateful filtering operations in general.
328 -- >>> deleteBy cmp x = Stream.scanMaybe (Fold.deleteBy cmp x)
329 -- >>> findIndices p = Stream.scanMaybe (Fold.findIndices p)
330 -- >>> elemIndices a = findIndices (== a)
331 -- >>> uniq = Stream.scanMaybe (Fold.uniqBy (==))
340 -- XXX These are available as scans in folds. We need to check the
341 -- performance though. If these are common and we need convenient stream
342 -- ops then we can expose these.
352 -- Finding the presence or location of an element, a sequence of elements
353 -- or another stream within a stream.
355 -- -- ** Searching Elements
359 -- * Combining Two Streams
360 -- | Note that these operations are suitable for statically fusing a few
361 -- streams, they have a quadratic O(n^2) time complexity wrt to the number
362 -- of streams. If you want to compose many streams dynamically using binary
363 -- combining operations see the corresponding operations in
364 -- "Streamly.Data.StreamK".
366 -- When fusing more than two streams it is more efficient if the binary
367 -- operations are composed as a balanced tree rather than a right
368 -- associative or left associative one e.g.:
370 -- >>> s1 = Stream.fromList [1,2] `Stream.append` Stream.fromList [3,4]
371 -- >>> s2 = Stream.fromList [4,5] `Stream.append` Stream.fromList [6,7]
372 -- >>> s = s1 `Stream.append` s2
390 -- XXX The argument order in this operation is such that it seems we are
391 -- transforming the first stream using the second stream because the second
392 -- stream is evaluated many times or buffered and better be finite, first
393 -- stream could potentially be infinite. In the tradition of using the
394 -- transformed stream at the end we can have a flipped version called
395 -- "crossMap" or "nestWith".
399 -- , CrossStream (..)
406 -- * Stream of streams
407 -- | Stream operations like map and filter represent loop processing in
408 -- imperative programming terms. Similarly, the imperative concept of
409 -- nested loops are represented by streams of streams. The 'concatMap'
410 -- operation represents nested looping.
411 -- A 'concatMap' operation loops over the input stream and then for each
412 -- element of the input stream generates another stream and then loops over
413 -- that inner stream as well producing effects and generating a single
416 -- One dimension loops are just a special case of nested loops. For
417 -- example, 'concatMap' can degenerate to a simple map operation:
419 -- > map f m = S.concatMap (\x -> S.fromPure (f x)) m
421 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
424 -- > filter p m = S.concatMap (\x -> if p x then S.fromPure x else S.nil) m
434 -- >>> splitWithSuffix p f = Stream.foldMany (Fold.takeEndBy p f)
435 -- >>> splitOnSuffix p f = Stream.foldMany (Fold.takeEndBy_ p f)
436 -- >>> groupsBy eq f = Stream.parseMany (Parser.groupBy eq f)
437 -- >>> groupsByRolling eq f = Stream.parseMany (Parser.groupByRolling eq f)
438 -- >>> groupsOf n f = Stream.foldMany (Fold.take n f)
439 , foldMany -- XXX Rename to foldRepeat
447 -- * Buffered Operations
448 -- | Operations that require buffering of the stream.
449 -- Reverse is essentially a left fold followed by an unfold.
452 -- * Multi-Stream folds
453 -- | Operations that consume multiple streams at the same time.
459 -- trimming sequences
462 -- Exceptions and resource management depend on the "exceptions" package
463 -- XXX We can have IO Stream operations not depending on "exceptions"
467 -- | Note that the stream exception handling routines catch and handle
468 -- exceptions only in the stream generation steps and not in the consumer
469 -- of the stream. For example, if we are folding or parsing a stream - any
470 -- exceptions in the fold or parse steps won't be observed by the stream
471 -- exception handlers. Exceptions in the fold or parse steps can be handled
472 -- using the fold or parse exception handling routines. You can wrap the
473 -- stream elimination function in the monad exception handler to observe
474 -- exceptions in the stream as well as the consumer.
476 -- Most of these combinators inhibit stream fusion, therefore, when
477 -- possible, they should be called in an outer loop to mitigate the cost.
478 -- For example, instead of calling them on a stream of chars call them on a
479 -- stream of arrays before flattening it to a stream of chars.
484 -- * Resource Management
485 -- | 'bracket' is the most general resource management operation, all other
486 -- operations can be expressed using it. These functions have IO suffix
487 -- because the allocation and cleanup functions are IO actions. For
488 -- generalized allocation and cleanup functions, see the functions without
489 -- the IO suffix in the "streamly" package.
491 -- Note that these operations bracket the stream generation only, they do
492 -- not cover the stream consumer. This means if an exception occurs in
493 -- the consumer of the stream (e.g. in a fold or parse step) then the
494 -- exception won't be observed by the stream resource handlers, in that
495 -- case the resource cleanup handler runs when the stream is garbage
498 -- Monad level resource management can always be used around the stream
499 -- elimination functions, such a function can observe exceptions in both
500 -- the stream and its consumer.
507 -- * Transforming Inner Monad
514 -- XXX Arrays could be different types, therefore, this should be in
515 -- specific array module. Or maybe we should abstract over array types.
516 -- * Stream of Arrays
521import Streamly.Internal.Data.Stream
523 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
524 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
525 notElem, maximum, minimum, head, last, tail, length, null,
526 reverse, iterate, init, and, or, lookup, foldr1, (!!),
527 scanl, scanl1, repeat, replicate, concatMap, span)
529import qualified Streamly.Internal.Data.Array.Type as Array
531#include "DocTestDataStream.hs"
535-- Streamly is a framework for modular data flow based programming and
536-- declarative concurrency. Powerful stream fusion framework in streamly
537-- allows high performance combinatorial programming even when using byte level
538-- streams. Streamly API is similar to Haskell lists.
540-- == Console Echo Example
542-- In the following example, 'repeatM' generates an infinite stream of 'String'
543-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
544-- 'putStrLn' on each element in the stream converting it to stream of '()'.
545-- Finally, 'drain' folds the stream to IO discarding the () values, thus
546-- producing only effects.
548-- >>> import Data.Function ((&))
552-- Stream.repeatM getLine -- Stream IO String
553-- & Stream.mapM putStrLn -- Stream IO ()
554-- & Stream.fold Fold.drain -- IO ()
557-- This is a console echo program. It is an example of a declarative loop
558-- written using streaming combinators. Compare it with an imperative @while@
561-- Hopefully, this gives you an idea how we can program declaratively by
562-- representing loops using streams. In this module, you can find all
563-- "Data.List" like functions and many more powerful combinators to perform
564-- common programming tasks.
568-- The fused 'Stream' type in this module employs stream fusion for C-like
569-- performance when looping over data. It represents the stream as a state
570-- machine using an explicit state, and a step function working on the state. A
571-- typical stream operation consumes elements from the previous state machine
572-- in a stream pipeline, transforms the elements and yields new values for the
573-- next stage to consume. The stream operations are modular and represent a
574-- single task, they have no knowledge of previous or next operation on the
577-- A typical stream pipeline consists of a stream producer, several stream
578-- transformation operations and a stream consumer. All these operations taken
579-- together form a closed loop processing the stream elements. Elements are
580-- transferred between stages using a boxed data constructor. However, all the
581-- stages of the pipeline are fused together by GHC, eliminating the boxing of
582-- intermediate constructors, and thus forming a tight C like loop without any
583-- boxed data being used in the loop.
585-- Stream fusion works effectively when:
587-- * the stream pipeline is composed statically (known at compile time)
588-- * all the operations forming the loop are inlined
589-- * the loop is not recursively defined, recursion breaks inlining
591-- If these conditions cannot be met, the CPS style stream type 'StreamK' may
592-- turn out to be a better choice than the fused stream type 'Stream'.
594-- == Stream vs StreamK
596-- The fused stream model avoids constructor allocations and function call
597-- overheads. However, the stream is represented as a state machine, and to
598-- generate stream elements it has to navigate the decision tree of the state
599-- machine. Moreover, the state machine is cranked for each element in the
600-- stream. This performs extremely well when the number of states are limited.
601-- The state machine starts getting expensive as the number of states increase.
602-- For example, generating a stream from a list requires a single state and is
603-- very efficient, even if it has millions of elements. However, using 'cons'
604-- to construct a million element stream would be a disaster.
606-- A typical worst case scenario for fused stream model is a large number of
607-- `cons` or `append` operations. A few static `cons` or `append` operations
608-- are very fast and much faster than a CPS style stream because CPS involves a
609-- function call for each element whereas fused stream involves a few
610-- conditional branches in the state machine. However, constructing a large
611-- stream using `cons` introduces as many states in the state machine as the
612-- number of elements. If we compose `cons` as a balanced binary tree it will
613-- take @n * log n@ time to navigate the tree, and @n * n@ if it is a right
614-- associative composition.
616-- Operations like 'cons' or 'append'; are typically recursively called to
617-- construct a lazy infinite stream. For such use cases the CPS style 'StreamK'
618-- should be used. CPS streams do not have a state machine that needs to be
619-- cranked for each element, past state has no effect on the future element
620-- processing. However, CPS incurs a function call overhead for each element
621-- processed, the overhead could be large compared to a fused state machine
622-- even if it has many states. However, because of its linear performance
623-- characterstics, after a certain threshold of stream compositions the CPS
624-- stream would perform much better than the quadratic fused stream operations.
626-- As a general guideline, you need to use 'StreamK' when you have to use
627-- 'cons', 'append' or other operations having quadratic complexity at a large
628-- scale. Typically, in such cases you need to compose the stream recursively,
629-- by calling an operation in a loop. The decision to compose the stream is
630-- taken at run time rather than statically at compile time.
632-- Typically you would compose a 'StreamK' of chunks of data so that the
633-- StreamK overhead is not high, and then process the chunks using 'Stream' by
634-- using statically fused stream pipeline operations on the chunks.
636-- 'Stream' and 'StreamK' types can be interconverted. See
637-- "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