-- | 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 a -> b
f ~(Cons a
x 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
  Stream a
xs >>= :: Stream a -> (a -> Stream b) -> Stream b
>>= 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 Stream a
xs 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 Stream a
xs 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 Int
p (Cons a
x 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
+ Int
1) a
x ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
    String -> ShowS
showString String
" <:> "               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 = Int
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 a
x Stream a
_ ) = a
x

-- | Extract the sequence following the head of the stream.
tail :: Stream a -> Stream a
tail :: Stream a -> Stream a
tail (Cons a
_ 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 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 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 a -> b
f ~(Cons a
x 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 a
y ~(Cons a
x 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 a
x Stream a
xs) 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 a -> b -> a
f a
z ~(Cons b
x 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' a -> b -> a
f a
z 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 a -> a -> a
f ~(Cons a
x 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' a -> a -> a
f ~(Cons a
x 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 a
x Stream a
xs) 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 a -> a
f 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 [a]
xs 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 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 [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 c -> (a, c)
f c
c =
  let (a
x,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 Int
n ~(Cons a
x Stream a
xs)
  | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = []
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
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
- Int
1) Stream a
xs)
  | Bool
otherwise = String -> [a]
forall a. HasCallStack => String -> a
error String
"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 Int
n Stream a
xs
  | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = Stream a
xs
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
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
- Int
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 String
"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 Int
n Stream a
xs
  | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = ([],Stream a
xs)
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = let ([a]
prefix,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
-Int
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 String
"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 a -> Bool
p (Cons a
x 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 a -> Bool
p ~(Cons a
x 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 a -> Bool
p (Cons a
x Stream a
xs)
  | a -> Bool
p a
x       = let ([a]
trues, 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 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 a -> Bool
p ~(Cons a
x 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 a -> Bool
p ~(Cons a
x Stream a
xs) =
  let (Stream a
trues,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 a
x Stream a
ys) = let ([a]
xs, Stream a
zs) = (a -> Bool) -> Stream a -> ([a], Stream a)
forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
span (\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 [] Stream a
_ = Bool
True
isPrefixOf (a
y:[a]
ys) (Cons a
x 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 a
x Stream a
xs) Int
n
  | Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = a
x
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
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
- Int
1)
  | Bool
otherwise = String -> a
forall a. HasCallStack => String -> a
error String
"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 a
x = (a -> Bool) -> Stream a -> Int
forall a. (a -> Bool) -> Stream a -> Int
findIndex (\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 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 a -> Bool
p = Int -> Stream a -> Int
forall a. Num a => a -> Stream a -> a
indexFrom Int
0
    where
    indexFrom :: a -> Stream a -> a
indexFrom a
ix (Cons a
x 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
+ 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 a -> Bool
p = Int -> Stream a -> Stream Int
forall a. Num a => a -> Stream a -> Stream a
indicesFrom Int
0
    where
    indicesFrom :: a -> Stream a -> Stream a
indicesFrom a
ix (Cons a
x 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
+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 a
x Stream a
xs) ~(Cons b
y 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 a
x Stream a
xs) ~(Cons b
y Stream b
ys) ~(Cons c
z 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 a -> b -> c
f ~(Cons a
x Stream a
xs) ~(Cons b
y 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 a -> b -> c -> d
f ~(Cons a
x Stream a
xs) ~(Cons b
y Stream b
ys) (Cons c
z 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 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 (a
x,b
y) 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 (a
x,b
y,c
z) 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 (a
x,b
_,c
_) = a
x                              
  snd3 :: (a,b,c) -> b
  snd3 :: (a, b, c) -> b
snd3 (a
_,b
y,c
_) = b
y
  thd3 :: (a,b,c) -> c                              
  thd3 :: (a, b, c) -> c
thd3 (a
_,b
_,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 Stream Char
xs = let (String
w, 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 String
x 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 Char
' ' (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 Stream Char
xs = let (String
l, 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
== Char
'\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 String
x 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 Char
'\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 a
x 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 (a
x:[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 String
"Stream.fromList applied to finite list"