{-# LANGUAGE PatternGuards #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE CPP #-}
#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif
-----------------------------------------------------------------------------

-- |

-- Module      :  Data.Stream.Infinite

-- Copyright   :  (C) 2011 Edward Kmett,

--                (C) 2007-2010 Wouter Swierstra, Bas van Dijk

-- License     :  BSD-style (see the file LICENSE)

--

-- Maintainer  :  Edward Kmett <ekmett@gmail.com>

-- Stability   :  provisional

-- Portability :  portable (Haskell 2010)

--

----------------------------------------------------------------------------

module Data.Stream.Infinite (
   -- * The type of streams

     Stream(..)
   -- * Basic functions

   , tail   -- :: Stream a -> Stream a

   , inits  -- :: Stream a -> Stream [a]

   , prepend -- :: [a] -> Stream a -> Stream a

   , concat -- :: Stream [a] -> Stream a

   -- * Stream transformations

   , intersperse -- :: a -> Stream a -> Stream

   , interleave  -- :: Stream a -> Stream a -> Stream a

   , scanl       -- :: (b -> a -> b) -> b -> Stream a -> Stream b

   , scanl'      -- :: (b -> a -> b) -> b -> Stream a -> Stream b

   , scanl1      -- :: (a -> a -> a) -> Stream a -> Stream a

   , scanl1'     -- :: (a -> a -> a) -> Stream a -> Stream a

   , transpose   -- :: Stream (Stream a) -> Stream (Stream a)

   -- * Building streams

   , iterate     -- :: (a -> a) -> a -> Stream a

   , cycle       -- :: NonEmpty a -> Stream a

   , unfold      -- :: (a -> (b, a)) -> a -> Stream b

   -- * Extracting sublists

   , take        -- :: Int -> Stream a -> [a]

   , drop        -- :: Int -> Stream a -> Stream a

   , splitAt     -- :: Int -> Stream a -> ([a],Stream a)

   , takeWhile   -- :: (a -> Bool) -> Stream a -> [a]

   , dropWhile   -- :: (a -> Bool) -> Stream a -> Stream a

   , span        -- :: (a -> Bool) -> Stream a -> ([a], Stream a)

   , break       -- :: (a -> Bool) -> Stream a -> ([a], Stream a)

   , filter      -- :: (a -> Bool) -> Stream a -> Stream a

   , partition   -- :: (a -> Bool) -> Stream a -> (Stream a, Stream a)

   , group       -- :: (a -> Bool) -> Stream a -> Stream (NonEmpty a)

   , groupBy     -- :: (a -> a -> Bool) -> Stream a -> Stream (NonEmpty a)

   -- * Sublist predicates

   , isPrefixOf  -- :: [a] -> Stream a -> Bool

   -- * Indexing streams

   , (!!)        -- :: Int -> Stream a -> a

   , elemIndex   -- :: Eq a => a -> Stream a -> Int

   , elemIndices -- :: Eq a => a -> Stream a -> Stream Int

   , findIndex   -- :: (a -> Bool) -> Stream a -> Int

   , findIndices -- :: (a -> Bool) -> Stream a -> Stream Int

   -- * Zipping and unzipping streams

   , zip         -- :: Stream a -> Stream b -> Stream (a, b)

   , zipWith     -- :: (a -> b -> c) -> Stream a -> Stream b -> Stream c

   , unzip       -- :: Functor f => f (a, b) -> (f a, f b)

   -- * Functions on streams of characters

   , words       -- :: Stream Char -> Stream String

   , unwords     -- :: Stream String -> Stream Char

   , lines       -- :: Stream Char -> Stream String

   , unlines     -- :: Stream String -> Stream Char

   ) where

import Prelude hiding
  ( tail, map, scanr, scanr1, scanl, scanl1
  , iterate, take, drop, takeWhile
  , dropWhile, repeat, cycle, filter
  , (!!), zip, unzip, zipWith, words
  , unwords, lines, unlines, break, span
  , splitAt, foldr, concat
  )

#if !(MIN_VERSION_base(4,8,0))
import Control.Applicative
#endif
import Control.Comonad
import Data.Char (isSpace)
import Data.Data
import Data.Functor.Apply
import Data.Functor.Extend
import Data.Functor.Rep
#if !(MIN_VERSION_base(4,8,0))
import Data.Semigroup
import Data.Traversable
#endif
import Data.Foldable hiding (concat)
import Data.Distributive
import Data.Semigroup.Traversable
import Data.Semigroup.Foldable
import Data.List.NonEmpty (NonEmpty(..))
import Data.Boring (Boring (..), Absurd (..))

data Stream a = a :> Stream a deriving
  ( Int -> Stream a -> ShowS
forall a. Show a => Int -> Stream a -> ShowS
forall a. Show a => [Stream a] -> ShowS
forall a. Show a => Stream a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Stream a] -> ShowS
$cshowList :: forall a. Show a => [Stream a] -> ShowS
show :: Stream a -> String
$cshow :: forall a. Show a => Stream a -> String
showsPrec :: Int -> Stream a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Stream a -> ShowS
Show
#ifdef LANGUAGE_DeriveDataTypeable
  , Stream a -> DataType
Stream a -> Constr
forall {a}. Data a => Typeable (Stream a)
forall a. Data a => Stream a -> DataType
forall a. Data a => Stream a -> Constr
forall a.
Data a =>
(forall b. Data b => b -> b) -> Stream a -> Stream a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> Stream a -> u
forall a u.
Data a =>
(forall d. Data d => d -> u) -> Stream a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Stream a -> r
forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Stream a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Stream a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Stream a -> c (Stream a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Stream a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Stream a))
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Stream a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Stream a -> c (Stream a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Stream a))
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Stream a -> m (Stream a)
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Stream a -> u
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> Stream a -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> Stream a -> [u]
$cgmapQ :: forall a u.
Data a =>
(forall d. Data d => d -> u) -> Stream a -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Stream a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Stream a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Stream a -> r
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Stream a -> r
gmapT :: (forall b. Data b => b -> b) -> Stream a -> Stream a
$cgmapT :: forall a.
Data a =>
(forall b. Data b => b -> b) -> Stream a -> Stream a
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Stream a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Stream a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Stream a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Stream a))
dataTypeOf :: Stream a -> DataType
$cdataTypeOf :: forall a. Data a => Stream a -> DataType
toConstr :: Stream a -> Constr
$ctoConstr :: forall a. Data a => Stream a -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Stream a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Stream a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Stream a -> c (Stream a)
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Stream a -> c (Stream a)
Data, Typeable
#endif
  )

infixr 5 :>

instance Functor Stream where
  fmap :: forall a b. (a -> b) -> Stream a -> Stream b
fmap a -> b
f (a
a :> Stream a
as) = a -> b
f a
a forall a. a -> Stream a -> Stream a
:> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Stream a
as
  a
b <$ :: forall a b. a -> Stream b -> Stream a
<$ Stream b
_ = forall (f :: * -> *) a. Applicative f => a -> f a
pure a
b

instance Distributive Stream where
  distribute :: forall (f :: * -> *) a. Functor f => f (Stream a) -> Stream (f a)
distribute f (Stream a)
w = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall (w :: * -> *) a. Comonad w => w a -> a
extract f (Stream a)
w forall a. a -> Stream a -> Stream a
:> forall (g :: * -> *) (f :: * -> *) a.
(Distributive g, Functor f) =>
f (g a) -> g (f a)
distribute (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Stream a -> Stream a
tail f (Stream a)
w)

instance Representable Stream where
  type Rep Stream = Int
  tabulate :: forall a. (Rep Stream -> a) -> Stream a
tabulate Rep Stream -> a
f      = forall a b. (a -> (b, a)) -> a -> Stream b
unfold (\Int
i -> (,) (Rep Stream -> a
f Int
i) forall a b. (a -> b) -> a -> b
$! (Int
i forall a. Num a => a -> a -> a
+ Int
1)) Int
0
  index :: forall a. Stream a -> Rep Stream -> a
index (a
x :> Stream a
xs) Rep Stream
n
    | Rep Stream
n forall a. Eq a => a -> a -> Bool
== Int
0    = a
x
    | Rep Stream
n forall a. Ord a => a -> a -> Bool
> Int
0     = Stream a
xs forall a. Stream a -> Int -> a
!! (Rep Stream
n forall a. Num a => a -> a -> a
- Int
1)
    | Bool
otherwise = forall a. HasCallStack => String -> a
error String
"Stream.!! negative argument"

-- | Extract the first element of the stream.

head :: Stream a -> a
head :: forall a. Stream a -> a
head (a
x :> Stream a
_) = a
x

-- | @since 3.3.1

instance Boring a => Boring (Stream a) where
  boring :: Stream a
boring = forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a. Boring a => a
boring

-- | @since 3.3.1

instance Absurd a => Absurd (Stream a) where
  absurd :: forall b. Stream a -> b
absurd = forall a b. Absurd a => a -> b
absurd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (w :: * -> *) a. Comonad w => w a -> a
extract

-- | Extract the sequence following the head of the stream.

tail :: Stream a -> Stream a
tail :: forall a. Stream a -> Stream a
tail (a
_ :> Stream a
as) = Stream a
as
{-# INLINE tail #-}

instance Extend Stream where
  duplicated :: forall a. Stream a -> Stream (Stream a)
duplicated = forall (w :: * -> *) a. Comonad w => w a -> w (w a)
duplicate
  extended :: forall a b. (Stream a -> b) -> Stream a -> Stream b
extended = forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend

instance Comonad Stream where
  duplicate :: forall a. Stream a -> Stream (Stream a)
duplicate Stream a
w = Stream a
w forall a. a -> Stream a -> Stream a
:> forall (w :: * -> *) a. Comonad w => w a -> w (w a)
duplicate (forall a. Stream a -> Stream a
tail Stream a
w)
  extend :: forall a b. (Stream a -> b) -> Stream a -> Stream b
extend Stream a -> b
f Stream a
w = Stream a -> b
f Stream a
w forall a. a -> Stream a -> Stream a
:> forall (w :: * -> *) a b. Comonad w => (w a -> b) -> w a -> w b
extend Stream a -> b
f (forall a. Stream a -> Stream a
tail Stream a
w)
  extract :: forall a. Stream a -> a
extract (a
a :> Stream a
_) = a
a

instance Apply Stream where
  (a -> b
f :> Stream (a -> b)
fs) <.> :: forall a b. Stream (a -> b) -> Stream a -> Stream b
<.> (a
a :> Stream a
as) = a -> b
f a
a forall a. a -> Stream a -> Stream a
:> (Stream (a -> b)
fs forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Stream a
as)
  Stream a
as        <. :: forall a b. Stream a -> Stream b -> Stream a
<.  Stream b
_         = Stream a
as
  Stream a
_          .> :: forall a b. Stream a -> Stream b -> Stream b
.> Stream b
bs        = Stream b
bs

instance ComonadApply Stream where
  (a -> b
f :> Stream (a -> b)
fs) <@> :: forall a b. Stream (a -> b) -> Stream a -> Stream b
<@> (a
a :> Stream a
as) = a -> b
f a
a forall a. a -> Stream a -> Stream a
:> (Stream (a -> b)
fs forall (w :: * -> *) a b.
ComonadApply w =>
w (a -> b) -> w a -> w b
<@> Stream a
as)
  Stream a
as        <@ :: forall a b. Stream a -> Stream b -> Stream a
<@  Stream b
_         = Stream a
as
  Stream a
_          @> :: forall a b. Stream a -> Stream b -> Stream b
@> Stream b
bs        = Stream b
bs

instance Applicative Stream where
  pure :: forall a. a -> Stream a
pure a
a = Stream a
as where as :: Stream a
as = a
a forall a. a -> Stream a -> Stream a
:> Stream a
as
  <*> :: forall a b. Stream (a -> b) -> Stream a -> Stream b
(<*>) = forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
(<.>)
  (<* ) = (<. )
  ( *>) = ( .>)

instance Foldable Stream where
  fold :: forall m. Monoid m => Stream m -> m
fold (m
m :> Stream m
ms) = m
m forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m
fold Stream m
ms
  foldMap :: forall m a. Monoid m => (a -> m) -> Stream a -> m
foldMap a -> m
f (a
a :> Stream a
as) = a -> m
f a
a forall a. Monoid a => a -> a -> a
`mappend` forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Stream a
as
  foldr :: forall a b. (a -> b -> b) -> b -> Stream a -> b
foldr a -> b -> b
f0 b
_ = forall {t} {t}. (t -> t -> t) -> Stream t -> t
go a -> b -> b
f0 where go :: (t -> t -> t) -> Stream t -> t
go t -> t -> t
f (t
a :> Stream t
as) = t -> t -> t
f t
a ((t -> t -> t) -> Stream t -> t
go t -> t -> t
f Stream t
as)
#if __GLASGOW_HASKELL__ > 710
  length :: forall a. Stream a -> Int
length Stream a
_ = forall a. HasCallStack => String -> a
error String
"infinite length"
  null :: forall a. Stream a -> Bool
null Stream a
_ = Bool
False
#endif

instance Traversable Stream where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Stream a -> f (Stream b)
traverse a -> f b
f ~(a
a :> Stream a
as) = forall a. a -> Stream a -> Stream a
(:>) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Stream a
as

instance Foldable1 Stream

instance Traversable1 Stream where
  traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> Stream a -> f (Stream b)
traverse1 a -> f b
f ~(a
a :> Stream a
as) = forall a. a -> Stream a -> Stream a
(:>) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
traverse1 a -> f b
f Stream a
as
  sequence1 :: forall (f :: * -> *) b. Apply f => Stream (f b) -> f (Stream b)
sequence1 ~(f b
a :> Stream (f b)
as) = forall a. a -> Stream a -> Stream a
(:>) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f b
a forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> forall (t :: * -> *) (f :: * -> *) b.
(Traversable1 t, Apply f) =>
t (f b) -> f (t b)
sequence1 Stream (f b)
as

-- | The unfold function is similar to the unfold for lists. Note

-- there is no base case: all streams must be infinite.

unfold :: (a -> (b, a)) -> a -> Stream b
unfold :: forall a b. (a -> (b, a)) -> a -> Stream b
unfold a -> (b, a)
f a
c | (b
x, a
d) <- a -> (b, a)
f a
c = b
x forall a. a -> Stream a -> Stream a
:> forall a b. (a -> (b, a)) -> a -> Stream b
unfold a -> (b, a)
f a
d

instance Monad Stream where
  Stream a
m >>= :: forall a b. Stream a -> (a -> Stream b) -> Stream b
>>= a -> Stream b
f = forall a b. (a -> (b, a)) -> a -> Stream b
unfold (\(Stream b
bs :> Stream (Stream b)
bss) -> (forall (w :: * -> *) a. Comonad w => w a -> a
extract Stream b
bs, forall a. Stream a -> Stream a
tail forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Stream (Stream b)
bss)) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Stream b
f Stream a
m)
#if !(MIN_VERSION_base(4,11,0))
  return = pure
  _ >> bs = bs
#endif

-- | 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 :: forall a. Stream a -> Stream a -> Stream a
interleave ~(a
x :> Stream a
xs) Stream a
ys = a
x forall a. a -> Stream a -> Stream a
:> forall a. Stream a -> Stream a -> Stream a
interleave Stream a
ys 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 :: forall a. Stream a -> Stream [a]
inits Stream a
xs = [] forall a. a -> Stream a -> Stream a
:> ((forall (w :: * -> *) a. Comonad w => w a -> a
extract Stream a
xs forall a. a -> [a] -> [a]
:) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Stream a -> Stream [a]
inits (forall a. Stream a -> Stream a
tail Stream a
xs))

-- | Prepend a list to a stream.

prepend :: Foldable f => f a -> Stream a -> Stream a
prepend :: forall (f :: * -> *) a. Foldable f => f a -> Stream a -> Stream a
prepend f a
xs Stream a
ys = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Stream a -> Stream a
(:>) Stream a
ys f a
xs

-- | Flatten a stream of lists into a stream.

concat :: Foldable f => Stream (f a) -> Stream a
concat :: forall (f :: * -> *) a. Foldable f => Stream (f a) -> Stream a
concat = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall (f :: * -> *) a. Foldable f => f a -> Stream a -> Stream a
prepend forall a. HasCallStack => a
undefined

-- | @'intersperse' y xs@ creates an alternating stream of

-- elements from @xs@ and @y@.

intersperse :: a -> Stream a -> Stream a
intersperse :: forall a. a -> Stream a -> Stream a
intersperse a
y ~(a
x :> Stream a
xs) = a
x forall a. a -> Stream a -> Stream a
:> a
y forall a. a -> Stream a -> Stream a
:> forall a. a -> Stream a -> Stream a
intersperse a
y Stream a
xs

-- | 'scanl' yields a stream of successive reduced values from:

--

-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]

scanl :: (a -> b -> a) -> a -> Stream b -> Stream a
scanl :: forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
scanl a -> b -> a
f a
z ~(b
x :> Stream b
xs) = a
z forall a. a -> Stream a -> Stream a
:> forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
scanl a -> b -> a
f (a -> b -> a
f a
z b
x) Stream b
xs

-- | 'scanl' yields a stream of successive reduced values from:

--

-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]

scanl' :: (a -> b -> a) -> a -> Stream b -> Stream a
scanl' :: forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
scanl' a -> b -> a
f a
z ~(b
x :> Stream b
xs) = a
z forall a. a -> Stream a -> Stream a
:> (forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
scanl' a -> b -> a
f forall a b. (a -> b) -> a -> b
$! a -> b -> a
f a
z b
x) Stream b
xs

-- | 'scanl1' is a variant of 'scanl' that has no starting value argument:

--

-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

scanl1 :: (a -> a -> a) -> Stream a -> Stream a
scanl1 :: forall a. (a -> a -> a) -> Stream a -> Stream a
scanl1 a -> a -> a
f ~(a
x :> Stream a
xs) = forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
scanl a -> a -> a
f a
x Stream a
xs

-- | @scanl1'@ is a strict 'scanl' that has no starting value.

scanl1' :: (a -> a -> a) -> Stream a -> Stream a
scanl1' :: forall a. (a -> a -> a) -> Stream a -> Stream a
scanl1' a -> a -> a
f ~(a
x :> Stream a
xs) = forall a b. (a -> b -> a) -> a -> Stream b -> Stream a
scanl' 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 :: forall a. Stream (Stream a) -> Stream (Stream a)
transpose ~((a
x :> Stream a
xs) :> Stream (Stream a)
yss) =
  (a
x forall a. a -> Stream a -> Stream a
:> (forall (w :: * -> *) a. Comonad w => w a -> a
extract forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Stream (Stream a)
yss)) forall a. a -> Stream a -> Stream a
:> forall a. Stream (Stream a) -> Stream (Stream a)
transpose (Stream a
xs forall a. a -> Stream a -> Stream a
:> (forall a. Stream a -> Stream a
tail forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Stream (Stream a)
yss))

-- | @'iterate' f x@ 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 :: forall a. (a -> a) -> a -> Stream a
iterate a -> a
f a
x = a
x forall a. a -> Stream a -> Stream a
:> forall a. (a -> a) -> a -> Stream a
iterate a -> a
f (a -> a
f 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 :: NonEmpty a -> Stream a
cycle :: forall a. NonEmpty a -> Stream a
cycle NonEmpty a
xs = Stream a
ys where ys :: Stream a
ys = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Stream a -> Stream a
(:>) Stream a
ys NonEmpty a
xs

-- | @'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 :: forall a. Int -> Stream a -> [a]
take Int
n ~(a
x :> Stream a
xs)
  | Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = []
  | Int
n forall a. Ord a => a -> a -> Bool
> Int
0 = a
x forall a. a -> [a] -> [a]
: forall a. Int -> Stream a -> [a]
take (Int
n forall a. Num a => a -> a -> a
- Int
1) Stream a
xs
  | Bool
otherwise = 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 :: forall a. Int -> Stream a -> Stream a
drop Int
n Stream a
xs
  | Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = Stream a
xs
  | Int
n forall a. Ord a => a -> a -> Bool
> Int
0 = forall a. Int -> Stream a -> Stream a
drop (Int
n forall a. Num a => a -> a -> a
- Int
1) (forall a. Stream a -> Stream a
tail Stream a
xs)
  | Bool
otherwise = forall a. HasCallStack => String -> a
error String
"Stream.drop: negative argument"

-- | @'splitAt' n xs@ 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 :: forall a. Int -> Stream a -> ([a], Stream a)
splitAt Int
n Stream a
xs
  | Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = ([],Stream a
xs)
  | Int
n forall a. Ord a => a -> a -> Bool
> Int
0, ([a]
prefix, Stream a
rest) <- forall a. Int -> Stream a -> ([a], Stream a)
splitAt (Int
n forall a. Num a => a -> a -> a
- Int
1) (forall a. Stream a -> Stream a
tail Stream a
xs) = (forall (w :: * -> *) a. Comonad w => w a -> a
extract Stream a
xs forall a. a -> [a] -> [a]
: [a]
prefix, Stream a
rest)
  | Bool
otherwise = 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 :: forall a. (a -> Bool) -> Stream a -> [a]
takeWhile a -> Bool
p (a
x :> Stream a
xs)
  | a -> Bool
p a
x = a
x forall a. a -> [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 :: forall a. (a -> Bool) -> Stream a -> Stream a
dropWhile a -> Bool
p ~(a
x :> Stream a
xs)
  | a -> Bool
p a
x = forall a. (a -> Bool) -> Stream a -> Stream a
dropWhile a -> Bool
p Stream a
xs
  | Bool
otherwise = a
x forall a. a -> Stream a -> Stream a
:> Stream a
xs

-- | @'span' p xs@ returns the longest prefix of @xs@ that satisfies

-- @p@, together with the remainder of the stream.

span :: (a -> Bool) -> Stream a -> ([a], Stream a)
span :: forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
span a -> Bool
p xxs :: Stream a
xxs@(a
x :> Stream a
xs)
  | a -> Bool
p a
x, ([a]
ts, Stream a
fs) <- forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
span a -> Bool
p Stream a
xs = (a
x forall a. a -> [a] -> [a]
: [a]
ts, Stream a
fs)
  | Bool
otherwise = ([], Stream a
xxs)

-- | The 'break' @p@ function is equivalent to 'span' @not . p@.

break :: (a -> Bool) -> Stream a -> ([a], Stream a)
break :: forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
break a -> Bool
p = forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
span (Bool -> Bool
not 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 :: forall a. (a -> Bool) -> Stream a -> Stream a
filter a -> Bool
p ~(a
x :> Stream a
xs)
  | a -> Bool
p a
x       = a
x forall a. a -> Stream a -> Stream a
:> forall a. (a -> Bool) -> Stream a -> Stream a
filter a -> Bool
p Stream a
xs
  | Bool
otherwise = 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 :: forall a. (a -> Bool) -> Stream a -> (Stream a, Stream a)
partition a -> Bool
p ~(a
x :> Stream a
xs)
  | a -> Bool
p a
x = (a
x forall a. a -> Stream a -> Stream a
:> Stream a
ts, Stream a
fs)
  | Bool
otherwise = (Stream a
ts, a
x forall a. a -> Stream a -> Stream a
:> Stream a
fs)
  where (Stream a
ts, Stream a
fs) = forall a. (a -> Bool) -> Stream a -> (Stream a, Stream a)
partition a -> Bool
p Stream a
xs

-- | 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 (NonEmpty a)
group :: forall a. Eq a => Stream a -> Stream (NonEmpty a)
group = forall a. (a -> a -> Bool) -> Stream a -> Stream (NonEmpty a)
groupBy forall a. Eq a => a -> a -> Bool
(==)

groupBy :: (a -> a -> Bool) -> Stream a -> Stream (NonEmpty a)
groupBy :: forall a. (a -> a -> Bool) -> Stream a -> Stream (NonEmpty a)
groupBy a -> a -> Bool
eq ~(a
x :> Stream a
ys)
  | ([a]
xs, Stream a
zs) <- forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
span (a -> a -> Bool
eq a
x) Stream a
ys
  = (a
x forall a. a -> [a] -> NonEmpty a
:| [a]
xs) forall a. a -> Stream a -> Stream a
:> forall a. (a -> a -> Bool) -> Stream a -> Stream (NonEmpty a)
groupBy a -> a -> Bool
eq 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 :: forall a. Eq a => [a] -> Stream a -> Bool
isPrefixOf [] Stream a
_ = Bool
True
isPrefixOf (a
y:[a]
ys) (a
x :> Stream a
xs)
  | a
y forall a. Eq a => a -> a -> Bool
== a
x    = 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
!! :: forall a. Stream a -> Int -> a
(!!) = forall (f :: * -> *) a. Representable f => f a -> Rep f -> a
index

-- | 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 :: forall a. Eq a => a -> Stream a -> Int
elemIndex a
x = forall a. (a -> Bool) -> Stream a -> Int
findIndex (\a
y -> a
x 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 :: forall a. Eq a => a -> Stream a -> Stream Int
elemIndices a
x = forall a. (a -> Bool) -> Stream a -> Stream Int
findIndices (a
xforall 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 :: forall a. (a -> Bool) -> Stream a -> Int
findIndex a -> Bool
p = Int -> Stream a -> Int
indexFrom Int
0
    where
    indexFrom :: Int -> Stream a -> Int
indexFrom Int
ix (a
x :> Stream a
xs)
      | a -> Bool
p a
x       = Int
ix
      | Bool
otherwise = (Int -> Stream a -> Int
indexFrom forall a b. (a -> b) -> a -> b
$! (Int
ix forall a. Num a => a -> a -> a
+ Int
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 :: forall a. (a -> Bool) -> Stream a -> Stream Int
findIndices a -> Bool
p = Int -> Stream a -> Stream Int
indicesFrom Int
0 where
  indicesFrom :: Int -> Stream a -> Stream Int
indicesFrom Int
ix (a
x :> Stream a
xs)
    | a -> Bool
p a
x = Int
ix forall a. a -> Stream a -> Stream a
:> Stream Int
ixs
    | Bool
otherwise = Stream Int
ixs
    where ixs :: Stream Int
ixs = (Int -> Stream a -> Stream Int
indicesFrom forall a b. (a -> b) -> a -> b
$! (Int
ixforall a. Num a => a -> a -> a
+Int
1)) Stream a
xs

-- | The 'zip' function takes two streams and returns a list of

-- corresponding pairs.

zip :: Stream a -> Stream b -> Stream (a,b)
zip :: forall a b. Stream a -> Stream b -> Stream (a, b)
zip ~(a
x :> Stream a
xs) ~(b
y :> Stream b
ys) = (a
x,b
y) forall a. a -> Stream a -> Stream a
:> forall a b. Stream a -> Stream b -> Stream (a, b)
zip Stream a
xs Stream b
ys

-- | 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 :: forall a b c. (a -> b -> c) -> Stream a -> Stream b -> Stream c
zipWith a -> b -> c
f ~(a
x :> Stream a
xs) ~(b
y :> Stream b
ys) = a -> b -> c
f a
x b
y forall a. a -> Stream a -> Stream a
:> 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 'unzip' function is the inverse of the 'zip' function.

unzip :: Stream (a,b) -> (Stream a, Stream b)
unzip :: forall a b. Stream (a, b) -> (Stream a, Stream b)
unzip Stream (a, b)
xs = (forall a b. (a, b) -> a
fst forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Stream (a, b)
xs, forall a b. (a, b) -> b
snd forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Stream (a, b)
xs)

-- | 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 | (String
w, Stream Char
ys) <- forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
break Char -> Bool
isSpace Stream Char
xs = String
w forall a. a -> Stream a -> Stream a
:> 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 ~(String
x :> Stream String
xs) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Stream a -> Stream a
(:>) (Char
' ' forall a. a -> Stream a -> Stream a
:> 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 | (String
l, Stream Char
ys) <- forall a. (a -> Bool) -> Stream a -> ([a], Stream a)
break (forall a. Eq a => a -> a -> Bool
== Char
'\n') Stream Char
xs = String
l forall a. a -> Stream a -> Stream a
:> Stream Char -> Stream String
lines (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 ~(String
x :> Stream String
xs) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> Stream a -> Stream a
(:>) (Char
'\n' forall a. a -> Stream a -> Stream a
:> Stream String -> Stream Char
unlines Stream String
xs) String
x