    -- | Streams are infinite lists. Most operations on streams are
    -- completely analogous to the definition in Data.List.
    --
    -- The functions provided in this package are fairly
    -- careful about totality, termination, and productivity.
    -- None of the functions should diverge, provided you adhere to the
    -- preconditions mentioned in the documentation.
    --
    -- Note: I get quite a lot of requests regarding a missing Traversable
    -- instance for Streams. This has been left out by design.

    module Data.Stream
       (
       -- * The type of streams
         Stream(..)
       -- * Basic functions
       , (<:>)
       , head
       , tail
       , inits
       , tails
       -- * Stream transformations
       , map
       , intersperse
       , interleave
       , scan
       , scan'
       , scan1
       , scan1'
       , transpose
       -- * Building streams
       , iterate
       , repeat
       , cycle
       , unfold
       , prefix
       -- * Extracting sublists
       , take
       , drop
       , splitAt
       , takeWhile
       , dropWhile
       , span
       , break
       , filter
       , partition
       , group
       -- * Sublist predicates
       , isPrefixOf
       -- * Indexing streams
       , (!!)
       , elemIndex
       , elemIndices
       , findIndex
       , findIndices
       -- * Zipping and unzipping streams
       , zip
       , zipWith
       , unzip
       , zip3
       , zipWith3
       , unzip3
       , distribute
       -- * Functions on streams of characters
       , words
       , unwords
       , lines
       , unlines
       -- * Converting to and from an infinite list
       , toList
       , fromList
       )
       where

    import Prelude hiding (head, tail, map, scanl, scanl1,
      iterate, take, drop, takeWhile,
      dropWhile, repeat, cycle, filter, (!!),
      zip, unzip, zipWith, zip3, unzip3, zipWith3,
      words,unwords,lines,unlines, break, span, splitAt)

    import Control.Applicative
    import Control.Monad (liftM2)
    import Data.Monoid (mappend)
    import Data.Char (isSpace)
    import Test.QuickCheck (Arbitrary, CoArbitrary, arbitrary, coarbitrary)
    import Test.LazySmallCheck (Serial, series, cons2)

    -- | An infinite sequence.
    --
    -- /Beware/: If you use any function from the @ Eq @ or @ Ord @
    -- class to compare two equal streams, these functions will diverge.

    data Stream a = Cons a (Stream a) deriving (Stream a -> Stream a -> Bool
    (Stream a -> Stream a -> Bool)
    -> (Stream a -> Stream a -> Bool) -> Eq (Stream a)
    forall a. Eq a => Stream a -> Stream a -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    /= :: Stream a -> Stream a -> Bool
    $c/= :: forall a. Eq a => Stream a -> Stream a -> Bool
    == :: Stream a -> Stream a -> Bool
    $c== :: forall a. Eq a => Stream a -> Stream a -> Bool
    Eq, Eq (Stream a)
    Eq (Stream a) =>
    (Stream a -> Stream a -> Ordering)
    -> (Stream a -> Stream a -> Bool)
    -> (Stream a -> Stream a -> Bool)
    -> (Stream a -> Stream a -> Bool)
    -> (Stream a -> Stream a -> Bool)
    -> (Stream a -> Stream a -> Stream a)
    -> (Stream a -> Stream a -> Stream a)
    -> Ord (Stream a)
    Stream a -> Stream a -> Bool
    Stream a -> Stream a -> Ordering
    Stream a -> Stream a -> Stream a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall a. Ord a => Eq (Stream a)
    forall a. Ord a => Stream a -> Stream a -> Bool
    forall a. Ord a => Stream a -> Stream a -> Ordering
    forall a. Ord a => Stream a -> Stream a -> Stream a
    min :: Stream a -> Stream a -> Stream a
    $cmin :: forall a. Ord a => Stream a -> Stream a -> Stream a
    max :: Stream a -> Stream a -> Stream a
    $cmax :: forall a. Ord a => Stream a -> Stream a -> Stream a
    >= :: Stream a -> Stream a -> Bool
    $c>= :: forall a. Ord a => Stream a -> Stream a -> Bool
    > :: Stream a -> Stream a -> Bool
    $c> :: forall a. Ord a => Stream a -> Stream a -> Bool
    <= :: Stream a -> Stream a -> Bool
    $c<= :: forall a. Ord a => Stream a -> Stream a -> Bool
    < :: Stream a -> Stream a -> Bool
    $c< :: forall a. Ord a => Stream a -> Stream a -> Bool
    compare :: Stream a -> Stream a -> Ordering
    $ccompare :: forall a. Ord a => Stream a -> Stream a -> Ordering
    $cp1Ord :: forall a. Ord a => Eq (Stream a)
    Ord)

    infixr 5 `Cons`

    instance Functor Stream where
      fmap :: (a -> b) -> Stream a -> Stream b
    fmap f :: a -> b
    f ~(Cons x :: a
    x xs :: Stream a
    xs) = b -> Stream b -> Stream b
    forall a. a -> Stream a -> Stream a
    Cons (a -> b
    f a
    x) ((a -> b) -> Stream a -> Stream b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    f Stream a
    xs)

    instance Applicative Stream where
      pure :: a -> Stream a
    pure = a -> Stream a
    forall a. a -> Stream a
    repeat
      <*> :: Stream (a -> b) -> Stream a -> Stream b
    (<*>) = ((a -> b) -> a -> b) -> Stream (a -> b) -> Stream a -> Stream b
    forall a b c. (a -> b -> c) -> Stream a -> Stream b -> Stream c
    zipWith (a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    ($)

    instance Monad Stream where
      return :: a -> Stream a
    return = a -> Stream a
    forall a. a -> Stream a
    repeat
      xs :: Stream a
    xs >>= :: Stream a -> (a -> Stream b) -> Stream b
    >>= f :: a -> Stream b
    f = Stream (Stream b) -> Stream b
    forall a. Stream (Stream a) -> Stream a
    join ((a -> Stream b) -> Stream a -> Stream (Stream b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Stream b
    f Stream a
    xs)
        where
          join :: Stream (Stream a) -> Stream a
          join :: Stream (Stream a) -> Stream a
    join ~(Cons xs :: Stream a
    xs xss :: Stream (Stream a)
    xss) = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons (Stream a -> a
    forall a. Stream a -> a
    head Stream a
    xs) (Stream (Stream a) -> Stream a
    forall a. Stream (Stream a) -> Stream a
    join ((Stream a -> Stream a) -> Stream (Stream a) -> Stream (Stream a)
    forall a b. (a -> b) -> Stream a -> Stream b
    map Stream a -> Stream a
    forall a. Stream a -> Stream a
    tail Stream (Stream a)
    xss))

    instance Arbitrary a => Arbitrary (Stream a) where
      arbitrary :: Gen (Stream a)
    arbitrary = (a -> Stream a -> Stream a)
    -> Gen a -> Gen (Stream a) -> Gen (Stream a)
    forall (m :: * -> *) a1 a2 r.
    Monad m =>
    (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
    liftM2 a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons Gen a
    forall a. Arbitrary a => Gen a
    arbitrary Gen (Stream a)
    forall a. Arbitrary a => Gen a
    arbitrary

    instance CoArbitrary a => CoArbitrary (Stream a) where
      coarbitrary :: Stream a -> Gen b -> Gen b
    coarbitrary xs :: Stream a
    xs gen :: Gen b
    gen = do
        Int
    n <- Gen Int
    forall a. Arbitrary a => Gen a
    arbitrary
        [a] -> Gen b -> Gen b
    forall a b. CoArbitrary a => a -> Gen b -> Gen b
    coarbitrary (Int -> Stream a -> [a]
    forall a. Int -> Stream a -> [a]
    take (Int -> Int
    forall a. Num a => a -> a
    abs Int
    n) Stream a
    xs) Gen b
    gen

    instance Serial a => Serial (Stream a) where
        series :: Series (Stream a)
    series = (a -> Stream a -> Stream a) -> Series (Stream a)
    forall a b c. (Serial a, Serial b) => (a -> b -> c) -> Series c
    cons2 a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons

    -- | A Show instance for Streams that takes the right associativity into
    -- account and so doesn't put parenthesis around the tail of the Stream.
    -- Note that 'show' returns an infinite 'String'.
    instance Show a => Show (Stream a) where
      showsPrec :: Int -> Stream a -> ShowS
    showsPrec p :: Int
    p (Cons x :: a
    x xs :: Stream a
    xs) =
        Bool -> ShowS -> ShowS
    showParen (Int
    p Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    consPrecedence)   (ShowS -> ShowS) -> ShowS -> ShowS
    forall a b. (a -> b) -> a -> b
    $
        Int -> a -> ShowS
    forall a. Show a => Int -> a -> ShowS
    showsPrec (Int
    consPrecedence Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + 1) a
    x ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
        String -> ShowS
    showString " <:> "               ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
        Int -> Stream a -> ShowS
    forall a. Show a => Int -> a -> ShowS
    showsPrec Int
    consPrecedence Stream a
    xs
        where
          consPrecedence :: Int
    consPrecedence = 5 :: Int

    infixr 5 <:>
    -- | The @ \<:\> @ operator is an infix version of the 'Cons'
    -- constructor.
    (<:>) :: a -> Stream a -> Stream a
    <:> :: a -> Stream a -> Stream a
    (<:>) = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons

    -- | Extract the first element of the sequence.
    head :: Stream a -> a
    head :: Stream a -> a
    head (Cons x :: a
    x _ ) = a
    x

    -- | Extract the sequence following the head of the stream.
    tail :: Stream a -> Stream a
    tail :: Stream a -> Stream a
    tail (Cons _ xs :: Stream a
    xs) = Stream a
    xs

    -- | The 'inits' function takes a stream @xs@ and returns all the
    -- finite prefixes of @xs@.
    --
    -- Note that this 'inits' is lazier then @Data.List.inits@:
    --
    -- > inits _|_ = [] ::: _|_
    --
    -- while for @Data.List.inits@:
    --
    -- > inits _|_ = _|_

    inits :: Stream a -> Stream ([a])
    inits :: Stream a -> Stream [a]
    inits xs :: Stream a
    xs = [a] -> Stream [a] -> Stream [a]
    forall a. a -> Stream a -> Stream a
    Cons [] (([a] -> [a]) -> Stream [a] -> Stream [a]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Stream a -> a
    forall a. Stream a -> a
    head Stream a
    xs a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :) (Stream a -> Stream [a]
    forall a. Stream a -> Stream [a]
    inits (Stream a -> Stream a
    forall a. Stream a -> Stream a
    tail Stream a
    xs)))

    -- | The 'tails' function takes a stream @xs@ and returns all the
    -- suffixes of @xs@.
    tails :: Stream a -> Stream (Stream a)
    tails :: Stream a -> Stream (Stream a)
    tails xs :: Stream a
    xs = Stream a -> Stream (Stream a) -> Stream (Stream a)
    forall a. a -> Stream a -> Stream a
    Cons Stream a
    xs (Stream a -> Stream (Stream a)
    forall a. Stream a -> Stream (Stream a)
    tails (Stream a -> Stream a
    forall a. Stream a -> Stream a
    tail Stream a
    xs))

    -- | Apply a function uniformly over all elements of a sequence.
    map :: (a -> b) -> Stream a -> Stream b
    map :: (a -> b) -> Stream a -> Stream b
    map f :: a -> b
    f ~(Cons x :: a
    x xs :: Stream a
    xs) = b -> Stream b -> Stream b
    forall a. a -> Stream a -> Stream a
    Cons (a -> b
    f a
    x) ((a -> b) -> Stream a -> Stream b
    forall a b. (a -> b) -> Stream a -> Stream b
    map a -> b
    f Stream a
    xs)

    -- | 'intersperse' @y@ @xs@ creates an alternating stream of
    -- elements from @xs@ and @y@.
    intersperse :: a -> Stream a -> Stream a
    intersperse :: a -> Stream a -> Stream a
    intersperse y :: a
    y ~(Cons x :: a
    x xs :: Stream a
    xs) = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x (a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    y (a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    intersperse a
    y Stream a
    xs))

    -- | Interleave two Streams @xs@ and @ys@, alternating elements
    -- from each list.
    --
    -- > [x1,x2,...] `interleave` [y1,y2,...] == [x1,y1,x2,y2,...]
    interleave :: Stream a -> Stream a -> Stream a
    interleave :: Stream a -> Stream a -> Stream a
    interleave ~(Cons x :: a
    x xs :: Stream a
    xs) ys :: Stream a
    ys = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x (Stream a -> Stream a -> Stream a
    forall a. Stream a -> Stream a -> Stream a
    interleave Stream a
    ys Stream a
    xs)

    -- | 'scan' yields a stream of successive reduced values from:
    --
    -- > scan f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
    scan :: (a -> b -> a) -> a -> Stream b -> Stream a
    scan :: (a -> b -> a) -> a -> Stream b -> Stream a
    scan f :: a -> b -> a
    f z :: a
    z ~(Cons x :: b
    x xs :: Stream b
    xs) =  a
    z a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    <:> (a -> b -> a) -> a -> Stream b -> Stream a
    forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
    scan a -> b -> a
    f (a -> b -> a
    f a
    z b
    x) Stream b
    xs

    -- | @scan'@ is a strict scan.
    scan' :: (a -> b -> a) -> a -> Stream b -> Stream a
    scan' :: (a -> b -> a) -> a -> Stream b -> Stream a
    scan' f :: a -> b -> a
    f z :: a
    z xs :: Stream b
    xs =  a
    z a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    <:> ((a -> b -> a) -> a -> Stream b -> Stream a
    forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
    scan' a -> b -> a
    f (a -> Stream b -> Stream a) -> a -> Stream b -> Stream a
    forall a b. (a -> b) -> a -> b
    $! (a -> b -> a
    f a
    z (Stream b -> b
    forall a. Stream a -> a
    head Stream b
    xs))) (Stream b -> Stream b
    forall a. Stream a -> Stream a
    tail Stream b
    xs)

    -- | 'scan1' is a variant of 'scan' that has no starting value argument:
    --
    -- > scan1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
    scan1 :: (a -> a -> a) -> Stream a -> Stream a
    scan1 :: (a -> a -> a) -> Stream a -> Stream a
    scan1 f :: a -> a -> a
    f ~(Cons x :: a
    x xs :: Stream a
    xs) = (a -> a -> a) -> a -> Stream a -> Stream a
    forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
    scan a -> a -> a
    f a
    x Stream a
    xs

    -- | @scan1'@ is a strict scan that has no starting value.
    scan1' :: (a -> a -> a) -> Stream a -> Stream a
    scan1' :: (a -> a -> a) -> Stream a -> Stream a
    scan1' f :: a -> a -> a
    f ~(Cons x :: a
    x xs :: Stream a
    xs) = (a -> a -> a) -> a -> Stream a -> Stream a
    forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
    scan' a -> a -> a
    f a
    x Stream a
    xs

    -- | 'transpose' computes the transposition of a stream of streams.
    transpose :: Stream (Stream a) -> Stream (Stream a)
    transpose :: Stream (Stream a) -> Stream (Stream a)
    transpose ~(Cons (Cons x :: a
    x xs :: Stream a
    xs) yss :: Stream (Stream a)
    yss) =
        (a
    x a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    <:> (Stream a -> a) -> Stream (Stream a) -> Stream a
    forall a b. (a -> b) -> Stream a -> Stream b
    map Stream a -> a
    forall a. Stream a -> a
    head Stream (Stream a)
    yss) Stream a -> Stream (Stream a) -> Stream (Stream a)
    forall a. a -> Stream a -> Stream a
    <:> Stream (Stream a) -> Stream (Stream a)
    forall a. Stream (Stream a) -> Stream (Stream a)
    transpose (Stream a
    xs Stream a -> Stream (Stream a) -> Stream (Stream a)
    forall a. a -> Stream a -> Stream a
    <:> (Stream a -> Stream a) -> Stream (Stream a) -> Stream (Stream a)
    forall a b. (a -> b) -> Stream a -> Stream b
    map Stream a -> Stream a
    forall a. Stream a -> Stream a
    tail Stream (Stream a)
    yss)

    -- | 'iterate' @f@ @x@ function produces the infinite sequence
    -- of repeated applications of @f@ to @x@.
    --
    -- > iterate f x = [x, f x, f (f x), ..]
    iterate :: (a -> a) -> a -> Stream a
    iterate :: (a -> a) -> a -> Stream a
    iterate f :: a -> a
    f x :: a
    x = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x ((a -> a) -> a -> Stream a
    forall a. (a -> a) -> a -> Stream a
    iterate a -> a
    f (a -> a
    f a
    x))

    -- | The 'prefix' function adds a list as a prefix to an existing
    -- stream. If the list is infinite, it is converted to a Stream and
    -- the second argument is ignored.
    prefix :: [a] -> Stream a -> Stream a
    prefix :: [a] -> Stream a -> Stream a
    prefix xs :: [a]
    xs ys :: Stream a
    ys = (a -> Stream a -> Stream a) -> Stream a -> [a] -> Stream a
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons Stream a
    ys [a]
    xs

    -- | 'repeat' @x@ returns a constant stream, where all elements are
    -- equal to @x@.
    repeat :: a -> Stream a
    repeat :: a -> Stream a
    repeat x :: a
    x = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x (a -> Stream a
    forall a. a -> Stream a
    repeat a
    x)

    -- | 'cycle' @xs@ returns the infinite repetition of @xs@:
    --
    -- > cycle [1,2,3] = Cons 1 (Cons 2 (Cons 3 (Cons 1 (Cons 2 ...
    cycle :: [a] -> Stream a
    cycle :: [a] -> Stream a
    cycle xs :: [a]
    xs = (a -> Stream a -> Stream a) -> Stream a -> [a] -> Stream a
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons ([a] -> Stream a
    forall a. [a] -> Stream a
    cycle [a]
    xs) [a]
    xs

    -- | The unfold function is similar to the unfold for lists. Note
    -- there is no base case: all streams must be infinite.
    unfold :: (c -> (a,c)) -> c -> Stream a
    unfold :: (c -> (a, c)) -> c -> Stream a
    unfold f :: c -> (a, c)
    f c :: c
    c =
      let (x :: a
    x,d :: c
    d) = c -> (a, c)
    f c
    c
      in a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x ((c -> (a, c)) -> c -> Stream a
    forall c a. (c -> (a, c)) -> c -> Stream a
    unfold c -> (a, c)
    f c
    d)

    -- | 'take' @n@ @xs@ returns the first @n@ elements of @xs@.
    --
    -- /Beware/: passing a negative integer as the first argument will
    -- cause an error.
    take :: Int -> Stream a  -> [a]
    take :: Int -> Stream a -> [a]
    take n :: Int
    n ~(Cons x :: a
    x xs :: Stream a
    xs)
      | Int
    n Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0    = []
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0     =  a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : (Int -> Stream a -> [a]
    forall a. Int -> Stream a -> [a]
    take (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - 1) Stream a
    xs)
      | Bool
    otherwise = String -> [a]
    forall a. HasCallStack => String -> a
    error "Stream.take: negative argument."

    -- | 'drop' @n@ @xs@ drops the first @n@ elements off the front of
    -- the sequence @xs@.
    --
    -- /Beware/: passing a negative integer as the first argument will
    -- cause an error.
    drop :: Int -> Stream a -> Stream a
    drop :: Int -> Stream a -> Stream a
    drop n :: Int
    n xs :: Stream a
    xs
      | Int
    n Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0    = Stream a
    xs
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0     = Int -> Stream a -> Stream a
    forall a. Int -> Stream a -> Stream a
    drop (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - 1) (Stream a -> Stream a
    forall a. Stream a -> Stream a
    tail Stream a
    xs)
      | Bool
    otherwise = String -> Stream a
    forall a. HasCallStack => String -> a
    error "Stream.drop: negative argument."

    -- | The 'splitAt' function takes an integer @n@ and a stream @xs@
    -- and returns a pair consisting of the prefix of @xs@ of length
    -- @n@ and the remaining stream immediately following this prefix.
    --
    -- /Beware/: passing a negative integer as the first argument will
    -- cause an error.
    splitAt :: Int -> Stream a -> ([a], Stream a)
    splitAt :: Int -> Stream a -> ([a], Stream a)
    splitAt n :: Int
    n xs :: Stream a
    xs
      | Int
    n Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0    = ([],Stream a
    xs)
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0     = let (prefix :: [a]
    prefix,rest :: Stream a
    rest) = Int -> Stream a -> ([a], Stream a)
    forall a. Int -> Stream a -> ([a], Stream a)
    splitAt (Int
    nInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -1) (Stream a -> Stream a
    forall a. Stream a -> Stream a
    tail Stream a
    xs)
                    in (Stream a -> a
    forall a. Stream a -> a
    head Stream a
    xs a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    prefix, Stream a
    rest)
      | Bool
    otherwise = String -> ([a], Stream a)
    forall a. HasCallStack => String -> a
    error "Stream.splitAt negative argument."

    -- | 'takeWhile' @p@ @xs@ returns the longest prefix of the stream
    -- @xs@ for which the predicate @p@ holds.
    takeWhile :: (a -> Bool) -> Stream a -> [a]
    takeWhile :: (a -> Bool) -> Stream a -> [a]
    takeWhile p :: a -> Bool
    p (Cons x :: a
    x xs :: Stream a
    xs)
      | a -> Bool
    p a
    x       = a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : (a -> Bool) -> Stream a -> [a]
    forall a. (a -> Bool) -> Stream a -> [a]
    takeWhile a -> Bool
    p Stream a
    xs
      | Bool
    otherwise = []

    -- | 'dropWhile' @p@ @xs@ returns the suffix remaining after
    -- 'takeWhile' @p@ @xs@.
    --
    -- /Beware/: this function may diverge if every element of @xs@
    -- satisfies @p@, e.g.  @dropWhile even (repeat 0)@ will loop.
    dropWhile :: (a -> Bool) -> Stream a -> Stream a
    dropWhile :: (a -> Bool) -> Stream a -> Stream a
    dropWhile p :: a -> Bool
    p ~(Cons x :: a
    x xs :: Stream a
    xs)
      | a -> Bool
    p a
    x       = (a -> Bool) -> Stream a -> Stream a
    forall a. (a -> Bool) -> Stream a -> Stream a
    dropWhile a -> Bool
    p Stream a
    xs
      | Bool
    otherwise = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x Stream a
    xs

    -- | 'span' @p@ @xs@ returns the longest prefix of @xs@ that satisfies
    -- @p@, together with the remainder of the stream.
    --
    -- /Beware/: this function may diverge if every element of @xs@
    -- satisfies @p@, e.g.  @span even (repeat 0)@ will loop.
    span :: (a -> Bool) -> Stream a -> ([a], Stream a)
    span :: (a -> Bool) -> Stream a -> ([a], Stream a)
    span p :: a -> Bool
    p (Cons x :: a
    x xs :: Stream a
    xs)
      | a -> Bool
    p a
    x       = let (trues :: [a]
    trues, falses :: Stream a
    falses) = (a -> Bool) -> Stream a -> ([a], Stream a)
    forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
    span a -> Bool
    p Stream a
    xs
                    in (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    trues, Stream a
    falses)
      | Bool
    otherwise = ([], a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x Stream a
    xs)

    -- | The 'break' @p@ function is equivalent to 'span' @not . p@.
    --
    -- /Beware/: this function may diverge for the same reason as @span@.
    break :: (a -> Bool) -> Stream a -> ([a], Stream a)
    break :: (a -> Bool) -> Stream a -> ([a], Stream a)
    break p :: a -> Bool
    p = (a -> Bool) -> Stream a -> ([a], Stream a)
    forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
    span (Bool -> Bool
    not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Bool
    p)

    -- | 'filter' @p@ @xs@, removes any elements from @xs@ that do not satisfy @p@.
    --
    -- /Beware/: this function may diverge if there is no element of
    -- @xs@ that satisfies @p@, e.g.  @filter odd (repeat 0)@ will loop.
    filter :: (a -> Bool) -> Stream a -> Stream a
    filter :: (a -> Bool) -> Stream a -> Stream a
    filter p :: a -> Bool
    p ~(Cons x :: a
    x xs :: Stream a
    xs)
      | a -> Bool
    p a
    x       = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x ((a -> Bool) -> Stream a -> Stream a
    forall a. (a -> Bool) -> Stream a -> Stream a
    filter a -> Bool
    p Stream a
    xs)
      | Bool
    otherwise = (a -> Bool) -> Stream a -> Stream a
    forall a. (a -> Bool) -> Stream a -> Stream a
    filter a -> Bool
    p Stream a
    xs

    -- | The 'partition' function takes a predicate @p@ and a stream
    -- @xs@, and returns a pair of streams. The first stream corresponds
    -- to the elements of @xs@ for which @p@ holds; the second stream
    -- corresponds to the elements of @xs@ for which @p@ does not hold.
    --
    -- /Beware/: One of the elements of the tuple may be undefined. For
    -- example, @fst (partition even (repeat 0)) == repeat 0@; on the
    -- other hand @snd (partition even (repeat 0))@ is undefined.
    partition :: (a -> Bool) -> Stream a -> (Stream a, Stream a)
    partition :: (a -> Bool) -> Stream a -> (Stream a, Stream a)
    partition p :: a -> Bool
    p ~(Cons x :: a
    x xs :: Stream a
    xs) =
      let (trues :: Stream a
    trues,falses :: Stream a
    falses) = (a -> Bool) -> Stream a -> (Stream a, Stream a)
    forall a. (a -> Bool) -> Stream a -> (Stream a, Stream a)
    partition a -> Bool
    p Stream a
    xs
      in if a -> Bool
    p a
    x then (a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x Stream a
    trues, Stream a
    falses)
                else (Stream a
    trues, a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x Stream a
    falses)

    -- | The 'group' function takes a stream and returns a stream of
    -- lists such that flattening the resulting stream is equal to the
    -- argument.  Moreover, each sublist in the resulting stream
    -- contains only equal elements.  For example,
    --
    -- > group $ cycle "Mississippi" = "M" ::: "i" ::: "ss" ::: "i" ::: "ss" ::: "i" ::: "pp" ::: "i" ::: "M" ::: "i" ::: ...
    group :: Eq a => Stream a -> Stream [a]
    group :: Stream a -> Stream [a]
    group ~(Cons x :: a
    x ys :: Stream a
    ys) = let (xs :: [a]
    xs, zs :: Stream a
    zs) = (a -> Bool) -> Stream a -> ([a], Stream a)
    forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
    span (\y :: a
    y -> a
    x a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    y) Stream a
    ys
                        in (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    xs) [a] -> Stream [a] -> Stream [a]
    forall a. a -> Stream a -> Stream a
    <:> Stream a -> Stream [a]
    forall a. Eq a => Stream a -> Stream [a]
    group Stream a
    zs

    -- | The 'isPrefix' function returns @True@ if the first argument is
    -- a prefix of the second.
    isPrefixOf :: Eq a => [a] -> Stream a -> Bool
    isPrefixOf :: [a] -> Stream a -> Bool
    isPrefixOf [] _ = Bool
    True
    isPrefixOf (y :: a
    y:ys :: [a]
    ys) (Cons x :: a
    x xs :: Stream a
    xs)
      | a
    y a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    x    = [a] -> Stream a -> Bool
    forall a. Eq a => [a] -> Stream a -> Bool
    isPrefixOf [a]
    ys Stream a
    xs
      | Bool
    otherwise = Bool
    False

    -- | @xs !! n@ returns the element of the stream @xs@ at index
    -- @n@. Note that the head of the stream has index 0.
    --
    -- /Beware/: passing a negative integer as the first argument will cause
    -- an error.
    (!!) :: Stream a -> Int -> a
    !! :: Stream a -> Int -> a
    (!!) (Cons x :: a
    x xs :: Stream a
    xs) n :: Int
    n
      | Int
    n Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0    = a
    x
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0     = Stream a
    xs Stream a -> Int -> a
    forall a. Stream a -> Int -> a
    !! (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - 1)
      | Bool
    otherwise = String -> a
    forall a. HasCallStack => String -> a
    error "Stream.!! negative argument"

    -- | The 'elemIndex' function returns the index of the first element
    -- in the given stream which is equal (by '==') to the query element,
    --
    -- /Beware/: 'elemIndex' @x@ @xs@ will diverge if none of the elements
    -- of @xs@ equal @x@.
    elemIndex :: Eq a => a -> Stream a -> Int
    elemIndex :: a -> Stream a -> Int
    elemIndex x :: a
    x = (a -> Bool) -> Stream a -> Int
    forall a. (a -> Bool) -> Stream a -> Int
    findIndex (\y :: a
    y -> a
    x a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    y)

    -- | The 'elemIndices' function extends 'elemIndex', by returning the
    -- indices of all elements equal to the query element, in ascending order.
    --
    -- /Beware/: 'elemIndices' @x@ @xs@ will diverge if any suffix of
    -- @xs@ does not contain @x@.
    elemIndices :: Eq a => a -> Stream a -> Stream Int
    elemIndices :: a -> Stream a -> Stream Int
    elemIndices x :: a
    x = (a -> Bool) -> Stream a -> Stream Int
    forall a. (a -> Bool) -> Stream a -> Stream Int
    findIndices (a
    xa -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    ==)

    -- | The 'findIndex' function takes a predicate and a stream and returns
    -- the index of the first element in the stream that satisfies the predicate,
    --
    -- /Beware/: 'findIndex' @p@ @xs@ will diverge if none of the elements of
    -- @xs@ satisfy @p@.
    findIndex :: (a -> Bool) -> Stream a -> Int
    findIndex :: (a -> Bool) -> Stream a -> Int
    findIndex p :: a -> Bool
    p = Int -> Stream a -> Int
    forall a. Num a => a -> Stream a -> a
    indexFrom 0
        where
        indexFrom :: a -> Stream a -> a
    indexFrom ix :: a
    ix (Cons x :: a
    x xs :: Stream a
    xs)
          | a -> Bool
    p a
    x       = a
    ix
          | Bool
    otherwise = (a -> Stream a -> a
    indexFrom (a -> Stream a -> a) -> a -> Stream a -> a
    forall a b. (a -> b) -> a -> b
    $! (a
    ix a -> a -> a
    forall a. Num a => a -> a -> a
    + 1)) Stream a
    xs

    -- | The 'findIndices' function extends 'findIndex', by returning the
    -- indices of all elements satisfying the predicate, in ascending
    -- order.
    --
    -- /Beware/: 'findIndices' @p@ @xs@ will diverge if all the elements
    -- of any suffix of @xs@ fails to satisfy @p@.
    findIndices :: (a -> Bool) -> Stream a -> Stream Int
    findIndices :: (a -> Bool) -> Stream a -> Stream Int
    findIndices p :: a -> Bool
    p = Int -> Stream a -> Stream Int
    forall a. Num a => a -> Stream a -> Stream a
    indicesFrom 0
        where
        indicesFrom :: a -> Stream a -> Stream a
    indicesFrom ix :: a
    ix (Cons x :: a
    x xs :: Stream a
    xs) =
          let ixs :: Stream a
    ixs = (a -> Stream a -> Stream a
    indicesFrom (a -> Stream a -> Stream a) -> a -> Stream a -> Stream a
    forall a b. (a -> b) -> a -> b
    $! (a
    ixa -> a -> a
    forall a. Num a => a -> a -> a
    +1)) Stream a
    xs
          in if a -> Bool
    p a
    x then a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    ix Stream a
    ixs else Stream a
    ixs

    -- | The 'zip' function takes two streams and returns the stream of
    -- pairs obtained by pairing elements at the same position in both
    -- argument streams.
    zip :: Stream a -> Stream b -> Stream (a,b)
    zip :: Stream a -> Stream b -> Stream (a, b)
    zip ~(Cons x :: a
    x xs :: Stream a
    xs) ~(Cons y :: b
    y ys :: Stream b
    ys) = (a, b) -> Stream (a, b) -> Stream (a, b)
    forall a. a -> Stream a -> Stream a
    Cons (a
    x,b
    y) (Stream a -> Stream b -> Stream (a, b)
    forall a b. Stream a -> Stream b -> Stream (a, b)
    zip Stream a
    xs Stream b
    ys)

    -- | The 'zip3' function behaves as the 'zip' function, but works on
    -- three streams.
    zip3 :: Stream a -> Stream b -> Stream c -> Stream (a,b,c)
    zip3 :: Stream a -> Stream b -> Stream c -> Stream (a, b, c)
    zip3 ~(Cons x :: a
    x xs :: Stream a
    xs) ~(Cons y :: b
    y ys :: Stream b
    ys) ~(Cons z :: c
    z zs :: Stream c
    zs) = (a, b, c) -> Stream (a, b, c) -> Stream (a, b, c)
    forall a. a -> Stream a -> Stream a
    Cons (a
    x,b
    y,c
    z) (Stream a -> Stream b -> Stream c -> Stream (a, b, c)
    forall a b c. Stream a -> Stream b -> Stream c -> Stream (a, b, c)
    zip3 Stream a
    xs Stream b
    ys Stream c
    zs)

    -- | The 'zipWith' function generalizes 'zip'. Rather than tupling
    -- the functions, the elements are combined using the function
    -- passed as the first argument to 'zipWith'.
    zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
    zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
    zipWith f :: a -> b -> c
    f ~(Cons x :: a
    x xs :: Stream a
    xs) ~(Cons y :: b
    y ys :: Stream b
    ys) = c -> Stream c -> Stream c
    forall a. a -> Stream a -> Stream a
    Cons (a -> b -> c
    f a
    x b
    y) ((a -> b -> c) -> Stream a -> Stream b -> Stream c
    forall a b c. (a -> b -> c) -> Stream a -> Stream b -> Stream c
    zipWith a -> b -> c
    f Stream a
    xs Stream b
    ys)

    -- | The 'zipWith3' behaves as 'zipWith' but takes three stream
    -- arguments.
    zipWith3 :: (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d
    zipWith3 :: (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d
    zipWith3 f :: a -> b -> c -> d
    f ~(Cons x :: a
    x xs :: Stream a
    xs) ~(Cons y :: b
    y ys :: Stream b
    ys) (Cons z :: c
    z zs :: Stream c
    zs) = d -> Stream d -> Stream d
    forall a. a -> Stream a -> Stream a
    Cons (a -> b -> c -> d
    f a
    x b
    y c
    z) ((a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d
    forall a b c d.
    (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d
    zipWith3 a -> b -> c -> d
    f Stream a
    xs Stream b
    ys Stream c
    zs)

    -- | The 'distribute' function is similar to the 'sequenceA' function
    -- defined in Data.Traversable. Since 'Streams' are not 'Foldable' in
    -- general, there is no 'Traversable' instance for streams. They do
    -- support a similar notion that only requires the outer type
    -- constructor to be functorial.
    distribute :: (Functor f) => f (Stream a) -> Stream (f a)
    distribute :: f (Stream a) -> Stream (f a)
    distribute t :: f (Stream a)
    t = f a -> Stream (f a) -> Stream (f a)
    forall a. a -> Stream a -> Stream a
    Cons ((Stream a -> a) -> f (Stream a) -> f a
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Stream a -> a
    forall a. Stream a -> a
    head f (Stream a)
    t) (f (Stream a) -> Stream (f a)
    forall (f :: * -> *) a. Functor f => f (Stream a) -> Stream (f a)
    distribute ((Stream a -> Stream a) -> f (Stream a) -> f (Stream a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Stream a -> Stream a
    forall a. Stream a -> Stream a
    tail f (Stream a)
    t))

    -- | The 'unzip' function is the inverse of the 'zip' function.
    unzip :: Stream (a,b) -> (Stream a, Stream b)
    unzip :: Stream (a, b) -> (Stream a, Stream b)
    unzip ~(Cons (x :: a
    x,y :: b
    y) xys :: Stream (a, b)
    xys) = (a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x ((Stream a, Stream b) -> Stream a
    forall a b. (a, b) -> a
    fst (Stream (a, b) -> (Stream a, Stream b)
    forall a b. Stream (a, b) -> (Stream a, Stream b)
    unzip Stream (a, b)
    xys)),
                                    b -> Stream b -> Stream b
    forall a. a -> Stream a -> Stream a
    Cons b
    y ((Stream a, Stream b) -> Stream b
    forall a b. (a, b) -> b
    snd (Stream (a, b) -> (Stream a, Stream b)
    forall a b. Stream (a, b) -> (Stream a, Stream b)
    unzip Stream (a, b)
    xys)))

    -- | The 'unzip3' function is the inverse of the 'zip' function.
    unzip3 :: Stream (a,b,c) -> (Stream a, Stream b, Stream c)
    unzip3 :: Stream (a, b, c) -> (Stream a, Stream b, Stream c)
    unzip3 ~(Cons (x :: a
    x,y :: b
    y,z :: c
    z) xyzs :: Stream (a, b, c)
    xyzs) =  ( a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x ((Stream a, Stream b, Stream c) -> Stream a
    forall a b c. (a, b, c) -> a
    fst3 (Stream (a, b, c) -> (Stream a, Stream b, Stream c)
    forall a b c. Stream (a, b, c) -> (Stream a, Stream b, Stream c)
    unzip3 Stream (a, b, c)
    xyzs))
                                   , b -> Stream b -> Stream b
    forall a. a -> Stream a -> Stream a
    Cons b
    y ((Stream a, Stream b, Stream c) -> Stream b
    forall a b c. (a, b, c) -> b
    snd3 (Stream (a, b, c) -> (Stream a, Stream b, Stream c)
    forall a b c. Stream (a, b, c) -> (Stream a, Stream b, Stream c)
    unzip3 Stream (a, b, c)
    xyzs))
                                   , c -> Stream c -> Stream c
    forall a. a -> Stream a -> Stream a
    Cons c
    z ((Stream a, Stream b, Stream c) -> Stream c
    forall a b c. (a, b, c) -> c
    thd3 (Stream (a, b, c) -> (Stream a, Stream b, Stream c)
    forall a b c. Stream (a, b, c) -> (Stream a, Stream b, Stream c)
    unzip3 Stream (a, b, c)
    xyzs)))
      where
      fst3 :: (a,b,c) -> a
      fst3 :: (a, b, c) -> a
    fst3 (x :: a
    x,_,_) = a
    x
      snd3 :: (a,b,c) -> b
      snd3 :: (a, b, c) -> b
    snd3 (_,y :: b
    y,_) = b
    y
      thd3 :: (a,b,c) -> c
      thd3 :: (a, b, c) -> c
    thd3 (_,_,z :: c
    z) = c
    z

    -- | The 'words' function breaks a stream of characters into a
    -- stream of words, which were delimited by white space.
    --
    -- /Beware/: if the stream of characters @xs@ does not contain white
    -- space, accessing the tail of @words xs@ will loop.
    words :: Stream Char -> Stream String
    words :: Stream Char -> Stream String
    words xs :: Stream Char
    xs = let (w :: String
    w, ys :: Stream Char
    ys) = (Char -> Bool) -> Stream Char -> (String, Stream Char)
    forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
    break Char -> Bool
    isSpace Stream Char
    xs
                     in String -> Stream String -> Stream String
    forall a. a -> Stream a -> Stream a
    Cons String
    w (Stream Char -> Stream String
    words Stream Char
    ys)

    -- | The 'unwords' function is an inverse operation to 'words'. It
    -- joins words with separating spaces.
    unwords :: Stream String -> Stream Char
    unwords :: Stream String -> Stream Char
    unwords ~(Cons x :: String
    x xs :: Stream String
    xs) = (Char -> Stream Char -> Stream Char)
    -> Stream Char -> String -> Stream Char
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr Char -> Stream Char -> Stream Char
    forall a. a -> Stream a -> Stream a
    Cons (Char -> Stream Char -> Stream Char
    forall a. a -> Stream a -> Stream a
    Cons ' ' (Stream String -> Stream Char
    unwords Stream String
    xs)) String
    x

    -- | The 'lines' function breaks a stream of characters into a list
    -- of strings at newline characters. The resulting strings do not
    -- contain newlines.
    --
    -- /Beware/: if the stream of characters @xs@ does not contain
    -- newline characters, accessing the tail of @lines xs@ will loop.
    lines :: Stream Char -> Stream String
    lines :: Stream Char -> Stream String
    lines xs :: Stream Char
    xs = let (l :: String
    l, ys :: Stream Char
    ys) = (Char -> Bool) -> Stream Char -> (String, Stream Char)
    forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
    break (Char -> Char -> Bool
    forall a. Eq a => a -> a -> Bool
    == '\n') Stream Char
    xs
                     in String -> Stream String -> Stream String
    forall a. a -> Stream a -> Stream a
    Cons String
    l (Stream Char -> Stream String
    lines (Stream Char -> Stream Char
    forall a. Stream a -> Stream a
    tail Stream Char
    ys))

    -- | The 'unlines' function is an inverse operation to 'lines'. It
    -- joins lines, after appending a terminating newline to each.
    unlines :: Stream String -> Stream Char
    unlines :: Stream String -> Stream Char
    unlines ~(Cons x :: String
    x xs :: Stream String
    xs) = (Char -> Stream Char -> Stream Char)
    -> Stream Char -> String -> Stream Char
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr Char -> Stream Char -> Stream Char
    forall a. a -> Stream a -> Stream a
    Cons (Char -> Stream Char -> Stream Char
    forall a. a -> Stream a -> Stream a
    Cons '\n' (Stream String -> Stream Char
    unlines Stream String
    xs)) String
    x

    -- | The 'toList' converts a stream into an infinite list.
    toList :: Stream a -> [a]
    toList :: Stream a -> [a]
    toList (Cons x :: a
    x xs :: Stream a
    xs) = a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : Stream a -> [a]
    forall a. Stream a -> [a]
    toList Stream a
    xs

    -- | The 'fromList' converts an infinite list to a
    -- stream.
    --
    -- /Beware/: Passing a finite list, will cause an error.
    fromList :: [a] -> Stream a
    fromList :: [a] -> Stream a
    fromList (x :: a
    x:xs :: [a]
    xs) = a -> Stream a -> Stream a
    forall a. a -> Stream a -> Stream a
    Cons a
    x ([a] -> Stream a
    forall a. [a] -> Stream a
    fromList [a]
    xs)
    fromList []     = String -> Stream a
    forall a. HasCallStack => String -> a
    error "Stream.fromList applied to finite list"