streamly-0.11.1: docs/User/HowTo/streamly-vs-lists.md
# Streams are concurrent monadic lists
THIS TUTORIAL IS OBSOLETE.
Streamly streams are a generalization of Haskell lists with a similar API with
two crucial additions:
* A list is a _pure sequence_ of values whereas a stream is a _monadic
sequence_ of values i.e. a sequence of values generated by monadic actions.
* The monadic actions producing the sequence can be executed concurrently.
Concurrency is declarative and can be switched on or off using an appropriate
combinator.
## Pure Streams vs Monadic Streams
A list is a sequence of pure values or pure steps that produce a value on
evaluation. Ideally, we want to process each element in the sequence through a
pipeline of processing stages without first accumulating all the elements in
the sequence. This style of processing is known as "streaming" and it runs in
constant memory because we do not accumulate elements in memory, data gets
consumed as soon as it is produced. If all the processing stages are pure,
lists can be used in a streaming style processing. For example, this is
streaming style processing:
```haskell docspec
>>> import Data.Function ((&))
>>> :{
replicate 10 1
& zipWith (+) [1..10]
& map (+1)
& filter odd
& sum
:}
35
```
However, if a list is generated in a strict monad (e.g. IO) it cannot be
consumed in a streaming fashion as described above. In that case the full list
first gets accumulated and then processed. This means we will consume memory
proportional to the size of the list and therefore it becomes unusable for
large lists. For example, the following code accumulates `xs` before it
processes it:
```haskell docspec
>>> import Control.Monad (replicateM)
>>> xs <- replicateM 10 (return 1)
>>> :{
zipWith (+) [1..10] xs
& map (+1)
& filter odd
& sum
:}
35
```
Monadic streams solve this problem. To be able to consume elements from
`replicateM` as it produces them we need a monadic representation of the stream
and stream processing operations that can consume the stream elements lazily
one at a time. Streamly provides a monadic representation for lists with the
same API. So we can represent the previous example in a streaming fashion by
replacing the list combinators with corresponding streamly combinators:
```haskell docspec
>>> import qualified Streamly.Data.Stream as S
>>> import qualified Streamly.Data.Fold as F
>>> :{
S.replicateM 10 (return 1)
& S.zipWith (+) (S.fromList [1..10])
& fmap (+1)
& S.filter odd
& S.fold F.sum
:}
35
```
Streamly's monadic streams are a generalization of pure streams (aka lists) and
therefore can represent pure streams just as easily, making lists a special
case.
## Streamly as lists
`Stream Identity a` can be used in place of `[a]` with equivalent or better
performance and almost identical interface except a few differences. Use of
`OverloadedLists` extension can make the difference even less significant.
### Construction
Lists are constructed using `[]` and `:`.
```haskell docspec
>>> "hello" : "world" : []
["hello","world"]
```
Pure streams are constructed using `S.nil` (corresponds to `[]`) and `S.cons`
or `.:` (corresponds to `:`):
```haskell docspec
>>> import Data.Functor.Identity (Identity)
>>> import Streamly.Data.StreamK (StreamK)
>>> import qualified Streamly.Data.StreamK as StreamK
>>> "hello" `StreamK.cons` "world" `StreamK.cons` StreamK.nil :: StreamK Identity String
fromList ["hello","world"]
```
### Pattern Matching
The crucial difference is that lists are built using constructors whereas
streams are built using functions. `S.nil` and `S.cons` are functions.
Therefore, you cannot directly pattern match on streams. However, the yet
unexposed `Streamly.Internal.Data.List` module also provides `Nil` and `Cons`
pattern synonyms corresponding to the list `[]` and `:` constructors for pattern
matches.
### Pure Operations
`Stream Identity a` is an instance of `Show`, `Read`, `Eq`, `Ord`, `IsList`,
`Foldable` and `Traversable` type classes. Furthermore, `Stream Identity Char`
is an instance of `IsString`. Use of `OverloadedLists` and `OverloadedStrings`
can make the use of streams in place of lists quite convenient.
Along with these we can use combinators from `Streamly.Data.Stream` to perform
all list operations on pure streams.
Lists:
```haskell docspec
>>> replicate 10 1
[1,1,1,1,1,1,1,1,1,1]
>>> map (+1) $ replicate 10 1
[2,2,2,2,2,2,2,2,2,2]
>>> length $ replicate 10 1
10
```
Pure streams are almost identical:
```
>>> S.replicate 10 1 :: S.Stream Identity Int
fromList [1,1,1,1,1,1,1,1,1,1]
>>> S.map (+1) $ S.replicate 10 1 :: S.Stream Identity Int
fromList [2,2,2,2,2,2,2,2,2,2]
>>> S.fold F.length (S.replicate 10 1 :: S.Stream Identity Int)
10
```
## Monadic Operations
Lists have great performance as long as we perform only pure operations on
them. When monadic operations are performed on lists, they may accumulate
potentially unbounded or large lists in memory degrading performance massively.
Such "unsafe" list operations exist in `Control.Monad`, `Data.Traversable`, and
`Data.Foldable` in `base`. They are typically found with an `M` suffix.
Streamly provides monadic streams and the equivalents of the above mentioned
monadic list operations work on streams without any issues.
Unsafe monadic operations involving lists, run these example with `+RTS -s`
options:
```haskell unshared
import Control.Monad
main = do
xs <- replicateM 10000000 (pure 1)
ys <- mapM (\x -> return $ x + 1) xs
print $ length ys
```
Streams:
```haskell unshared
import qualified Streamly.Data.Stream as S
import qualified Streamly.Data.Fold as F
main = do
n <- S.fold F.length
$ S.mapM (\x -> return $ x + 1)
$ S.replicateM 10000000 (pure 1)
print n
```
## Splitting Operations
Another unsafe category of operations for lists is stream splitting operations
e.g. `lines`, `splitAt` and `group`. Such operations may also accumulate
unbounded data in memory.
Stream splitting operations in streamly are streaming in nature and can work
without accumulating any data in memory.
### Monadic Lists
Monadic streams are nothing but lists made monadic. We can construct streams
using monadic actions, just the way pure lists are constructed:
<!-- We are not type checking this -->
```
>>> import qualified Streamly.Data.StreamK as StreamK
>>> StreamK.toList $ getLine `StreamK.cons` getLine `StreamK.cons` StreamK.nil
hello
world
["hello","world"]
```
The monadic action `getLine` is executed twice in a sequence, the first one
gets "hello" and second one gets "world" from the terminal and a stream
consisting of those strings is produced.
## Concurrent Monadic Lists
Streamly streams are not just monadic lists but they are concurrent monadic
lists. All the monadic streaming operations provided by streamly are inherently
concurrent. Concurrent behavior can be enabled by just using an appropriate
modifying combinator, without any other change to the code.
The following code prints one element every second:
```haskell docspec
>>> import Control.Concurrent
>>> import qualified Streamly.Data.Stream.Prelude as S
>>> import qualified Streamly.Data.Fold as F
>>> func = S.mapM (\x -> threadDelay 1000000 >> print x) $ S.replicate 10 1
>>> main = S.fold F.drain func
```
To run it concurrently, depending on what you want to make concurrent, you can
use `parMapM` or `parBuffered`.
```haskell docspec
>>> func = S.parMapM id (\x -> threadDelay 1000000 >> print x) $ S.replicate 10 1
>>> main = S.fold F.drain func
```
The `parMapM` combinator now maps the monadic delay action concurrently on all
the stream elements. It prints all the 10 elements after one second because all
the delay actions run concurrently. Alternatively we can write:
```haskell docspec
>>> func = S.parReplicateM id 10 (threadDelay 1000000 >> print 1)
>>> main = S.fold F.drain func
```
Here, the `parReplicateM` operation replicates the action concurrently. In real
applications this could be a request to a web server that you may want to
perform multiple times concurrently.
## Performance: Streamly vs Lists
The following figures show the ratio of time and memory consumed by `[Int]`
(`base-4.12`) vs `Stream Identity Int`
([streamly@00c7613](https://github.com/composewell/streamly)) for exactly the
same operation. `5x` on the y axis means lists take 5 times more resources
compared to streamly. Whereas a `1/5x` means that lists take 5 times less
resources compared to streamly. We only show those operations that are at least
10% better or worse in one library compared to the other. The operations are
shown in a sorted order, from list's worst performing ones on the left to its
best ones on the right.
## Why use streams instead of lists?
By using monadic streams instead of lists you get the following benefits:
* Use just one library for pure or monadic lists. There is no difference in
pure or monadic code, its all the same.
* You can use a monadic action anywhere in the code e.g. printing a warning or
error message or any other effectful operations. This is not possible in pure
list code.
* You can make the code concurrent whenever you want without having to modify
it.
* You do not have the risk of using unsafe/accumulating list operations
degrading performance massively and resulting in space leaks.
* Streamly provides safe versions of partial list functions like `head`, `tail`
etc.
* You get better fusion and therefore better performance for many operations,
the only operation which is significantly faster for lists is `concatMap`.
## References
* [Data.List](https://hackage.haskell.org/package/base/docs/Data-List.html)
* [Control.Monad](http://hackage.haskell.org/package/base/docs/Control-Monad.html)
* [Data.Foldable](http://hackage.haskell.org/package/base/docs/Data-Foldable.html)
* [Data.Traversable](http://hackage.haskell.org/package/base/docs/Data-Traversable.html)