2-- Module : Streamly.Data.Stream
3-- Copyright : (c) 2017 Composewell Technologies
6-- Maintainer : streamly@composewell.com
10-- To run examples in this module:
12-- >>> import qualified Streamly.Data.Fold as Fold
13-- >>> import qualified Streamly.Data.Stream as Stream
15-- We will add some more imports in the examples as needed.
17-- For effectful streams we will use the following IO action:
19-- >>> effect n = print n >> return n
23-- Streamly is a framework for modular data flow based programming and
24-- declarative concurrency. Powerful stream fusion framework in streamly
25-- allows high performance combinatorial programming even when using byte level
26-- streams. Streamly API is similar to Haskell lists.
28-- == Console Echo Example
30-- In the following example, 'repeatM' generates an infinite stream of 'String'
31-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
32-- 'putStrLn' on each element in the stream converting it to stream of '()'.
33-- Finally, 'drain' folds the stream to IO discarding the () values, thus
34-- producing only effects.
36-- >>> import Data.Function ((&))
40-- Stream.repeatM getLine -- Stream IO String
41-- & Stream.mapM putStrLn -- Stream IO ()
42-- & Stream.fold Fold.drain -- IO ()
45-- This is a console echo program. It is an example of a declarative loop
46-- written using streaming combinators. Compare it with an imperative @while@
49-- Hopefully, this gives you an idea how we can program declaratively by
50-- representing loops using streams. In this module, you can find all
51-- "Data.List" like functions and many more powerful combinators to perform
52-- common programming tasks.
54-- == Performance Notes
56-- The 'Stream' type represents a stream by composing state as data which
57-- enables stream fusion. Stream fusion generates a tight loop without any
58-- constructor allocations between the stages, providing C like performance for
59-- the loop. Stream fusion works when multiple functions are combined in a
60-- pipeline statically. Therefore, the operations in this module must be
61-- inlined and must not be used recursively to allow for stream fusion.
63-- Using the 'Stream' type binary stream construction operations like 'cons',
64-- 'append' etc. degrade quadratically (O(n^2)) when combined many times. If
65-- you need to combine these operations, say more than 50 times in a single
66-- loop, then you should use the continuation style stream type 'StreamK'
67-- instead. Also, if you need to use these operations in a recursive loop you
68-- should use 'StreamK' instead.
70-- The 'StreamK' type represents a stream by composing function calls,
71-- therefore, a function call overhead is incurred at each composition. It is
72-- quite fast in general but may be a few times slower than a fused stream.
73-- However, it allows for scalable dynamic composition and control flow
74-- manipulation. Using the 'StreamK' type binary operations like 'cons' and
75-- 'append' provide linear (O(n)) performance.
77-- 'Stream' and 'StreamK' types can be interconverted.
81-- >>> fromListM = Stream.sequence . Stream.fromList
82-- >>> fromIndices f = fmap f $ Stream.enumerateFrom 0
84-- Also see "Streamly.Internal.Data.Stream" module for many more @Pre-release@
85-- combinators. See the <https://github.com/composewell/streamly-examples>
86-- repository for many more real world examples of stream programming.
88module Streamly.Data.Stream
92 -- | Functions ending in the general shape @b -> Stream m a@.
94 -- See also: "Streamly.Internal.Data.Stream.Generate" for
95 -- @Pre-release@ functions.
98 -- | Primitives to construct a stream from pure values or monadic actions.
99 -- All other stream construction and generation combinators described later
100 -- can be expressed in terms of these primitives. However, the special
101 -- versions provided in this module can be much more efficient in most
102 -- cases. Users can create custom combinators using these primitives.
109 -- | 'unfoldrM' is the most general way of generating a stream efficiently.
110 -- All other generation operations can be expressed using it.
115 -- | Generate a monadic stream from a seed value or values.
123 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
124 -- to be slightly faster than the idioms like @[from, then..]@.
127 -- | We can use the 'Enum' type class to enumerate a type producing a list
128 -- and then convert it to a stream:
131 -- 'fromList' $ 'Prelude.enumFromThen' from then
134 -- However, this is not particularly efficient.
135 -- The 'Enumerable' type class provides corresponding functions that
136 -- generate a stream instead of a list, efficiently.
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.
152 -- | Most of the above stream generation operations can also be expressed
153 -- using the corresponding unfolds in the "Streamly.Data.Unfold" module.
154 , unfold -- XXX rename to fromUnfold?
157 -- | Functions ending in the general shape @Stream m a -> m b@ or @Stream m
158 -- a -> m (b, Stream m a)@
160 -- See also: "Streamly.Internal.Data.Stream.Eliminate" for @Pre-release@
163-- EXPLANATION: In imperative terms a fold can be considered as a loop over the stream
164-- that reduces the stream to a single value.
165-- Left and right folds both use a fold function @f@ and an identity element
166-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
167-- new data structure. The new structure may be a recursive construction (a
168-- container) or a non-recursive single value reduction of the original
171-- Both right and left folds are mathematical duals of each other, they are
172-- functionally equivalent. Operationally, a left fold on a left associated
173-- structure behaves exactly in the same way as a right fold on a right
174-- associated structure. Similarly, a left fold on a right associated structure
175-- behaves in the same way as a right fold on a left associated structure.
176-- However, the behavior of a right fold on a right associated structure is
177-- operationally different (even though functionally equivalent) than a left
178-- fold on the same structure.
180-- On right associated structures like Haskell @cons@ lists or Streamly
181-- streams, a lazy right fold is naturally suitable for lazy recursive
182-- reconstruction of a new structure, while a strict left fold is naturally
183-- suitable for efficient reduction. In right folds control is in the hand of
184-- the @puller@ whereas in left folds the control is in the hand of the
187-- The behavior of right and left folds are described in detail in the
188-- individual fold's documentation. To illustrate the two folds for right
189-- associated @cons@ lists:
191-- > foldr :: (a -> b -> b) -> b -> [a] -> b
193-- > foldr f z (x:xs) = x `f` foldr f z xs
195-- > foldl :: (b -> a -> b) -> b -> [a] -> b
197-- > foldl f z (x:xs) = foldl f (z `f` x) xs
199-- @foldr@ is conceptually equivalent to:
202-- > foldr f z [x] = f x z
203-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
205-- @foldl@ is conceptually equivalent to:
208-- > foldl f z [x] = f z x
209-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
211-- Left and right folds are duals of each other.
214-- foldr f z xs = foldl (flip f) z (reverse xs)
215-- foldl f z xs = foldr (flip f) z (reverse xs)
221-- foldr f z xs = foldl g id xs z where g k x = k . f x
222-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
226-- NOTE: Folds are inherently serial as each step needs to use the result of
227-- the previous step. However, it is possible to fold parts of the stream in
228-- parallel and then combine the results using a monoid.
231 -- Consuming a part of the stream and returning the rest. Functions
232 -- ending in the general shape @Stream m a -> m (b, Stream m a)@
235 -- ** Strict Left Folds
236 -- XXX Need to have a general parse operation here which can be used to
237 -- express all others.
238 , fold -- XXX rename to run? We can have a Stream.run and Fold.run.
239 -- XXX fold1 can be achieved using Monoids or Refolds.
240 -- XXX We can call this just "break" and parseBreak as "munch"
243 -- XXX should we have a Fold returning function in stream module?
251 -- ** Lazy Right Folds
252 -- | Consuming a stream to build a right associated expression, suitable
253 -- for lazy evaluation. Evaluation of the input happens when the output of
254 -- the fold is evaluated, the fold output is a lazy thunk.
256 -- This is suitable for stream transformation operations, for example,
257 -- operations like mapping a function over the stream.
262 -- | Usually you can use the folds in "Streamly.Data.Fold". However, some
263 -- folds that may be commonly used or may have an edge in performance in
264 -- some cases are provided here.
269 -- | Stateless one-to-one transformations. Use 'fmap' for mapping a pure
270 -- function on a stream.
273 -- In imperative terms a map operation can be considered as a loop over
274 -- the stream that transforms the stream into another stream by performing
275 -- an operation on each element of the stream.
277 -- 'map' is the least powerful transformation operation with strictest
278 -- guarantees. A map, (1) is a stateless loop which means that no state is
279 -- allowed to be carried from one iteration to another, therefore,
280 -- operations on different elements are guaranteed to not affect each
281 -- other, (2) is a strictly one-to-one transformation of stream elements
282 -- which means it guarantees that no elements can be added or removed from
283 -- the stream, it can merely transform them.
291 -- | Stateful one-to-one transformations.
293 -- See also: "Streamly.Internal.Data.Stream.Transform" for
294 -- @Pre-release@ functions.
298 -- | We can perform scans using folds with the 'scan' combinator in the
299 -- next section. However, the combinators supplied in this section are
300 -- better amenable to stream fusion when combined with other operations.
301 -- Note that 'postscan' using folds fuses well and does not require custom
302 -- combinators like these.
309 -- ** Scanning By 'Fold'
312 -- XXX postscan1 can be implemented using Monoids or Refolds.
315 -- Indexing can be considered as a special type of zipping where we zip a
316 -- stream with an index stream.
320 -- | Add elements to the stream.
322 -- Inserting elements is a special case of interleaving/merging streams.
329 -- | Remove elements from the stream.
331 -- ** Stateless Filters
332 -- | 'mapMaybeM' is the most general stateless filtering operation. All
333 -- other filtering operations can be expressed using it.
336 -- In imperative terms a filter over a stream corresponds to a loop with a
337 -- @continue@ clause for the cases when the predicate fails.
350 -- ** Stateful Filters
351 -- | 'scanMaybe' is the most general stateful filtering operation. The
352 -- filtering folds (folds returning a 'Maybe' type) in
353 -- "Streamly.Internal.Data.Fold" can be used along with 'scanMaybe' to
354 -- perform stateful filtering operations in general.
363 -- XXX These are available as scans in folds. We need to check the
364 -- performance though. If these are common and we need convenient stream
365 -- ops then we can expose these.
375 -- Finding the presence or location of an element, a sequence of elements
376 -- or another stream within a stream.
378 -- -- ** Searching Elements
382 -- * Combining Two Streams
387 -- | When interleaving more than two streams you may want to interleave
388 -- them pairwise creating a balanced binary merge tree.
392 -- | When merging more than two streams you may want to merging them
393 -- pairwise creating a balanced binary merge tree.
395 -- Merging of @n@ streams can be performed by combining the streams pair
396 -- wise using 'mergeMapWith' to give O(n * log n) time complexity. If used
397 -- with 'concatMapWith' it will have O(n^2) performance.
403 -- | When zipping more than two streams you may want to zip them
404 -- pairwise creating a balanced binary tree.
406 -- Zipping of @n@ streams can be performed by combining the streams pair
407 -- wise using 'mergeMapWith' with O(n * log n) time complexity. If used
408 -- with 'concatMapWith' it will have O(n^2) performance.
414 -- XXX The argument order in this operation is such that it seems we are
415 -- transforming the first stream using the second stream because the second
416 -- stream is evaluated many times or buffered and better be finite, first
417 -- stream could potentially be infinite. In the tradition of using the
418 -- transformed stream at the end we can have a flipped version called
419 -- "crossMap" or "nestWith".
423 -- , CrossStream (..)
430 -- * Stream of streams
431 -- | Stream operations like map and filter represent loop processing in
432 -- imperative programming terms. Similarly, the imperative concept of
433 -- nested loops are represented by streams of streams. The 'concatMap'
434 -- operation represents nested looping.
435 -- A 'concatMap' operation loops over the input stream and then for each
436 -- element of the input stream generates another stream and then loops over
437 -- that inner stream as well producing effects and generating a single
440 -- One dimension loops are just a special case of nested loops. For
441 -- example, 'concatMap' can degenerate to a simple map operation:
443 -- > map f m = S.concatMap (\x -> S.fromPure (f x)) m
445 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
448 -- > filter p m = S.concatMap (\x -> if p x then S.fromPure x else S.nil) m
456 , foldMany -- XXX Rename to foldRepeat
460 -- * Buffered Operations
461 -- | Operations that require buffering of the stream.
462 -- Reverse is essentially a left fold followed by an unfold.
465 -- * Multi-Stream folds
466 -- | Operations that consume multiple streams at the same time.
472 -- trimming sequences
475 -- Exceptions and resource management depend on the "exceptions" package
476 -- XXX We can have IO Stream operations not depending on "exceptions"
480 -- | Most of these combinators inhibit stream fusion, therefore, when
481 -- possible, they should be called in an outer loop to mitigate the cost.
482 -- For example, instead of calling them on a stream of chars call them on a
483 -- stream of arrays before flattening it to a stream of chars.
485 -- See also: "Streamly.Internal.Data.Stream.Exception" for
486 -- @Pre-release@ functions.
491 -- * Resource Management
492 -- | 'bracket' is the most general resource management operation, all other
493 -- operations can be expressed using it. These functions have IO suffix
494 -- because the allocation and cleanup functions are IO actions. For
495 -- generalized allocation and cleanup functions see the functions without
496 -- the IO suffix in the "streamly" package.
503 -- * Transforming Inner Monad
517import qualified Streamly.Internal.Data.Array.Type as Array
518import Streamly.Internal.Data.Stream.StreamD
520 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
521 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
522 notElem, maximum, minimum, head, last, tail, length, null,
523 reverse, iterate, init, and, or, lookup, foldr1, (!!),
524 scanl, scanl1, repeat, replicate, concatMap, span)
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