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