4-- Module : Streamly.Data.Unfold
5-- Copyright : (c) 2019 Composewell Technologies
7-- Maintainer : streamly@composewell.com
11-- Fast, composable stream producers with ability to terminate, supporting
12-- nested stream fusion. Nested stream operations like
13-- 'Streamly.Data.Stream.concatMap' in the "Streamly.Data.Stream" module do not
14-- fuse, however, the 'Streamly.Data.Stream.unfoldMany' operation, using the
15-- 'Unfold' type, is a fully fusible alternative to
16-- 'Streamly.Data.Stream.concatMap'.
18-- Please refer to "Streamly.Internal.Data.Unfold" for more functions that have
19-- not yet been released.
21-- Exception combinators are not exposed, we would like to encourage the use of
22-- 'Stream' type instead whenever exception handling is required. We can
23-- consider exposing the unfold exception functions if there is a compelling
24-- use case to use unfolds instead of stream.
26module Streamly.Data.Unfold
29 -- | To execute the code examples provided in this module in ghci, please
30 -- run the following commands first.
41 -- One to one correspondence with
42 -- "Streamly.Internal.Data.Stream.Generate"
44 -- ** Basic Constructors
51 -- | Generate a monadic stream from a seed.
65 -- ** Mapping on Input
69 -- ** Mapping on Output
95 ( concat, map, mapM, takeWhile, take, filter, const, drop, dropWhile
98import Streamly.Internal.Data.Unfold
100#include "DocTestDataUnfold.hs"
104-- An 'Unfold' is a source or a producer of a stream of values. It takes a
105-- seed value as an input and unfolds it into a sequence of values.
107-- For example, the 'fromList' Unfold generates a stream of values from a
108-- supplied list. Unfolds can be converted to 'Streamly.Internal.Data.Stream'
109-- using the 'Stream.unfold' operation.
111-- >>> stream = Stream.unfold Unfold.fromList [1..100]
112-- >>> Stream.fold Fold.sum stream
115-- The input seed of an unfold can be transformed using 'lmap':
117-- >>> u = Unfold.lmap (fmap (+1)) Unfold.fromList
118-- >>> Stream.fold Fold.toList $ Stream.unfold u [1..5]
121-- Output stream of an 'Unfold' can be transformed using transformation
122-- combinators. For example, to retain only the first two elements of an
125-- >>> u = Unfold.take 2 Unfold.fromList
126-- >>> Stream.fold Fold.toList $ Stream.unfold u [1..100]
129-- Unfolds can be nested efficiently. For example, to implement nested looping:
131-- >>> u1 = Unfold.lmap fst Unfold.fromList
132-- >>> u2 = Unfold.lmap snd Unfold.fromList
133-- >>> u = Unfold.crossWith (,) u1 u2
134-- >>> Stream.fold Fold.toList $ Stream.unfold u ([1,2,3], [4,5,6])
135-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
137-- 'Unfold' @u1@ generates a stream from the first list in the input tuple,
138-- @u2@ generates another stream from the second list. The combines 'Unfold'
139-- @u@ nests the two streams i.e. for each element in first stream, for each
140-- element in second stream apply the supplied function (i.e. @(,)@) to the
143-- This is the equivalent of the nested looping construct from imperative
144-- languages, also known as the cross product of two streams in functional
147-- Please see "Streamly.Internal.Data.Unfold" for additional @Pre-release@
150-- == Creating New Unfolds
152-- There are many commonly used unfolds provided in this module. However, you
153-- can always create your own as well. An 'Unfold' is just a data
154-- representation of a stream generator function. It consists of an @inject@
155-- function which covnerts the supplied seed into an internal state of the
156-- unfold, and a @step@ function which takes the state and generates the next
157-- output in the stream. For those familiar with the list "Data.List.unfoldr"
158-- function, this is a data representation of the same.
160-- Smart constructor functions are provided in this module for constructing new
161-- 'Unfolds'. For example, you can use the 'Unfold.unfoldr' constructor to
162-- create an 'Unfold' from a pure step function, unfoldr uses 'id' as the
165-- Let's define a simple pure step function:
169-- f (x:xs) = Just (x, xs)
172-- Create an 'Unfold' from the step function:
174-- >>> u = Unfold.unfoldr f
178-- >>> Stream.fold Fold.toList $ Stream.unfold u [1,2,3]
181-- The 'Unfold.unfoldr' smart constructor is essentially the same as the list
182-- "Data.List.unfoldr" function. We can use the same step function in both::
184-- >>> Data.List.unfoldr f [1,2,3]
187-- == Unfolds vs. Streams
189-- The 'Unfold' abstraction for representing streams was introduced in Streamly
190-- to provide C like performance for nested looping of streams. 'Unfold' and
191-- 'Stream' abstractions are similar with the following differences:
193-- * 'Stream' is less efficient than 'Unfold' for nesting.
194-- * 'Stream' is more powerful than 'Unfold'.
195-- * 'Stream' API is more convenient for programming
197-- Unfolds can be easily converted to streams using 'Stream.unfold', however,
198-- vice versa is not possible. To provide a familiar analogy, 'Unfold' is to
199-- 'Stream' as 'Applicative' is to 'Monad'.
201-- To demonstrate the efficiency of unfolds, the nested loop example in the
202-- previous section can be implemented with concatMap or Monad instance of
203-- streams as follows:
207-- x <- Stream.unfold Unfold.fromList [1,2,3]
208-- y <- Stream.unfold Unfold.fromList [4,5,6]
212-- As you can see, this is more convenient to write than using the 'crossWith'
213-- unfold combinator. However, this turns out to be many times slower than the
214-- unfold implementation. The Unfold version is equivalent in performance to
215-- the C implementation of the same nested loop. Similarly, unfolds can be
216-- nested with streams using the 'unfoldMany' combinator which is a much more
217-- efficient alternative to the 'concatMap' operation.
219-- Streams use a hybrid implementation approach using direct style as well as
220-- CPS. Unfolds do not use CPS, therefore, lack the power that is afforded to
221-- streams by CPS. The CPS implementation allows infinitely scalable @cons@ and
222-- @append@ operations in streams. It is also used to implement concurrency in
225-- To summarize, unfolds are a high performance solution to the nesting
226-- problem. Since streams provide a more palatable API for programming, work
227-- with streams unless you need unfolds for better performance in nesting
228-- situations. There is little difference in the way in which unfolds and
229-- streams are written, it is easy to adapt a stream to an unfold. If you are
230-- writing an unfold you can convert it to stream for free using
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