4-- Module : Streamly.Data.Unfold
5-- Copyright : (c) 2019 Composewell Technologies
7-- Maintainer : streamly@composewell.com
11-- An 'Unfold' is a source or a producer of a stream of values. It takes a
12-- seed value as an input and unfolds it into a sequence of values.
14-- >>> import qualified Streamly.Data.Fold as Fold
15-- >>> import qualified Streamly.Data.Unfold as Unfold
16-- >>> import qualified Streamly.Internal.Data.Stream as Stream
18-- For example, the 'fromList' Unfold generates a stream of values from a
19-- supplied list. Unfolds can be converted to 'Streamly.Internal.Data.Stream'
20-- using the 'Stream.unfold' operation.
22-- >>> stream = Stream.unfold Unfold.fromList [1..100]
23-- >>> Stream.fold Fold.sum stream
26-- The input seed of an unfold can be transformed using 'lmap':
28-- >>> u = Unfold.lmap (fmap (+1)) Unfold.fromList
29-- >>> Stream.fold Fold.toList $ Stream.unfold u [1..5]
32-- Output stream of an 'Unfold' can be transformed using transformation
33-- combinators. For example, to retain only the first two elements of an
36-- >>> u = Unfold.take 2 Unfold.fromList
37-- >>> Stream.fold Fold.toList $ Stream.unfold u [1..100]
40-- Unfolds can be nested efficiently. For example, to implement nested looping:
42-- >>> u1 = Unfold.lmap fst Unfold.fromList
43-- >>> u2 = Unfold.lmap snd Unfold.fromList
44-- >>> u = Unfold.crossWith (,) u1 u2
45-- >>> Stream.fold Fold.toList $ Stream.unfold u ([1,2,3], [4,5,6])
46-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
48-- 'Unfold' @u1@ generates a stream from the first list in the input tuple,
49-- @u2@ generates another stream from the second list. The combines 'Unfold'
50-- @u@ nests the two streams i.e. for each element in first stream, for each
51-- element in second stream apply the supplied function (i.e. @(,)@) to the
54-- This is the equivalent of the nested looping construct from imperative
55-- languages, also known as the cross product of two streams in functional
58-- Please see "Streamly.Internal.Data.Unfold" for additional @Pre-release@
61-- = Creating New Unfolds
63-- There are many commonly used unfolds provided in this module. However, you
64-- can always create your own as well. An 'Unfold' is just a data
65-- representation of a stream generator function. It consists of an @inject@
66-- function which covnerts the supplied seed into an internal state of the
67-- unfold, and a @step@ function which takes the state and generates the next
68-- output in the stream. For those familiar with the list "Data.List.unfoldr"
69-- function, this is a data representation of the same.
71-- Smart constructor functions are provided in this module for constructing new
72-- 'Unfolds'. For example, you can use the 'Unfold.unfoldr' constructor to
73-- create an 'Unfold' from a pure step function, unfoldr uses 'id' as the
76-- Let's define a simple pure step function:
80-- f (x:xs) = Just (x, xs)
83-- Create an 'Unfold' from the step function:
85-- >>> u = Unfold.unfoldr f
89-- >>> Stream.fold Fold.toList $ Stream.unfold u [1,2,3]
92-- The 'Unfold.unfoldr' smart constructor is essentially the same as the list
93-- "Data.List.unfoldr" function. We can use the same step function in both::
95-- >>> Data.List.unfoldr f [1,2,3]
98-- = Unfolds vs. Streams
100-- The 'Unfold' abstraction for representing streams was introduced in Streamly
101-- to provide C like performance for nested looping of streams. 'Unfold' and
102-- 'Stream' abstractions are similar with the following differences:
104-- * 'Stream' is less efficient than 'Unfold' for nesting.
105-- * 'Stream' is more powerful than 'Unfold'.
106-- * 'Stream' API is more convenient for programming
108-- Unfolds can be easily converted to streams using 'Stream.unfold', however,
109-- vice versa is not possible. To provide a familiar analogy, 'Unfold' is to
110-- 'Stream' as 'Applicative' is to 'Monad'.
112-- To demonstrate the efficiency of unfolds, the nested loop example in the
113-- previous section can be implemented with concatMap or Monad instance of
114-- streams as follows:
118-- x <- Stream.unfold Unfold.fromList [1,2,3]
119-- y <- Stream.unfold Unfold.fromList [4,5,6]
123-- As you can see, this is more convenient to write than using the 'crossWith'
124-- unfold combinator. However, this turns out to be many times slower than the
125-- unfold implementation. The Unfold version is equivalent in performance to
126-- the C implementation of the same nested loop. Similarly, unfolds can be
127-- nested with streams using the 'unfoldMany' combinator which is a much more
128-- efficient alternative to the 'concatMap' operation.
130-- Streams use a hybrid implementation approach using direct style as well as
131-- CPS. Unfolds do not use CPS, therefore, lack the power that is afforded to
132-- streams by CPS. The CPS implementation allows infinitely scalable @cons@ and
133-- @append@ operations in streams. It is also used to implement concurrency in
136-- To summarize, unfolds are a high performance solution to the nesting
137-- problem. Since streams provide a more palatable API for programming, work
138-- with streams unless you need unfolds for better performance in nesting
139-- situations. There is little difference in the way in which unfolds and
140-- streams are written, it is easy to adapt a stream to an unfold. If you are
141-- writing an unfold you can convert it to stream for free using
144-- What makes streams less efficient is also what makes them more conveient to
145-- use and powerful. The stream data type (Stream m a) bundles the state along
146-- with the stream generator function making it opaque, whereas an unfold
147-- exposes the state (Unfold m s a) to the user. This allows the Unfold to be
148-- unfolded (inlined) inside a nested loop without having to bundle the state
149-- and the generator together, the stream state can be saved and passed
150-- independent of the generator function. On the other hand in a stream type we
151-- have to bundle the stream state and the generator function together to save
152-- the stream. This makes it inefficient because it requires boxing and
153-- constructor allocation. However, this makes streams more convenient as we do
154-- not need to pass around the state/seed separately.
156module Streamly.Data.Unfold
162 -- One to one correspondence with
163 -- "Streamly.Internal.Data.Stream.Generate"
165 -- ** Basic Constructors
172 -- | Generate a monadic stream from a seed.
177 -- ** From Containers
183 -- ** Mapping on Input
187 -- ** Mapping on Output
212 ( concat, map, mapM, takeWhile, take, filter, const, drop, dropWhile
215import Streamly.Internal.Data.Unfold
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