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:

logo