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.StreamD.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.StreamD.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.StreamD.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 -- | Note that the stream exception handling routines catch and handle
470 -- exceptions only in the stream generation steps and not in the consumer
471 -- of the stream. For example, if we are folding or parsing a stream - any
472 -- exceptions in the fold or parse steps won't be observed by the stream
473 -- exception handlers. Exceptions in the fold or parse steps can be handled
474 -- using the fold or parse exception handling routines. You can wrap the
475 -- stream elimination function in the monad exception handler to observe
476 -- exceptions in the stream as well as the consumer.
478 -- Most of these combinators inhibit stream fusion, therefore, when
479 -- possible, they should be called in an outer loop to mitigate the cost.
480 -- For example, instead of calling them on a stream of chars call them on a
481 -- stream of arrays before flattening it to a stream of chars.
483 -- See also: "Streamly.Internal.Data.Stream.StreamD.Exception" for
484 -- @Pre-release@ functions.
489 -- * Resource Management
490 -- | 'bracket' is the most general resource management operation, all other
491 -- operations can be expressed using it. These functions have IO suffix
492 -- because the allocation and cleanup functions are IO actions. For
493 -- generalized allocation and cleanup functions, see the functions without
494 -- the IO suffix in the "streamly" package.
496 -- Note that these operations bracket the stream generation only, they do
497 -- not cover the stream consumer. This means if an exception occurs in
498 -- the consumer of the stream (e.g. in a fold or parse step) then the
499 -- exception won't be observed by the stream resource handlers, in that
500 -- case the resource cleanup handler runs when the stream is garbage
503 -- Monad level resource management can always be used around the stream
504 -- elimination functions, such a function can observe exceptions in both
505 -- the stream and its consumer.
512 -- * Transforming Inner Monad
519 -- * Stream of Arrays
525import Control.Monad.IO.Class (MonadIO)
526import Data.Word (Word8)
527import Streamly.Data.Array (Array)
528import Streamly.Internal.Data.Stream
530 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
531 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
532 notElem, maximum, minimum, head, last, tail, length, null,
533 reverse, iterate, init, and, or, lookup, foldr1, (!!),
534 scanl, scanl1, repeat, replicate, concatMap, span)
536import qualified Streamly.Internal.Data.Array.Type as Array
537import qualified Streamly.Internal.Data.Stream.Chunked as ArrayStream
539#include "DocTestDataStream.hs"
543-- Streamly is a framework for modular data flow based programming and
544-- declarative concurrency. Powerful stream fusion framework in streamly
545-- allows high performance combinatorial programming even when using byte level
546-- streams. Streamly API is similar to Haskell lists.
548-- == Console Echo Example
550-- In the following example, 'repeatM' generates an infinite stream of 'String'
551-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
552-- 'putStrLn' on each element in the stream converting it to stream of '()'.
553-- Finally, 'drain' folds the stream to IO discarding the () values, thus
554-- producing only effects.
556-- >>> import Data.Function ((&))
560-- Stream.repeatM getLine -- Stream IO String
561-- & Stream.mapM putStrLn -- Stream IO ()
562-- & Stream.fold Fold.drain -- IO ()
565-- This is a console echo program. It is an example of a declarative loop
566-- written using streaming combinators. Compare it with an imperative @while@
569-- Hopefully, this gives you an idea how we can program declaratively by
570-- representing loops using streams. In this module, you can find all
571-- "Data.List" like functions and many more powerful combinators to perform
572-- common programming tasks.
576-- The fused 'Stream' type employs stream fusion for C-like performance when
577-- looping over data. It represents a stream source or transformation by
578-- defining a state machine with explicit state, and a step function working on
579-- the state. A typical stream operation consumes elements from the previous
580-- state machine in the pipeline, transforms them and yields new values for the
581-- next stage to consume. The stream operations are modular and represent a
582-- single task, they have no knowledge of previous or next operation on the
585-- A typical stream pipeline consists of a stream producer, several stream
586-- transformation operations and a stream consumer. All these operations taken
587-- together form a closed loop processing the stream elements. Elements are
588-- transferred between stages using a boxed data constructor. However, all the
589-- stages of the pipeline are fused together by GHC, eliminating the
590-- intermediate constructors, and thus forming a tight C like loop without any
591-- boxed data being used in the loop.
593-- Stream fusion works effectively when:
595-- * the stream pipeline is composed statically (known at compile time)
596-- * all the operations forming the loop are inlined
597-- * the loop is not recursively defined, recursion breaks inlining
599-- If these conditions cannot be met, the CPS style stream type 'StreamK' may
600-- turn out to be a better choice than the fused stream type 'Stream'.
602-- == Stream vs StreamK
604-- The fused stream model avoids constructor allocations or function call
605-- overheads. However, the stream is represented as a state machine and to
606-- generate elements it has to navigate the decision tree of the state machine.
607-- Moreover, the state machine is cranked for each element in the stream. This
608-- performs extremely well when the number of states are limited. The state
609-- machine starts getting expensive as the number of states increase. For
610-- example, generating a million element stream from a list requires a single
611-- state and is very efficient. However, using fused 'cons' to generate a
612-- million element stream would be a disaster.
614-- A typical worst case scenario for fused stream model is a large number of
615-- `cons` or `append` operations. A few static `cons` or `append` operations
616-- are very fast and much faster than a CPS style stream. However, if we
617-- construct a large stream using `cons` it introduces as many states in the
618-- state machine as the number of elements. If we compose the `cons` as a
619-- binary tree it will take @n * log n@ time to navigate the tree, and @n * n@
620-- if it is a right associative composition.
622-- For quadratic cases of fused stream, after a certain threshold the CPS
623-- stream would perform much better and exhibit linear performance behavior.
624-- Operations like 'cons' or 'append'; are typically recursively called to
625-- construct a lazy infinite stream. For such use cases the CPS style 'StreamK'
626-- type is provided. CPS streams do not have a state machine that needs to be
627-- cranked for each element, past state has no effect on the future element
628-- processing. However, it incurs a function call overhead for each operation
629-- for each element, which could be very large overhead compared to fused state
630-- machines even if it has many states and cranks it for each element. But in
631-- some cases scales tip in favor of the CPS stream. In those cases even though
632-- CPS has a large constant overhead, it has a linear performance rather than
635-- As a general guideline, if you have to use 'cons' or 'append' or operations
636-- of similar nature, at a large scale, then 'StreamK' should be used. When you
637-- need to compose the stream dynamically or recursively, then 'StreamK' should
638-- be used. Typically you would use a dynamically generated 'StreamK' with
639-- chunks of data which can then be processed by statically fused stream
640-- pipeline operations.
642-- 'Stream' and 'StreamK' types can be interconverted. See
643-- "Streamly.Data.StreamK" module for conversion operations.
645-- | Split a stream of arrays on a given separator byte, dropping the separator
646-- and coalescing all the arrays between two separators into a single array.
648{-# INLINE chunksSplitOn #-}
652 -> Stream m (Array Word8)
653 -> Stream m (Array Word8)
654chunksSplitOn = 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