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@.
45 -- See also: "Streamly.Internal.Data.Stream.StreamD.Generate" for
46 -- @Pre-release@ functions.
50 -- >>> fromIndices f = fmap f $ Stream.enumerateFrom 0
51 -- >>> fromIndicesM f = Stream.mapM f $ Stream.enumerateFrom 0
52 -- >>> fromListM = Stream.sequence . Stream.fromList
53 -- >>> fromFoldable = StreamK.toStream . StreamK.fromFoldable
54 -- >>> fromFoldableM = Stream.sequence . fromFoldable
57 -- | A fused 'Stream' is never constructed using these primitives, they are
58 -- typically generated by converting containers like list into streams, or
59 -- generated using custom functions provided in this module. The 'cons'
60 -- primitive in this module has a rare use in fusing a small number of
61 -- elements. On the other hand, it is common to construct 'StreamK' stream
62 -- using the StreamK.'StreamK.cons' primitive.
69 -- | 'unfoldrM' is the most general way of generating a stream efficiently.
70 -- All other generation operations can be expressed using it.
75 -- | Generate a monadic stream from a seed value or values.
83 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
84 -- to be slightly faster than the idioms like @[from, then..]@.
87 -- | We can use the 'Enum' type class to enumerate a type producing a list
88 -- and then convert it to a stream:
91 -- 'fromList' $ 'Prelude.enumFromThen' from then
94 -- However, this is not particularly efficient.
95 -- The 'Enumerable' type class provides corresponding functions that
96 -- generate a stream instead of a list, efficiently.
106 -- ** From Containers
107 -- | Convert an input structure, container or source into a stream. All of
108 -- these can be expressed in terms of primitives.
112 -- | Most of the above stream generation operations can also be expressed
113 -- using the corresponding unfolds in the "Streamly.Data.Unfold" module.
114 , unfold -- XXX rename to fromUnfold?
117 -- | Functions ending in the general shape @Stream m a -> m b@ or @Stream m
118 -- a -> m (b, Stream m a)@
120 -- See also: "Streamly.Internal.Data.Stream.StreamD.Eliminate" for @Pre-release@
123-- EXPLANATION: In imperative terms a fold can be considered as a loop over the stream
124-- that reduces the stream to a single value.
125-- Left and right folds both use a fold function @f@ and an identity element
126-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
127-- new data structure. The new structure may be a recursive construction (a
128-- container) or a non-recursive single value reduction of the original
131-- Both right and left folds are mathematical duals of each other, they are
132-- functionally equivalent. Operationally, a left fold on a left associated
133-- structure behaves exactly in the same way as a right fold on a right
134-- associated structure. Similarly, a left fold on a right associated structure
135-- behaves in the same way as a right fold on a left associated structure.
136-- However, the behavior of a right fold on a right associated structure is
137-- operationally different (even though functionally equivalent) than a left
138-- fold on the same structure.
140-- On right associated structures like Haskell @cons@ lists or Streamly
141-- streams, a lazy right fold is naturally suitable for lazy recursive
142-- reconstruction of a new structure, while a strict left fold is naturally
143-- suitable for efficient reduction. In right folds control is in the hand of
144-- the @puller@ whereas in left folds the control is in the hand of the
147-- The behavior of right and left folds are described in detail in the
148-- individual fold's documentation. To illustrate the two folds for right
149-- associated @cons@ lists:
151-- > foldr :: (a -> b -> b) -> b -> [a] -> b
153-- > foldr f z (x:xs) = x `f` foldr f z xs
155-- > foldl :: (b -> a -> b) -> b -> [a] -> b
157-- > foldl f z (x:xs) = foldl f (z `f` x) xs
159-- @foldr@ is conceptually equivalent to:
162-- > foldr f z [x] = f x z
163-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
165-- @foldl@ is conceptually equivalent to:
168-- > foldl f z [x] = f z x
169-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
171-- Left and right folds are duals of each other.
174-- foldr f z xs = foldl (flip f) z (reverse xs)
175-- foldl f z xs = foldr (flip f) z (reverse xs)
181-- foldr f z xs = foldl g id xs z where g k x = k . f x
182-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
186-- NOTE: Folds are inherently serial as each step needs to use the result of
187-- the previous step. However, it is possible to fold parts of the stream in
188-- parallel and then combine the results using a monoid.
191 -- Consuming a part of the stream and returning the rest. Functions
192 -- ending in the general shape @Stream m a -> m (b, Stream m a)@
195 -- ** Strict Left Folds
196 -- XXX Need to have a general parse operation here which can be used to
197 -- express all others.
198 , fold -- XXX rename to run? We can have a Stream.run and Fold.run.
199 -- XXX fold1 can be achieved using Monoids or Refolds.
200 -- XXX We can call this just "break" and parseBreak as "munch"
203 -- XXX should we have a Fold returning function in stream module?
211 -- ** Lazy Right Folds
212 -- | Consuming a stream to build a right associated expression, suitable
213 -- for lazy evaluation. Evaluation of the input happens when the output of
214 -- the fold is evaluated, the fold output is a lazy thunk.
216 -- This is suitable for stream transformation operations, for example,
217 -- operations like mapping a function over the stream.
222 -- | Usually you can use the folds in "Streamly.Data.Fold". However, some
223 -- folds that may be commonly used or may have an edge in performance in
224 -- some cases are provided here.
228 -- >>> foldlM' f a = Stream.fold (Fold.foldlM' f a)
229 -- >>> foldl1 f = Stream.fold (Fold.foldl1' f)
230 -- >>> foldl' f a = Stream.fold (Fold.foldl' f a)
231 -- >>> drain = Stream.fold Fold.drain
232 -- >>> mapM_ f = Stream.fold (Fold.drainMapM f)
233 -- >>> length = Stream.fold Fold.length
234 -- >>> head = Stream.fold Fold.one
238 -- | Stateless one-to-one transformations. Use 'fmap' for mapping a pure
239 -- function on a stream.
242 -- In imperative terms a map operation can be considered as a loop over
243 -- the stream that transforms the stream into another stream by performing
244 -- an operation on each element of the stream.
246 -- 'map' is the least powerful transformation operation with strictest
247 -- guarantees. A map, (1) is a stateless loop which means that no state is
248 -- allowed to be carried from one iteration to another, therefore,
249 -- operations on different elements are guaranteed to not affect each
250 -- other, (2) is a strictly one-to-one transformation of stream elements
251 -- which means it guarantees that no elements can be added or removed from
252 -- the stream, it can merely transform them.
260 -- | Stateful one-to-one transformations.
262 -- See also: "Streamly.Internal.Data.Stream.StreamD.Transform" for
263 -- @Pre-release@ functions.
267 -- | We can perform scans using folds with the 'scan' combinator in the
268 -- next section. However, the combinators supplied in this section are
269 -- better amenable to stream fusion when combined with other operations.
270 -- Note that 'postscan' using folds fuses well and does not require custom
271 -- combinators like these.
278 -- ** Scanning By 'Fold'
281 -- >>> scanl' f z = Stream.scan (Fold.foldl' f z)
282 -- >>> scanlM' f z = Stream.scan (Fold.foldlM' f z)
283 -- >>> postscanl' f z = Stream.postscan (Fold.foldl' f z)
284 -- >>> postscanlM' f z = Stream.postscan (Fold.foldlM' f z)
285 -- >>> scanl1' f = Stream.catMaybes . Stream.scan (Fold.foldl1' f)
286 -- >>> scanl1M' f = Stream.catMaybes . Stream.scan (Fold.foldlM1' f)
289 -- XXX postscan1 can be implemented using Monoids or Refolds.
292 -- Indexing can be considered as a special type of zipping where we zip a
293 -- stream with an index stream.
297 -- | Add elements to the stream.
299 -- Inserting elements is a special case of interleaving/merging streams.
306 -- | Remove elements from the stream.
308 -- ** Stateless Filters
309 -- | 'mapMaybeM' is the most general stateless filtering operation. All
310 -- other filtering operations can be expressed using it.
313 -- In imperative terms a filter over a stream corresponds to a loop with a
314 -- @continue@ clause for the cases when the predicate fails.
327 -- ** Stateful Filters
328 -- | 'scanMaybe' is the most general stateful filtering operation. The
329 -- filtering folds (folds returning a 'Maybe' type) in
330 -- "Streamly.Internal.Data.Fold" can be used along with 'scanMaybe' to
331 -- perform stateful filtering operations in general.
335 -- >>> deleteBy cmp x = Stream.scanMaybe (Fold.deleteBy cmp x)
336 -- >>> findIndices p = Stream.scanMaybe (Fold.findIndices p)
337 -- >>> elemIndices a = findIndices (== a)
338 -- >>> uniq = Stream.scanMaybe (Fold.uniqBy (==))
347 -- XXX These are available as scans in folds. We need to check the
348 -- performance though. If these are common and we need convenient stream
349 -- ops then we can expose these.
359 -- Finding the presence or location of an element, a sequence of elements
360 -- or another stream within a stream.
362 -- -- ** Searching Elements
366 -- * Combining Two Streams
367 -- | Note that these operations are suitable for statically fusing a few
368 -- streams, they have a quadratic O(n^2) time complexity wrt to the number
369 -- of streams. If you want to compose many streams dynamically using binary
370 -- combining operations see the corresponding operations in
371 -- "Streamly.Data.StreamK".
373 -- When fusing more than two streams it is more efficient if the binary
374 -- operations are composed as a balanced tree rather than a right
375 -- associative or left associative one e.g.:
377 -- >>> s1 = Stream.fromList [1,2] `Stream.append` Stream.fromList [3,4]
378 -- >>> s2 = Stream.fromList [4,5] `Stream.append` Stream.fromList [6,7]
379 -- >>> s = s1 `Stream.append` s2
397 -- XXX The argument order in this operation is such that it seems we are
398 -- transforming the first stream using the second stream because the second
399 -- stream is evaluated many times or buffered and better be finite, first
400 -- stream could potentially be infinite. In the tradition of using the
401 -- transformed stream at the end we can have a flipped version called
402 -- "crossMap" or "nestWith".
406 -- , CrossStream (..)
413 -- * Stream of streams
414 -- | Stream operations like map and filter represent loop processing in
415 -- imperative programming terms. Similarly, the imperative concept of
416 -- nested loops are represented by streams of streams. The 'concatMap'
417 -- operation represents nested looping.
418 -- A 'concatMap' operation loops over the input stream and then for each
419 -- element of the input stream generates another stream and then loops over
420 -- that inner stream as well producing effects and generating a single
423 -- One dimension loops are just a special case of nested loops. For
424 -- example, 'concatMap' can degenerate to a simple map operation:
426 -- > map f m = S.concatMap (\x -> S.fromPure (f x)) m
428 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
431 -- > filter p m = S.concatMap (\x -> if p x then S.fromPure x else S.nil) m
441 -- >>> splitWithSuffix p f = Stream.foldMany (Fold.takeEndBy p f)
442 -- >>> splitOnSuffix p f = Stream.foldMany (Fold.takeEndBy_ p f)
443 -- >>> groupsBy eq f = Stream.parseMany (Parser.groupBy eq f)
444 -- >>> groupsByRolling eq f = Stream.parseMany (Parser.groupByRolling eq f)
445 -- >>> groupsOf n f = Stream.foldMany (Fold.take n f)
446 , foldMany -- XXX Rename to foldRepeat
454 -- * Buffered Operations
455 -- | Operations that require buffering of the stream.
456 -- Reverse is essentially a left fold followed by an unfold.
459 -- * Multi-Stream folds
460 -- | Operations that consume multiple streams at the same time.
466 -- trimming sequences
469 -- Exceptions and resource management depend on the "exceptions" package
470 -- XXX We can have IO Stream operations not depending on "exceptions"
474 -- | Note that the stream exception handling routines catch and handle
475 -- exceptions only in the stream generation steps and not in the consumer
476 -- of the stream. For example, if we are folding or parsing a stream - any
477 -- exceptions in the fold or parse steps won't be observed by the stream
478 -- exception handlers. Exceptions in the fold or parse steps can be handled
479 -- using the fold or parse exception handling routines. You can wrap the
480 -- stream elimination function in the monad exception handler to observe
481 -- exceptions in the stream as well as the consumer.
483 -- Most of these combinators inhibit stream fusion, therefore, when
484 -- possible, they should be called in an outer loop to mitigate the cost.
485 -- For example, instead of calling them on a stream of chars call them on a
486 -- stream of arrays before flattening it to a stream of chars.
488 -- See also: "Streamly.Internal.Data.Stream.StreamD.Exception" for
489 -- @Pre-release@ functions.
494 -- * Resource Management
495 -- | 'bracket' is the most general resource management operation, all other
496 -- operations can be expressed using it. These functions have IO suffix
497 -- because the allocation and cleanup functions are IO actions. For
498 -- generalized allocation and cleanup functions, see the functions without
499 -- the IO suffix in the "streamly" package.
501 -- Note that these operations bracket the stream generation only, they do
502 -- not cover the stream consumer. This means if an exception occurs in
503 -- the consumer of the stream (e.g. in a fold or parse step) then the
504 -- exception won't be observed by the stream resource handlers, in that
505 -- case the resource cleanup handler runs when the stream is garbage
508 -- Monad level resource management can always be used around the stream
509 -- elimination functions, such a function can observe exceptions in both
510 -- the stream and its consumer.
517 -- * Transforming Inner Monad
524 -- * Stream of Arrays
530import Control.Monad.IO.Class (MonadIO)
531import Data.Word (Word8)
532import Streamly.Data.Array (Array)
533import Streamly.Internal.Data.Stream
535 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
536 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
537 notElem, maximum, minimum, head, last, tail, length, null,
538 reverse, iterate, init, and, or, lookup, foldr1, (!!),
539 scanl, scanl1, repeat, replicate, concatMap, span)
541import qualified Streamly.Internal.Data.Array.Type as Array
542import qualified Streamly.Internal.Data.Stream.Chunked as ArrayStream
544#include "DocTestDataStream.hs"
548-- Streamly is a framework for modular data flow based programming and
549-- declarative concurrency. Powerful stream fusion framework in streamly
550-- allows high performance combinatorial programming even when using byte level
551-- streams. Streamly API is similar to Haskell lists.
553-- == Console Echo Example
555-- In the following example, 'repeatM' generates an infinite stream of 'String'
556-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
557-- 'putStrLn' on each element in the stream converting it to stream of '()'.
558-- Finally, 'drain' folds the stream to IO discarding the () values, thus
559-- producing only effects.
561-- >>> import Data.Function ((&))
565-- Stream.repeatM getLine -- Stream IO String
566-- & Stream.mapM putStrLn -- Stream IO ()
567-- & Stream.fold Fold.drain -- IO ()
570-- This is a console echo program. It is an example of a declarative loop
571-- written using streaming combinators. Compare it with an imperative @while@
574-- Hopefully, this gives you an idea how we can program declaratively by
575-- representing loops using streams. In this module, you can find all
576-- "Data.List" like functions and many more powerful combinators to perform
577-- common programming tasks.
581-- The fused 'Stream' type in this module employs stream fusion for C-like
582-- performance when looping over data. It represents the stream as a state
583-- machine using an explicit state, and a step function working on the state. A
584-- typical stream operation consumes elements from the previous state machine
585-- in a stream pipeline, transforms the elements and yields new values for the
586-- next stage to consume. The stream operations are modular and represent a
587-- single task, they have no knowledge of previous or next operation on the
590-- A typical stream pipeline consists of a stream producer, several stream
591-- transformation operations and a stream consumer. All these operations taken
592-- together form a closed loop processing the stream elements. Elements are
593-- transferred between stages using a boxed data constructor. However, all the
594-- stages of the pipeline are fused together by GHC, eliminating the boxing of
595-- intermediate constructors, and thus forming a tight C like loop without any
596-- boxed data being used in the loop.
598-- Stream fusion works effectively when:
600-- * the stream pipeline is composed statically (known at compile time)
601-- * all the operations forming the loop are inlined
602-- * the loop is not recursively defined, recursion breaks inlining
604-- If these conditions cannot be met, the CPS style stream type 'StreamK' may
605-- turn out to be a better choice than the fused stream type 'Stream'.
607-- == Stream vs StreamK
609-- The fused stream model avoids constructor allocations and function call
610-- overheads. However, the stream is represented as a state machine, and to
611-- generate stream elements it has to navigate the decision tree of the state
612-- machine. Moreover, the state machine is cranked for each element in the
613-- stream. This performs extremely well when the number of states are limited.
614-- The state machine starts getting expensive as the number of states increase.
615-- For example, generating a stream from a list requires a single state and is
616-- very efficient, even if it has millions of elements. However, using 'cons'
617-- to construct a million element stream would be a disaster.
619-- A typical worst case scenario for fused stream model is a large number of
620-- `cons` or `append` operations. A few static `cons` or `append` operations
621-- are very fast and much faster than a CPS style stream because CPS involves a
622-- function call for each element whereas fused stream involves a few
623-- conditional branches in the state machine. However, constructing a large
624-- stream using `cons` introduces as many states in the state machine as the
625-- number of elements. If we compose `cons` as a balanced binary tree it will
626-- take @n * log n@ time to navigate the tree, and @n * n@ if it is a right
627-- associative composition.
629-- Operations like 'cons' or 'append'; are typically recursively called to
630-- construct a lazy infinite stream. For such use cases the CPS style 'StreamK'
631-- should be used. CPS streams do not have a state machine that needs to be
632-- cranked for each element, past state has no effect on the future element
633-- processing. However, CPS incurs a function call overhead for each element
634-- processed, the overhead could be large compared to a fused state machine
635-- even if it has many states. However, because of its linear performance
636-- characterstics, after a certain threshold of stream compositions the CPS
637-- stream would perform much better than the quadratic fused stream operations.
639-- As a general guideline, you need to use 'StreamK' when you have to use
640-- 'cons', 'append' or other operations having quadratic complexity at a large
641-- scale. Typically, in such cases you need to compose the stream recursively,
642-- by calling an operation in a loop. The decision to compose the stream is
643-- taken at run time rather than statically at compile time.
645-- Typically you would compose a 'StreamK' of chunks of data so that the
646-- StreamK overhead is not high, and then process the chunks using 'Stream' by
647-- using statically fused stream pipeline operations on the chunks.
649-- 'Stream' and 'StreamK' types can be interconverted. See
650-- "Streamly.Data.StreamK" module for conversion operations.
652-- | Split a stream of arrays on a given separator byte, dropping the separator
653-- and coalescing all the arrays between two separators into a single array.
655{-# INLINE chunksSplitOn #-}
659 -> Stream m (Array Word8)
660 -> Stream m (Array Word8)
661chunksSplitOn = 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