{-# LANGUAGE GADTs, Rank2Types #-}

-- A difference list based implementation of a small part of the
-- Data.Stream interface from the stream-fusion package.

module Stream where

import Prelude hiding (concatMap)
import qualified Data.List as List

data Stream a where
    Stream :: { unStream :: forall r. (a -> r) -> [r] -> [r] } -> Stream a

empty :: Stream a
empty = Stream (\_ -> id)

singleton :: a -> Stream a
singleton x = Stream (\f -> (f x :))

fromList :: [a] -> Stream a
fromList xs = Stream (\f zs -> foldr (\x xs -> f x : xs) zs xs)

toList :: Stream a -> [a]
toList (Stream s) = s id []

instance Functor Stream where
    fmap f (Stream s) = Stream (\g -> s (g . f))

concatMap :: (a -> Stream b) -> Stream a -> Stream b
concatMap f g = Stream $ \h zs -> foldr (\x -> unStream (f x) h) zs (toList g)

filter :: (a -> Bool) -> Stream a -> Stream a
filter p = concatMap (\x -> if p x then singleton x else empty)

stream :: [a] -> Stream a
stream = fromList

foldl' :: (a -> b -> a) -> a -> Stream b -> a
foldl' f i s = List.foldl' f i (toList s)