1{-# OPTIONS_GHC -Wno-orphans #-}
6-- Module : Streamly.Data.Stream
7-- Copyright : (c) 2017 Composewell Technologies
10-- Maintainer : streamly@composewell.com
11-- Stability : released
14-- To run examples in this module:
16-- >>> import qualified Streamly.Data.Fold as Fold
17-- >>> import qualified Streamly.Data.Stream as Stream
19-- We will add some more imports in the examples as needed.
21-- For effectful streams we will use the following IO action:
23-- >>> effect n = print n >> return n
27-- Streamly is a framework for modular data flow based programming and
28-- declarative concurrency. Powerful stream fusion framework in streamly
29-- allows high performance combinatorial programming even when using byte level
30-- streams. Streamly API is similar to Haskell lists.
32-- Streams can be constructed
33-- like lists, except that they use 'nil' instead of '[]' and 'cons' instead of
36-- `cons` constructs a pure stream which is more or less the same as a list:
38-- >>> import Streamly.Data.Stream (Stream, cons, consM, nil)
39-- >>> stream = 1 `cons` 2 `cons` nil :: Stream IO Int
40-- >>> Stream.fold Fold.toList stream -- IO [Int]
43-- 'consM' constructs a stream from effectful actions:
45-- >>> stream = effect 1 `consM` effect 2 `consM` nil
46-- >>> Stream.fold Fold.toList stream
51-- == Console Echo Example
53-- In the following example, 'repeatM' generates an infinite stream of 'String'
54-- by repeatedly performing the 'getLine' IO action. 'mapM' then applies
55-- 'putStrLn' on each element in the stream converting it to stream of '()'.
56-- Finally, 'drain' folds the stream to IO discarding the () values, thus
57-- producing only effects.
59-- >>> import Data.Function ((&))
63-- Stream.repeat getLine -- Stream IO (IO String)
64-- & Stream.sequence -- Stream IO String
65-- & Stream.mapM putStrLn -- Stream IO ()
66-- & Stream.fold Fold.drain -- IO ()
69-- This is a console echo program. It is an example of a declarative loop
70-- written using streaming combinators. Compare it with an imperative @while@
73-- Hopefully, this gives you an idea how we can program declaratively by
74-- representing loops using streams. In this module, you can find all
75-- "Data.List" like functions and many more powerful combinators to perform
76-- common programming tasks.
80-- >>> repeatM = Stream.sequence . Stream.repeat
81-- >>> replicateM n = Stream.sequence . Stream.replicate n
82-- >>> fromListM = Stream.sequence . Stream.fromList
83-- >>> fromFoldableM = Stream.sequence . Stream.fromFoldable
84-- >>> fromIndices f = fmap f $ Stream.enumerateFrom 0
86-- Also see "Streamly.Internal.Data.Stream" module for many more @Pre-release@
87-- combinators. See the <https://github.com/composewell/streamly-examples>
88-- repository for many more real world examples of stream programming.
90module Streamly.Data.Stream
94 -- | Functions ending in the general shape @b -> Stream m a@.
96 -- See also: "Streamly.Internal.Data.Stream.Generate" for
97 -- @Pre-release@ functions.
100 -- | Primitives to construct a stream from pure values or monadic actions.
101 -- All other stream construction and generation combinators described later
102 -- can be expressed in terms of these primitives. However, the special
103 -- versions provided in this module can be much more efficient in most
104 -- cases. Users can create custom combinators using these primitives.
108 -- , cons2 -- fused version
109 -- , consM2 -- fused version
112 -- | 'unfoldrM' is the most general way of generating a stream efficiently.
113 -- All other generation operations can be expressed using it.
118 -- | Generate a monadic stream from a seed value or values.
124 -- Note: Using enumeration functions e.g. 'Prelude.enumFromThen' turns out
125 -- to be slightly faster than the idioms like @[from, then..]@.
128 -- | We can use the 'Enum' type class to enumerate a type producing a list
129 -- and then convert it to a stream:
132 -- 'fromList' $ 'Prelude.enumFromThen' from then
135 -- However, this is not particularly efficient.
136 -- The 'Enumerable' type class provides corresponding functions that
137 -- generate a stream instead of a list, efficiently.
147 -- ** From Containers
148 -- | Convert an input structure, container or source into a stream. All of
149 -- these can be expressed in terms of primitives.
154 -- | Most of the above stream generation operations can also be expressed
155 -- using the corresponding unfolds in the "Streamly.Data.Unfold" module.
156 , unfold -- XXX rename to fromUnfold?
159 -- | Functions ending in the general shape @Stream m a -> m b@ or @Stream m
160 -- a -> m (b, Stream m a)@
162 -- See also: "Streamly.Internal.Data.Stream.Eliminate" for @Pre-release@
165-- EXPLANATION: In imperative terms a fold can be considered as a loop over the stream
166-- that reduces the stream to a single value.
167-- Left and right folds both use a fold function @f@ and an identity element
168-- @z@ (@zero@) to deconstruct a recursive data structure and reconstruct a
169-- new data structure. The new structure may be a recursive construction (a
170-- container) or a non-recursive single value reduction of the original
173-- Both right and left folds are mathematical duals of each other, they are
174-- functionally equivalent. Operationally, a left fold on a left associated
175-- structure behaves exactly in the same way as a right fold on a right
176-- associated structure. Similarly, a left fold on a right associated structure
177-- behaves in the same way as a right fold on a left associated structure.
178-- However, the behavior of a right fold on a right associated structure is
179-- operationally different (even though functionally equivalent) than a left
180-- fold on the same structure.
182-- On right associated structures like Haskell @cons@ lists or Streamly
183-- streams, a lazy right fold is naturally suitable for lazy recursive
184-- reconstruction of a new structure, while a strict left fold is naturally
185-- suitable for efficient reduction. In right folds control is in the hand of
186-- the @puller@ whereas in left folds the control is in the hand of the
189-- The behavior of right and left folds are described in detail in the
190-- individual fold's documentation. To illustrate the two folds for right
191-- associated @cons@ lists:
193-- > foldr :: (a -> b -> b) -> b -> [a] -> b
195-- > foldr f z (x:xs) = x `f` foldr f z xs
197-- > foldl :: (b -> a -> b) -> b -> [a] -> b
199-- > foldl f z (x:xs) = foldl f (z `f` x) xs
201-- @foldr@ is conceptually equivalent to:
204-- > foldr f z [x] = f x z
205-- > foldr f z xs = foldr f (foldr f z (tail xs)) [head xs]
207-- @foldl@ is conceptually equivalent to:
210-- > foldl f z [x] = f z x
211-- > foldl f z xs = foldl f (foldl f z (init xs)) [last xs]
213-- Left and right folds are duals of each other.
216-- foldr f z xs = foldl (flip f) z (reverse xs)
217-- foldl f z xs = foldr (flip f) z (reverse xs)
223-- foldr f z xs = foldl g id xs z where g k x = k . f x
224-- foldl f z xs = foldr g id xs z where g x k = k . flip f x
228-- NOTE: Folds are inherently serial as each step needs to use the result of
229-- the previous step. However, it is possible to fold parts of the stream in
230-- parallel and then combine the results using a monoid.
233 -- Consuming a part of the stream and returning the rest. Functions
234 -- ending in the general shape @Stream m a -> m (b, Stream m a)@
238 -- XXX Need to have a general parse operation here which can be used to
239 -- express all others.
240 , fold -- XXX rename to run? We can have a Stream.run and Fold.run.
241 -- XXX fold1 can be achieved using Monoids or Refolds.
249 -- -- ** Lazy Right Folds
250 -- Consuming a stream to build a right associated expression, suitable
251 -- for lazy evaluation. Evaluation of the input happens when the output of
252 -- the fold is evaluated, the fold output is a lazy thunk.
254 -- This is suitable for stream transformation operations, for example,
255 -- operations like mapping a function over the stream.
260 -- | Stateless one-to-one transformations. Use 'fmap' for mapping a pure
261 -- function on a stream.
264 -- In imperative terms a map operation can be considered as a loop over
265 -- the stream that transforms the stream into another stream by performing
266 -- an operation on each element of the stream.
268 -- 'map' is the least powerful transformation operation with strictest
269 -- guarantees. A map, (1) is a stateless loop which means that no state is
270 -- allowed to be carried from one iteration to another, therefore,
271 -- operations on different elements are guaranteed to not affect each
272 -- other, (2) is a strictly one-to-one transformation of stream elements
273 -- which means it guarantees that no elements can be added or removed from
274 -- the stream, it can merely transform them.
277 -- , trace -- XXX Use "tracing" map instead?
282 -- | Stateful one-to-one transformations.
284 -- See also: "Streamly.Internal.Data.Stream.Transform" for
285 -- @Pre-release@ functions.
288 -- XXX postscan1 can be implemented using Monoids or Refolds.
289 -- Indexing can be considered as a special type of zipping where we zip a
290 -- stream with an index stream.
295 -- | Add elements to the stream.
297 -- Inserting elements is a special case of interleaving/merging streams.
303 -- | Remove elements from the stream.
305 -- ** Stateless Filters
306 -- | 'mapMaybeM' is the most general stateless filtering operation. All
307 -- other filtering operations can be expressed using it.
309 -- In imperative terms a filter over a stream corresponds to a loop with a
310 -- @continue@ clause for the cases when the predicate fails.
317 -- ** Stateful Filters
318 -- | 'scanMaybe' is the most general stateful filtering operation. The
319 -- filtering folds (folds returning a 'Maybe' type) in
320 -- "Streamly.Internal.Data.Fold" can be used along with 'scanMaybe' to
321 -- perform stateful filtering operations in general.
333 -- Finding the presence or location of an element, a sequence of elements
334 -- or another stream within a stream.
336 -- -- ** Searching Elements
340 -- * Combining Two Streams
350 -- | Merging of @n@ streams can be performed by combining the streams pair
352 -- 'Streamly.Internal.Data.Stream.IsStream.Expand.concatPairsWith' to give
353 -- O(n * log n) time complexity.
354 -- If used with 'concatMapWith' it will have O(n^2) performance.
362 -- | Zipping of @n@ streams can be performed by combining the streams pair
364 -- 'Streamly.Internal.Data.Stream.IsStream.Expand.concatPairsWith' with
365 -- O(n * log n) time complexity.
366 -- If used with 'concatMapWith' it will have O(n^2) performance.
377 -- * Stream of streams
378 -- | Stream operations like map and filter represent loop processing in
379 -- imperative programming terms. Similarly, the imperative concept of
380 -- nested loops are represented by streams of streams. The 'concatMap'
381 -- operation represents nested looping.
382 -- A 'concatMap' operation loops over the input stream and then for each
383 -- element of the input stream generates another stream and then loops over
384 -- that inner stream as well producing effects and generating a single
386 -- The 'Monad' instances of different stream types provide a more
387 -- convenient way of writing nested loops. Note that the monad bind
388 -- operation is just @flip concatMap@.
390 -- One dimension loops are just a special case of nested loops. For
391 -- example, 'concatMap' can degenerate to a simple map operation:
393 -- > map f m = S.concatMap (\x -> S.fromPure (f x)) m
395 -- Similarly, 'concatMap' can perform filtering by mapping an element to a
398 -- > filter p m = S.concatMap (\x -> if p x then S.fromPure x else S.nil) m
406 , foldMany -- XXX Rename to foldRepeat
409 -- * Buffered Operations
410 -- | Operations that require buffering of the stream.
411 -- Reverse is essentially a left fold followed by an unfold.
414 -- * Multi-Stream folds
415 -- | Operations that consume multiple streams at the same time.
421 -- trimming sequences
425 -- | Most of these combinators inhibit stream fusion, therefore, when
426 -- possible, they should be called in an outer loop to mitigate the cost.
427 -- For example, instead of calling them on a stream of chars call them on a
428 -- stream of arrays before flattening it to a stream of chars.
430 -- See also: "Streamly.Internal.Data.Stream.Exception" for
431 -- @Pre-release@ functions.
436 -- * Resource Management
437 -- | 'bracket' is the most general resource management operation, all other
438 -- operations can be expressed using it.
444 -- * Lifting Inner Monad
445 -- | See also: "Streamly.Internal.Data.Stream.Lift" for
446 -- @Pre-release@ functions.
459import Streamly.Internal.Data.Stream
461 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
462 foldl, map, mapM, mapM_, sequence, all, any, sum, product, elem,
463 notElem, maximum, minimum, head, last, tail, length, null,
464 reverse, iterate, init, and, or, lookup, foldr1, (!!),
465 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