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: