-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Infinite lists
--   
--   Modern lightweight library for infinite lists with fusion:
--   
--   
--   
- API similar to Data.List.
--   
- No dependencies other than base.
--   
- Top performance, driven by fusion.
--   
- Avoid dangerous instances like Foldable.
--   
- Use NonEmpty where applicable.
--   
- Use Word for indices.
--   
- Be lazy, but not too lazy.
--   
--   
--   
--   {-# LANGUAGE PostfixOperators #-}
--   import Data.List.Infinite (Infinite(..), (...), (....))
--   import qualified Data.List.Infinite as Inf
--   
@package infinite-list
@version 0.1.3

-- | Modern lightweight library for infinite lists with fusion:
--   
--   
--   
- API similar to Data.List.
--   
- No dependencies other than base.
--   
- Top performance, driven by fusion.
--   
- Avoid dangerous instances like Foldable.
--   
- Use NonEmpty where applicable.
--   
- Use Word for indices.
--   
- Be lazy, but not too lazy.
--   
--   
--   
--   {-# LANGUAGE PostfixOperators #-}
--   import Data.List.Infinite (Infinite(..), (...), (....))
--   import qualified Data.List.Infinite as Inf
--   
module Data.List.Infinite

-- | Type of infinite lists.
--   
--   In terms of recursion schemes, Infinite a is a fix
--   point of the base functor (a,), foldr is a
--   catamorphism and unfoldr is an anamorphism.
data Infinite a
(:<) :: a -> Infinite a -> Infinite a
infixr 5 :<

-- | Get the first elements of an infinite list.
head :: Infinite a -> a

-- | Get the elements of an infinite list after the first one.
tail :: Infinite a -> Infinite a

-- | Split an infinite list into its head and tail.
uncons :: Infinite a -> (a, Infinite a)

-- | Convert to a list. Use cycle to go in the opposite direction.
toList :: Infinite a -> [a]

-- | Right-associative fold of an infinite list, necessarily lazy in the
--   accumulator. Any unconditional attempt to force the accumulator even
--   to the weak head normal form (WHNF) will hang the computation. E. g.,
--   the following definition isn't productive:
--   
--   
--   import Data.List.NonEmpty (NonEmpty(..))
--   toNonEmpty = foldr (\a (x :| xs) -> a :| x : xs) :: Infinite a -> NonEmpty a
--   
--   
--   One should use lazy patterns, e. g.,
--   
--   
--   toNonEmpty = foldr (\a ~(x :| xs) -> a :| x : xs)
--   
--   
--   This is a catamorphism on infinite lists.
foldr :: (a -> b -> b) -> Infinite a -> b

-- | Apply a function to every element of an infinite list.
map :: (a -> b) -> Infinite a -> Infinite b

-- | Fold an infinite list from the left and return a list of successive
--   reductions, starting from the initial accumulator:
--   
--   
--   scanl f acc (x1 :< x2 :< ...) = acc :< f acc x1 :< f (f acc x1) x2 :< ...
--   
scanl :: (b -> a -> b) -> b -> Infinite a -> Infinite b

-- | Same as scanl, but strict in accumulator.
scanl' :: (b -> a -> b) -> b -> Infinite a -> Infinite b

-- | Fold an infinite list from the left and return a list of successive
--   reductions, starting from the first element:
--   
--   
--   scanl1 f (x0 :< x1 :< x2 :< ...) = x0 :< f x0 x1 :< f (f x0 x1) x2 :< ...
--   
scanl1 :: (a -> a -> a) -> Infinite a -> Infinite a

-- | Fold an infinite list from the left and return a list of successive
--   reductions, keeping accumulator in a state:
--   
--   
--   mapAccumL f acc0 (x1 :< x2 :< ...) =
--     let (acc1, y1) = f acc0 x1 in
--       let (acc2, y2) = f acc1 x2 in
--         ...
--           y1 :< y2 :< ...
--   
--   
--   If you are looking how to traverse with a state, look no further.
mapAccumL :: (acc -> x -> (acc, y)) -> acc -> Infinite x -> Infinite y

-- | Same as mapAccumL, but strict in accumulator.
mapAccumL' :: (acc -> x -> (acc, y)) -> acc -> Infinite x -> Infinite y

-- | Map each element to an action, evaluate these actions from left to
--   right and ignore the results. Note that the return type is Void
--   instead of usual ().
--   
--   
--   >>> traverse_ print (0...) -- hit Ctrl+C to terminate
--   0
--   1
--   2Interrupted
--   
--   
--   traverse_ could be productive for some short-circuiting
--   f:
--   
--   
--   >>> traverse_ (\x -> if x > 10 then Left x else Right ()) (0...)
--   Left 11
--   
traverse_ :: Applicative f => (a -> f ()) -> Infinite a -> f Void

-- | Flipped traverse_.
for_ :: Applicative f => Infinite a -> (a -> f ()) -> f Void

-- | Flatten out an infinite list of non-empty lists.
--   
--   The peculiar type with NonEmpty is to guarantee that
--   concat is productive and results in an infinite list. Otherwise
--   the concatenation of infinitely many [a] could still be a
--   finite list.
concat :: Infinite (NonEmpty a) -> Infinite a

-- | First map every element, then concat.
--   
--   The peculiar type with NonEmpty is to guarantee that
--   concatMap is productive and results in an infinite list.
--   Otherwise the concatenation of infinitely many [b] could
--   still be a finite list.
concatMap :: (a -> NonEmpty b) -> Infinite a -> Infinite b

-- | Insert an element between adjacent elements of an infinite list.
intersperse :: a -> Infinite a -> Infinite a

-- | Insert a non-empty list between adjacent elements of an infinite list,
--   and subsequently flatten it out.
--   
--   The peculiar type with NonEmpty is to guarantee that
--   intercalate is productive and results in an infinite list. If
--   separator is an empty list, concatenation of infinitely many
--   [a] could still be a finite list.
intercalate :: NonEmpty a -> Infinite [a] -> Infinite a

-- | Interleave two infinite lists.
interleave :: Infinite a -> Infinite a -> Infinite a

-- | Transpose rows and columns of an argument.
--   
--   This is actually distribute from Distributive
--   type class in disguise.
transpose :: Functor f => f (Infinite a) -> Infinite (f a)

-- | Generate an infinite list of all finite subsequences of the argument.
--   
--   
--   >>> take 8 (subsequences (0...))
--   [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]
--   
subsequences :: Infinite a -> Infinite [a]

-- | Generate an infinite list of all non-empty finite subsequences of the
--   argument.
--   
--   
--   >>> take 7 (subsequences1 (0...))
--   [0 :| [],1 :| [],0 :| [1],2 :| [],0 :| [2],1 :| [2],0 :| [1,2]]
--   
subsequences1 :: Infinite a -> Infinite (NonEmpty a)

-- | Generate an infinite list of all finite (such that only finite number
--   of elements change their positions) permutations of the argument.
--   
--   
--   >>> take 6 (fmap (take 3) (permutations (0...)))
--   [[0,1,2],[1,0,2],[2,1,0],[1,2,0],[2,0,1],[0,2,1]]
--   
permutations :: Infinite a -> Infinite (Infinite a)

-- | Generate an infinite progression, starting from a given element,
--   similar to [x..]. For better user experience consider
--   enabling {-# LANGUAGE PostfixOperators #-}:
--   
--   
--   >>> :set -XPostfixOperators
--   
--   >>> Data.List.Infinite.take 10 (0...)
--   [0,1,2,3,4,5,6,7,8,9]
--   
--   
--   Beware that for finite types (...) applies cycle atop of
--   [x..]:
--   
--   
--   >>> :set -XPostfixOperators
--   
--   >>> Data.List.Infinite.take 10 (EQ...)
--   [EQ,GT,EQ,GT,EQ,GT,EQ,GT,EQ,GT]
--   
--   
--   Remember that Int is a finite type as well. One is unlikely to
--   hit this on a 64-bit architecture, but on a 32-bit machine it's fairly
--   possible to traverse ((0 :: Int) ...) far enough to
--   encounter 0 again.
(...) :: Enum a => a -> Infinite a
infix 0 ...

-- | Generate an infinite arithmetic progression, starting from given
--   elements, similar to [x,y..]. For better user experience
--   consider enabling {-# LANGUAGE PostfixOperators #-}:
--   
--   
--   >>> :set -XPostfixOperators
--   
--   >>> Data.List.Infinite.take 10 ((1,3)....)
--   [1,3,5,7,9,11,13,15,17,19]
--   
--   
--   Beware that for finite types (....) applies cycle atop
--   of [x,y..]:
--   
--   
--   >>> :set -XPostfixOperators
--   
--   >>> Data.List.Infinite.take 10 ((EQ,GT)....)
--   [EQ,GT,EQ,GT,EQ,GT,EQ,GT,EQ,GT]
--   
--   
--   Remember that Int is a finite type as well: for a sufficiently
--   large step of progression y - x one may observe ((x ::
--   Int, y)....) cycling back to emit x fairly soon.
(....) :: Enum a => (a, a) -> Infinite a
infix 0 ....

-- | Generate an infinite list of repeated applications.
iterate :: (a -> a) -> a -> Infinite a

-- | Same as iterate, but strict in accumulator.
iterate' :: (a -> a) -> a -> Infinite a

-- | Build an infinite list from a seed value.
--   
--   This is an anamorphism on infinite lists.
unfoldr :: (b -> (a, b)) -> b -> Infinite a

-- | Generate an infinite list of f 0, f 1, f
--   2...
--   
--   tabulate and (!!) witness that Infinite is
--   Representable.
tabulate :: (Word -> a) -> Infinite a

-- | Repeat the same element ad infinitum.
repeat :: a -> Infinite a

-- | Repeat a non-empty list ad infinitum. If you were looking for
--   something like fromList :: [a] -> Infinite a, look no
--   further.
--   
--   It would be less annoying to take [a] instead of
--   NonEmpty a, but we strive to avoid partial functions.
cycle :: NonEmpty a -> Infinite a

-- | Prepend a list to an infinite list.
prependList :: [a] -> Infinite a -> Infinite a

-- | Take a prefix of given length.
take :: Int -> Infinite a -> [a]

-- | Drop a prefix of given length.
drop :: Int -> Infinite a -> Infinite a

-- | Split an infinite list into a prefix of given length and the rest.
splitAt :: Int -> Infinite a -> ([a], Infinite a)

-- | Take the longest prefix satisfying a predicate.
takeWhile :: (a -> Bool) -> Infinite a -> [a]

-- | Drop the longest prefix satisfying a predicate.
--   
--   This function isn't productive (e. g., head .
--   dropWhile f won't terminate), if all elements of the
--   input list satisfy the predicate.
dropWhile :: (a -> Bool) -> Infinite a -> Infinite a

-- | Split an infinite list into the longest prefix satisfying a predicate
--   and the rest.
--   
--   This function isn't productive in the second component of the tuple
--   (e. g., head . snd . span
--   f won't terminate), if all elements of the input list satisfy
--   the predicate.
span :: (a -> Bool) -> Infinite a -> ([a], Infinite a)

-- | Split an infinite list into the longest prefix not satisfying a
--   predicate and the rest.
--   
--   This function isn't productive in the second component of the tuple
--   (e. g., head . snd . break
--   f won't terminate), if no elements of the input list satisfy
--   the predicate.
break :: (a -> Bool) -> Infinite a -> ([a], Infinite a)

-- | Group consecutive equal elements.
group :: Eq a => Infinite a -> Infinite (NonEmpty a)

-- | Generate all prefixes of an infinite list.
--   
--   
--   >>> :set -XPostfixOperators
--   
--   >>> Data.List.Infinite.take 5 $ Data.List.Infinite.inits (0...)
--   [[],[0],[0,1],[0,1,2],[0,1,2,3]]
--   
--   
--   If you need reversed prefixes, they can be generated cheaper using
--   scanl':
--   
--   
--   >>> :set -XPostfixOperators
--   
--   >>> Data.List.Infinite.take 5 $ Data.List.Infinite.scanl' (flip (:)) [] (0...)
--   [[],[0],[1,0],[2,1,0],[3,2,1,0]]
--   
inits :: Infinite a -> Infinite [a]

-- | Generate all non-empty prefixes of an infinite list.
inits1 :: Infinite a -> Infinite (NonEmpty a)

-- | Generate all suffixes of an infinite list.
tails :: Infinite a -> Infinite (Infinite a)

-- | Check whether a list is a prefix of an infinite list.
isPrefixOf :: Eq a => [a] -> Infinite a -> Bool

-- | If a list is a prefix of an infinite list, strip it and return the
--   rest. Otherwise return Nothing.
stripPrefix :: Eq a => [a] -> Infinite a -> Maybe (Infinite a)

-- | Filter an infinite list, removing elements which does not satisfy a
--   predicate.
--   
--   This function isn't productive (e. g., head .
--   filter f won't terminate), if no elements of the input
--   list satisfy the predicate.
--   
--   A common objection is that since it could happen that no elements of
--   the input satisfy the predicate, the return type should be
--   [a] instead of Infinite a. This would not
--   however make filter any more productive. Note that such
--   hypothetical filter could not ever generate []
--   constructor, only (:), so we would just have a more lax type
--   gaining nothing instead. Same reasoning applies to other filtering /
--   partitioning / searching functions.
filter :: (a -> Bool) -> Infinite a -> Infinite a

-- | Find the first pair, whose first component is equal to the first
--   argument, and return the second component. If there is nothing to be
--   found, this function will hang indefinitely.
lookup :: Eq a => a -> Infinite (a, b) -> b

-- | Find the first element, satisfying a predicate. If there is nothing to
--   be found, this function will hang indefinitely.
find :: (a -> Bool) -> Infinite a -> a

-- | Apply a function to every element of an infinite list and collect
--   Just results.
--   
--   This function isn't productive (e. g., head .
--   mapMaybe f won't terminate), if no elements of the
--   input list result in Just.
mapMaybe :: (a -> Maybe b) -> Infinite a -> Infinite b

-- | Keep only Just elements.
--   
--   This function isn't productive (e. g., head .
--   catMaybes won't terminate), if no elements of the input list
--   are Just.
catMaybes :: Infinite (Maybe a) -> Infinite a

-- | Split an infinite list into two infinite lists: the first one contains
--   elements, satisfying a predicate, and the second one the rest.
--   
--   This function isn't productive in the first component of the tuple (e.
--   g., head . fst . partition
--   f won't terminate), if no elements of the input list satisfy
--   the predicate. Same for the second component, if all elements of the
--   input list satisfy the predicate.
partition :: (a -> Bool) -> Infinite a -> (Infinite a, Infinite a)

-- | Apply a function to every element of an infinite list and separate
--   Left and Right results.
--   
--   This function isn't productive (e. g., head . fst
--   . mapEither f won't terminate), if no elements
--   of the input list result in Left or Right.
mapEither :: (a -> Either b c) -> Infinite a -> (Infinite b, Infinite c)

-- | Separate Left and Right elements.
--   
--   This function isn't productive (e. g., head . fst
--   . partitionEithers won't terminate), if no elements of
--   the input list are Left or Right.
partitionEithers :: Infinite (Either a b) -> (Infinite a, Infinite b)

-- | Return n-th element of an infinite list. On contrary to
--   Data.List.!!, this function takes Word instead
--   of Int to avoid error on negative arguments.
--   
--   If you are concerned that unsigned indices may accidentally underflow,
--   compile with -fno-ignore-asserts: there is an assert
--   checking that the index does not exceed fromIntegral
--   (maxBound :: Int).
--   
--   This is actually index from Representable
--   type class in disguise.
(!!) :: Infinite a -> Word -> a
infixl 9 !!

-- | Return an index of the first element, equal to a given. If there is
--   nothing to be found, this function will hang indefinitely.
elemIndex :: Eq a => a -> Infinite a -> Word

-- | Return indices of all elements, equal to a given.
--   
--   This function isn't productive (e. g., head .
--   elemIndices f won't terminate), if no elements of the
--   input list are equal the given one.
elemIndices :: Eq a => a -> Infinite a -> Infinite Word

-- | Return an index of the first element, satisfying a predicate. If there
--   is nothing to be found, this function will hang indefinitely.
findIndex :: (a -> Bool) -> Infinite a -> Word

-- | Return indices of all elements, satisfying a predicate.
--   
--   This function isn't productive (e. g., head .'
--   findIndices f won't terminate), if no elements of the
--   input list satisfy the predicate.
findIndices :: (a -> Bool) -> Infinite a -> Infinite Word

-- | Zip two infinite lists.
zip :: Infinite a -> Infinite b -> Infinite (a, b)

-- | Zip two infinite lists with a given function.
zipWith :: (a -> b -> c) -> Infinite a -> Infinite b -> Infinite c

-- | Zip three infinite lists.
zip3 :: Infinite a -> Infinite b -> Infinite c -> Infinite (a, b, c)

-- | Zip three infinite lists with a given function.
zipWith3 :: (a -> b -> c -> d) -> Infinite a -> Infinite b -> Infinite c -> Infinite d

-- | Zip four infinite lists.
zip4 :: Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite (a, b, c, d)

-- | Zip four infinite lists with a given function.
zipWith4 :: (a -> b -> c -> d -> e) -> Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite e

-- | Zip five infinite lists.
zip5 :: Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite e -> Infinite (a, b, c, d, e)

-- | Zip five infinite lists with a given function.
zipWith5 :: (a -> b -> c -> d -> e -> f) -> Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite e -> Infinite f

-- | Zip six infinite lists.
zip6 :: Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite e -> Infinite f -> Infinite (a, b, c, d, e, f)

-- | Zip six infinite lists with a given function.
zipWith6 :: (a -> b -> c -> d -> e -> f -> g) -> Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite e -> Infinite f -> Infinite g

-- | Zip seven infinite lists.
zip7 :: Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite e -> Infinite f -> Infinite g -> Infinite (a, b, c, d, e, f, g)

-- | Zip seven infinite lists with a given function.
zipWith7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> Infinite a -> Infinite b -> Infinite c -> Infinite d -> Infinite e -> Infinite f -> Infinite g -> Infinite h

-- | Zip an Infinite with any Traversable, maintaining the
--   shape of the latter.
--   
--   
--   >>> import Data.Functor.Compose (Compose(..))
--   
--   >>> heteroZip (0...) (Compose [Just 10, Nothing, Just 20])
--   Compose [Just (0,10),Nothing,Just (1,20)]
--   
heteroZip :: Traversable t => Infinite a -> t b -> t (a, b)

-- | Use a given function to zip an Infinite with any
--   Traversable, maintaining the shape of the latter.
--   
--   
--   >>> import Data.Functor.Compose (Compose(..))
--   
--   >>> heteroZipWith (+) (0...) (Compose [Just 10, Nothing, Just 20])
--   Compose [Just 10,Nothing,Just 21]
--   
heteroZipWith :: Traversable t => (a -> b -> c) -> Infinite a -> t b -> t c

-- | Unzip an infinite list of tuples.
unzip :: Infinite (a, b) -> (Infinite a, Infinite b)

-- | Unzip an infinite list of triples.
unzip3 :: Infinite (a, b, c) -> (Infinite a, Infinite b, Infinite c)

-- | Unzip an infinite list of quadruples.
unzip4 :: Infinite (a, b, c, d) -> (Infinite a, Infinite b, Infinite c, Infinite d)

-- | Unzip an infinite list of quintuples.
unzip5 :: Infinite (a, b, c, d, e) -> (Infinite a, Infinite b, Infinite c, Infinite d, Infinite e)

-- | Unzip an infinite list of sextuples.
unzip6 :: Infinite (a, b, c, d, e, f) -> (Infinite a, Infinite b, Infinite c, Infinite d, Infinite e, Infinite f)

-- | Unzip an infinite list of septuples.
unzip7 :: Infinite (a, b, c, d, e, f, g) -> (Infinite a, Infinite b, Infinite c, Infinite d, Infinite e, Infinite f, Infinite g)

-- | Split an infinite string into lines, by \n. Empty lines are
--   preserved.
--   
--   In contrast to their counterparts from Data.List, it holds that
--   unlines . lines = id.
lines :: Infinite Char -> Infinite [Char]

-- | Split an infinite string into words, by any isSpace symbol.
--   Leading spaces are removed and, as underlined by the return type,
--   repeated spaces are treated as a single delimiter.
words :: Infinite Char -> Infinite (NonEmpty Char)

-- | Concatenate lines together with \n.
--   
--   In contrast to their counterparts from Data.List, it holds that
--   unlines . lines = id.
unlines :: Infinite [Char] -> Infinite Char

-- | Concatenate words together with a space.
--   
--   The function is meant to be a counterpart of with words. If you
--   need to concatenate together Infinite
--   [Char], use intercalate
--   (pure ' ').
unwords :: Infinite (NonEmpty Char) -> Infinite Char

-- | Remove duplicate from a list, keeping only the first occurrence of
--   each element. Because of a very weak constraint on a, this
--   operation takes O(n²) time. Consider using nubOrd
--   instead.
nub :: Eq a => Infinite a -> Infinite a

-- | Same as nub, but asymptotically faster, taking only
--   O(n log n) time.
nubOrd :: Ord a => Infinite a -> Infinite a

-- | Remove all occurrences of an element from an infinite list.
delete :: Eq a => a -> Infinite a -> Infinite a

-- | Take an infinite list and remove the first occurrence of every element
--   of a finite list.
(\\) :: Eq a => Infinite a -> [a] -> Infinite a

-- | Union of a finite and an infinite list. It contains the finite list as
--   a prefix and afterwards all non-duplicate elements of the infinite
--   list, which are not members of the finite list.
union :: Eq a => [a] -> Infinite a -> Infinite a

-- | Return all elements of an infinite list, which are simultaneously
--   members of a finite list.
intersect :: Eq a => Infinite a -> [a] -> Infinite a

-- | Insert an element at the first position where it is less than or equal
--   to the next one. If the input was sorted, the output remains sorted as
--   well.
insert :: Ord a => a -> Infinite a -> Infinite a

-- | Overloaded version of nub. Consider using nubOrdBy
--   instead.
nubBy :: (a -> a -> Bool) -> Infinite a -> Infinite a

-- | Overloaded version of nubOrd.
nubOrdBy :: (a -> a -> Ordering) -> Infinite a -> Infinite a

-- | Overloaded version of delete.
deleteBy :: (a -> b -> Bool) -> a -> Infinite b -> Infinite b

-- | Overloaded version of (\\).
deleteFirstsBy :: (a -> b -> Bool) -> Infinite b -> [a] -> Infinite b

-- | Overloaded version of union.
unionBy :: (a -> a -> Bool) -> [a] -> Infinite a -> Infinite a

-- | Overloaded version of intersect.
intersectBy :: (a -> b -> Bool) -> Infinite a -> [b] -> Infinite a

-- | Overloaded version of group.
groupBy :: (a -> a -> Bool) -> Infinite a -> Infinite (NonEmpty a)

-- | Overloaded version of insert.
insertBy :: (a -> a -> Ordering) -> a -> Infinite a -> Infinite a

-- | Take a prefix of given length.
genericTake :: Integral i => i -> Infinite a -> [a]

-- | Drop a prefix of given length.
genericDrop :: Integral i => i -> Infinite a -> Infinite a

-- | Split an infinite list into a prefix of given length and the rest.
genericSplitAt :: Integral i => i -> Infinite a -> ([a], Infinite a)
instance GHC.Internal.Base.Applicative Data.List.Infinite.Internal.Infinite
instance GHC.Internal.Base.Functor Data.List.Infinite.Internal.Infinite
instance GHC.Internal.Control.Monad.Fix.MonadFix Data.List.Infinite.Internal.Infinite
instance GHC.Internal.Base.Monad Data.List.Infinite.Internal.Infinite
