git.iko.soy/streamly
on aa2b166 help sign in
streamly/src/Streamly/Data/Unfold.hs
165 lines 4.9 kB history raw
1#include "inline.hs"
3-- |
4-- Module : Streamly.Data.Unfold
5-- Copyright : (c) 2019 Composewell Technologies
6-- License : BSD3
7-- Maintainer : streamly@composewell.com
8-- Stability : released
9-- Portability : GHC
10--
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.
13--
14-- >>> import qualified Streamly.Data.Fold as Fold
15-- >>> import qualified Streamly.Data.Unfold as Unfold
16-- >>> import qualified Streamly.Prelude as Stream
17--
18-- For example, the 'fromList' Unfold generates a stream of values from a
19-- supplied list. Unfolds can be converted to 'Streamly.Prelude.SerialT'
20-- stream using the Stream.unfold operation.
21--
22-- >>> stream = Stream.unfold Unfold.fromList [1..100]
23-- >>> Stream.sum stream
24-- 5050
25--
26-- All the serial stream generation operations in "Streamly.Prelude"
27-- can be expressed using unfolds:
28--
29-- > Stream.fromList = Stream.unfold Unfold.fromList [1..100]
30--
31-- Conceptually, an 'Unfold' is just like "Data.List.unfoldr". Let us write a
32-- step function to unfold a list using "Data.List.unfoldr":
33--
34-- >>> :{
35-- f [] = Nothing
36-- f (x:xs) = Just (x, xs)
37-- :}
38--
39-- >>> Data.List.unfoldr f [1,2,3]
40-- [1,2,3]
41--
42-- Unfold.unfoldr is just the same, it uses the same step function:
43--
44-- >>> Stream.toList $ Stream.unfold (Unfold.unfoldr f) [1,2,3]
45-- [1,2,3]
46--
47-- The input of an unfold can be transformed using 'lmap':
48--
49-- >>> u = Unfold.lmap (fmap (+1)) Unfold.fromList
50-- >>> Stream.toList $ Stream.unfold u [1..5]
51-- [2,3,4,5,6]
52--
53-- 'Unfold' streams can be transformed using transformation combinators. For
54-- example, to retain only the first two elements of an unfold:
55--
56-- >>> u = Unfold.take 2 Unfold.fromList
57-- >>> Stream.toList $ Stream.unfold u [1..100]
58-- [1,2]
59--
60-- Multiple unfolds can be combined in several interesting ways. For example,
61-- to generate nested looping as in imperative languages (also known as cross
62-- product of the two streams):
63--
64-- >>> u1 = Unfold.lmap fst Unfold.fromList
65-- >>> u2 = Unfold.lmap snd Unfold.fromList
66-- >>> u = Unfold.crossWith (,) u1 u2
67-- >>> Stream.toList $ Stream.unfold u ([1,2,3], [4,5,6])
68-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
69--
70-- Nested loops using unfolds provide C like performance due to complete stream
71-- fusion.
72--
73-- Please see "Streamly.Internal.Data.Unfold" for additional @Pre-release@
74-- functions.
75--
76-- = Unfolds vs. Streams
77--
78-- Unfolds' raison d'etre is their efficiency in nested stream operations due
79-- to complete stream fusion. 'Streamly.Prelude.concatMap' or the 'Monad'
80-- instance of streams use stream generation operations of the shape @a -> t m
81-- b@ and then flatten the resulting stream. This implementation is more
82-- powerful but does not allow for complete stream fusion. Unfolds provide
83-- less powerful but more efficient 'Streamly.Prelude.unfoldMany', 'many' and
84-- 'crossWith' operations as an alternative to a subset of use cases of
85-- 'concatMap' and 'Applicative' stream operations.
86--
87-- "Streamly.Prelude" exports polymorphic stream generation operations that
88-- provide the same functionality as unfolds in this module. Since unfolds can
89-- be easily converted to streams, several modules in streamly provide only
90-- unfolds for serial stream generation. We cannot use unfolds exclusively for
91-- stream generation as they do not support concurrency.
93module Streamly.Data.Unfold
94 (
95 -- * Unfold Type
96 Unfold
98 -- * Unfolds
99 -- One to one correspondence with
100 -- "Streamly.Internal.Data.Stream.IsStream.Generate"
102 -- ** Basic Constructors
103 , unfoldrM
104 , unfoldr
105 , function
106 , functionM
108 -- ** Generators
109 -- | Generate a monadic stream from a seed.
110 , repeatM
111 , replicateM
112 , iterateM
114 -- ** From Containers
115 , fromList
116 , fromListM
117 , fromStream
119 -- * Combinators
120 -- ** Mapping on Input
121 , lmap
122 , lmapM
124 -- ** Mapping on Output
125 , mapM
127 -- ** Filtering
128 , takeWhileM
129 , takeWhile
130 , take
131 , filter
132 , filterM
133 , drop
134 , dropWhile
135 , dropWhileM
137 -- ** Zipping
138 , zipWith
140 -- ** Cross Product
141 , crossWith
143 -- ** Nesting
144 , many
145 )
146where
148import Prelude hiding
149 ( concat, map, mapM, takeWhile, take, filter, const, drop, dropWhile
150 , zipWith
151 )
152import Streamly.Internal.Data.Stream.IsStream.Type (IsStream)
153import Streamly.Internal.Data.Unfold hiding (fromStream)
155import qualified Streamly.Internal.Data.Stream.IsStream.Type as IsStream
156import qualified Streamly.Internal.Data.Unfold as Unfold
158-- | Convert a stream into an 'Unfold'. Note that a stream converted to an
159-- 'Unfold' may not be as efficient as an 'Unfold' in some situations.
160--
161-- /Since: 0.8.0/
162--
163{-# INLINE_NORMAL fromStream #-}
164fromStream :: (IsStream t, Applicative m) => Unfold m (t m a) a
165fromStream = lmap IsStream.adapt Unfold.fromStream