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.
74 -- Non-empty pure streams can be cycled using repeat and unfold:
76 -- >>> cycle = Stream.unfoldMany Unfold.fromList . Stream.repeat
78 -- Non-empty StreamK can be cycled using append:
80 -- >>> cycle xs = let ys = xs `StreamK.append` ys in ys
89 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
90 -- to be slightly faster than the idioms like @[from, then..]@.
93 -- | We can use the 'Enum' type class to enumerate a type producing a list
94 -- and then convert it to a stream:
97 -- 'fromList' $ 'Prelude.enumFromThen' from then
100 -- However, this is not particularly efficient.
101 -- The 'Enumerable' type class provides corresponding functions that
102 -- generate a stream instead of a list, efficiently.
112 -- ** From Containers
113 -- | Convert an input structure, container or source into a stream. All of
114 -- these can be expressed in terms of primitives.
118 -- | Most of the above stream generation operations can also be expressed
119 -- using the corresponding unfolds in the "Streamly.Data.Unfold" module.
120 , unfold -- XXX rename to fromUnfold?
123 -- | Functions ending in the general shape @Stream m a -> m b@ or @Stream m
124 -- a -> m (b, Stream m a)@
127-- EXPLANATION: In imperative terms a fold can be considered as a loop over the stream
128-- that reduces the stream to a single value.
129-- Left and right folds both use a fold function @f@ and an identity element
130-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
131-- new data structure. The new structure may be a recursive construction (a
132-- container) or a non-recursive single value reduction of the original
135-- Both right and left folds are mathematical duals of each other, they are
136-- functionally equivalent. Operationally, a left fold on a left associated
137-- structure behaves exactly in the same way as a right fold on a right
138-- associated structure. Similarly, a left fold on a right associated structure
139-- behaves in the same way as a right fold on a left associated structure.
140-- However, the behavior of a right fold on a right associated structure is
141-- operationally different (even though functionally equivalent) than a left
142-- fold on the same structure.
144-- On right associated structures like Haskell @cons@ lists or Streamly
145-- streams, a lazy right fold is naturally suitable for lazy recursive
146-- reconstruction of a new structure, while a strict left fold is naturally
147-- suitable for efficient reduction. In right folds control is in the hand of
148-- the @puller@ whereas in left folds the control is in the hand of the
151-- The behavior of right and left folds are described in detail in the
152-- individual fold's documentation. To illustrate the two folds for right
153-- associated @cons@ lists:
155-- > foldr :: (a -> b -> b) -> b -> [a] -> b
157-- > foldr f z (x:xs) = x `f` foldr f z xs
159-- > foldl :: (b -> a -> b) -> b -> [a] -> b
161-- > foldl f z (x:xs) = foldl f (z `f` x) xs
163-- @foldr@ is conceptually equivalent to:
166-- > foldr f z [x] = f x z
167-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
169-- @foldl@ is conceptually equivalent to:
172-- > foldl f z [x] = f z x
173-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
175-- Left and right folds are duals of each other.
178-- foldr f z xs = foldl (flip f) z (reverse xs)
179-- foldl f z xs = foldr (flip f) z (reverse xs)
185-- foldr f z xs = foldl g id xs z where g k x = k . f x
186-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
190-- NOTE: Folds are inherently serial as each step needs to use the result of
191-- the previous step. However, it is possible to fold parts of the stream in
192-- parallel and then combine the results using a monoid.
195 -- Consuming a part of the stream and returning the rest. Functions
196 -- ending in the general shape @Stream m a -> m (b, Stream m a)@
199 -- ** Strict Left Folds
200 -- XXX Need to have a general parse operation here which can be used to
201 -- express all others.
202 , fold -- XXX rename to run? We can have a Stream.run and Fold.run.
203 -- XXX fold1 can be achieved using Monoids or Refolds.
204 -- XXX We can call this just "break" and parseBreak as "munch"
207 -- XXX should we have a Fold returning function in stream module?
215 -- ** Lazy Right Folds
216 -- | Consuming a stream to build a right associated expression, suitable
217 -- for lazy evaluation. Evaluation of the input happens when the output of
218 -- the fold is evaluated, the fold output is a lazy thunk.
220 -- This is suitable for stream transformation operations, for example,
221 -- operations like mapping a function over the stream.
227 -- | Streams are folded using folds in "Streamly.Data.Fold". Here are some
228 -- idioms and equivalents of Data.List APIs using folds:
230 -- >>> foldlM' f a = Stream.fold (Fold.foldlM' f a)
231 -- >>> foldl1' f = Stream.fold (Fold.foldl1' f)
232 -- >>> foldl' f a = Stream.fold (Fold.foldl' f a)
233 -- >>> drain = Stream.fold Fold.drain
234 -- >>> mapM_ f = Stream.fold (Fold.drainMapM f)
235 -- >>> length = Stream.fold Fold.length
236 -- >>> genericLength = Stream.fold Fold.lengthGeneric
237 -- >>> head = Stream.fold Fold.one
238 -- >>> last = Stream.fold Fold.latest
239 -- >>> null = Stream.fold Fold.null
240 -- >>> and = Stream.fold Fold.and
241 -- >>> or = Stream.fold Fold.or
242 -- >>> any p = Stream.fold (Fold.any p)
243 -- >>> all p = Stream.fold (Fold.all p)
244 -- >>> sum = Stream.fold Fold.sum
245 -- >>> product = Stream.fold Fold.product
246 -- >>> maximum = Stream.fold Fold.maximum
247 -- >>> maximumBy cmp = Stream.fold (Fold.maximumBy cmp)
248 -- >>> minimum = Stream.fold Fold.minimum
249 -- >>> minimumBy cmp = Stream.fold (Fold.minimumBy cmp)
250 -- >>> elem x = Stream.fold (Fold.elem x)
251 -- >>> notElem x = Stream.fold (Fold.notElem x)
252 -- >>> lookup x = Stream.fold (Fold.lookup x)
253 -- >>> find p = Stream.fold (Fold.find p)
254 -- >>> (!?) i = Stream.fold (Fold.index i)
255 -- >>> genericIndex i = Stream.fold (Fold.indexGeneric i)
256 -- >>> elemIndex x = Stream.fold (Fold.elemIndex x)
257 -- >>> findIndex p = Stream.fold (Fold.findIndex p)
259 -- Some equivalents of Data.List APIs from the Stream module:
261 -- >>> head = fmap (fmap fst) . Stream.uncons
262 -- >>> tail = fmap (fmap snd) . Stream.uncons
263 -- >>> tail = Stream.tail -- unreleased API
264 -- >>> init = Stream.init -- unreleased API
266 -- A Stream based toList fold implementation is provided below because it
267 -- has a better performance compared to the fold.
269 -- Functions in Data.List, missing here:
270 -- unsnoc = Stream.parseBreak (Parser.init Fold.toList)
278 -- | Stateless one-to-one transformations. Use 'fmap' for mapping a pure
279 -- function on a stream.
282 -- In imperative terms a map operation can be considered as a loop over
283 -- the stream that transforms the stream into another stream by performing
284 -- an operation on each element of the stream.
286 -- 'map' is the least powerful transformation operation with strictest
287 -- guarantees. A map, (1) is a stateless loop which means that no state is
288 -- allowed to be carried from one iteration to another, therefore,
289 -- operations on different elements are guaranteed to not affect each
290 -- other, (2) is a strictly one-to-one transformation of stream elements
291 -- which means it guarantees that no elements can be added or removed from
292 -- the stream, it can merely transform them.
300 -- | Stateful one-to-one transformations.
305 -- | We can perform scans using folds with the 'scan' combinator in the
306 -- next section. However, the combinators supplied in this section are
307 -- better amenable to stream fusion when combined with other operations.
308 -- Note that 'postscan' using folds fuses well and does not require custom
309 -- combinators like these.
316 -- ** Scanning By 'Fold'
319 -- >>> scanl' f z = Stream.scan (Fold.foldl' f z)
320 -- >>> scanlM' f z = Stream.scan (Fold.foldlM' f z)
321 -- >>> postscanl' f z = Stream.postscan (Fold.foldl' f z)
322 -- >>> postscanlM' f z = Stream.postscan (Fold.foldlM' f z)
323 -- >>> scanl1' f = Stream.catMaybes . Stream.scan (Fold.foldl1' f)
324 -- >>> scanl1M' f = Stream.catMaybes . Stream.scan (Fold.foldlM1' f)
327 -- XXX postscan1 can be implemented using Monoids or Refolds.
328 -- The following scans from Data.List are not provided.
339 -- Indexing can be considered as a special type of zipping where we zip a
340 -- stream with an index stream.
344 -- | Add elements to the stream.
346 -- >>> insert = Stream.insertBy compare
348 -- Inserting elements is a special case of interleaving/merging streams.
355 -- | Remove elements from the stream.
357 -- ** Stateless Filters
358 -- | 'mapMaybeM' is the most general stateless filtering operation. All
359 -- other filtering operations can be expressed using it.
362 -- In imperative terms a filter over a stream corresponds to a loop with a
363 -- @continue@ clause for the cases when the predicate fails.
376 -- ** Stateful Filters
377 -- | 'scanMaybe' is the most general stateful filtering operation. The
378 -- filtering folds (folds returning a 'Maybe' type) in
379 -- "Streamly.Internal.Data.Fold" can be used along with 'scanMaybe' to
380 -- perform stateful filtering operations in general.
382 -- Idioms and equivalents of Data.List APIs:
384 -- >>> deleteBy cmp x = Stream.scanMaybe (Fold.deleteBy cmp x)
385 -- >>> deleteBy = Stream.deleteBy -- unreleased API
386 -- >>> delete = deleteBy (==)
387 -- >>> findIndices p = Stream.scanMaybe (Fold.findIndices p)
388 -- >>> elemIndices a = findIndices (== a)
389 -- >>> uniq = Stream.scanMaybe (Fold.uniqBy (==))
390 -- >>> partition p = Stream.fold (Fold.partition Fold.toList Fold.toList) . fmap (if p then Left else Right)
398 -- XXX write to an array in reverse and then read in reverse
399 -- > dropWhileEnd = reverse . dropWhile p . reverse
401 -- XXX These are available as scans in folds. We need to check the
402 -- performance though. If these are common and we need convenient stream
403 -- ops then we can expose these.
413 -- Finding the presence or location of an element, a sequence of elements
414 -- or another stream within a stream.
416 -- -- ** Searching Elements
420 -- * Combining Two Streams
421 -- | Note that these operations are suitable for statically fusing a few
422 -- streams, they have a quadratic O(n^2) time complexity wrt to the number
423 -- of streams. If you want to compose many streams dynamically using binary
424 -- combining operations see the corresponding operations in
425 -- "Streamly.Data.StreamK".
427 -- When fusing more than two streams it is more efficient if the binary
428 -- operations are composed as a balanced tree rather than a right
429 -- associative or left associative one e.g.:
431 -- >>> s1 = Stream.fromList [1,2] `Stream.append` Stream.fromList [3,4]
432 -- >>> s2 = Stream.fromList [4,5] `Stream.append` Stream.fromList [6,7]
433 -- >>> s = s1 `Stream.append` s2
436 -- | Equivalent of Data.List append:
438 -- >>> (++) = Stream.append
449 -- | Idioms and equivalents of Data.List APIs:
451 -- >>> zip = Stream.zipWith (,)
452 -- >>> unzip = Stream.fold (Fold.unzip Fold.toList Fold.toList)
455 -- XXX zipWith3,4,5,6,7
456 -- XXX unzip3,4,5,6,7
460 -- XXX The argument order in this operation is such that it seems we are
461 -- transforming the first stream using the second stream because the second
462 -- stream is evaluated many times or buffered and better be finite, first
463 -- stream could potentially be infinite. In the tradition of using the
464 -- transformed stream at the end we can have a flipped version called
465 -- "crossMap" or "nestWith".
469 -- , CrossStream (..)
476 -- * Stream of streams
477 -- | Stream operations like map and filter represent loop processing in
478 -- imperative programming terms. Similarly, the imperative concept of
479 -- nested loops are represented by streams of streams. The 'concatMap'
480 -- operation represents nested looping.
481 -- A 'concatMap' operation loops over the input stream and then for each
482 -- element of the input stream generates another stream and then loops over
483 -- that inner stream as well producing effects and generating a single
486 -- One dimension loops are just a special case of nested loops. For
487 -- example, 'concatMap' can degenerate to a simple map operation:
489 -- >>> map f m = Stream.concatMap (\x -> Stream.fromPure (f x)) m
491 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
494 -- >>> filter p m = Stream.concatMap (\x -> if p x then Stream.fromPure x else Stream.nil) m
496 -- Idioms and equivalents of Data.List APIs:
498 -- >>> concat = Stream.concatMap id
499 -- >>> unlines = Stream.interposeSuffix '\n'
500 -- >>> unlines = Stream.intercalateSuffix Unfold.fromList "\n"
501 -- >>> unwords = Stream.interpose ' '
502 -- >>> unwords = Stream.intercalate Unfold.fromList " "
509 -- | Idioms and equivalents of Data.List APIs:
511 -- >>> groupsOf n = Stream.foldMany (Fold.take n Fold.toList)
512 -- >>> groupBy eq = Stream.groupsWhile eq Fold.toList
513 -- >>> groupBy eq = Stream.parseMany (Parser.groupBy eq Fold.toList)
514 -- >>> groupsByRolling eq = Stream.parseMany (Parser.groupByRolling eq Fold.toList)
515 -- >>> groups = groupBy (==)
516 , foldMany -- XXX Rename to foldRepeat
521 -- | Idioms and equivalents of Data.List APIs:
523 -- >>> splitWithSuffix p f = Stream.foldMany (Fold.takeEndBy p f)
524 -- >>> splitOnSuffix p f = Stream.foldMany (Fold.takeEndBy_ p f)
525 -- >>> lines = splitOnSuffix (== '\n')
526 -- >>> words = Stream.wordsBy isSpace
527 -- >>> splitAt n = Stream.fold (Fold.splitAt n Fold.toList Fold.toList)
528 -- >>> span p = Parser.splitWith (,) (Parser.takeWhile p Fold.toList) (Parser.fromFold Fold.toList)
529 -- >>> break p = span (not . p)
533 -- * Buffered Operations
534 -- | Operations that require buffering of the stream.
535 -- Reverse is essentially a left fold followed by an unfold.
537 -- Idioms and equivalents of Data.List APIs:
539 -- >>> nub = Stream.fold Fold.toList . Stream.scanMaybe Fold.nub
540 -- >>> nub = Stream.ordNub -- unreleased API
541 -- >>> sortBy = StreamK.sortBy
542 -- >>> sortOn f = StreamK.sortOn -- unreleased API
543 -- >>> deleteFirstsBy = Stream.deleteFirstsBy -- unreleased
544 -- >>> (\\) = Stream.deleteFirstsBy (==) -- unreleased
545 -- >>> intersectBy = Stream.intersectBy -- unreleased
546 -- >>> intersect = Stream.intersectBy (==) -- unreleased
547 -- >>> unionBy = Stream.unionBy -- unreleased
548 -- >>> union = Stream.unionBy (==) -- unreleased
551 -- XXX transpose: write the streams to arrays and then stream transposed.
558 -- * Multi-Stream folds
559 -- | Operations that consume multiple streams at the same time.
568 -- trimming sequences
571 -- , stripSuffixUnbox
573 -- Exceptions and resource management depend on the "exceptions" package
574 -- XXX We can have IO Stream operations not depending on "exceptions"
578 -- | Note that the stream exception handling routines catch and handle
579 -- exceptions only in the stream generation steps and not in the consumer
580 -- of the stream. For example, if we are folding or parsing a stream - any
581 -- exceptions in the fold or parse steps won't be observed by the stream
582 -- exception handlers. Exceptions in the fold or parse steps can be handled
583 -- using the fold or parse exception handling routines. You can wrap the
584 -- stream elimination function in the monad exception handler to observe
585 -- exceptions in the stream as well as the consumer.
587 -- Most of these combinators inhibit stream fusion, therefore, when
588 -- possible, they should be called in an outer loop to mitigate the cost.
589 -- For example, instead of calling them on a stream of chars call them on a
590 -- stream of arrays before flattening it to a stream of chars.
595 -- * Resource Management
596 -- | 'bracket' is the most general resource management operation, all other
597 -- operations can be expressed using it. These functions have IO suffix
598 -- because the allocation and cleanup functions are IO actions. For
599 -- generalized allocation and cleanup functions, see the functions without
600 -- the IO suffix in the "streamly" package.
602 -- Note that these operations bracket the stream generation only, they do
603 -- not cover the stream consumer. This means if an exception occurs in
604 -- the consumer of the stream (e.g. in a fold or parse step) then the
605 -- exception won't be observed by the stream resource handlers, in that
606 -- case the resource cleanup handler runs when the stream is garbage
609 -- Monad level resource management can always be used around the stream
610 -- elimination functions, such a function can observe exceptions in both
611 -- the stream and its consumer.
618 -- * Transforming Inner Monad
625 -- XXX Arrays could be different types, therefore, this should be in
626 -- specific array module. Or maybe we should abstract over array types.
627 -- * Stream of Arrays
632import Streamly.Internal.Data.Stream
634 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
635 mapM, sequence, reverse, iterate, foldr1, repeat, replicate,
638import qualified Streamly.Internal.Data.Array.Type as Array
640#include "DocTestDataStream.hs"
644-- Streamly is a framework for modular data flow based programming and
645-- declarative concurrency. Powerful stream fusion framework in streamly
646-- allows high performance combinatorial programming even when using byte level
647-- streams. Streamly API is similar to Haskell lists.
649-- == Console Echo Example
651-- In the following example, 'repeatM' generates an infinite stream of 'String'
652-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
653-- 'putStrLn' on each element in the stream converting it to stream of '()'.
654-- Finally, 'drain' folds the stream to IO discarding the () values, thus
655-- producing only effects.
657-- >>> import Data.Function ((&))
661-- Stream.repeatM getLine -- Stream IO String
662-- & Stream.mapM putStrLn -- Stream IO ()
663-- & Stream.fold Fold.drain -- IO ()
666-- This is a console echo program. It is an example of a declarative loop
667-- written using streaming combinators. Compare it with an imperative @while@
670-- Hopefully, this gives you an idea how we can program declaratively by
671-- representing loops using streams. In this module, you can find all
672-- "Data.List" like functions and many more powerful combinators to perform
673-- common programming tasks.
677-- The fused 'Stream' type in this module employs stream fusion for C-like
678-- performance when looping over data. It represents the stream as a state
679-- machine using an explicit state, and a step function working on the state. A
680-- typical stream operation consumes elements from the previous state machine
681-- in a stream pipeline, transforms the elements and yields new values for the
682-- next stage to consume. The stream operations are modular and represent a
683-- single task, they have no knowledge of previous or next operation on the
686-- A typical stream pipeline consists of a stream producer, several stream
687-- transformation operations and a stream consumer. All these operations taken
688-- together form a closed loop processing the stream elements. Elements are
689-- transferred between stages using a boxed data constructor. However, all the
690-- stages of the pipeline are fused together by GHC, eliminating the boxing of
691-- intermediate constructors, and thus forming a tight C like loop without any
692-- boxed data being used in the loop.
694-- Stream fusion works effectively when:
696-- * the stream pipeline is composed statically (known at compile time)
697-- * all the operations forming the loop are inlined
698-- * the loop is not recursively defined, recursion breaks inlining
700-- If these conditions cannot be met, the CPS style stream type 'StreamK' may
701-- turn out to be a better choice than the fused stream type 'Stream'.
703-- == Stream vs StreamK
705-- The fused stream model avoids constructor allocations and function call
706-- overheads. However, the stream is represented as a state machine, and to
707-- generate stream elements it has to navigate the decision tree of the state
708-- machine. Moreover, the state machine is cranked for each element in the
709-- stream. This performs extremely well when the number of states are limited.
710-- The state machine starts getting expensive as the number of states increase.
711-- For example, generating a stream from a list requires a single state and is
712-- very efficient, even if it has millions of elements. However, using 'cons'
713-- to construct a million element stream would be a disaster.
715-- A typical worst case scenario for fused stream model is a large number of
716-- `cons` or `append` operations. A few static `cons` or `append` operations
717-- are very fast and much faster than a CPS style stream because CPS involves a
718-- function call for each element whereas fused stream involves a few
719-- conditional branches in the state machine. However, constructing a large
720-- stream using `cons` introduces as many states in the state machine as the
721-- number of elements. If we compose `cons` as a balanced binary tree it will
722-- take @n * log n@ time to navigate the tree, and @n * n@ if it is a right
723-- associative composition.
725-- Operations like 'cons' or 'append'; are typically recursively called to
726-- construct a lazy infinite stream. For such use cases the CPS style 'StreamK'
727-- should be used. CPS streams do not have a state machine that needs to be
728-- cranked for each element, past state has no effect on the future element
729-- processing. However, CPS incurs a function call overhead for each element
730-- processed, the overhead could be large compared to a fused state machine
731-- even if it has many states. However, because of its linear performance
732-- characterstics, after a certain threshold of stream compositions the CPS
733-- stream would perform much better than the quadratic fused stream operations.
735-- As a general guideline, you need to use 'StreamK' when you have to use
736-- 'cons', 'append' or other operations having quadratic complexity at a large
737-- scale. Typically, in such cases you need to compose the stream recursively,
738-- by calling an operation in a loop. The decision to compose the stream is
739-- taken at run time rather than statically at compile time.
741-- Typically you would compose a 'StreamK' of chunks of data so that the
742-- StreamK overhead is not high, and then process the chunks using 'Stream' by
743-- using statically fused stream pipeline operations on the chunks.
745-- 'Stream' and 'StreamK' types can be interconverted. See
746-- "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