git.iko.soy/streamly
on fec4a83 help sign in
streamly/docs/User/HowTo/streamly-vs-lists.md
267 lines 9.2 kB history raw
1# Streams are concurrent monadic lists
3THIS TUTORIAL IS OBSOLETE.
5Streamly streams are a generalization of Haskell lists with a similar API with
6two crucial additions:
8* A list is a _pure sequence_ of values whereas a stream is a _monadic
9 sequence_ of values i.e. a sequence of values generated by monadic actions.
10* The monadic actions producing the sequence can be executed concurrently.
11 Concurrency is declarative and can be switched on or off using an appropriate
12 combinator.
14## Pure Streams vs Monadic Streams
16A list is a sequence of pure values or pure steps that produce a value on
17evaluation. Ideally, we want to process each element in the sequence through a
18pipeline of processing stages without first accumulating all the elements in
19the sequence. This style of processing is known as "streaming" and it runs in
20constant memory because we do not accumulate elements in memory, data gets
21consumed as soon as it is produced. If all the processing stages are pure,
22lists can be used in a streaming style processing. For example, this is
23streaming style processing:
25```
26 replicate 10 1
27 & zipWith (+) [1..10]
28 & map (+1)
29 & filter odd
30 & sum
31```
33However, if a list is generated in a strict monad (e.g. IO) it cannot be
34consumed in a streaming fashion as described above. In that case the full list
35first gets accumulated and then processed. This means we will consume memory
36proportional to the size of the list and therefore it becomes unusable for
37large lists. For example, the following code accumulates `xs` before it
38processes it:
40```
41 xs <- replicateM 10 (return 1)
42 zipWith (+) [1..10] xs
43 & map (+1)
44 & filter odd
45 & sum
46```
48Monadic streams solve this problem. To be able to consume elements from
49`replicateM` as it produces them we need a monadic representation of the stream
50and stream processing operations that can consume the stream elements lazily
51one at a time. Streamly provides a monadic representation for lists with the
52same API. So we can represent the previous example in a streaming fashion by
53replacing the list combinators with corresponding streamly combinators:
55```
56 S.replicateM 10 (return 1)
57 & S.zipWith (+) (S.fromList [1..10])
58 & S.map (+1)
59 & S.filter odd
60 & S.sum
61```
63Streamly's monadic streams are a generalization of pure streams (aka lists) and
64therefore can represent pure streams just as easily, making lists a special
65case.
67## Streamly as lists
69`SerialT Identity a` can be used in place of `[a]` with equivalent or better
70performance and almost identical interface except a few differences. Use of
71`OverloadedLists` extension can make the difference even less significant.
74### Construction
76Lists are constructed using `[]` and `:`.
78```
79> "hello" : "world" : []
80["hello","world"]
81```
83Pure streams are constructed using `S.nil` (corresponds to `[]`) and `S.cons`
84or `.:` (corresponds to `:`):
86```
87import Streamly
88import Streamly.Prelude ((.:))
89import qualified Streamly.Prelude as S
91> "hello" .: "world" .: S.nil :: SerialT Identity String
92fromList ["hello","world"]
93```
95### Pattern Matching
97The crucial difference is that lists are built using constructors whereas
98streams are built using functions. `S.nil` and `S.cons` are functions.
99Therefore, you cannot directly pattern match on streams. However, the yet
100unexposed `Streamly.List` module also provides `Nil` and `Cons` pattern
101synonyms corresponding to the list `[]` and `:` constructors for pattern
102matches.
104### Pure Operations
106`SerialT Identity a` is an instance of `Show`, `Read`, `Eq`, `Ord`, `IsList`,
107`Foldable` and `Traversable` type classes. Furthermore, `SerialT Identity Char`
108is an instance of `IsString`. Use of `OverloadedLists` and `OverloadedStrings`
109can make the use of streams in place of lists quite convenient.
111Along with these we can use combinators from `Streamly.Prelude` to perform all
112list operations on pure streams.
114Lists:
116```
117> replicate 10 1
118> map (+1) $ replicate 10 1
119> length $ replicate 10 1
120```
122Pure streams are almost identical:
124```
125> S.replicate 10 1 :: SerialT Identity Int
126> S.map (+1) $ S.replicate 10 1 :: SerialT Identity Int
127> length (S.replicate 10 1 :: SerialT Identity Int)
128```
130## Monadic Operations
132Lists have great performance as long as we perform only pure operations on
133them. When monadic operations are performed on lists, they may accumulate
134potentially unbounded or large lists in memory degrading performance massively.
136Such "unsafe" list operations exist in `Control.Monad`, `Data.Traversable`, and
137`Data.Foldable` in `base`. They are typically found with an `M` suffix.
139Streamly provides monadic streams and the equivalents of the above mentioned
140monadic list operations work on streams without any issues.
142Unsafe monadic operations involving lists, run these example with `+RTS -s`
143options:
145```
146import Control.Monad
147main = do
148 xs <- replicateM 10000000 (pure 1)
149 ys <- mapM (\x -> return $ x + 1) xs
150 print $ length ys
151```
153Streams:
155```
156import Streamly
157import qualified Streamly.Prelude as S
158main = do
159 n <- S.length
160 $ S.mapM (\x -> return $ x + 1)
161 $ S.replicateM 10000000 (pure 1)
162 print n
163```
165## Splitting Operations
167Another unsafe category of operations for lists is stream splitting operations
168e.g. `lines`, `splitAt` and `group`. Such operations may also accumulate
169unbounded data in memory.
171Stream splitting operations in streamly are streaming in nature and can work
172without accumulating any data in memory.
174### Monadic Lists
176Monadic streams are nothing but lists made monadic. We can construct streams
177using monadic actions, just the way pure lists are constructed:
179```
180> import Streamly.Prelude ((|:))
181> import qualified Streamly.Prelude as S
182> S.toList $ getLine |: getLine |: S.nil
183hello
184world
185["hello","world"]
186```
188`|:` is the monadic construction equivalent of `:`.
189The monadic action `getLine` is executed twice in a sequence, the first one
190gets "hello" and second one gets "world" from the terminal and a stream
191consisting of those strings is produced.
193## Concurrent Monadic Lists
195Streamly streams are not just monadic lists but they are concurrent monadic
196lists. All the monadic streaming operations provided by streamly are inherently
197concurrent. Concurrent behavior can be enabled by just using an appropriate
198modifying combinator, without any other change to the code.
200The following code prints one element every second:
202```haskell
203import Control.Concurrent
204import Streamly
205import qualified Streamly.Prelude as S
207func = S.mapM (\x -> threadDelay 1000000 >> print x) $ S.replicate 10 1
208main = runStream func
209```
211To run it concurrently, just run the same code with `fromAsync` combinator:
213```haskell
214main = runStream $ fromAsync func
215```
217The `mapM` combinator now maps the monadic delay action concurrently on all the
218stream elements. It prints all the 10 elements after one second because all
219the delay actions run concurrently. Alternatively we can write:
221```
222func = S.mapM $ fromAsync $ S.replicateM (threadDelay 1000000 >> print 1)
223main = runStream func
224```
226Here, the `replicateM` operation replicates the action concurrently. In real
227applications this could be a request to a web server that you may want to
228perform multiple times concurrently.
230## Performance: Streamly vs Lists
232The following figures show the ratio of time and memory consumed by `[Int]`
233(`base-4.12`) vs `SerialT Identity Int`
234([streamly@00c7613](https://github.com/composewell/streamly)) for exactly the
235same operation. `5x` on the y axis means lists take 5 times more resources
236compared to streamly. Whereas a `1/5x` means that lists take 5 times less
237resources compared to streamly. We only show those operations that are at least
23810% better or worse in one library compared to the other. The operations are
239shown in a sorted order, from list's worst performing ones on the left to its
240best ones on the right.
242![Streamly vs Lists (time) comparison](/docs/User/HowTo/streamly-vs-list-time.svg)
244## Why use streams instead of lists?
246By using monadic streams instead of lists you get the following benefits:
248* Use just one library for pure or monadic lists. There is no difference in
249 pure or monadic code, its all the same.
250* You can use a monadic action anywhere in the code e.g. printing a warning or
251 error message or any other effectful operations. This is not possible in pure
252 list code.
253* You can make the code concurrent whenever you want without having to modify
254 it.
255* You do not have the risk of using unsafe/accumulating list operations
256 degrading performance massively and resulting in space leaks.
257* Streamly provides safe versions of partial list functions like `head`, `tail`
258 etc.
259* You get better fusion and therefore better performance for many operations,
260 the only operation which is significantly faster for lists is `concatMap`.
262## References
264* [Data.List](https://hackage.haskell.org/package/base/docs/Data-List.html)
265* [Control.Monad](http://hackage.haskell.org/package/base/docs/Control-Monad.html)
266* [Data.Foldable](http://hackage.haskell.org/package/base/docs/Data-Foldable.html)
267* [Data.Traversable](http://hackage.haskell.org/package/base/docs/Data-Traversable.html)