# Haskell Streams

List definitions:

```
data List a = Cons a (List a) | Nil
```

Stream definitions:

```
data Stream a = forall s. Stream (s -> Step a s) s -- ^ Note the existential quantification here
-- We do not care about the type of the underlying state
-- Only that it gives us values of type a
data Step a s = Done
| Yield a s
| Skip s
```

Recognize the similarities between `Stream`

data constructor and unfoldr

```
Stream :: forall s a. (s -> Step a, s) -> s -> Stream a
unfoldr :: forall s a. (s -> Maybe (a, s)) -> s -> [a]
```

Stream is **not a recursive structure**. You can see both `map`

and `fromList`

definitions for intuition:

```
map :: (a -> b) -> Stream a -> Stream b
map f (Stream next s) = Stream next' s
where
next s = case next of
Done -> Done
Skip s' -> Skip
Yield x s' -> Yield (f x) s'
fromList :: [a] -> Stream a
fromList ls = Stream next xs
where
next [] = Done
next (x:xs) = Yield x xs
```

Conversion to list is efficient as well since Haskell is lazy:

```
toList :: Stream a -> [a]
toList (Stream next s) = unfold s
where
unfold s1 = case next s of
Done -> []
Skip s' -> unfold s' -- Thunk'd
Yield x s' -> x : unfold s' -- Thunk'd
```

Usecases for streams:

References / Further reading: