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.
222 -- >>> foldlM' f a = Stream.fold (Fold.foldlM' f a)
223 -- >>> foldl1 f = Stream.fold (Fold.foldl1' f)
224 -- >>> foldl' f a = Stream.fold (Fold.foldl' f a)
225 -- >>> drain = Stream.fold Fold.drain
226 -- >>> mapM_ f = Stream.fold (Fold.drainMapM f)
227 -- >>> length = Stream.fold Fold.length
228 -- >>> head = Stream.fold Fold.one
232 -- | Stateless one-to-one transformations. Use 'fmap' for mapping a pure
233 -- function on a stream.
236 -- In imperative terms a map operation can be considered as a loop over
237 -- the stream that transforms the stream into another stream by performing
238 -- an operation on each element of the stream.
240 -- 'map' is the least powerful transformation operation with strictest
241 -- guarantees. A map, (1) is a stateless loop which means that no state is
242 -- allowed to be carried from one iteration to another, therefore,
243 -- operations on different elements are guaranteed to not affect each
244 -- other, (2) is a strictly one-to-one transformation of stream elements
245 -- which means it guarantees that no elements can be added or removed from
246 -- the stream, it can merely transform them.
254 -- | Stateful one-to-one transformations.
256 -- See also: "Streamly.Internal.Data.Stream.Transform" for
257 -- @Pre-release@ functions.
261 -- | We can perform scans using folds with the 'scan' combinator in the
262 -- next section. However, the combinators supplied in this section are
263 -- better amenable to stream fusion when combined with other operations.
264 -- Note that 'postscan' using folds fuses well and does not require custom
265 -- combinators like these.
272 -- ** Scanning By 'Fold'
275 -- >>> scanl' f z = Stream.scan (Fold.foldl' f z)
276 -- >>> scanlM' f z = Stream.scan (Fold.foldlM' f z)
277 -- >>> postscanl' f z = Stream.postscan (Fold.foldl' f z)
278 -- >>> postscanlM' f z = Stream.postscan (Fold.foldlM' f z)
279 -- >>> scanl1' f = Stream.catMaybes . Stream.scan (Fold.foldl1' f)
280 -- >>> scanl1M' f = Stream.catMaybes . Stream.scan (Fold.foldlM1' f)
283 -- XXX postscan1 can be implemented using Monoids or Refolds.
286 -- Indexing can be considered as a special type of zipping where we zip a
287 -- stream with an index stream.
291 -- | Add elements to the stream.
293 -- Inserting elements is a special case of interleaving/merging streams.
300 -- | Remove elements from the stream.
302 -- ** Stateless Filters
303 -- | 'mapMaybeM' is the most general stateless filtering operation. All
304 -- other filtering operations can be expressed using it.
307 -- In imperative terms a filter over a stream corresponds to a loop with a
308 -- @continue@ clause for the cases when the predicate fails.
321 -- ** Stateful Filters
322 -- | 'scanMaybe' is the most general stateful filtering operation. The
323 -- filtering folds (folds returning a 'Maybe' type) in
324 -- "Streamly.Internal.Data.Fold" can be used along with 'scanMaybe' to
325 -- perform stateful filtering operations in general.
329 -- >>> deleteBy cmp x = Stream.scanMaybe (Fold.deleteBy cmp x)
330 -- >>> findIndices p = Stream.scanMaybe (Fold.findIndices p)
331 -- >>> elemIndices a = findIndices (== a)
332 -- >>> uniq = Stream.scanMaybe (Fold.uniqBy (==))
341 -- XXX These are available as scans in folds. We need to check the
342 -- performance though. If these are common and we need convenient stream
343 -- ops then we can expose these.
353 -- Finding the presence or location of an element, a sequence of elements
354 -- or another stream within a stream.
356 -- -- ** Searching Elements
360 -- * Combining Two Streams
365 -- | When interleaving more than two streams you may want to interleave
366 -- them pairwise creating a balanced binary merge tree.
370 -- | When merging more than two streams you may want to merging them
371 -- pairwise creating a balanced binary merge tree.
373 -- Merging of @n@ streams can be performed by combining the streams pair
374 -- wise using 'mergeMapWith' to give O(n * log n) time complexity. If used
375 -- with 'concatMapWith' it will have O(n^2) performance.
381 -- | When zipping more than two streams you may want to zip them
382 -- pairwise creating a balanced binary tree.
384 -- Zipping of @n@ streams can be performed by combining the streams pair
385 -- wise using 'mergeMapWith' with O(n * log n) time complexity. If used
386 -- with 'concatMapWith' it will have O(n^2) performance.
392 -- XXX The argument order in this operation is such that it seems we are
393 -- transforming the first stream using the second stream because the second
394 -- stream is evaluated many times or buffered and better be finite, first
395 -- stream could potentially be infinite. In the tradition of using the
396 -- transformed stream at the end we can have a flipped version called
397 -- "crossMap" or "nestWith".
401 -- , CrossStream (..)
408 -- * Stream of streams
409 -- | Stream operations like map and filter represent loop processing in
410 -- imperative programming terms. Similarly, the imperative concept of
411 -- nested loops are represented by streams of streams. The 'concatMap'
412 -- operation represents nested looping.
413 -- A 'concatMap' operation loops over the input stream and then for each
414 -- element of the input stream generates another stream and then loops over
415 -- that inner stream as well producing effects and generating a single
418 -- One dimension loops are just a special case of nested loops. For
419 -- example, 'concatMap' can degenerate to a simple map operation:
421 -- > map f m = S.concatMap (\x -> S.fromPure (f x)) m
423 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
426 -- > filter p m = S.concatMap (\x -> if p x then S.fromPure x else S.nil) m
436 -- >>> splitWithSuffix p f = Stream.foldMany (Fold.takeEndBy p f)
437 -- >>> splitOnSuffix p f = Stream.foldMany (Fold.takeEndBy_ p f)
438 -- >>> groupsBy eq f = Stream.parseMany (Parser.groupBy eq f)
439 -- >>> groupsByRolling eq f = Stream.parseMany (Parser.groupByRolling eq f)
440 -- >>> groupsOf n f = Stream.foldMany (Fold.take n f)
441 , foldMany -- XXX Rename to foldRepeat
449 -- * Buffered Operations
450 -- | Operations that require buffering of the stream.
451 -- Reverse is essentially a left fold followed by an unfold.
454 -- * Multi-Stream folds
455 -- | Operations that consume multiple streams at the same time.
461 -- trimming sequences
464 -- Exceptions and resource management depend on the "exceptions" package
465 -- XXX We can have IO Stream operations not depending on "exceptions"
469 -- | Most of these combinators inhibit stream fusion, therefore, when
470 -- possible, they should be called in an outer loop to mitigate the cost.
471 -- For example, instead of calling them on a stream of chars call them on a
472 -- stream of arrays before flattening it to a stream of chars.
474 -- See also: "Streamly.Internal.Data.Stream.Exception" for
475 -- @Pre-release@ functions.
480 -- * Resource Management
481 -- | 'bracket' is the most general resource management operation, all other
482 -- operations can be expressed using it. These functions have IO suffix
483 -- because the allocation and cleanup functions are IO actions. For
484 -- generalized allocation and cleanup functions see the functions without
485 -- the IO suffix in the "streamly" package.
492 -- * Transforming Inner Monad
499 -- * Stream of Arrays
505import Control.Monad.IO.Class (MonadIO)
506import Data.Word (Word8)
507import Streamly.Data.Array (Array)
508import Streamly.Internal.Data.Stream
510 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
511 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
512 notElem, maximum, minimum, head, last, tail, length, null,
513 reverse, iterate, init, and, or, lookup, foldr1, (!!),
514 scanl, scanl1, repeat, replicate, concatMap, span)
516import qualified Streamly.Internal.Data.Array.Type as Array
517import qualified Streamly.Internal.Data.Stream.Chunked as ArrayStream
519#include "DocTestDataStream.hs"
523-- Streamly is a framework for modular data flow based programming and
524-- declarative concurrency. Powerful stream fusion framework in streamly
525-- allows high performance combinatorial programming even when using byte level
526-- streams. Streamly API is similar to Haskell lists.
528-- == Console Echo Example
530-- In the following example, 'repeatM' generates an infinite stream of 'String'
531-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
532-- 'putStrLn' on each element in the stream converting it to stream of '()'.
533-- Finally, 'drain' folds the stream to IO discarding the () values, thus
534-- producing only effects.
536-- >>> import Data.Function ((&))
540-- Stream.repeatM getLine -- Stream IO String
541-- & Stream.mapM putStrLn -- Stream IO ()
542-- & Stream.fold Fold.drain -- IO ()
545-- This is a console echo program. It is an example of a declarative loop
546-- written using streaming combinators. Compare it with an imperative @while@
549-- Hopefully, this gives you an idea how we can program declaratively by
550-- representing loops using streams. In this module, you can find all
551-- "Data.List" like functions and many more powerful combinators to perform
552-- common programming tasks.
556-- The fused 'Stream' type employs stream fusion for C-like performance when
557-- looping over data. It represents a stream source or transformation by
558-- defining a state machine with explicit state, and a step function working on
559-- the state. A typical stream operation consumes elements from the previous
560-- state machine in the pipeline, transforms them and yields new values for the
561-- next stage to consume. The stream operations are modular and represent a
562-- single task, they have no knowledge of previous or next operation on the
565-- A typical stream pipeline consists of a stream producer, several stream
566-- transformation operations and a stream consumer. All these operations taken
567-- together form a closed loop processing the stream elements. Elements are
568-- transferred between stages using a boxed data constructor. However, all the
569-- stages of the pipeline are fused together by GHC, eliminating the
570-- intermediate constructors, and thus forming a tight C like loop without any
571-- boxed data being used in the loop.
573-- Stream fusion works effectively when:
575-- * the stream pipeline is composed statically (known at compile time)
576-- * all the operations forming the loop are inlined
577-- * the loop is not recursively defined, recursion breaks inlining
579-- If these conditions cannot be met, the CPS style stream type 'StreamK' may
580-- turn out to be a better choice than the fused stream type 'Stream'.
582-- == Stream vs StreamK
584-- The fused stream model avoids constructor allocations or function call
585-- overheads. However, the stream is represented as a state machine and to
586-- generate elements it has to navigate the decision tree of the state machine.
587-- Moreover, the state machine is cranked for each element in the stream. This
588-- performs extremely well when the number of states are limited. The state
589-- machine starts getting expensive as the number of states increase. For
590-- example, generating a million element stream from a list requires a single
591-- state and is very efficient. However, using fused 'cons' to generate a
592-- million element stream would be a disaster.
594-- A typical worst case scenario for fused stream model is a large number of
595-- `cons` or `append` operations. A few static `cons` or `append` operations
596-- are very fast and much faster than a CPS style stream. However, if we
597-- construct a large stream using `cons` it introduces as many states in the
598-- state machine as the number of elements. If we compose the `cons` as a
599-- binary tree it will take @n * log n@ time to navigate the tree, and @n * n@
600-- if it is a right associative composition.
602-- For quadratic cases of fused stream, after a certain threshold the CPS
603-- stream would perform much better and exhibit linear performance behavior.
604-- Operations like 'cons' or 'append'; are typically recursively called to
605-- construct a lazy infinite stream. For such use cases the CPS style 'StreamK'
606-- type is provided. CPS streams do not have a state machine that needs to be
607-- cranked for each element, past state has no effect on the future element
608-- processing. However, it incurs a function call overhead for each operation
609-- for each element, which could be very large overhead compared to fused state
610-- machines even if it has many states and cranks it for each element. But in
611-- some cases scales tip in favor of the CPS stream. In those cases even though
612-- CPS has a large constant overhead, it has a linear performance rather than
615-- As a general guideline, if you have to use 'cons' or 'append' or operations
616-- of similar nature, at a large scale, then 'StreamK' should be used. When you
617-- need to compose the stream dynamically or recursively, then 'StreamK' should
618-- be used. Typically you would use a dynamically generated 'StreamK' with
619-- chunks of data which can then be processed by statically fused stream
620-- pipeline operations.
622-- 'Stream' and 'StreamK' types can be interconverted. See
623-- "Streamly.Data.StreamK" module for conversion operations.
625-- | Split a stream of arrays on a given separator byte, dropping the separator
626-- and coalescing all the arrays between two separators into a single array.
628{-# INLINE chunksSplitOn #-}
632 -> Stream m (Array Word8)
633 -> Stream m (Array Word8)
634chunksSplitOn = ArrayStream.splitOn
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