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

-- | An enhanced core prelude; a common foundation for alternate preludes.
--   
--   Please see the README on Github at
--   https://github.com/snoyberg/basic-prelude#readme
@package basic-prelude
@version 0.7.0

module CorePrelude

-- | ($) is the function application operator.
--   
--   Applying ($) to a function f and an argument
--   x gives the same result as applying f to x
--   directly. The definition is akin to this:
--   
--   
--   ($) :: (a -> b) -> a -> b
--   ($) f x = f x
--   
--   
--   This is id specialized from a -> a to
--   (a -> b) -> (a -> b) which by the associativity of
--   (->) is the same as (a -> b) -> a -> b.
--   
--   On the face of it, this may appear pointless! But it's actually one of
--   the most useful and important operators in Haskell.
--   
--   The order of operations is very different between ($) and
--   normal function application. Normal function application has
--   precedence 10 - higher than any operator - and associates to the left.
--   So these two definitions are equivalent:
--   
--   
--   expr = min 5 1 + 5
--   expr = ((min 5) 1) + 5
--   
--   
--   ($) has precedence 0 (the lowest) and associates to the
--   right, so these are equivalent:
--   
--   
--   expr = min 5 $ 1 + 5
--   expr = (min 5) (1 + 5)
--   
--   
--   
Examples
--   
--   A common use cases of ($) is to avoid parentheses in complex
--   expressions.
--   
--   For example, instead of using nested parentheses in the following
--   Haskell function:
--   
--   
--   -- | Sum numbers in a string: strSum "100  5 -7" == 98
--   strSum :: String -> Int
--   strSum s = sum (mapMaybe readMaybe (words s))
--   
--   
--   we can deploy the function application operator:
--   
--   
--   -- | Sum numbers in a string: strSum "100  5 -7" == 98
--   strSum :: String -> Int
--   strSum s = sum $ mapMaybe readMaybe $ words s
--   
--   
--   ($) is also used as a section (a partially applied operator),
--   in order to indicate that we wish to apply some yet-unspecified
--   function to a given value. For example, to apply the argument
--   5 to a list of functions:
--   
--   
--   applyFive :: [Int]
--   applyFive = map ($ 5) [(+1), (2^)]
--   >>> [6, 32]
--   
--   
--   
Technical Remark (Representation Polymorphism)
--   
--   ($) is fully representation-polymorphic. This allows it to
--   also be used with arguments of unlifted and even unboxed kinds, such
--   as unboxed integers:
--   
--   
--   fastMod :: Int -> Int -> Int
--   fastMod (I# x) (I# m) = I# $ remInt# x m
--   
($) :: (a -> b) -> a -> b
infixr 0 $

-- | Strict (call-by-value) application operator. It takes a function and
--   an argument, evaluates the argument to weak head normal form (WHNF),
--   then calls the function with that value.
($!) :: (a -> b) -> a -> b
infixr 0 $!

-- | Boolean "and", lazy in the second argument
(&&) :: Bool -> Bool -> Bool
infixr 3 &&

-- | Boolean "or", lazy in the second argument
(||) :: Bool -> Bool -> Bool
infixr 2 ||

-- | morphism composition
(.) :: forall (b :: k) (c :: k) (a :: k). Category cat => cat b c -> cat a b -> cat a c
infixr 9 .

-- | Boolean "not"
not :: Bool -> Bool

-- | otherwise is defined as the value True. It helps to make
--   guards more readable. eg.
--   
--   
--   f x | x < 0     = ...
--       | otherwise = ...
--   
otherwise :: Bool

-- | Extract the first component of a pair.
fst :: (a, b) -> a

-- | Extract the second component of a pair.
snd :: (a, b) -> b

-- | the identity morphism
id :: forall (a :: k). Category cat => cat a a

-- | The maybe function takes a default value, a function, and a
--   Maybe value. If the Maybe value is Nothing, the
--   function returns the default value. Otherwise, it applies the function
--   to the value inside the Just and returns the result.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> maybe False odd (Just 3)
--   True
--   
--   
--   
--   >>> maybe False odd Nothing
--   False
--   
--   
--   Read an integer from a string using readMaybe. If we succeed,
--   return twice the integer; that is, apply (*2) to it. If
--   instead we fail to parse an integer, return 0 by default:
--   
--   
--   >>> import GHC.Internal.Text.Read ( readMaybe )
--   
--   >>> maybe 0 (*2) (readMaybe "5")
--   10
--   
--   >>> maybe 0 (*2) (readMaybe "")
--   0
--   
--   
--   Apply show to a Maybe Int. If we have Just n,
--   we want to show the underlying Int n. But if we have
--   Nothing, we return the empty string instead of (for example)
--   "Nothing":
--   
--   
--   >>> maybe "" show (Just 5)
--   "5"
--   
--   >>> maybe "" show Nothing
--   ""
--   
maybe :: b -> (a -> b) -> Maybe a -> b

-- | Case analysis for the Either type. If the value is
--   Left a, apply the first function to a; if it
--   is Right b, apply the second function to b.
--   
--   
Examples
--   
--   We create two values of type Either String
--   Int, one using the Left constructor and another
--   using the Right constructor. Then we apply "either" the
--   length function (if we have a String) or the "times-two"
--   function (if we have an Int):
--   
--   
--   >>> let s = Left "foo" :: Either String Int
--   
--   >>> let n = Right 3 :: Either String Int
--   
--   >>> either length (*2) s
--   3
--   
--   >>> either length (*2) n
--   6
--   
either :: (a -> c) -> (b -> c) -> Either a b -> c

-- | flip f takes its (first) two arguments in the reverse
--   order of f.
--   
--   
--   flip f x y = f y x
--   
--   
--   
--   flip . flip = id
--   
--   
--   
Examples
--   
--   
--   >>> flip (++) "hello" "world"
--   "worldhello"
--   
--   
--   
--   >>> let (.>) = flip (.) in (+1) .> show $ 5
--   "6"
--   
flip :: (a -> b -> c) -> b -> a -> c

-- | const x y always evaluates to x, ignoring its second
--   argument.
--   
--   
--   const x = \_ -> x
--   
--   
--   This function might seem useless at first glance, but it can be very
--   useful in a higher order context.
--   
--   
Examples
--   
--   
--   >>> const 42 "hello"
--   42
--   
--   
--   
--   >>> map (const 42) [0..3]
--   [42,42,42,42]
--   
const :: a -> b -> a

-- | error stops execution and displays an error message.
error :: HasCallStack => [Char] -> a
putStr :: MonadIO m => Text -> m ()
putStrLn :: MonadIO m => Text -> m ()
print :: (MonadIO m, Show a) => a -> m ()
getArgs :: MonadIO m => m [Text]

-- | error applied to Text
--   
--   Since 0.4.1
terror :: HasCallStack => Text -> a
odd :: Integral a => a -> Bool
even :: Integral a => a -> Bool

-- | uncurry converts a curried function to a function on pairs.
--   
--   
Examples
--   
--   
--   >>> uncurry (+) (1,2)
--   3
--   
--   
--   
--   >>> uncurry ($) (show, 1)
--   "1"
--   
--   
--   
--   >>> map (uncurry max) [(1,2), (3,4), (6,8)]
--   [2,4,8]
--   
uncurry :: (a -> b -> c) -> (a, b) -> c

-- | Convert an uncurried function to a curried function.
--   
--   
Examples
--   
--   
--   >>> curry fst 1 2
--   1
--   
curry :: ((a, b) -> c) -> a -> b -> c

-- | Swap the components of a pair.
swap :: (a, b) -> (b, a)

-- | until p f yields the result of applying f
--   until p holds.
until :: (a -> Bool) -> (a -> a) -> a -> a

-- | asTypeOf is a type-restricted version of const. It is
--   usually used as an infix operator, and its typing forces its first
--   argument (which is usually overloaded) to have the same type as the
--   second.
asTypeOf :: a -> a -> a

-- | A special case of error. It is expected that compilers will
--   recognize this and insert error messages which are more appropriate to
--   the context in which undefined appears.
undefined :: HasCallStack => a

-- | The value of seq a b is bottom if a is
--   bottom, and otherwise equal to b. In other words, it
--   evaluates the first argument a to weak head normal form
--   (WHNF). seq is usually introduced to improve performance by
--   avoiding unneeded laziness.
--   
--   A note on evaluation order: the expression seq a b
--   does not guarantee that a will be evaluated before
--   b. The only guarantee given by seq is that the both
--   a and b will be evaluated before seq returns
--   a value. In particular, this means that b may be evaluated
--   before a. If you need to guarantee a specific order of
--   evaluation, you must use the function pseq from the
--   "parallel" package.
seq :: a -> b -> b
infixr 0 `seq`

-- | The Ord class is used for totally ordered datatypes.
--   
--   Instances of Ord can be derived for any user-defined datatype
--   whose constituent types are in Ord. The declared order of the
--   constructors in the data declaration determines the ordering in
--   derived Ord instances. The Ordering datatype allows a
--   single comparison to determine the precise ordering of two objects.
--   
--   Ord, as defined by the Haskell report, implements a total order
--   and has the following properties:
--   
--   
--   
- Comparability x <= y || y <= x =
--   True
--   
- Transitivity if x <= y && y <=
--   z = True, then x <= z = True
--   
- Reflexivity x <= x = True
--   
- Antisymmetry if x <= y && y <=
--   x = True, then x == y = True
--   
--   
--   The following operator interactions are expected to hold:
--   
--   
--   
- x >= y = y <= x
--   
- x < y = x <= y && x /= y
--   
- x > y = y < x
--   
- x < y = compare x y == LT
--   
- x > y = compare x y == GT
--   
- x == y = compare x y == EQ
--   
- min x y == if x <= y then x else y = True
--   
- max x y == if x >= y then x else y = True
--   
--   
--   Note that (7.) and (8.) do not require min and
--   max to return either of their arguments. The result is merely
--   required to equal one of the arguments in terms of (==).
--   
--   Minimal complete definition: either compare or <=.
--   Using compare can be more efficient for complex types.
class Eq a => Ord a
compare :: Ord a => a -> a -> Ordering
(<) :: Ord a => a -> a -> Bool
(<=) :: Ord a => a -> a -> Bool
(>) :: Ord a => a -> a -> Bool
(>=) :: Ord a => a -> a -> Bool
max :: Ord a => a -> a -> a
min :: Ord a => a -> a -> a
infix 4 >=
infix 4 <
infix 4 <=
infix 4 >

-- | The Eq class defines equality (==) and inequality
--   (/=). All the basic datatypes exported by the Prelude
--   are instances of Eq, and Eq may be derived for any
--   datatype whose constituents are also instances of Eq.
--   
--   The Haskell Report defines no laws for Eq. However, instances
--   are encouraged to follow these properties:
--   
--   
--   
- Reflexivity x == x = True
--   
- Symmetry x == y = y == x
--   
- Transitivity if x == y && y == z =
--   True, then x == z = True
--   
- Extensionality if x == y = True and
--   f is a function whose return type is an instance of
--   Eq, then f x == f y = True
--   
- Negation x /= y = not (x ==
--   y)
--   
class Eq a
(==) :: Eq a => a -> a -> Bool
(/=) :: Eq a => a -> a -> Bool
infix 4 ==
infix 4 /=

-- | The Bounded class is used to name the upper and lower limits of
--   a type. Ord is not a superclass of Bounded since types
--   that are not totally ordered may also have upper and lower bounds.
--   
--   The Bounded class may be derived for any enumeration type;
--   minBound is the first constructor listed in the data
--   declaration and maxBound is the last. Bounded may also
--   be derived for single-constructor datatypes whose constituent types
--   are in Bounded.
class Bounded a
minBound :: Bounded a => a
maxBound :: Bounded a => a

-- | Class Enum defines operations on sequentially ordered types.
--   
--   The enumFrom... methods are used in Haskell's translation of
--   arithmetic sequences.
--   
--   Instances of Enum may be derived for any enumeration type
--   (types whose constructors have no fields). The nullary constructors
--   are assumed to be numbered left-to-right by fromEnum from
--   0 through n-1. See Chapter 10 of the Haskell
--   Report for more details.
--   
--   For any type that is an instance of class Bounded as well as
--   Enum, the following should hold:
--   
--   
--   
- The calls succ maxBound and pred
--   minBound should result in a runtime error.
--   
- fromEnum and toEnum should give a runtime error if
--   the result value is not representable in the result type. For example,
--   toEnum 7 :: Bool is an error.
--   
- enumFrom and enumFromThen should be defined with an
--   implicit bound, thus:
--   
--   
--   
--   enumFrom     x   = enumFromTo     x maxBound
--   enumFromThen x y = enumFromThenTo x y bound
--     where
--       bound | fromEnum y >= fromEnum x = maxBound
--             | otherwise                = minBound
--   
class Enum a

-- | Successor of a value. For numeric types, succ adds 1.
succ :: Enum a => a -> a

-- | Predecessor of a value. For numeric types, pred subtracts 1.
pred :: Enum a => a -> a

-- | Convert from an Int.
toEnum :: Enum a => Int -> a

-- | Convert to an Int. It is implementation-dependent what
--   fromEnum returns when applied to a value that is too large to
--   fit in an Int.
fromEnum :: Enum a => a -> Int

-- | Used in Haskell's translation of [n..] with [n..] =
--   enumFrom n, a possible implementation being enumFrom n = n :
--   enumFrom (succ n).
--   
--   
Examples
--   
--   
--   
- 
enumFrom 4 :: [Integer] = [4,5,6,7,...]

--   
- 
enumFrom 6 :: [Int] = [6,7,8,9,...,maxBound ::
--   Int]

--   
enumFrom :: Enum a => a -> [a]

-- | Used in Haskell's translation of [n,n'..] with [n,n'..] =
--   enumFromThen n n', a possible implementation being
--   enumFromThen n n' = n : n' : worker (f x) (f x n'),
--   worker s v = v : worker s (s v), x = fromEnum n' -
--   fromEnum n and
--   
--   
--   f n y
--     | n > 0 = f (n - 1) (succ y)
--     | n < 0 = f (n + 1) (pred y)
--     | otherwise = y
--   
--   
--   
--   
Examples
--   
--   
--   
- 
enumFromThen 4 6 :: [Integer] = [4,6,8,10...]

--   
- 
enumFromThen 6 2 :: [Int] = [6,2,-2,-6,...,minBound ::
--   Int]

--   
enumFromThen :: Enum a => a -> a -> [a]

-- | Used in Haskell's translation of [n..m] with [n..m] =
--   enumFromTo n m, a possible implementation being
--   
--   
--   enumFromTo n m
--      | n <= m = n : enumFromTo (succ n) m
--      | otherwise = []
--   
--   
--   
--   
Examples
--   
--   
--   
- 
enumFromTo 6 10 :: [Int] = [6,7,8,9,10]

--   
- 
enumFromTo 42 1 :: [Integer] = []

--   
enumFromTo :: Enum a => a -> a -> [a]

-- | Used in Haskell's translation of [n,n'..m] with [n,n'..m]
--   = enumFromThenTo n n' m, a possible implementation being
--   enumFromThenTo n n' m = worker (f x) (c x) n m, x =
--   fromEnum n' - fromEnum n, c x = bool (>=) ((x
--   0)
--   
--   
--   f n y
--      | n > 0 = f (n - 1) (succ y)
--      | n < 0 = f (n + 1) (pred y)
--      | otherwise = y
--   
--   
--   
--   and
--   
--   
--   worker s c v m
--      | c v m = v : worker s c (s v) m
--      | otherwise = []
--   
--   
--   
--   
Examples
--   
--   
--   
- 
enumFromThenTo 4 2 -6 :: [Integer] =
--   [4,2,0,-2,-4,-6]

--   
- 
enumFromThenTo 6 8 2 :: [Int] = []

--   
enumFromThenTo :: Enum a => a -> a -> a -> [a]

-- | Conversion of values to readable Strings.
--   
--   Derived instances of Show have the following properties, which
--   are compatible with derived instances of Read:
--   
--   
--   
- The result of show is a syntactically correct Haskell
--   expression containing only constants, given the fixity declarations in
--   force at the point where the type is declared. It contains only the
--   constructor names defined in the data type, parentheses, and spaces.
--   When labelled constructor fields are used, braces, commas, field
--   names, and equal signs are also used.
--   
- If the constructor is defined to be an infix operator, then
--   showsPrec will produce infix applications of the
--   constructor.
--   
- the representation will be enclosed in parentheses if the
--   precedence of the top-level constructor in x is less than
--   d (associativity is ignored). Thus, if d is
--   0 then the result is never surrounded in parentheses; if
--   d is 11 it is always surrounded in parentheses,
--   unless it is an atomic expression.
--   
- If the constructor is defined using record syntax, then
--   show will produce the record-syntax form, with the fields given
--   in the same order as the original declaration.
--   
--   
--   For example, given the declarations
--   
--   
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--   
--   
--   the derived instance of Show is equivalent to
--   
--   
--   instance (Show a) => Show (Tree a) where
--   
--          showsPrec d (Leaf m) = showParen (d > app_prec) $
--               showString "Leaf " . showsPrec (app_prec+1) m
--            where app_prec = 10
--   
--          showsPrec d (u :^: v) = showParen (d > up_prec) $
--               showsPrec (up_prec+1) u .
--               showString " :^: "      .
--               showsPrec (up_prec+1) v
--            where up_prec = 5
--   
--   
--   Note that right-associativity of :^: is ignored. For example,
--   
--   
--   
- show (Leaf 1 :^: Leaf 2 :^: Leaf 3) produces the
--   string "Leaf 1 :^: (Leaf 2 :^: Leaf 3)".
--   
class Show a

-- | Parsing of Strings, producing values.
--   
--   Derived instances of Read make the following assumptions, which
--   derived instances of Show obey:
--   
--   
--   
- If the constructor is defined to be an infix operator, then the
--   derived Read instance will parse only infix applications of the
--   constructor (not the prefix form).
--   
- Associativity is not used to reduce the occurrence of parentheses,
--   although precedence may be.
--   
- If the constructor is defined using record syntax, the derived
--   Read will parse only the record-syntax form, and furthermore,
--   the fields must be given in the same order as the original
--   declaration.
--   
- The derived Read instance allows arbitrary Haskell
--   whitespace between tokens of the input string. Extra parentheses are
--   also allowed.
--   
--   
--   For example, given the declarations
--   
--   
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--   
--   
--   the derived instance of Read in Haskell 2010 is equivalent to
--   
--   
--   instance (Read a) => Read (Tree a) where
--   
--           readsPrec d r =  readParen (d > app_prec)
--                            (\r -> [(Leaf m,t) |
--                                    ("Leaf",s) <- lex r,
--                                    (m,t) <- readsPrec (app_prec+1) s]) r
--   
--                         ++ readParen (d > up_prec)
--                            (\r -> [(u:^:v,w) |
--                                    (u,s) <- readsPrec (up_prec+1) r,
--                                    (":^:",t) <- lex s,
--                                    (v,w) <- readsPrec (up_prec+1) t]) r
--   
--             where app_prec = 10
--                   up_prec = 5
--   
--   
--   Note that right-associativity of :^: is unused.
--   
--   The derived instance in GHC is equivalent to
--   
--   
--   instance (Read a) => Read (Tree a) where
--   
--           readPrec = parens $ (prec app_prec $ do
--                                    Ident "Leaf" <- lexP
--                                    m <- step readPrec
--                                    return (Leaf m))
--   
--                        +++ (prec up_prec $ do
--                                    u <- step readPrec
--                                    Symbol ":^:" <- lexP
--                                    v <- step readPrec
--                                    return (u :^: v))
--   
--             where app_prec = 10
--                   up_prec = 5
--   
--           readListPrec = readListPrecDefault
--   
--   
--   Why do both readsPrec and readPrec exist, and why does
--   GHC opt to implement readPrec in derived Read instances
--   instead of readsPrec? The reason is that readsPrec is
--   based on the ReadS type, and although ReadS is mentioned
--   in the Haskell 2010 Report, it is not a very efficient parser data
--   structure.
--   
--   readPrec, on the other hand, is based on a much more efficient
--   ReadPrec datatype (a.k.a "new-style parsers"), but its
--   definition relies on the use of the RankNTypes language
--   extension. Therefore, readPrec (and its cousin,
--   readListPrec) are marked as GHC-only. Nevertheless, it is
--   recommended to use readPrec instead of readsPrec
--   whenever possible for the efficiency improvements it brings.
--   
--   As mentioned above, derived Read instances in GHC will
--   implement readPrec instead of readsPrec. The default
--   implementations of readsPrec (and its cousin, readList)
--   will simply use readPrec under the hood. If you are writing a
--   Read instance by hand, it is recommended to write it like so:
--   
--   
--   instance Read T where
--     readPrec     = ...
--     readListPrec = readListPrecDefault
--   
class Read a

-- | A type f is a Functor if it provides a function fmap
--   which, given any types a and b lets you apply any
--   function from (a -> b) to turn an f a into an
--   f b, preserving the structure of f. Furthermore
--   f needs to adhere to the following:
--   
--   
--   
- Identity fmap id == id
--   
- Composition fmap (f . g) == fmap f .
--   fmap g
--   
--   
--   Note, that the second law follows from the free theorem of the type
--   fmap and the first law, so you need only check that the former
--   condition holds. See these articles by School of Haskell or
--   David Luposchainsky for an explanation.
class Functor (f :: Type -> Type)

-- | fmap is used to apply a function of type (a -> b)
--   to a value of type f a, where f is a functor, to produce a
--   value of type f b. Note that for any type constructor with
--   more than one parameter (e.g., Either), only the last type
--   parameter can be modified with fmap (e.g., b in
--   `Either a b`).
--   
--   Some type constructors with two parameters or more have a
--   Bifunctor instance that allows both the last and the
--   penultimate parameters to be mapped over.
--   
--   
Examples
--   
--   Convert from a Maybe Int to a Maybe String
--   using show:
--   
--   
--   >>> fmap show Nothing
--   Nothing
--   
--   >>> fmap show (Just 3)
--   Just "3"
--   
--   
--   Convert from an Either Int Int to an Either Int
--   String using show:
--   
--   
--   >>> fmap show (Left 17)
--   Left 17
--   
--   >>> fmap show (Right 17)
--   Right "17"
--   
--   
--   Double each element of a list:
--   
--   
--   >>> fmap (*2) [1,2,3]
--   [2,4,6]
--   
--   
--   Apply even to the second element of a pair:
--   
--   
--   >>> fmap even (2,2)
--   (2,True)
--   
--   
--   It may seem surprising that the function is only applied to the last
--   element of the tuple compared to the list example above which applies
--   it to every element in the list. To understand, remember that tuples
--   are type constructors with multiple type parameters: a tuple of 3
--   elements (a,b,c) can also be written (,,) a b c and
--   its Functor instance is defined for Functor ((,,) a
--   b) (i.e., only the third parameter is free to be mapped over with
--   fmap).
--   
--   It explains why fmap can be used with tuples containing
--   values of different types as in the following example:
--   
--   
--   >>> fmap even ("hello", 1.0, 4)
--   ("hello",1.0,True)
--   
fmap :: Functor f => (a -> b) -> f a -> f b

-- | Replace all locations in the input with the same value. The default
--   definition is fmap . const, but this may be
--   overridden with a more efficient version.
--   
--   
Examples
--   
--   Perform a computation with Maybe and replace the result with a
--   constant value if it is Just:
--   
--   
--   >>> 'a' <$ Just 2
--   Just 'a'
--   
--   >>> 'a' <$ Nothing
--   Nothing
--   
(<$) :: Functor f => a -> f b -> f a
infixl 4 <$

-- | The Monad class defines the basic operations over a
--   monad, a concept from a branch of mathematics known as
--   category theory. From the perspective of a Haskell programmer,
--   however, it is best to think of a monad as an abstract datatype
--   of actions. Haskell's do expressions provide a convenient
--   syntax for writing monadic expressions.
--   
--   Instances of Monad should satisfy the following:
--   
--   
--   
- Left identity return a >>= k = k
--   a
--   
- Right identity m >>= return =
--   m
--   
- Associativity m >>= (\x -> k x
--   >>= h) = (m >>= k) >>=
--   h
--   
--   
--   Furthermore, the Monad and Applicative operations should
--   relate as follows:
--   
--   
--   
- 
pure = return

--   
- 
m1 <*> m2 = m1 >>= (\x1 -> m2
--   >>= (\x2 -> return (x1 x2)))

--   
--   
--   The above laws imply:
--   
--   
--   
- 
fmap f xs = xs >>= return .
--   f

--   
- 
(>>) = (*>)

--   
--   
--   and that pure and (<*>) satisfy the applicative
--   functor laws.
--   
--   The instances of Monad for List, Maybe and
--   IO defined in the Prelude satisfy these laws.
class Applicative m => Monad (m :: Type -> Type)

-- | Sequentially compose two actions, passing any value produced by the
--   first as an argument to the second.
--   
--   'as >>= bs' can be understood as the do
--   expression
--   
--   
--   do a <- as
--      bs a
--   
--   
--   An alternative name for this function is 'bind', but some people may
--   refer to it as 'flatMap', which results from it being equivialent to
--   
--   
--   \x f -> join (fmap f x) :: Monad m => m a -> (a -> m b) -> m b
--   
--   
--   which can be seen as mapping a value with Monad m => m a ->
--   m (m b) and then 'flattening' m (m b) to m b
--   using join.
(>>=) :: Monad m => m a -> (a -> m b) -> m b

-- | Sequentially compose two actions, discarding any value produced by the
--   first, like sequencing operators (such as the semicolon) in imperative
--   languages.
--   
--   'as >> bs' can be understood as the do
--   expression
--   
--   
--   do as
--      bs
--   
--   
--   or in terms of (>>=) as
--   
--   
--   as >>= const bs
--   
(>>) :: Monad m => m a -> m b -> m b

-- | Inject a value into the monadic type. This function should not
--   be different from its default implementation as pure. The
--   justification for the existence of this function is merely historic.
return :: Monad m => a -> m a
infixl 1 >>=
infixl 1 >>

-- | Same as >>=, but with the arguments interchanged.
--   
--   
--   as >>= f == f =<< as
--   
(=<<) :: Monad m => (a -> m b) -> m a -> m b
infixr 1 =<<

-- | IsString is used in combination with the
--   -XOverloadedStrings language extension to convert the
--   literals to different string types.
--   
--   For example, if you use the text package, you can say
--   
--   
--   {-# LANGUAGE OverloadedStrings  #-}
--   
--   myText = "hello world" :: Text
--   
--   
--   Internally, the extension will convert this to the equivalent of
--   
--   
--   myText = fromString @Text ("hello world" :: String)
--   
--   
--   Note: You can use fromString in normal code as well,
--   but the usual performance/memory efficiency problems with
--   String apply.
class IsString a
fromString :: IsString a => String -> a

-- | Basic numeric class.
--   
--   The Haskell Report defines no laws for Num. However,
--   (+) and (*) are customarily expected
--   to define a ring and have the following properties:
--   
--   
--   
- Associativity of (+) (x + y) +
--   z = x + (y + z)
--   
- Commutativity of (+) x + y
--   = y + x
--   
- fromInteger 0 is the additive
--   identity x + fromInteger 0 = x
--   
- negate gives the additive inverse x +
--   negate x = fromInteger 0
--   
- Associativity of (*) (x * y) *
--   z = x * (y * z)
--   
- fromInteger 1 is the multiplicative
--   identity x * fromInteger 1 = x and
--   fromInteger 1 * x = x
--   
- Distributivity of (*) with respect to
--   (+) a * (b + c) = (a * b) + (a *
--   c) and (b + c) * a = (b * a) + (c * a)
--   
- Coherence with toInteger if the type also
--   implements Integral, then fromInteger is a left inverse
--   for toInteger, i.e. fromInteger (toInteger i) ==
--   i
--   
--   
--   Note that it isn't customarily expected that a type instance of
--   both Num and Ord implement an ordered ring. Indeed, in
--   base only Integer and Rational do.
class Num a
(+) :: Num a => a -> a -> a
(-) :: Num a => a -> a -> a
(*) :: Num a => a -> a -> a

-- | Unary negation.
negate :: Num a => a -> a

-- | Absolute value.
abs :: Num a => a -> a

-- | Sign of a number. The functions abs and signum should
--   satisfy the law:
--   
--   
--   abs x * signum x == x
--   
--   
--   For real numbers, the signum is either -1 (negative),
--   0 (zero) or 1 (positive).
signum :: Num a => a -> a

-- | Conversion from an Integer. An integer literal represents the
--   application of the function fromInteger to the appropriate
--   value of type Integer, so such literals have type
--   (Num a) => a.
fromInteger :: Num a => Integer -> a
infixl 6 -
infixl 6 +
infixl 7 *

-- | Real numbers.
--   
--   The Haskell report defines no laws for Real, however
--   Real instances are customarily expected to adhere to the
--   following law:
--   
--   
--   
- Coherence with fromRational if the type also
--   implements Fractional, then fromRational is a left
--   inverse for toRational, i.e. fromRational (toRational i) =
--   i
--   
--   
--   The law does not hold for Float, Double, CFloat,
--   CDouble, etc., because these types contain non-finite values,
--   which cannot be roundtripped through Rational.
class (Num a, Ord a) => Real a

-- | Rational equivalent of its real argument with full precision.
toRational :: Real a => a -> Rational

-- | Integral numbers, supporting integer division.
--   
--   The Haskell Report defines no laws for Integral. However,
--   Integral instances are customarily expected to define a
--   Euclidean domain and have the following properties for the
--   div/mod and quot/rem pairs, given suitable
--   Euclidean functions f and g:
--   
--   
--   
- x = y * quot x y + rem x y with rem x y
--   = fromInteger 0 or g (rem x y) < g
--   y
--   
- x = y * div x y + mod x y with mod x y
--   = fromInteger 0 or f (mod x y) < f
--   y
--   
--   
--   An example of a suitable Euclidean function, for Integer's
--   instance, is abs.
--   
--   In addition, toInteger should be total, and
--   fromInteger should be a left inverse for it, i.e.
--   fromInteger (toInteger i) = i.
class (Real a, Enum a) => Integral a

-- | Integer division truncated toward zero.
--   
--   WARNING: This function is partial (because it throws when 0 is passed
--   as the divisor) for all the integer types in base.
quot :: Integral a => a -> a -> a

-- | Integer remainder, satisfying
--   
--   
--   (x `quot` y)*y + (x `rem` y) == x
--   
--   
--   WARNING: This function is partial (because it throws when 0 is passed
--   as the divisor) for all the integer types in base.
rem :: Integral a => a -> a -> a

-- | Integer division truncated toward negative infinity.
--   
--   WARNING: This function is partial (because it throws when 0 is passed
--   as the divisor) for all the integer types in base.
div :: Integral a => a -> a -> a

-- | Integer modulus, satisfying
--   
--   
--   (x `div` y)*y + (x `mod` y) == x
--   
--   
--   WARNING: This function is partial (because it throws when 0 is passed
--   as the divisor) for all the integer types in base.
mod :: Integral a => a -> a -> a

-- | Simultaneous quot and rem.
--   
--   WARNING: This function is partial (because it throws when 0 is passed
--   as the divisor) for all the integer types in base.
quotRem :: Integral a => a -> a -> (a, a)

-- | simultaneous div and mod.
--   
--   WARNING: This function is partial (because it throws when 0 is passed
--   as the divisor) for all the integer types in base.
divMod :: Integral a => a -> a -> (a, a)

-- | Conversion to Integer.
toInteger :: Integral a => a -> Integer
infixl 7 `quot`
infixl 7 `rem`
infixl 7 `div`
infixl 7 `mod`

-- | Fractional numbers, supporting real division.
--   
--   The Haskell Report defines no laws for Fractional. However,
--   (+) and (*) are customarily expected
--   to define a division ring and have the following properties:
--   
--   
--   
- recip gives the multiplicative inverse x
--   * recip x = recip x * x = fromInteger 1
--   
- Totality of toRational toRational is
--   total
--   
- Coherence with toRational if the type also
--   implements Real, then fromRational is a left inverse for
--   toRational, i.e. fromRational (toRational i) = i
--   
--   
--   Note that it isn't customarily expected that a type instance of
--   Fractional implement a field. However, all instances in
--   base do.
class Num a => Fractional a

-- | Fractional division.
(/) :: Fractional a => a -> a -> a

-- | Reciprocal fraction.
recip :: Fractional a => a -> a

-- | Conversion from a Rational (that is Ratio
--   Integer). A floating literal stands for an application of
--   fromRational to a value of type Rational, so such
--   literals have type (Fractional a) => a.
fromRational :: Fractional a => Rational -> a
infixl 7 /

-- | Trigonometric and hyperbolic functions and related functions.
--   
--   The Haskell Report defines no laws for Floating. However,
--   (+), (*) and exp are
--   customarily expected to define an exponential field and have the
--   following properties:
--   
--   
--   
- exp (a + b) = exp a * exp b
--   
- exp (fromInteger 0) = fromInteger 1
--   
class Fractional a => Floating a
pi :: Floating a => a
exp :: Floating a => a -> a
log :: Floating a => a -> a
sqrt :: Floating a => a -> a
(**) :: Floating a => a -> a -> a
logBase :: Floating a => a -> a -> a
sin :: Floating a => a -> a
cos :: Floating a => a -> a
tan :: Floating a => a -> a
asin :: Floating a => a -> a
acos :: Floating a => a -> a
atan :: Floating a => a -> a
sinh :: Floating a => a -> a
cosh :: Floating a => a -> a
tanh :: Floating a => a -> a
asinh :: Floating a => a -> a
acosh :: Floating a => a -> a
atanh :: Floating a => a -> a
infixr 8 **

-- | Extracting components of fractions.
class (Real a, Fractional a) => RealFrac a

-- | The function properFraction takes a real fractional number
--   x and returns a pair (n,f) such that x =
--   n+f, and:
--   
--   
--   
- n is an integral number with the same sign as x;
--   and
--   
- f is a fraction with the same type and sign as
--   x, and with absolute value less than 1.
--   
--   
--   The default definitions of the ceiling, floor,
--   truncate and round functions are in terms of
--   properFraction.
properFraction :: (RealFrac a, Integral b) => a -> (b, a)

-- | truncate x returns the integer nearest x
--   between zero and x
truncate :: (RealFrac a, Integral b) => a -> b

-- | round x returns the nearest integer to x; the
--   even integer if x is equidistant between two integers
round :: (RealFrac a, Integral b) => a -> b

-- | ceiling x returns the least integer not less than
--   x
ceiling :: (RealFrac a, Integral b) => a -> b

-- | floor x returns the greatest integer not greater than
--   x
floor :: (RealFrac a, Integral b) => a -> b

-- | Efficient, machine-independent access to the components of a
--   floating-point number.
class (RealFrac a, Floating a) => RealFloat a

-- | a constant function, returning the radix of the representation (often
--   2)
floatRadix :: RealFloat a => a -> Integer

-- | a constant function, returning the number of digits of
--   floatRadix in the significand
floatDigits :: RealFloat a => a -> Int

-- | a constant function, returning the lowest and highest values the
--   exponent may assume
floatRange :: RealFloat a => a -> (Int, Int)

-- | The function decodeFloat applied to a real floating-point
--   number returns the significand expressed as an Integer and an
--   appropriately scaled exponent (an Int). If
--   decodeFloat x yields (m,n), then x
--   is equal in value to m*b^^n, where b is the
--   floating-point radix, and furthermore, either m and
--   n are both zero or else b^(d-1) <= abs m <
--   b^d, where d is the value of floatDigits
--   x. In particular, decodeFloat 0 = (0,0). If the
--   type contains a negative zero, also decodeFloat (-0.0) =
--   (0,0). The result of decodeFloat x is
--   unspecified if either of isNaN x or
--   isInfinite x is True.
decodeFloat :: RealFloat a => a -> (Integer, Int)

-- | encodeFloat performs the inverse of decodeFloat in the
--   sense that for finite x with the exception of -0.0,
--   uncurry encodeFloat (decodeFloat x) = x.
--   encodeFloat m n is one of the two closest
--   representable floating-point numbers to m*b^^n (or
--   ±Infinity if overflow occurs); usually the closer, but if
--   m contains too many bits, the result may be rounded in the
--   wrong direction.
encodeFloat :: RealFloat a => Integer -> Int -> a

-- | exponent corresponds to the second component of
--   decodeFloat. exponent 0 = 0 and for finite
--   nonzero x, exponent x = snd (decodeFloat x)
--   + floatDigits x. If x is a finite floating-point
--   number, it is equal in value to significand x * b ^^
--   exponent x, where b is the floating-point radix.
--   The behaviour is unspecified on infinite or NaN values.
exponent :: RealFloat a => a -> Int

-- | The first component of decodeFloat, scaled to lie in the open
--   interval (-1,1), either 0.0 or of absolute
--   value >= 1/b, where b is the floating-point
--   radix. The behaviour is unspecified on infinite or NaN
--   values.
significand :: RealFloat a => a -> a

-- | multiplies a floating-point number by an integer power of the radix
scaleFloat :: RealFloat a => Int -> a -> a

-- | True if the argument is an IEEE "not-a-number" (NaN) value
isNaN :: RealFloat a => a -> Bool

-- | True if the argument is an IEEE infinity or negative infinity
isInfinite :: RealFloat a => a -> Bool

-- | True if the argument is too small to be represented in
--   normalized format
isDenormalized :: RealFloat a => a -> Bool

-- | True if the argument is an IEEE negative zero
isNegativeZero :: RealFloat a => a -> Bool

-- | True if the argument is an IEEE floating point number
isIEEE :: RealFloat a => a -> Bool

-- | a version of arctangent taking two real floating-point arguments. For
--   real floating x and y, atan2 y x
--   computes the angle (from the positive x-axis) of the vector from the
--   origin to the point (x,y). atan2 y x returns
--   a value in the range [-pi, pi]. It follows the
--   Common Lisp semantics for the origin when signed zeroes are supported.
--   atan2 y 1, with y in a type that is
--   RealFloat, should return the same value as atan
--   y. A default definition of atan2 is provided, but
--   implementors can provide a more accurate implementation.
atan2 :: RealFloat a => a -> a -> a

-- | The Maybe type encapsulates an optional value. A value of type
--   Maybe a either contains a value of type a
--   (represented as Just a), or it is empty (represented
--   as Nothing). Using Maybe is a good way to deal with
--   errors or exceptional cases without resorting to drastic measures such
--   as error.
--   
--   The Maybe type is also a monad. It is a simple kind of error
--   monad, where all errors are represented by Nothing. A richer
--   error monad can be built using the Either type.
data Maybe a
Nothing :: Maybe a
Just :: a -> Maybe a
data Ordering
LT :: Ordering
EQ :: Ordering
GT :: Ordering
data Bool
False :: Bool
True :: Bool

-- | The character type Char represents Unicode codespace and its
--   elements are code points as in definitions D9 and D10 of the
--   Unicode Standard.
--   
--   Character literals in Haskell are single-quoted: 'Q',
--   'Я' or 'Ω'. To represent a single quote itself use
--   '\'', and to represent a backslash use '\\'. The
--   full grammar can be found in the section 2.6 of the Haskell 2010
--   Language Report.
--   
--   To specify a character by its code point one can use decimal,
--   hexadecimal or octal notation: '\65', '\x41' and
--   '\o101' are all alternative forms of 'A'. The
--   largest code point is '\x10ffff'.
--   
--   There is a special escape syntax for ASCII control characters:
--   
--   TODO: table
--   
--   Data.Char provides utilities to work with Char.
data Char

-- | A value of type IO a is a computation which, when
--   performed, does some I/O before returning a value of type a.
--   
--   There is really only one way to "perform" an I/O action: bind it to
--   Main.main in your program. When your program is run, the I/O
--   will be performed. It isn't possible to perform I/O from an arbitrary
--   function, unless that function is itself in the IO monad and
--   called at some point, directly or indirectly, from Main.main.
--   
--   IO is a monad, so IO actions can be combined using
--   either the do-notation or the >> and >>=
--   operations from the Monad class.
data IO a

-- | The Either type represents values with two possibilities: a
--   value of type Either a b is either Left
--   a or Right b.
--   
--   The Either type is sometimes used to represent a value which is
--   either correct or an error; by convention, the Left constructor
--   is used to hold an error value and the Right constructor is
--   used to hold a correct value (mnemonic: "right" also means "correct").
--   
--   
Examples
--   
--   The type Either String Int is the type
--   of values which can be either a String or an Int. The
--   Left constructor can be used only on Strings, and the
--   Right constructor can be used only on Ints:
--   
--   
--   >>> let s = Left "foo" :: Either String Int
--   
--   >>> s
--   Left "foo"
--   
--   >>> let n = Right 3 :: Either String Int
--   
--   >>> n
--   Right 3
--   
--   >>> :type s
--   s :: Either String Int
--   
--   >>> :type n
--   n :: Either String Int
--   
--   
--   The fmap from our Functor instance will ignore
--   Left values, but will apply the supplied function to values
--   contained in a Right:
--   
--   
--   >>> let s = Left "foo" :: Either String Int
--   
--   >>> let n = Right 3 :: Either String Int
--   
--   >>> fmap (*2) s
--   Left "foo"
--   
--   >>> fmap (*2) n
--   Right 6
--   
--   
--   The Monad instance for Either allows us to chain
--   together multiple actions which may fail, and fail overall if any of
--   the individual steps failed. First we'll write a function that can
--   either parse an Int from a Char, or fail.
--   
--   
--   >>> import Data.Char ( digitToInt, isDigit )
--   
--   >>> :{
--       let parseEither :: Char -> Either String Int
--           parseEither c
--             | isDigit c = Right (digitToInt c)
--             | otherwise = Left "parse error"
--   
--   >>> :}
--   
--   
--   The following should work, since both '1' and '2'
--   can be parsed as Ints.
--   
--   
--   >>> :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x <- parseEither '1'
--             y <- parseEither '2'
--             return (x + y)
--   
--   >>> :}
--   
--   
--   
--   >>> parseMultiple
--   Right 3
--   
--   
--   But the following should fail overall, since the first operation where
--   we attempt to parse 'm' as an Int will fail:
--   
--   
--   >>> :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x <- parseEither 'm'
--             y <- parseEither '2'
--             return (x + y)
--   
--   >>> :}
--   
--   
--   
--   >>> parseMultiple
--   Left "parse error"
--   
data Either a b
Left :: a -> Either a b
Right :: b -> Either a b

-- | A space-efficient representation of a Word8 vector, supporting
--   many efficient operations.
--   
--   A ByteString contains 8-bit bytes, or by using the operations
--   from Data.ByteString.Char8 it can be interpreted as containing
--   8-bit characters.
data ByteString
type LByteString = ByteString

-- | A space efficient, packed, unboxed Unicode text type.
data Text
type LText = Text

-- | A Map from keys k to values a.
--   
--   The Semigroup operation for Map is union, which
--   prefers values from the left operand. If m1 maps a key
--   k to a value a1, and m2 maps the same key
--   to a different value a2, then their union m1 <>
--   m2 maps k to a1.
data Map k a

-- | A map from keys to values. A map cannot contain duplicate keys; each
--   key can map to at most one value.
data HashMap k v

-- | A map of integers to values a.
data IntMap a

-- | A set of values a.
data Set a

-- | A set of values. A set cannot contain duplicate values.
data HashSet a

-- | A set of integers.
data IntSet

-- | General-purpose finite sequences.
data Seq a
data Vector a
type UVector = Vector
class (Vector Vector a, MVector MVector a) => Unbox a
type SVector = Vector

-- | The member functions of this class facilitate writing values of
--   primitive types to raw memory (which may have been allocated with the
--   above mentioned routines) and reading values from blocks of raw
--   memory. The class, furthermore, includes support for computing the
--   storage requirements and alignment restrictions of storable types.
--   
--   Memory addresses are represented as values of type Ptr
--   a, for some a which is an instance of class
--   Storable. The type argument to Ptr helps provide some
--   valuable type safety in FFI code (you can't mix pointers of different
--   types without an explicit cast), while helping the Haskell type system
--   figure out which marshalling method is needed for a given pointer.
--   
--   All marshalling between Haskell and a foreign language ultimately
--   boils down to translating Haskell data structures into the binary
--   representation of a corresponding data structure of the foreign
--   language and vice versa. To code this marshalling in Haskell, it is
--   necessary to manipulate primitive data types stored in unstructured
--   memory blocks. The class Storable facilitates this manipulation
--   on all types for which it is instantiated, which are the standard
--   basic types of Haskell, the fixed size Int types
--   (Int8, Int16, Int32, Int64), the fixed
--   size Word types (Word8, Word16, Word32,
--   Word64), StablePtr, all types from
--   Foreign.C.Types, as well as Ptr.
class Storable a

-- | The class of types that can be converted to a hash value.
--   
--   Minimal implementation: hashWithSalt.
--   
--   Hashable is intended exclusively for use in in-memory data
--   structures. . Hashable does not have a fixed standard.
--   This allows it to improve over time. . Because it does not have a
--   fixed standard, different computers or computers on different versions
--   of the code will observe different hash values. As such,
--   Hashable is not recommended for use other than in-memory
--   datastructures. Specifically, Hashable is not intended for
--   network use or in applications which persist hashed values. For stable
--   hashing use named hashes: sha256, crc32, xxhash etc.
--   
--   If you are looking for Hashable instance in time
--   package, check time-compat
class Eq a => Hashable a

-- | A Word is an unsigned integral type, with the same size as
--   Int.
data Word

-- | 8-bit unsigned integer type
data Word8

-- | 32-bit unsigned integer type
data Word32

-- | 64-bit unsigned integer type
data Word64

-- | A fixed-precision integer type with at least the range [-2^29 ..
--   2^29-1]. The exact range for a given implementation can be
--   determined by using minBound and maxBound from the
--   Bounded class.
data Int

-- | 32-bit signed integer type
data Int32

-- | 64-bit signed integer type
data Int64

-- | Arbitrary precision integers. In contrast with fixed-size integral
--   types such as Int, the Integer type represents the
--   entire infinite range of integers.
--   
--   Integers are stored in a kind of sign-magnitude form, hence do not
--   expect two's complement form when using bit operations.
--   
--   If the value is small (i.e., fits into an Int), the IS
--   constructor is used. Otherwise IP and IN constructors
--   are used to store a BigNat representing the positive or the
--   negative value magnitude, respectively.
--   
--   Invariant: IP and IN are used iff the value does not fit
--   in IS.
data Integer

-- | Arbitrary-precision rational numbers, represented as a ratio of two
--   Integer values. A rational number may be constructed using the
--   % operator.
type Rational = Ratio Integer

-- | Single-precision floating point numbers. It is desirable that this
--   type be at least equal in range and precision to the IEEE
--   single-precision type.
data Float

-- | Double-precision floating point numbers. It is desirable that this
--   type be at least equal in range and precision to the IEEE
--   double-precision type.
data Double

-- | raise a number to a non-negative integral power
(^) :: (Num a, Integral b) => a -> b -> a
infixr 8 ^

-- | raise a number to an integral power
(^^) :: (Fractional a, Integral b) => a -> b -> a
infixr 8 ^^

-- | the same as flip (-).
--   
--   Because - is treated specially in the Haskell grammar,
--   (- e) is not a section, but an application of
--   prefix negation. However, (subtract
--   exp) is equivalent to the disallowed section.
subtract :: Num a => a -> a -> a

-- | General coercion from Integral types.
--   
--   WARNING: This function performs silent truncation if the result type
--   is not at least as big as the argument's type.
fromIntegral :: (Integral a, Num b) => a -> b

-- | General coercion to Fractional types.
--   
--   WARNING: This function goes through the Rational type, which
--   does not have values for NaN for example. This means it does
--   not round-trip.
--   
--   For Double it also behaves differently with or without -O0:
--   
--   
--   Prelude> realToFrac nan -- With -O0
--   -Infinity
--   Prelude> realToFrac nan
--   NaN
--   
realToFrac :: (Real a, Fractional b) => a -> b

-- | The class of monoids (types with an associative binary operation that
--   has an identity). Instances should satisfy the following:
--   
--   
--   
- Right identity x <> mempty =
--   x
--   
- Left identity mempty <> x =
--   x
--   
- Associativity x <> (y <> z) =
--   (x <> y) <> z (Semigroup
--   law)
--   
- Concatenation mconcat = foldr
--   (<>) mempty
--   
--   
--   You can alternatively define mconcat instead of mempty,
--   in which case the laws are:
--   
--   
--   
- Unit mconcat (pure x) = x
--   
- Multiplication mconcat (join xss) =
--   mconcat (fmap mconcat xss)
--   
- Subclass mconcat (toList xs) =
--   sconcat xs
--   
--   
--   The method names refer to the monoid of lists under concatenation, but
--   there are many other instances.
--   
--   Some types can be viewed as a monoid in more than one way, e.g. both
--   addition and multiplication on numbers. In such cases we often define
--   newtypes and make those instances of Monoid, e.g.
--   Sum and Product.
--   
--   NOTE: Semigroup is a superclass of Monoid since
--   base-4.11.0.0.
class Semigroup a => Monoid a

-- | Identity of mappend
--   
--   
Examples
--   
--   
--   >>> "Hello world" <> mempty
--   "Hello world"
--   
--   
--   
--   >>> mempty <> [1, 2, 3]
--   [1,2,3]
--   
mempty :: Monoid a => a

-- | An associative operation
--   
--   NOTE: This method is redundant and has the default
--   implementation mappend = (<>) since
--   base-4.11.0.0. Should it be implemented manually, since
--   mappend is a synonym for (<>), it is expected that
--   the two functions are defined the same way. In a future GHC release
--   mappend will be removed from Monoid.
mappend :: Monoid a => a -> a -> a

-- | Fold a list using the monoid.
--   
--   For most types, the default definition for mconcat will be
--   used, but the function is included in the class definition so that an
--   optimized version can be provided for specific types.
--   
--   
--   >>> mconcat ["Hello", " ", "Haskell", "!"]
--   "Hello Haskell!"
--   
mconcat :: Monoid a => [a] -> a

-- | An associative operation.
--   
--   
Examples
--   
--   
--   >>> [1,2,3] <> [4,5,6]
--   [1,2,3,4,5,6]
--   
--   
--   
--   >>> Just [1, 2, 3] <> Just [4, 5, 6]
--   Just [1,2,3,4,5,6]
--   
--   
--   
--   >>> putStr "Hello, " <> putStrLn "World!"
--   Hello, World!
--   
(<>) :: Semigroup a => a -> a -> a
infixr 6 <>

-- | The Foldable class represents data structures that can be reduced to a
--   summary value one element at a time. Strict left-associative folds are
--   a good fit for space-efficient reduction, while lazy right-associative
--   folds are a good fit for corecursive iteration, or for folds that
--   short-circuit after processing an initial subsequence of the
--   structure's elements.
--   
--   Instances can be derived automatically by enabling the
--   DeriveFoldable extension. For example, a derived instance for
--   a binary tree might be:
--   
--   
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   
--   
--   A more detailed description can be found in the Overview
--   section of Data.Foldable#overview.
--   
--   For the class laws see the Laws section of
--   Data.Foldable#laws.
class Foldable (t :: Type -> Type)

-- | The sum of a collection of actions using (<|>),
--   generalizing concat.
--   
--   asum is just like msum, but generalised to
--   Alternative.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> asum [Just "Hello", Nothing, Just "World"]
--   Just "Hello"
--   
asum :: (Foldable t, Alternative f) => t (f a) -> f a

-- | Functors representing data structures that can be transformed to
--   structures of the same shape by performing an
--   Applicative (or, therefore, Monad) action on each
--   element from left to right.
--   
--   A more detailed description of what same shape means, the
--   various methods, how traversals are constructed, and example advanced
--   use-cases can be found in the Overview section of
--   Data.Traversable#overview.
--   
--   For the class laws see the Laws section of
--   Data.Traversable#laws.
class (Functor t, Foldable t) => Traversable (t :: Type -> Type)

-- | Send the first component of the input through the argument arrow, and
--   copy the rest unchanged to the output.
first :: Arrow a => a b c -> a (b, d) (c, d)

-- | A mirror image of first.
--   
--   The default definition may be overridden with a more efficient version
--   if desired.
second :: Arrow a => a b c -> a (d, b) (d, c)

-- | Split the input between the two argument arrows and combine their
--   output. Note that this is in general not a functor.
--   
--   The default definition may be overridden with a more efficient version
--   if desired.
(***) :: Arrow a => a b c -> a b' c' -> a (b, b') (c, c')
infixr 3 ***

-- | Fanout: send the input to both argument arrows and combine their
--   output.
--   
--   The default definition may be overridden with a more efficient version
--   if desired.
(&&&) :: Arrow a => a b c -> a b c' -> a b (c, c')
infixr 3 &&&

-- | Case analysis for the Bool type. bool f t p
--   evaluates to f when p is False, and evaluates
--   to t when p is True.
--   
--   This is equivalent to if p then t else f; that is, one can
--   think of it as an if-then-else construct with its arguments reordered.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> bool "foo" "bar" True
--   "bar"
--   
--   >>> bool "foo" "bar" False
--   "foo"
--   
--   
--   Confirm that bool f t p and if p then t else
--   f are equivalent:
--   
--   
--   >>> let p = True; f = "bar"; t = "foo"
--   
--   >>> bool f t p == if p then t else f
--   True
--   
--   >>> let p = False
--   
--   >>> bool f t p == if p then t else f
--   True
--   
bool :: a -> a -> Bool -> a

-- | The mapMaybe function is a version of map which can
--   throw out elements. In particular, the functional argument returns
--   something of type Maybe b. If this is Nothing,
--   no element is added on to the result list. If it is Just
--   b, then b is included in the result list.
--   
--   
Examples
--   
--   Using mapMaybe f x is a shortcut for
--   catMaybes $ map f x in most cases:
--   
--   
--   >>> import GHC.Internal.Text.Read ( readMaybe )
--   
--   >>> let readMaybeInt = readMaybe :: String -> Maybe Int
--   
--   >>> mapMaybe readMaybeInt ["1", "Foo", "3"]
--   [1,3]
--   
--   >>> catMaybes $ map readMaybeInt ["1", "Foo", "3"]
--   [1,3]
--   
--   
--   If we map the Just constructor, the entire list should be
--   returned:
--   
--   
--   >>> mapMaybe Just [1,2,3]
--   [1,2,3]
--   
mapMaybe :: (a -> Maybe b) -> [a] -> [b]

-- | The catMaybes function takes a list of Maybes and
--   returns a list of all the Just values.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> catMaybes [Just 1, Nothing, Just 3]
--   [1,3]
--   
--   
--   When constructing a list of Maybe values, catMaybes can
--   be used to return all of the "success" results (if the list is the
--   result of a map, then mapMaybe would be more
--   appropriate):
--   
--   
--   >>> import GHC.Internal.Text.Read ( readMaybe )
--   
--   >>> [readMaybe x :: Maybe Int | x <- ["1", "Foo", "3"] ]
--   [Just 1,Nothing,Just 3]
--   
--   >>> catMaybes $ [readMaybe x :: Maybe Int | x <- ["1", "Foo", "3"] ]
--   [1,3]
--   
catMaybes :: [Maybe a] -> [a]

-- | The fromMaybe function takes a default value and a Maybe
--   value. If the Maybe is Nothing, it returns the default
--   value; otherwise, it returns the value contained in the Maybe.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> fromMaybe "" (Just "Hello, World!")
--   "Hello, World!"
--   
--   
--   
--   >>> fromMaybe "" Nothing
--   ""
--   
--   
--   Read an integer from a string using readMaybe. If we fail to
--   parse an integer, we want to return 0 by default:
--   
--   
--   >>> import GHC.Internal.Text.Read ( readMaybe )
--   
--   >>> fromMaybe 0 (readMaybe "5")
--   5
--   
--   >>> fromMaybe 0 (readMaybe "")
--   0
--   
fromMaybe :: a -> Maybe a -> a

-- | The isJust function returns True iff its argument is of
--   the form Just _.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> isJust (Just 3)
--   True
--   
--   
--   
--   >>> isJust (Just ())
--   True
--   
--   
--   
--   >>> isJust Nothing
--   False
--   
--   
--   Only the outer constructor is taken into consideration:
--   
--   
--   >>> isJust (Just Nothing)
--   True
--   
isJust :: Maybe a -> Bool

-- | The isNothing function returns True iff its argument is
--   Nothing.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> isNothing (Just 3)
--   False
--   
--   
--   
--   >>> isNothing (Just ())
--   False
--   
--   
--   
--   >>> isNothing Nothing
--   True
--   
--   
--   Only the outer constructor is taken into consideration:
--   
--   
--   >>> isNothing (Just Nothing)
--   False
--   
isNothing :: Maybe a -> Bool

-- | The listToMaybe function returns Nothing on an empty
--   list or Just a where a is the first element
--   of the list.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> listToMaybe []
--   Nothing
--   
--   
--   
--   >>> listToMaybe [9]
--   Just 9
--   
--   
--   
--   >>> listToMaybe [1,2,3]
--   Just 1
--   
--   
--   Composing maybeToList with listToMaybe should be the
--   identity on singleton/empty lists:
--   
--   
--   >>> maybeToList $ listToMaybe [5]
--   [5]
--   
--   >>> maybeToList $ listToMaybe []
--   []
--   
--   
--   But not on lists with more than one element:
--   
--   
--   >>> maybeToList $ listToMaybe [1,2,3]
--   [1]
--   
listToMaybe :: [a] -> Maybe a

-- | The maybeToList function returns an empty list when given
--   Nothing or a singleton list when given Just.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> maybeToList (Just 7)
--   [7]
--   
--   
--   
--   >>> maybeToList Nothing
--   []
--   
--   
--   One can use maybeToList to avoid pattern matching when combined
--   with a function that (safely) works on lists:
--   
--   
--   >>> import GHC.Internal.Text.Read ( readMaybe )
--   
--   >>> sum $ maybeToList (readMaybe "3")
--   3
--   
--   >>> sum $ maybeToList (readMaybe "")
--   0
--   
maybeToList :: Maybe a -> [a]

-- | Partitions a list of Either into two lists. All the Left
--   elements are extracted, in order, to the first component of the
--   output. Similarly the Right elements are extracted to the
--   second component of the output.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> let list = [ Left "foo", Right 3, Left "bar", Right 7, Left "baz" ]
--   
--   >>> partitionEithers list
--   (["foo","bar","baz"],[3,7])
--   
--   
--   The pair returned by partitionEithers x should be the
--   same pair as (lefts x, rights x):
--   
--   
--   >>> let list = [ Left "foo", Right 3, Left "bar", Right 7, Left "baz" ]
--   
--   >>> partitionEithers list == (lefts list, rights list)
--   True
--   
partitionEithers :: [Either a b] -> ([a], [b])

-- | Extracts from a list of Either all the Left elements.
--   All the Left elements are extracted in order.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> let list = [ Left "foo", Right 3, Left "bar", Right 7, Left "baz" ]
--   
--   >>> lefts list
--   ["foo","bar","baz"]
--   
lefts :: [Either a b] -> [a]

-- | Extracts from a list of Either all the Right elements.
--   All the Right elements are extracted in order.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> let list = [ Left "foo", Right 3, Left "bar", Right 7, Left "baz" ]
--   
--   >>> rights list
--   [3,7]
--   
rights :: [Either a b] -> [b]

-- | on b u x y runs the binary function b
--   on the results of applying unary function u to two
--   arguments x and y. From the opposite perspective, it
--   transforms two inputs and combines the outputs.
--   
--   
--   (op `<a>on</a>` f) x y = f x `<tt>op</tt>` f y
--   
--   
--   
Examples
--   
--   
--   >>> sortBy (compare `on` length) [[0, 1, 2], [0, 1], [], [0]]
--   [[],[0],[0,1],[0,1,2]]
--   
--   
--   
--   >>> ((+) `on` length) [1, 2, 3] [-1]
--   4
--   
--   
--   
--   >>> ((,) `on` (*2)) 2 3
--   (4,6)
--   
--   
--   
Algebraic properties
--   
--   
--   
- 
(*) `on` id = (*) -- (if (*) ∉ {⊥, const
--   ⊥})

--   
--   
--   
--   
- 
((*) `on` f) `on` g = (*) `on` (f . g)

--   
- 
flip on f . flip on g = flip on (g .
--   f)

--   
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
infixl 0 `on`

-- | 
--   comparing p x y = compare (p x) (p y)
--   
--   
--   Useful combinator for use in conjunction with the xxxBy
--   family of functions from Data.List, for example:
--   
--   
--   ... sortBy (comparing fst) ...
--   
comparing :: Ord a => (b -> a) -> b -> b -> Ordering
equating :: Eq a => (b -> a) -> b -> b -> Bool

-- | The Down type allows you to reverse sort order conveniently. A
--   value of type Down a contains a value of type
--   a (represented as Down a).
--   
--   If a has an Ord instance associated with it
--   then comparing two values thus wrapped will give you the opposite of
--   their normal sort order. This is particularly useful when sorting in
--   generalised list comprehensions, as in: then sortWith by
--   Down x.
--   
--   
--   >>> compare True False
--   GT
--   
--   
--   
--   >>> compare (Down True) (Down False)
--   LT
--   
--   
--   If a has a Bounded instance then the wrapped
--   instance also respects the reversed ordering by exchanging the values
--   of minBound and maxBound.
--   
--   
--   >>> minBound :: Int
--   -9223372036854775808
--   
--   
--   
--   >>> minBound :: Down Int
--   Down 9223372036854775807
--   
--   
--   All other instances of Down a behave as they do for
--   a.
newtype Down a
Down :: a -> Down a

[getDown] :: Down a -> a

-- | A functor with application, providing operations to
--   
--   
--   
- embed pure expressions (pure), and
--   
- sequence computations and combine their results (<*>
--   and liftA2).
--   
--   
--   A minimal complete definition must include implementations of
--   pure and of either <*> or liftA2. If it
--   defines both, then they must behave the same as their default
--   definitions:
--   
--   
--   (<*>) = liftA2 id
--   
--   
--   
--   liftA2 f x y = f <$> x <*> y
--   
--   
--   Further, any definition must satisfy the following:
--   
--   
--   
- Identity 
pure id <*> v =
--   v

--   
- Composition 
pure (.) <*> u
--   <*> v <*> w = u <*> (v
--   <*> w)

--   
- Homomorphism 
pure f <*>
--   pure x = pure (f x)

--   
- Interchange 
u <*> pure y =
--   pure ($ y) <*> u

--   
--   
--   The other methods have the following default definitions, which may be
--   overridden with equivalent specialized implementations:
--   
--   
--   
- 
u *> v = (id <$ u)
--   <*> v

--   
- 
u <* v = liftA2 const u v

--   
--   
--   As a consequence of these laws, the Functor instance for
--   f will satisfy
--   
--   
--   
- 
fmap f x = pure f <*> x

--   
--   
--   It may be useful to note that supposing
--   
--   
--   forall x y. p (q x y) = f x . g y
--   
--   
--   it follows from the above that
--   
--   
--   liftA2 p (liftA2 q u v) = liftA2 f u . liftA2 g v
--   
--   
--   If f is also a Monad, it should satisfy
--   
--   
--   
- 
pure = return

--   
- 
m1 <*> m2 = m1 >>= (\x1 -> m2
--   >>= (\x2 -> return (x1 x2)))

--   
- 
(*>) = (>>)

--   
--   
--   (which implies that pure and <*> satisfy the
--   applicative functor laws).
class Functor f => Applicative (f :: Type -> Type)

-- | Lift a value into the Structure.
--   
--   
Examples
--   
--   
--   >>> pure 1 :: Maybe Int
--   Just 1
--   
--   
--   
--   >>> pure 'z' :: [Char]
--   "z"
--   
--   
--   
--   >>> pure (pure ":D") :: Maybe [String]
--   Just [":D"]
--   
pure :: Applicative f => a -> f a

-- | Sequential application.
--   
--   A few functors support an implementation of <*> that is
--   more efficient than the default one.
--   
--   
Example
--   
--   Used in combination with (<$>),
--   (<*>) can be used to build a record.
--   
--   
--   >>> data MyState = MyState {arg1 :: Foo, arg2 :: Bar, arg3 :: Baz}
--   
--   
--   
--   >>> produceFoo :: Applicative f => f Foo
--   
--   >>> produceBar :: Applicative f => f Bar
--   
--   >>> produceBaz :: Applicative f => f Baz
--   
--   
--   
--   >>> mkState :: Applicative f => f MyState
--   
--   >>> mkState = MyState <$> produceFoo <*> produceBar <*> produceBaz
--   
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

-- | Lift a binary function to actions.
--   
--   Some functors support an implementation of liftA2 that is more
--   efficient than the default one. In particular, if fmap is an
--   expensive operation, it is likely better to use liftA2 than to
--   fmap over the structure and then use <*>.
--   
--   This became a typeclass method in 4.10.0.0. Prior to that, it was a
--   function defined in terms of <*> and fmap.
--   
--   
Example
--   
--   
--   >>> liftA2 (,) (Just 3) (Just 5)
--   Just (3,5)
--   
--   
--   
--   >>> liftA2 (+) [1, 2, 3] [4, 5, 6]
--   [5,6,7,6,7,8,7,8,9]
--   
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

-- | Sequence actions, discarding the value of the first argument.
--   
--   
Examples
--   
--   If used in conjunction with the Applicative instance for Maybe,
--   you can chain Maybe computations, with a possible "early return" in
--   case of Nothing.
--   
--   
--   >>> Just 2 *> Just 3
--   Just 3
--   
--   
--   
--   >>> Nothing *> Just 3
--   Nothing
--   
--   
--   Of course a more interesting use case would be to have effectful
--   computations instead of just returning pure values.
--   
--   
--   >>> import Data.Char
--   
--   >>> import GHC.Internal.Text.ParserCombinators.ReadP
--   
--   >>> let p = string "my name is " *> munch1 isAlpha <* eof
--   
--   >>> readP_to_S p "my name is Simon"
--   [("Simon","")]
--   
(*>) :: Applicative f => f a -> f b -> f b

-- | Sequence actions, discarding the value of the second argument.
(<*) :: Applicative f => f a -> f b -> f a
infixl 4 <*>
infixl 4 *>
infixl 4 <*

-- | An infix synonym for fmap.
--   
--   The name of this operator is an allusion to $. Note the
--   similarities between their types:
--   
--   
--    ($)  ::              (a -> b) ->   a ->   b
--   (<$>) :: Functor f => (a -> b) -> f a -> f b
--   
--   
--   Whereas $ is function application, <$> is function
--   application lifted over a Functor.
--   
--   
Examples
--   
--   Convert from a Maybe Int to a Maybe
--   String using show:
--   
--   
--   >>> show <$> Nothing
--   Nothing
--   
--   
--   
--   >>> show <$> Just 3
--   Just "3"
--   
--   
--   Convert from an Either Int Int to an
--   Either Int String using show:
--   
--   
--   >>> show <$> Left 17
--   Left 17
--   
--   
--   
--   >>> show <$> Right 17
--   Right "17"
--   
--   
--   Double each element of a list:
--   
--   
--   >>> (*2) <$> [1,2,3]
--   [2,4,6]
--   
--   
--   Apply even to the second element of a pair:
--   
--   
--   >>> even <$> (2,2)
--   (2,True)
--   
(<$>) :: Functor f => (a -> b) -> f a -> f b
infixl 4 <$>

-- | An associative binary operation
(<|>) :: Alternative f => f a -> f a -> f a
infixl 3 <|>

-- | Left-to-right composition of Kleisli arrows.
--   
--   '(bs >=> cs) a' can be understood as the
--   do expression
--   
--   
--   do b <- bs a
--      cs b
--   
--   
--   or in terms of (>>=) as
--   
--   
--   bs a >>= cs
--   
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
infixr 1 >=>

-- | Lift a computation from the argument monad to the constructed monad.
lift :: (MonadTrans t, Monad m) => m a -> t m a

-- | Monads in which IO computations may be embedded. Any monad
--   built by applying a sequence of monad transformers to the IO
--   monad will be an instance of this class.
--   
--   Instances should satisfy the following laws, which state that
--   liftIO is a transformer of monads:
--   
--   
--   
- 
liftIO . return = return

--   
- 
liftIO (m >>= f) = liftIO m >>=
--   (liftIO . f)

--   
class Monad m => MonadIO (m :: Type -> Type)

-- | Lift a computation from the IO monad. This allows us to run IO
--   computations in any monadic stack, so long as it supports these kinds
--   of operations (i.e. IO is the base monad for the stack).
--   
--   
Example
--   
--   
--   import Control.Monad.Trans.State -- from the "transformers" library
--   
--   printState :: Show s => StateT s IO ()
--   printState = do
--     state <- get
--     liftIO $ print state
--   
--   
--   Had we omitted liftIO, we would have ended up with
--   this error:
--   
--   
--   • Couldn't match type ‘IO’ with ‘StateT s IO’
--    Expected type: StateT s IO ()
--      Actual type: IO ()
--   
--   
--   The important part here is the mismatch between StateT s IO
--   () and IO ().
--   
--   Luckily, we know of a function that takes an IO a and
--   returns an (m a): liftIO, enabling us to run
--   the program and see the expected results:
--   
--   
--   > evalStateT printState "hello"
--   "hello"
--   
--   > evalStateT printState 3
--   3
--   
liftIO :: MonadIO m => IO a -> m a

-- | Any type that you wish to throw or catch as an exception must be an
--   instance of the Exception class. The simplest case is a new
--   exception type directly below the root:
--   
--   
--   data MyException = ThisException | ThatException
--       deriving Show
--   
--   instance Exception MyException
--   
--   
--   The default method definitions in the Exception class do what
--   we need in this case. You can now throw and catch
--   ThisException and ThatException as exceptions:
--   
--   
--   *Main> throw ThisException `catch` \e -> putStrLn ("Caught " ++ show (e :: MyException))
--   Caught ThisException
--   
--   
--   In more complicated examples, you may wish to define a whole hierarchy
--   of exceptions:
--   
--   
--   ---------------------------------------------------------------------
--   -- Make the root exception type for all the exceptions in a compiler
--   
--   data SomeCompilerException = forall e . Exception e => SomeCompilerException e
--   
--   instance Show SomeCompilerException where
--       show (SomeCompilerException e) = show e
--   
--   instance Exception SomeCompilerException
--   
--   compilerExceptionToException :: Exception e => e -> SomeException
--   compilerExceptionToException = toException . SomeCompilerException
--   
--   compilerExceptionFromException :: Exception e => SomeException -> Maybe e
--   compilerExceptionFromException x = do
--       SomeCompilerException a <- fromException x
--       cast a
--   
--   ---------------------------------------------------------------------
--   -- Make a subhierarchy for exceptions in the frontend of the compiler
--   
--   data SomeFrontendException = forall e . Exception e => SomeFrontendException e
--   
--   instance Show SomeFrontendException where
--       show (SomeFrontendException e) = show e
--   
--   instance Exception SomeFrontendException where
--       toException = compilerExceptionToException
--       fromException = compilerExceptionFromException
--   
--   frontendExceptionToException :: Exception e => e -> SomeException
--   frontendExceptionToException = toException . SomeFrontendException
--   
--   frontendExceptionFromException :: Exception e => SomeException -> Maybe e
--   frontendExceptionFromException x = do
--       SomeFrontendException a <- fromException x
--       cast a
--   
--   ---------------------------------------------------------------------
--   -- Make an exception type for a particular frontend compiler exception
--   
--   data MismatchedParentheses = MismatchedParentheses
--       deriving Show
--   
--   instance Exception MismatchedParentheses where
--       toException   = frontendExceptionToException
--       fromException = frontendExceptionFromException
--   
--   
--   We can now catch a MismatchedParentheses exception as
--   MismatchedParentheses, SomeFrontendException or
--   SomeCompilerException, but not other types, e.g.
--   IOException:
--   
--   
--   *Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: MismatchedParentheses))
--   Caught MismatchedParentheses
--   *Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: SomeFrontendException))
--   Caught MismatchedParentheses
--   *Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: SomeCompilerException))
--   Caught MismatchedParentheses
--   *Main> throw MismatchedParentheses `catch` \e -> putStrLn ("Caught " ++ show (e :: IOException))
--   *** Exception: MismatchedParentheses
--   
class (Typeable e, Show e) => Exception e

-- | toException should produce a SomeException with no
--   attached ExceptionContext.
toException :: Exception e => e -> SomeException
fromException :: Exception e => SomeException -> Maybe e

-- | Render this exception value in a human-friendly manner.
--   
--   Default implementation: show.
displayException :: Exception e => e -> String
backtraceDesired :: Exception e => e -> Bool

-- | The class Typeable allows a concrete representation of a type
--   to be calculated.
class Typeable (a :: k)

-- | The SomeException type is the root of the exception type
--   hierarchy. When an exception of type e is thrown, behind the
--   scenes it is encapsulated in a SomeException.
data SomeException

-- | Exceptions that occur in the IO monad. An
--   IOException records a more specific error type, a descriptive
--   string and maybe the handle that was used when the error was flagged.
data IOException

-- | File and directory names are values of type String, whose
--   precise meaning is operating system dependent. Files can be opened,
--   yielding a handle which can then be used to operate on the contents of
--   that file.
type FilePath = String

-- | Combine two paths with a path separator. If the second path starts
--   with a path separator or a drive letter, then it returns the second.
--   The intention is that readFile (dir </> file)
--   will access the same file as setCurrentDirectory dir; readFile
--   file.
--   
--   
--   Posix:   "/directory" </> "file.ext" == "/directory/file.ext"
--   Windows: "/directory" </> "file.ext" == "/directory\\file.ext"
--            "directory" </> "/file.ext" == "/file.ext"
--   Valid x => (takeDirectory x </> takeFileName x) `equalFilePath` x
--   
--   
--   Combined:
--   
--   
--   Posix:   "/" </> "test" == "/test"
--   Posix:   "home" </> "bob" == "home/bob"
--   Posix:   "x:" </> "foo" == "x:/foo"
--   Windows: "C:\\foo" </> "bar" == "C:\\foo\\bar"
--   Windows: "home" </> "bob" == "home\\bob"
--   
--   
--   Not combined:
--   
--   
--   Posix:   "home" </> "/bob" == "/bob"
--   Windows: "home" </> "C:\\bob" == "C:\\bob"
--   
--   
--   Not combined (tricky):
--   
--   On Windows, if a filepath starts with a single slash, it is relative
--   to the root of the current drive. In [1], this is (confusingly)
--   referred to as an absolute path. The current behavior of
--   </> is to never combine these forms.
--   
--   
--   Windows: "home" </> "/bob" == "/bob"
--   Windows: "home" </> "\\bob" == "\\bob"
--   Windows: "C:\\home" </> "\\bob" == "\\bob"
--   
--   
--   On Windows, from [1]: "If a file name begins with only a disk
--   designator but not the backslash after the colon, it is interpreted as
--   a relative path to the current directory on the drive with the
--   specified letter." The current behavior of </> is to
--   never combine these forms.
--   
--   
--   Windows: "D:\\foo" </> "C:bar" == "C:bar"
--   Windows: "C:\\foo" </> "C:bar" == "C:bar"
--   
(</>) :: FilePath -> FilePath -> FilePath
infixr 5 </>

-- | Add an extension, even if there is already one there, equivalent to
--   addExtension.
--   
--   
--   "/directory/path" <.> "ext" == "/directory/path.ext"
--   "/directory/path" <.> ".ext" == "/directory/path.ext"
--   
(<.>) :: FilePath -> String -> FilePath
infixr 7 <.>

-- | String is an alias for a list of characters.
--   
--   String constants in Haskell are values of type String. That
--   means if you write a string literal like "hello world", it
--   will have the type [Char], which is the same as
--   String.
--   
--   Note: You can ask the compiler to automatically infer different
--   types with the -XOverloadedStrings language extension, for
--   example "hello world" :: Text. See IsString for more
--   information.
--   
--   Because String is just a list of characters, you can use
--   normal list functions to do basic string manipulation. See
--   Data.List for operations on lists.
--   
--   
Performance considerations
--   
--   [Char] is a relatively memory-inefficient type. It is a
--   linked list of boxed word-size characters, internally it looks
--   something like:
--   
--   
--   ╭─────┬───┬──╮  ╭─────┬───┬──╮  ╭─────┬───┬──╮  ╭────╮
--   │ (:) │   │ ─┼─>│ (:) │   │ ─┼─>│ (:) │   │ ─┼─>│ [] │
--   ╰─────┴─┼─┴──╯  ╰─────┴─┼─┴──╯  ╰─────┴─┼─┴──╯  ╰────╯
--           v               v               v
--          'a'             'b'             'c'
--   
--   
--   The String "abc" will use 5*3+1 = 16 (in general
--   5n+1) words of space in memory.
--   
--   Furthermore, operations like (++) (string concatenation) are
--   O(n) (in the left argument).
--   
--   For historical reasons, the base library uses String
--   in a lot of places for the conceptual simplicity, but library code
--   dealing with user-data should use the text package for Unicode
--   text, or the the bytestring package for binary data.
type String = [Char]

-- | Like hashWithSalt, but no salt is used. The default
--   implementation uses hashWithSalt with some default salt.
--   Instances might want to implement this method to provide a more
--   efficient implementation than the default implementation.
hash :: Hashable a => a -> Int

-- | Return a hash value for the argument, using the given salt.
--   
--   The general contract of hashWithSalt is:
--   
--   
--   
- If two values are equal according to the == method, then
--   applying the hashWithSalt method on each of the two values
--   must produce the same integer result if the same salt is used
--   in each case.
--   
- It is not required that if two values are unequal according
--   to the == method, then applying the hashWithSalt method
--   on each of the two values must produce distinct integer results.
--   However, the programmer should be aware that producing distinct
--   integer results for unequal values may improve the performance of
--   hashing-based data structures.
--   
- This method can be used to compute different hash values for the
--   same input by providing a different salt in each application of the
--   method. This implies that any instance that defines
--   hashWithSalt must make use of the salt in its
--   implementation.
--   
- hashWithSalt may return negative Int values.
--   
hashWithSalt :: Hashable a => Int -> a -> Int
infixl 0 `hashWithSalt`

-- | BasicPrelude mostly re-exports several key libraries in their
--   entirety. The exception is Data.List, where various functions are
--   replaced by similar versions that are either generalized, operate on
--   Text, or are implemented strictly.
module BasicPrelude

-- | List index (subscript) operator, starting from 0. Returns
--   Nothing if the index is out of bounds
--   
--   This is the total variant of the partial !! operator.
--   
--   WARNING: This function takes linear time in the index.
--   
--   
Examples
--   
--   
--   >>> ['a', 'b', 'c'] !? 0
--   Just 'a'
--   
--   
--   
--   >>> ['a', 'b', 'c'] !? 2
--   Just 'c'
--   
--   
--   
--   >>> ['a', 'b', 'c'] !? 3
--   Nothing
--   
--   
--   
--   >>> ['a', 'b', 'c'] !? (-1)
--   Nothing
--   
(!?) :: [a] -> Int -> Maybe a
infixl 9 !?

-- | The builtin linked list type.
--   
--   In Haskell, lists are one of the most important data types as they are
--   often used analogous to loops in imperative programming languages.
--   These lists are singly linked, which makes them unsuited for
--   operations that require <math> access. Instead, they are
--   intended to be traversed.
--   
--   You can use List a or [a] in type signatures:
--   
--   
--   length :: [a] -> Int
--   
--   
--   or
--   
--   
--   length :: List a -> Int
--   
--   
--   They are fully equivalent, and List a will be normalised to
--   [a].
--   
--   
Usage
--   
--   Lists are constructed recursively using the right-associative
--   constructor operator (or cons) (:) :: a -> [a] ->
--   [a], which prepends an element to a list, and the empty list
--   [].
--   
--   
--   (1 : 2 : 3 : []) == (1 : (2 : (3 : []))) == [1, 2, 3]
--   
--   
--   Lists can also be constructed using list literals of the form
--   [x_1, x_2, ..., x_n] which are syntactic sugar and, unless
--   -XOverloadedLists is enabled, are translated into uses of
--   (:) and []
--   
--   String literals, like "I 💜 hs", are translated into
--   Lists of characters, ['I', ' ', '💜', ' ', 'h', 's'].
--   
--   
Implementation
--   
--   Internally and in memory, all the above are represented like this,
--   with arrows being pointers to locations in memory.
--   
--   
--   ╭───┬───┬──╮   ╭───┬───┬──╮   ╭───┬───┬──╮   ╭────╮
--   │(:)│   │ ─┼──>│(:)│   │ ─┼──>│(:)│   │ ─┼──>│ [] │
--   ╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰────╯
--         v              v              v
--         1              2              3
--   
--   
--   
Examples
--   
--   
--   >>> ['H', 'a', 's', 'k', 'e', 'l', 'l']
--   "Haskell"
--   
--   
--   
--   >>> 1 : [4, 1, 5, 9]
--   [1,4,1,5,9]
--   
--   
--   
--   >>> [] : [] : []
--   [[],[]]
--   
data [] a

-- | The unfoldr function is a `dual' to foldr: while
--   foldr reduces a list to a summary value, unfoldr builds
--   a list from a seed value. The function takes the element and returns
--   Nothing if it is done producing the list or returns Just
--   (a,b), in which case, a is a prepended to the list
--   and b is used as the next element in a recursive call. For
--   example,
--   
--   
--   iterate f == unfoldr (\x -> Just (x, f x))
--   
--   
--   In some cases, unfoldr can undo a foldr operation:
--   
--   
--   unfoldr f' (foldr f z xs) == xs
--   
--   
--   if the following holds:
--   
--   
--   f' (f x y) = Just (x,y)
--   f' z       = Nothing
--   
--   
--   
Laziness
--   
--   
--   >>> take 1 (unfoldr (\x -> Just (x, undefined)) 'a')
--   "a"
--   
--   
--   
Examples
--   
--   
--   >>> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
--   [10,9,8,7,6,5,4,3,2,1]
--   
--   
--   
--   >>> take 10 $ unfoldr (\(x, y) -> Just (x, (y, x + y))) (0, 1)
--   [0,1,1,2,3,5,8,13,21,54]
--   
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

-- | Sort a list by comparing the results of a key function applied to each
--   element. sortOn f is equivalent to sortBy
--   (comparing f), but has the performance advantage of only
--   evaluating f once for each element in the input list. This is
--   called the decorate-sort-undecorate paradigm, or Schwartzian
--   transform.
--   
--   Elements are arranged from lowest to highest, keeping duplicates in
--   the order they appeared in the input.
--   
--   The argument must be finite.
--   
--   
Examples
--   
--   
--   >>> sortOn fst [(2, "world"), (4, "!"), (1, "Hello")]
--   [(1,"Hello"),(2,"world"),(4,"!")]
--   
--   
--   
--   >>> sortOn length ["jim", "creed", "pam", "michael", "dwight", "kevin"]
--   ["jim","pam","creed","kevin","dwight","michael"]
--   
--   
--   
Performance notes
--   
--   This function minimises the projections performed, by materialising
--   the projections in an intermediate list.
--   
--   For trivial projections, you should prefer using sortBy with
--   comparing, for example:
--   
--   
--   >>> sortBy (comparing fst) [(3, 1), (2, 2), (1, 3)]
--   [(1,3),(2,2),(3,1)]
--   
--   
--   Or, for the exact same API as sortOn, you can use `sortBy .
--   comparing`:
--   
--   
--   >>> (sortBy . comparing) fst [(3, 1), (2, 2), (1, 3)]
--   [(1,3),(2,2),(3,1)]
--   
sortOn :: Ord b => (a -> b) -> [a] -> [a]

-- | The transpose function transposes the rows and columns of its
--   argument.
--   
--   
Laziness
--   
--   transpose is lazy in its elements
--   
--   
--   >>> take 1 (transpose ['a' : undefined, 'b' : undefined])
--   ["ab"]
--   
--   
--   
Examples
--   
--   
--   >>> transpose [[1,2,3],[4,5,6]]
--   [[1,4],[2,5],[3,6]]
--   
--   
--   If some of the rows are shorter than the following rows, their
--   elements are skipped:
--   
--   
--   >>> transpose [[10,11],[20],[],[30,31,32]]
--   [[10,20,30],[11,31],[32]]
--   
--   
--   For this reason the outer list must be finite; otherwise
--   transpose hangs:
--   
--   
--   >>> transpose (repeat [])
--   * Hangs forever *
--   
transpose :: [[a]] -> [[a]]

-- | The sortBy function is the non-overloaded version of
--   sort. The argument must be finite.
--   
--   The supplied comparison relation is supposed to be reflexive and
--   antisymmetric, otherwise, e. g., for _ _ -> GT, the
--   ordered list simply does not exist. The relation is also expected to
--   be transitive: if it is not then sortBy might fail to find an
--   ordered permutation, even if it exists.
--   
--   
Examples
--   
--   
--   >>> sortBy (\(a,_) (b,_) -> compare a b) [(2, "world"), (4, "!"), (1, "Hello")]
--   [(1,"Hello"),(2,"world"),(4,"!")]
--   
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

-- | cycle ties a finite list into a circular one, or equivalently,
--   the infinite repetition of the original list. It is the identity on
--   infinite lists.
--   
--   
Examples
--   
--   
--   >>> cycle []
--   *** Exception: Prelude.cycle: empty list
--   
--   
--   
--   >>> take 10 (cycle [42])
--   [42,42,42,42,42,42,42,42,42,42]
--   
--   
--   
--   >>> take 10 (cycle [2, 5, 7])
--   [2,5,7,2,5,7,2,5,7,2]
--   
--   
--   
--   >>> take 1 (cycle (42 : undefined))
--   [42]
--   
cycle :: HasCallStack => [a] -> [a]

-- | <math>. filter, applied to a predicate and a list,
--   returns the list of those elements that satisfy the predicate; i.e.,
--   
--   
--   filter p xs = [ x | x <- xs, p x]
--   
--   
--   
Examples
--   
--   
--   >>> filter odd [1, 2, 3]
--   [1,3]
--   
--   
--   
--   >>> filter (\l -> length l > 3) ["Hello", ", ", "World", "!"]
--   ["Hello","World"]
--   
--   
--   
--   >>> filter (/= 3) [1, 2, 3, 4, 3, 2, 1]
--   [1,2,4,2,1]
--   
filter :: (a -> Bool) -> [a] -> [a]

-- | <math>. zip takes two lists and returns a list of
--   corresponding pairs.
--   
--   zip is right-lazy:
--   
--   
--   >>> zip [] undefined
--   []
--   
--   >>> zip undefined []
--   *** Exception: Prelude.undefined
--   ...
--   
--   
--   zip is capable of list fusion, but it is restricted to its
--   first list argument and its resulting list.
--   
--   
Examples
--   
--   
--   >>> zip [1, 2, 3] ['a', 'b', 'c']
--   [(1,'a'),(2,'b'),(3,'c')]
--   
--   
--   If one input list is shorter than the other, excess elements of the
--   longer list are discarded, even if one of the lists is infinite:
--   
--   
--   >>> zip [1] ['a', 'b']
--   [(1,'a')]
--   
--   
--   
--   >>> zip [1, 2] ['a']
--   [(1,'a')]
--   
--   
--   
--   >>> zip [] [1..]
--   []
--   
--   
--   
--   >>> zip [1..] []
--   []
--   
zip :: [a] -> [b] -> [(a, b)]

-- | <math>. Extract the first element of a list, which must be
--   non-empty.
--   
--   To disable the warning about partiality put {-# OPTIONS_GHC
--   -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of
--   the file. To disable it throughout a package put the same options into
--   ghc-options section of Cabal file. To disable it in GHCi put
--   :set -Wno-x-partial -Wno-unrecognised-warning-flags into
--   ~/.ghci config file. See also the migration guide.
--   
--   
Examples
--   
--   
--   >>> head [1, 2, 3]
--   1
--   
--   
--   
--   >>> head [1..]
--   1
--   
--   
--   
--   >>> head []
--   *** Exception: Prelude.head: empty list
--   
head :: HasCallStack => [a] -> a

-- | <math>. Decompose a list into its head and tail.
--   
--   
--   
- If the list is empty, returns Nothing.
--   
- If the list is non-empty, returns Just (x, xs),
--   where x is the head of the list and xs its
--   tail.
--   
--   
--   
Examples
--   
--   
--   >>> uncons []
--   Nothing
--   
--   
--   
--   >>> uncons [1]
--   Just (1,[])
--   
--   
--   
--   >>> uncons [1, 2, 3]
--   Just (1,[2,3])
--   
uncons :: [a] -> Maybe (a, [a])

-- | <math>. Decompose a list into init and last.
--   
--   
--   
- If the list is empty, returns Nothing.
--   
- If the list is non-empty, returns Just (xs, x),
--   where xs is the initial part of the list and
--   x is its last element.
--   
--   
--   unsnoc is dual to uncons: for a finite list xs
--   
--   
--   unsnoc xs = (\(hd, tl) -> (reverse tl, hd)) <$> uncons (reverse xs)
--   
--   
--   
Examples
--   
--   
--   >>> unsnoc []
--   Nothing
--   
--   
--   
--   >>> unsnoc [1]
--   Just ([],1)
--   
--   
--   
--   >>> unsnoc [1, 2, 3]
--   Just ([1,2],3)
--   
--   
--   
Laziness
--   
--   
--   >>> fst <$> unsnoc [undefined]
--   Just []
--   
--   
--   
--   >>> head . fst <$> unsnoc (1 : undefined)
--   Just *** Exception: Prelude.undefined
--   
--   
--   
--   >>> head . fst <$> unsnoc (1 : 2 : undefined)
--   Just 1
--   
unsnoc :: [a] -> Maybe ([a], a)

-- | <math>. Extract the elements after the head of a list, which
--   must be non-empty.
--   
--   To disable the warning about partiality put {-# OPTIONS_GHC
--   -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of
--   the file. To disable it throughout a package put the same options into
--   ghc-options section of Cabal file. To disable it in GHCi put
--   :set -Wno-x-partial -Wno-unrecognised-warning-flags into
--   ~/.ghci config file. See also the migration guide.
--   
--   
Examples
--   
--   
--   >>> tail [1, 2, 3]
--   [2,3]
--   
--   
--   
--   >>> tail [1]
--   []
--   
--   
--   
--   >>> tail []
--   *** Exception: Prelude.tail: empty list
--   
tail :: HasCallStack => [a] -> [a]

-- | <math>. Extract the last element of a list, which must be finite
--   and non-empty.
--   
--   WARNING: This function is partial. Consider using unsnoc
--   instead.
--   
--   
Examples
--   
--   
--   >>> last [1, 2, 3]
--   3
--   
--   
--   
--   >>> last [1..]
--   * Hangs forever *
--   
--   
--   
--   >>> last []
--   *** Exception: Prelude.last: empty list
--   
last :: HasCallStack => [a] -> a

-- | <math>. Return all the elements of a list except the last one.
--   The list must be non-empty.
--   
--   WARNING: This function is partial. Consider using unsnoc
--   instead.
--   
--   
Examples
--   
--   
--   >>> init [1, 2, 3]
--   [1,2]
--   
--   
--   
--   >>> init [1]
--   []
--   
--   
--   
--   >>> init []
--   *** Exception: Prelude.init: empty list
--   
init :: HasCallStack => [a] -> [a]

-- | Test whether the structure is empty. The default implementation is
--   Left-associative and lazy in both the initial element and the
--   accumulator. Thus optimised for structures where the first element can
--   be accessed in constant time. Structures where this is not the case
--   should have a non-default implementation.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> null []
--   True
--   
--   
--   
--   >>> null [1]
--   False
--   
--   
--   null is expected to terminate even for infinite structures. The
--   default implementation terminates provided the structure is bounded on
--   the left (there is a leftmost element).
--   
--   
--   >>> null [1..]
--   False
--   
null :: Foldable t => t a -> Bool

-- | Returns the size/length of a finite structure as an Int. The
--   default implementation just counts elements starting with the
--   leftmost. Instances for structures that can compute the element count
--   faster than via element-by-element counting, should provide a
--   specialised implementation.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> length []
--   0
--   
--   
--   
--   >>> length ['a', 'b', 'c']
--   3
--   
--   >>> length [1..]
--   * Hangs forever *
--   
length :: Foldable t => t a -> Int

-- | A strict version of foldl1.
foldl1' :: HasCallStack => (a -> a -> a) -> [a] -> a

-- | <math>. scanl is similar to foldl, but returns a
--   list of successive reduced values from the left:
--   
--   
--   scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
--   
--   
--   Note that
--   
--   
--   last (scanl f z xs) == foldl f z xs
--   
--   
--   
Examples
--   
--   
--   >>> scanl (+) 0 [1..4]
--   [0,1,3,6,10]
--   
--   
--   
--   >>> scanl (+) 42 []
--   [42]
--   
--   
--   
--   >>> scanl (-) 100 [1..4]
--   [100,99,97,94,90]
--   
--   
--   
--   >>> scanl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
--   ["foo","afoo","bafoo","cbafoo","dcbafoo"]
--   
--   
--   
--   >>> take 10 (scanl (+) 0 [1..])
--   [0,1,3,6,10,15,21,28,36,45]
--   
--   
--   
--   >>> take 1 (scanl undefined 'a' undefined)
--   "a"
--   
scanl :: (b -> a -> b) -> b -> [a] -> [b]

-- | <math>. scanl1 is a variant of scanl that has no
--   starting value argument:
--   
--   
--   scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
--   
--   
--   
Examples
--   
--   
--   >>> scanl1 (+) [1..4]
--   [1,3,6,10]
--   
--   
--   
--   >>> scanl1 (+) []
--   []
--   
--   
--   
--   >>> scanl1 (-) [1..4]
--   [1,-1,-4,-8]
--   
--   
--   
--   >>> scanl1 (&&) [True, False, True, True]
--   [True,False,False,False]
--   
--   
--   
--   >>> scanl1 (||) [False, False, True, True]
--   [False,False,True,True]
--   
--   
--   
--   >>> take 10 (scanl1 (+) [1..])
--   [1,3,6,10,15,21,28,36,45,55]
--   
--   
--   
--   >>> take 1 (scanl1 undefined ('a' : undefined))
--   "a"
--   
scanl1 :: (a -> a -> a) -> [a] -> [a]

-- | <math>. A strict version of scanl.
scanl' :: (b -> a -> b) -> b -> [a] -> [b]

-- | <math>. scanr is the right-to-left dual of scanl.
--   Note that the order of parameters on the accumulating function are
--   reversed compared to scanl. Also note that
--   
--   
--   head (scanr f z xs) == foldr f z xs.
--   
--   
--   
Examples
--   
--   
--   >>> scanr (+) 0 [1..4]
--   [10,9,7,4,0]
--   
--   
--   
--   >>> scanr (+) 42 []
--   [42]
--   
--   
--   
--   >>> scanr (-) 100 [1..4]
--   [98,-97,99,-96,100]
--   
--   
--   
--   >>> scanr (\nextChar reversedString -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
--   ["abcdfoo","bcdfoo","cdfoo","dfoo","foo"]
--   
--   
--   
--   >>> force $ scanr (+) 0 [1..]
--   *** Exception: stack overflow
--   
scanr :: (a -> b -> b) -> b -> [a] -> [b]

-- | <math>. scanr1 is a variant of scanr that has no
--   starting value argument.
--   
--   
Examples
--   
--   
--   >>> scanr1 (+) [1..4]
--   [10,9,7,4]
--   
--   
--   
--   >>> scanr1 (+) []
--   []
--   
--   
--   
--   >>> scanr1 (-) [1..4]
--   [-2,3,-1,4]
--   
--   
--   
--   >>> scanr1 (&&) [True, False, True, True]
--   [False,False,True,True]
--   
--   
--   
--   >>> scanr1 (||) [True, True, False, False]
--   [True,True,False,False]
--   
--   
--   
--   >>> force $ scanr1 (+) [1..]
--   *** Exception: stack overflow
--   
scanr1 :: (a -> a -> a) -> [a] -> [a]

-- | iterate f x returns an infinite list of repeated
--   applications of f to x:
--   
--   
--   iterate f x == [x, f x, f (f x), ...]
--   
--   
--   
Laziness
--   
--   Note that iterate is lazy, potentially leading to thunk
--   build-up if the consumer doesn't force each iterate. See
--   iterate' for a strict variant of this function.
--   
--   
--   >>> take 1 $ iterate undefined 42
--   [42]
--   
--   
--   
Examples
--   
--   
--   >>> take 10 $ iterate not True
--   [True,False,True,False,True,False,True,False,True,False]
--   
--   
--   
--   >>> take 10 $ iterate (+3) 42
--   [42,45,48,51,54,57,60,63,66,69]
--   
--   
--   iterate id == repeat:
--   
--   
--   >>> take 10 $ iterate id 1
--   [1,1,1,1,1,1,1,1,1,1]
--   
iterate :: (a -> a) -> a -> [a]

-- | iterate' is the strict version of iterate.
--   
--   It forces the result of each application of the function to weak head
--   normal form (WHNF) before proceeding.
--   
--   
--   >>> take 1 $ iterate' undefined 42
--   *** Exception: Prelude.undefined
--   
iterate' :: (a -> a) -> a -> [a]

-- | repeat x is an infinite list, with x the
--   value of every element.
--   
--   
Examples
--   
--   
--   >>> take 10 $ repeat 17
--   [17,17,17,17,17,17,17,17,17, 17]
--   
--   
--   
--   >>> repeat undefined
--   [*** Exception: Prelude.undefined
--   
repeat :: a -> [a]

-- | replicate n x is a list of length n with
--   x the value of every element. It is an instance of the more
--   general genericReplicate, in which n may be of any
--   integral type.
--   
--   
Examples
--   
--   
--   >>> replicate 0 True
--   []
--   
--   
--   
--   >>> replicate (-1) True
--   []
--   
--   
--   
--   >>> replicate 4 True
--   [True,True,True,True]
--   
replicate :: Int -> a -> [a]

-- | takeWhile, applied to a predicate p and a list
--   xs, returns the longest prefix (possibly empty) of
--   xs of elements that satisfy p.
--   
--   
Laziness
--   
--   
--   >>> takeWhile (const False) undefined
--   *** Exception: Prelude.undefined
--   
--   
--   
--   >>> takeWhile (const False) (undefined : undefined)
--   []
--   
--   
--   
--   >>> take 1 (takeWhile (const True) (1 : undefined))
--   [1]
--   
--   
--   
Examples
--   
--   
--   >>> takeWhile (< 3) [1,2,3,4,1,2,3,4]
--   [1,2]
--   
--   
--   
--   >>> takeWhile (< 9) [1,2,3]
--   [1,2,3]
--   
--   
--   
--   >>> takeWhile (< 0) [1,2,3]
--   []
--   
takeWhile :: (a -> Bool) -> [a] -> [a]

-- | dropWhile p xs returns the suffix remaining after
--   takeWhile p xs.
--   
--   
Examples
--   
--   
--   >>> dropWhile (< 3) [1,2,3,4,5,1,2,3]
--   [3,4,5,1,2,3]
--   
--   
--   
--   >>> dropWhile (< 9) [1,2,3]
--   []
--   
--   
--   
--   >>> dropWhile (< 0) [1,2,3]
--   [1,2,3]
--   
dropWhile :: (a -> Bool) -> [a] -> [a]

-- | take n, applied to a list xs, returns the
--   prefix of xs of length n, or xs itself if
--   n >= length xs.
--   
--   It is an instance of the more general genericTake, in which
--   n may be of any integral type.
--   
--   
Laziness
--   
--   
--   >>> take 0 undefined
--   []
--   
--   >>> take 2 (1 : 2 : undefined)
--   [1,2]
--   
--   
--   
Examples
--   
--   
--   >>> take 5 "Hello World!"
--   "Hello"
--   
--   
--   
--   >>> take 3 [1,2,3,4,5]
--   [1,2,3]
--   
--   
--   
--   >>> take 3 [1,2]
--   [1,2]
--   
--   
--   
--   >>> take 3 []
--   []
--   
--   
--   
--   >>> take (-1) [1,2]
--   []
--   
--   
--   
--   >>> take 0 [1,2]
--   []
--   
take :: Int -> [a] -> [a]

-- | drop n xs returns the suffix of xs after the
--   first n elements, or [] if n >= length
--   xs.
--   
--   It is an instance of the more general genericDrop, in which
--   n may be of any integral type.
--   
--   
Examples
--   
--   
--   >>> drop 6 "Hello World!"
--   "World!"
--   
--   
--   
--   >>> drop 3 [1,2,3,4,5]
--   [4,5]
--   
--   
--   
--   >>> drop 3 [1,2]
--   []
--   
--   
--   
--   >>> drop 3 []
--   []
--   
--   
--   
--   >>> drop (-1) [1,2]
--   [1,2]
--   
--   
--   
--   >>> drop 0 [1,2]
--   [1,2]
--   
drop :: Int -> [a] -> [a]

-- | splitAt n xs returns a tuple where first element is
--   xs prefix of length n and second element is the
--   remainder of the list:
--   
--   splitAt is an instance of the more general
--   genericSplitAt, in which n may be of any integral
--   type.
--   
--   
Laziness
--   
--   It is equivalent to (take n xs, drop n xs)
--   unless n is _|_: splitAt _|_ xs = _|_, not
--   (_|_, _|_)).
--   
--   The first component of the tuple is produced lazily:
--   
--   
--   >>> fst (splitAt 0 undefined)
--   []
--   
--   
--   
--   >>> take 1 (fst (splitAt 10 (1 : undefined)))
--   [1]
--   
--   
--   
Examples
--   
--   
--   >>> splitAt 6 "Hello World!"
--   ("Hello ","World!")
--   
--   
--   
--   >>> splitAt 3 [1,2,3,4,5]
--   ([1,2,3],[4,5])
--   
--   
--   
--   >>> splitAt 1 [1,2,3]
--   ([1],[2,3])
--   
--   
--   
--   >>> splitAt 3 [1,2,3]
--   ([1,2,3],[])
--   
--   
--   
--   >>> splitAt 4 [1,2,3]
--   ([1,2,3],[])
--   
--   
--   
--   >>> splitAt 0 [1,2,3]
--   ([],[1,2,3])
--   
--   
--   
--   >>> splitAt (-1) [1,2,3]
--   ([],[1,2,3])
--   
splitAt :: Int -> [a] -> ([a], [a])

-- | span, applied to a predicate p and a list xs,
--   returns a tuple where first element is the longest prefix (possibly
--   empty) of xs of elements that satisfy p and second
--   element is the remainder of the list:
--   
--   span p xs is equivalent to (takeWhile p xs,
--   dropWhile p xs), even if p is _|_.
--   
--   
Laziness
--   
--   
--   >>> span undefined []
--   ([],[])
--   
--   >>> fst (span (const False) undefined)
--   *** Exception: Prelude.undefined
--   
--   >>> fst (span (const False) (undefined : undefined))
--   []
--   
--   >>> take 1 (fst (span (const True) (1 : undefined)))
--   [1]
--   
--   
--   span produces the first component of the tuple lazily:
--   
--   
--   >>> take 10 (fst (span (const True) [1..]))
--   [1,2,3,4,5,6,7,8,9,10]
--   
--   
--   
Examples
--   
--   
--   >>> span (< 3) [1,2,3,4,1,2,3,4]
--   ([1,2],[3,4,1,2,3,4])
--   
--   
--   
--   >>> span (< 9) [1,2,3]
--   ([1,2,3],[])
--   
--   
--   
--   >>> span (< 0) [1,2,3]
--   ([],[1,2,3])
--   
span :: (a -> Bool) -> [a] -> ([a], [a])

-- | break, applied to a predicate p and a list
--   xs, returns a tuple where first element is longest prefix
--   (possibly empty) of xs of elements that do not satisfy
--   p and second element is the remainder of the list:
--   
--   break p is equivalent to span (not .
--   p) and consequently to (takeWhile (not . p) xs,
--   dropWhile (not . p) xs), even if p is
--   _|_.
--   
--   
Laziness
--   
--   
--   >>> break undefined []
--   ([],[])
--   
--   
--   
--   >>> fst (break (const True) undefined)
--   *** Exception: Prelude.undefined
--   
--   
--   
--   >>> fst (break (const True) (undefined : undefined))
--   []
--   
--   
--   
--   >>> take 1 (fst (break (const False) (1 : undefined)))
--   [1]
--   
--   
--   break produces the first component of the tuple lazily:
--   
--   
--   >>> take 10 (fst (break (const False) [1..]))
--   [1,2,3,4,5,6,7,8,9,10]
--   
--   
--   
Examples
--   
--   
--   >>> break (> 3) [1,2,3,4,1,2,3,4]
--   ([1,2,3],[4,1,2,3,4])
--   
--   
--   
--   >>> break (< 9) [1,2,3]
--   ([],[1,2,3])
--   
--   
--   
--   >>> break (> 9) [1,2,3]
--   ([1,2,3],[])
--   
break :: (a -> Bool) -> [a] -> ([a], [a])

-- | <math>. reverse xs returns the elements of
--   xs in reverse order. xs must be finite.
--   
--   
Laziness
--   
--   reverse is lazy in its elements.
--   
--   
--   >>> head (reverse [undefined, 1])
--   1
--   
--   
--   
--   >>> reverse (1 : 2 : undefined)
--   *** Exception: Prelude.undefined
--   
--   
--   
Examples
--   
--   
--   >>> reverse []
--   []
--   
--   
--   
--   >>> reverse [42]
--   [42]
--   
--   
--   
--   >>> reverse [2,5,7]
--   [7,5,2]
--   
--   
--   
--   >>> reverse [1..]
--   * Hangs forever *
--   
reverse :: [a] -> [a]

-- | and returns the conjunction of a container of Bools. For the
--   result to be True, the container must be finite; False,
--   however, results from a False value finitely far from the left
--   end.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> and []
--   True
--   
--   
--   
--   >>> and [True]
--   True
--   
--   
--   
--   >>> and [False]
--   False
--   
--   
--   
--   >>> and [True, True, False]
--   False
--   
--   
--   
--   >>> and (False : repeat True) -- Infinite list [False,True,True,True,...
--   False
--   
--   
--   
--   >>> and (repeat True)
--   * Hangs forever *
--   
and :: Foldable t => t Bool -> Bool

-- | or returns the disjunction of a container of Bools. For the
--   result to be False, the container must be finite; True,
--   however, results from a True value finitely far from the left
--   end.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> or []
--   False
--   
--   
--   
--   >>> or [True]
--   True
--   
--   
--   
--   >>> or [False]
--   False
--   
--   
--   
--   >>> or [True, True, False]
--   True
--   
--   
--   
--   >>> or (True : repeat False) -- Infinite list [True,False,False,False,...
--   True
--   
--   
--   
--   >>> or (repeat False)
--   * Hangs forever *
--   
or :: Foldable t => t Bool -> Bool

-- | Determines whether any element of the structure satisfies the
--   predicate.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> any (> 3) []
--   False
--   
--   
--   
--   >>> any (> 3) [1,2]
--   False
--   
--   
--   
--   >>> any (> 3) [1,2,3,4,5]
--   True
--   
--   
--   
--   >>> any (> 3) [1..]
--   True
--   
--   
--   
--   >>> any (> 3) [0, -1..]
--   * Hangs forever *
--   
any :: Foldable t => (a -> Bool) -> t a -> Bool

-- | Determines whether all elements of the structure satisfy the
--   predicate.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> all (> 3) []
--   True
--   
--   
--   
--   >>> all (> 3) [1,2]
--   False
--   
--   
--   
--   >>> all (> 3) [1,2,3,4,5]
--   False
--   
--   
--   
--   >>> all (> 3) [1..]
--   False
--   
--   
--   
--   >>> all (> 3) [4..]
--   * Hangs forever *
--   
all :: Foldable t => (a -> Bool) -> t a -> Bool

-- | notElem is the negation of elem.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> 3 `notElem` []
--   True
--   
--   
--   
--   >>> 3 `notElem` [1,2]
--   True
--   
--   
--   
--   >>> 3 `notElem` [1,2,3,4,5]
--   False
--   
--   
--   For infinite structures, notElem terminates if the value exists
--   at a finite distance from the left side of the structure:
--   
--   
--   >>> 3 `notElem` [1..]
--   False
--   
--   
--   
--   >>> 3 `notElem` ([4..] ++ [3])
--   * Hangs forever *
--   
notElem :: (Foldable t, Eq a) => a -> t a -> Bool
infix 4 `notElem`

-- | <math>. lookup key assocs looks up a key in an
--   association list. For the result to be Nothing, the list must
--   be finite.
--   
--   
Examples
--   
--   
--   >>> lookup 2 []
--   Nothing
--   
--   
--   
--   >>> lookup 2 [(1, "first")]
--   Nothing
--   
--   
--   
--   >>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
--   Just "second"
--   
lookup :: Eq a => a -> [(a, b)] -> Maybe b

-- | Map a function over all the elements of a container and concatenate
--   the resulting lists.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> concatMap (take 3) [[1..], [10..], [100..], [1000..]]
--   [1,2,3,10,11,12,100,101,102,1000,1001,1002]
--   
--   
--   
--   >>> concatMap (take 3) (Just [1..])
--   [1,2,3]
--   
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]

-- | List index (subscript) operator, starting from 0. It is an instance of
--   the more general genericIndex, which takes an index of any
--   integral type.
--   
--   WARNING: This function is partial, and should only be used if you are
--   sure that the indexing will not fail. Otherwise, use !?.
--   
--   WARNING: This function takes linear time in the index.
--   
--   
Examples
--   
--   
--   >>> ['a', 'b', 'c'] !! 0
--   'a'
--   
--   
--   
--   >>> ['a', 'b', 'c'] !! 2
--   'c'
--   
--   
--   
--   >>> ['a', 'b', 'c'] !! 3
--   *** Exception: Prelude.!!: index too large
--   
--   
--   
--   >>> ['a', 'b', 'c'] !! (-1)
--   *** Exception: Prelude.!!: negative index
--   
(!!) :: HasCallStack => [a] -> Int -> a
infixl 9 !!

-- | zip3 takes three lists and returns a list of triples, analogous
--   to zip. It is capable of list fusion, but it is restricted to
--   its first list argument and its resulting list.
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]

-- | <math>. zipWith generalises zip by zipping with
--   the function given as the first argument, instead of a tupling
--   function.
--   
--   
--   zipWith (,) xs ys == zip xs ys
--   zipWith f [x1,x2,x3..] [y1,y2,y3..] == [f x1 y1, f x2 y2, f x3 y3..]
--   
--   
--   zipWith is right-lazy:
--   
--   
--   >>> let f = undefined
--   
--   >>> zipWith f [] undefined
--   []
--   
--   
--   zipWith is capable of list fusion, but it is restricted to its
--   first list argument and its resulting list.
--   
--   
Examples
--   
--   zipWith (+) can be applied to two lists to
--   produce the list of corresponding sums:
--   
--   
--   >>> zipWith (+) [1, 2, 3] [4, 5, 6]
--   [5,7,9]
--   
--   
--   
--   >>> zipWith (++) ["hello ", "foo"] ["world!", "bar"]
--   ["hello world!","foobar"]
--   
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

-- | <math>. The zipWith3 function takes a function which
--   combines three elements, as well as three lists and returns a list of
--   the function applied to corresponding elements, analogous to
--   zipWith. It is capable of list fusion, but it is restricted to
--   its first list argument and its resulting list.
--   
--   
--   zipWith3 (,,) xs ys zs == zip3 xs ys zs
--   zipWith3 f [x1,x2,x3..] [y1,y2,y3..] [z1,z2,z3..] == [f x1 y1 z1, f x2 y2 z2, f x3 y3 z3..]
--   
--   
--   
Examples
--   
--   
--   >>> zipWith3 (\x y z -> [x, y, z]) "123" "abc" "xyz"
--   ["1ax","2by","3cz"]
--   
--   
--   
--   >>> zipWith3 (\x y z -> (x * y) + z) [1, 2, 3] [4, 5, 6] [7, 8, 9]
--   [11,18,27]
--   
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]

-- | unzip transforms a list of pairs into a list of first
--   components and a list of second components.
--   
--   
Examples
--   
--   
--   >>> unzip []
--   ([],[])
--   
--   
--   
--   >>> unzip [(1, 'a'), (2, 'b')]
--   ([1,2],"ab")
--   
unzip :: [(a, b)] -> ([a], [b])

-- | The unzip3 function takes a list of triples and returns three
--   lists of the respective components, analogous to unzip.
--   
--   
Examples
--   
--   
--   >>> unzip3 []
--   ([],[],[])
--   
--   
--   
--   >>> unzip3 [(1, 'a', True), (2, 'b', False)]
--   ([1,2],"ab",[True,False])
--   
unzip3 :: [(a, b, c)] -> ([a], [b], [c])

-- | The find function takes a predicate and a structure and returns
--   the leftmost element of the structure matching the predicate, or
--   Nothing if there is no such element.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> find (> 42) [0, 5..]
--   Just 45
--   
--   
--   
--   >>> find (> 12) [1..7]
--   Nothing
--   
find :: Foldable t => (a -> Bool) -> t a -> Maybe a

-- | The dropWhileEnd function drops the largest suffix of a list in
--   which the given predicate holds for all elements.
--   
--   
Laziness
--   
--   This function is lazy in spine, but strict in elements, which makes it
--   different from reverse . dropWhile p
--   . reverse, which is strict in spine, but lazy in
--   elements. For instance:
--   
--   
--   >>> take 1 (dropWhileEnd (< 0) (1 : undefined))
--   [1]
--   
--   
--   
--   >>> take 1 (reverse $ dropWhile (< 0) $ reverse (1 : undefined))
--   *** Exception: Prelude.undefined
--   
--   
--   but on the other hand
--   
--   
--   >>> last (dropWhileEnd (< 0) [undefined, 1])
--   *** Exception: Prelude.undefined
--   
--   
--   
--   >>> last (reverse $ dropWhile (< 0) $ reverse [undefined, 1])
--   1
--   
--   
--   
Examples
--   
--   
--   >>> dropWhileEnd isSpace "foo\n"
--   "foo"
--   
--   
--   
--   >>> dropWhileEnd isSpace "foo bar"
--   "foo bar"
--   
--   >>> dropWhileEnd (> 10) [1..20]
--   [1,2,3,4,5,6,7,8,9,10]
--   
dropWhileEnd :: (a -> Bool) -> [a] -> [a]

-- | <math>. The stripPrefix function drops the given prefix
--   from a list. It returns Nothing if the list did not start with
--   the prefix given, or Just the list after the prefix, if it
--   does.
--   
--   
Examples
--   
--   
--   >>> stripPrefix "foo" "foobar"
--   Just "bar"
--   
--   
--   
--   >>> stripPrefix "foo" "foo"
--   Just ""
--   
--   
--   
--   >>> stripPrefix "foo" "barfoo"
--   Nothing
--   
--   
--   
--   >>> stripPrefix "foo" "barfoobaz"
--   Nothing
--   
stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]

-- | The elemIndex function returns the index of the first element
--   in the given list which is equal (by ==) to the query element,
--   or Nothing if there is no such element. For the result to be
--   Nothing, the list must be finite.
--   
--   
Examples
--   
--   
--   >>> elemIndex 4 [0..]
--   Just 4
--   
--   
--   
--   >>> elemIndex 'o' "haskell"
--   Nothing
--   
--   
--   
--   >>> elemIndex 0 [1..]
--   * hangs forever *
--   
elemIndex :: Eq a => a -> [a] -> Maybe Int

-- | The elemIndices function extends elemIndex, by returning
--   the indices of all elements equal to the query element, in ascending
--   order.
--   
--   
Examples
--   
--   
--   >>> elemIndices 'o' "Hello World"
--   [4,7]
--   
--   
--   
--   >>> elemIndices 1 [1, 2, 3, 1, 2, 3]
--   [0,3]
--   
elemIndices :: Eq a => a -> [a] -> [Int]

-- | The findIndex function takes a predicate and a list and returns
--   the index of the first element in the list satisfying the predicate,
--   or Nothing if there is no such element. For the result to be
--   Nothing, the list must be finite.
--   
--   
Examples
--   
--   
--   >>> findIndex isSpace "Hello World!"
--   Just 5
--   
--   
--   
--   >>> findIndex odd [0, 2, 4, 6]
--   Nothing
--   
--   
--   
--   >>> findIndex even [1..]
--   Just 1
--   
--   
--   
--   >>> findIndex odd [0, 2 ..]
--   * hangs forever *
--   
findIndex :: (a -> Bool) -> [a] -> Maybe Int

-- | The findIndices function extends findIndex, by returning
--   the indices of all elements satisfying the predicate, in ascending
--   order.
--   
--   
Examples
--   
--   
--   >>> findIndices (`elem` "aeiou") "Hello World!"
--   [1,4,7]
--   
--   
--   
--   >>> findIndices (\l -> length l > 3) ["a", "bcde", "fgh", "ijklmnop"]
--   [1,3]
--   
findIndices :: (a -> Bool) -> [a] -> [Int]

-- | <math>. The isPrefixOf function takes two lists and
--   returns True iff the first list is a prefix of the second.
--   
--   
Examples
--   
--   
--   >>> "Hello" `isPrefixOf` "Hello World!"
--   True
--   
--   
--   
--   >>> "Hello" `isPrefixOf` "Wello Horld!"
--   False
--   
--   
--   For the result to be True, the first list must be finite;
--   False, however, results from any mismatch:
--   
--   
--   >>> [0..] `isPrefixOf` [1..]
--   False
--   
--   
--   
--   >>> [0..] `isPrefixOf` [0..99]
--   False
--   
--   
--   
--   >>> [0..99] `isPrefixOf` [0..]
--   True
--   
--   
--   
--   >>> [0..] `isPrefixOf` [0..]
--   * Hangs forever *
--   
--   
--   isPrefixOf shortcuts when the first argument is empty:
--   
--   
--   >>> isPrefixOf [] undefined
--   True
--   
isPrefixOf :: Eq a => [a] -> [a] -> Bool

-- | The isSuffixOf function takes two lists and returns True
--   iff the first list is a suffix of the second.
--   
--   
Examples
--   
--   
--   >>> "ld!" `isSuffixOf` "Hello World!"
--   True
--   
--   
--   
--   >>> "World" `isSuffixOf` "Hello World!"
--   False
--   
--   
--   The second list must be finite; however the first list may be
--   infinite:
--   
--   
--   >>> [0..] `isSuffixOf` [0..99]
--   False
--   
--   
--   
--   >>> [0..99] `isSuffixOf` [0..]
--   * Hangs forever *
--   
isSuffixOf :: Eq a => [a] -> [a] -> Bool

-- | The isInfixOf function takes two lists and returns True
--   iff the first list is contained, wholly and intact, anywhere within
--   the second.
--   
--   
Examples
--   
--   
--   >>> isInfixOf "Haskell" "I really like Haskell."
--   True
--   
--   
--   
--   >>> isInfixOf "Ial" "I really like Haskell."
--   False
--   
--   
--   For the result to be True, the first list must be finite; for
--   the result to be False, the second list must be finite:
--   
--   
--   >>> [20..50] `isInfixOf` [0..]
--   True
--   
--   
--   
--   >>> [0..] `isInfixOf` [20..50]
--   False
--   
--   
--   
--   >>> [0..] `isInfixOf` [0..]
--   * Hangs forever *
--   
isInfixOf :: Eq a => [a] -> [a] -> Bool

-- | <math>. The nub function removes duplicate elements from
--   a list. In particular, it keeps only the first occurrence of each
--   element. (The name nub means `essence'.) It is a special case
--   of nubBy, which allows the programmer to supply their own
--   equality test.
--   
--   If there exists instance Ord a, it's faster to use
--   nubOrd from the containers package (link to the
--   latest online documentation), which takes only <math> time
--   where d is the number of distinct elements in the list.
--   
--   Another approach to speed up nub is to use map
--   Data.List.NonEmpty.head .
--   Data.List.NonEmpty.group . sort, which takes
--   <math> time, requires instance Ord a and doesn't
--   preserve the order.
--   
--   
Examples
--   
--   
--   >>> nub [1,2,3,4,3,2,1,2,4,3,5]
--   [1,2,3,4,5]
--   
--   
--   
--   >>> nub "hello, world!"
--   "helo, wrd!"
--   
nub :: Eq a => [a] -> [a]

-- | The nubBy function behaves just like nub, except it uses
--   a user-supplied equality predicate instead of the overloaded
--   (==) function.
--   
--   
Examples
--   
--   
--   >>> nubBy (\x y -> mod x 3 == mod y 3) [1,2,4,5,6]
--   [1,2,6]
--   
--   
--   
--   >>> nubBy (/=) [2, 7, 1, 8, 2, 8, 1, 8, 2, 8]
--   [2,2,2]
--   
--   
--   
--   >>> nubBy (>) [1, 2, 3, 2, 1, 5, 4, 5, 3, 2]
--   [1,2,3,5,5]
--   
nubBy :: (a -> a -> Bool) -> [a] -> [a]

-- | <math>. delete x removes the first occurrence of
--   x from its list argument.
--   
--   It is a special case of deleteBy, which allows the programmer
--   to supply their own equality test.
--   
--   
Examples
--   
--   
--   >>> delete 'a' "banana"
--   "bnana"
--   
--   
--   
--   >>> delete "not" ["haskell", "is", "not", "awesome"]
--   ["haskell","is","awesome"]
--   
delete :: Eq a => a -> [a] -> [a]

-- | <math>. The deleteBy function behaves like delete,
--   but takes a user-supplied equality predicate.
--   
--   
Examples
--   
--   
--   >>> deleteBy (<=) 4 [1..10]
--   [1,2,3,5,6,7,8,9,10]
--   
--   
--   
--   >>> deleteBy (/=) 5 [5, 5, 4, 3, 5, 2]
--   [5,5,3,5,2]
--   
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]

-- | The \\ function is list difference (non-associative). In the
--   result of xs \\ ys, the first occurrence of
--   each element of ys in turn (if any) has been removed from
--   xs. Thus (xs ++ ys) \\ xs == ys.
--   
--   It is a special case of deleteFirstsBy, which allows the
--   programmer to supply their own equality test.
--   
--   
Examples
--   
--   
--   >>> "Hello World!" \\ "ell W"
--   "Hoorld!"
--   
--   
--   The second list must be finite, but the first may be infinite.
--   
--   
--   >>> take 5 ([0..] \\ [2..4])
--   [0,1,5,6,7]
--   
--   
--   
--   >>> take 5 ([0..] \\ [2..])
--   * Hangs forever *
--   
(\\) :: Eq a => [a] -> [a] -> [a]
infix 5 \\

-- | The union function returns the list union of the two lists. It
--   is a special case of unionBy, which allows the programmer to
--   supply their own equality test.
--   
--   
Examples
--   
--   
--   >>> "dog" `union` "cow"
--   "dogcw"
--   
--   
--   If equal elements are present in both lists, an element from the first
--   list will be used. If the second list contains equal elements, only
--   the first one will be retained:
--   
--   
--   >>> import Data.Semigroup(Arg(..))
--   
--   >>> union [Arg () "dog"] [Arg () "cow"]
--   [Arg () "dog"]
--   
--   >>> union [] [Arg () "dog", Arg () "cow"]
--   [Arg () "dog"]
--   
--   
--   However if the first list contains duplicates, so will the result:
--   
--   
--   >>> "coot" `union` "duck"
--   "cootduk"
--   
--   >>> "duck" `union` "coot"
--   "duckot"
--   
--   
--   union is productive even if both arguments are infinite.
--   
--   
--   >>> [0, 2 ..] `union` [1, 3 ..]
--   [0,2,4,6,8,10,12..
--   
union :: Eq a => [a] -> [a] -> [a]

-- | The unionBy function is the non-overloaded version of
--   union. Both arguments may be infinite.
--   
--   
Examples
--   
--   
--   >>> unionBy (>) [3, 4, 5] [1, 2, 3, 4, 5, 6]
--   [3,4,5,4,5,6]
--   
--   
--   
--   >>> import Data.Semigroup (Arg(..))
--   
--   >>> unionBy (/=) [Arg () "Saul"] [Arg () "Kim"]
--   [Arg () "Saul", Arg () "Kim"]
--   
unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]

-- | The intersect function takes the list intersection of two
--   lists. It is a special case of intersectBy, which allows the
--   programmer to supply their own equality test.
--   
--   
Examples
--   
--   
--   >>> [1,2,3,4] `intersect` [2,4,6,8]
--   [2,4]
--   
--   
--   If equal elements are present in both lists, an element from the first
--   list will be used, and all duplicates from the second list quashed:
--   
--   
--   >>> import Data.Semigroup
--   
--   >>> intersect [Arg () "dog"] [Arg () "cow", Arg () "cat"]
--   [Arg () "dog"]
--   
--   
--   However if the first list contains duplicates, so will the result.
--   
--   
--   >>> "coot" `intersect` "heron"
--   "oo"
--   
--   >>> "heron" `intersect` "coot"
--   "o"
--   
--   
--   If the second list is infinite, intersect either hangs or
--   returns its first argument in full. Otherwise if the first list is
--   infinite, intersect might be productive:
--   
--   
--   >>> intersect [100..] [0..]
--   [100,101,102,103...
--   
--   >>> intersect [0] [1..]
--   * Hangs forever *
--   
--   >>> intersect [1..] [0]
--   * Hangs forever *
--   
--   >>> intersect (cycle [1..3]) [2]
--   [2,2,2,2...
--   
intersect :: Eq a => [a] -> [a] -> [a]

-- | The intersectBy function is the non-overloaded version of
--   intersect. It is productive for infinite arguments only if the
--   first one is a subset of the second.
intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]

-- | <math>. The intersperse function takes an element and a
--   list and `intersperses' that element between the elements of the list.
--   
--   
Laziness
--   
--   intersperse has the following properties
--   
--   
--   >>> take 1 (intersperse undefined ('a' : undefined))
--   "a"
--   
--   
--   
--   >>> take 2 (intersperse ',' ('a' : undefined))
--   "a*** Exception: Prelude.undefined
--   
--   
--   
Examples
--   
--   
--   >>> intersperse ',' "abcde"
--   "a,b,c,d,e"
--   
--   
--   
--   >>> intersperse 1 [3, 4, 5]
--   [3,1,4,1,5]
--   
intersperse :: a -> [a] -> [a]

-- | The partition function takes a predicate and a list, and
--   returns the pair of lists of elements which do and do not satisfy the
--   predicate, respectively; i.e.,
--   
--   
--   partition p xs == (filter p xs, filter (not . p) xs)
--   
--   
--   
Examples
--   
--   
--   >>> partition (`elem` "aeiou") "Hello World!"
--   ("eoo","Hll Wrld!")
--   
--   
--   
--   >>> partition even [1..10]
--   ([2,4,6,8,10],[1,3,5,7,9])
--   
--   
--   
--   >>> partition (< 5) [1..10]
--   ([1,2,3,4],[5,6,7,8,9,10])
--   
partition :: (a -> Bool) -> [a] -> ([a], [a])

-- | <math>. The insert function takes an element and a list
--   and inserts the element into the list at the first position where it
--   is less than or equal to the next element. In particular, if the list
--   is sorted before the call, the result will also be sorted. It is a
--   special case of insertBy, which allows the programmer to supply
--   their own comparison function.
--   
--   
Examples
--   
--   
--   >>> insert (-1) [1, 2, 3]
--   [-1,1,2,3]
--   
--   
--   
--   >>> insert 'd' "abcefg"
--   "abcdefg"
--   
--   
--   
--   >>> insert 4 [1, 2, 3, 5, 6, 7]
--   [1,2,3,4,5,6,7]
--   
insert :: Ord a => a -> [a] -> [a]

-- | <math>. The non-overloaded version of insert.
--   
--   
Examples
--   
--   
--   >>> insertBy (\x y -> compare (length x) (length y)) [1, 2] [[1], [1, 2, 3], [1, 2, 3, 4]]
--   [[1],[1,2],[1,2,3],[1,2,3,4]]
--   
insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]

-- | <math>. The genericLength function is an overloaded
--   version of length. In particular, instead of returning an
--   Int, it returns any type which is an instance of Num. It
--   is, however, less efficient than length.
--   
--   
Examples
--   
--   
--   >>> genericLength [1, 2, 3] :: Int
--   3
--   
--   >>> genericLength [1, 2, 3] :: Float
--   3.0
--   
--   
--   Users should take care to pick a return type that is wide enough to
--   contain the full length of the list. If the width is insufficient, the
--   overflow behaviour will depend on the (+) implementation in
--   the selected Num instance. The following example overflows
--   because the actual list length of 200 lies outside of the
--   Int8 range of -128..127.
--   
--   
--   >>> genericLength [1..200] :: Int8
--   -56
--   
genericLength :: Num i => [a] -> i

-- | The genericTake function is an overloaded version of
--   take, which accepts any Integral value as the number of
--   elements to take.
genericTake :: Integral i => i -> [a] -> [a]

-- | The genericDrop function is an overloaded version of
--   drop, which accepts any Integral value as the number of
--   elements to drop.
genericDrop :: Integral i => i -> [a] -> [a]

-- | The genericSplitAt function is an overloaded version of
--   splitAt, which accepts any Integral value as the
--   position at which to split.
genericSplitAt :: Integral i => i -> [a] -> ([a], [a])

-- | The genericIndex function is an overloaded version of
--   !!, which accepts any Integral value as the index.
genericIndex :: Integral i => [a] -> i -> a

-- | The genericReplicate function is an overloaded version of
--   replicate, which accepts any Integral value as the
--   number of repetitions to make.
genericReplicate :: Integral i => i -> a -> [a]

-- | The zip4 function takes four lists and returns a list of
--   quadruples, analogous to zip. It is capable of list fusion, but
--   it is restricted to its first list argument and its resulting list.
zip4 :: [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)]

-- | The zip5 function takes five lists and returns a list of
--   five-tuples, analogous to zip. It is capable of list fusion,
--   but it is restricted to its first list argument and its resulting
--   list.
zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)]

-- | The zip6 function takes six lists and returns a list of
--   six-tuples, analogous to zip. It is capable of list fusion, but
--   it is restricted to its first list argument and its resulting list.
zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a, b, c, d, e, f)]

-- | The zip7 function takes seven lists and returns a list of
--   seven-tuples, analogous to zip. It is capable of list fusion,
--   but it is restricted to its first list argument and its resulting
--   list.
zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [(a, b, c, d, e, f, g)]

-- | The zipWith4 function takes a function which combines four
--   elements, as well as four lists and returns a list of their point-wise
--   combination, analogous to zipWith. It is capable of list
--   fusion, but it is restricted to its first list argument and its
--   resulting list.
zipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]

-- | The zipWith5 function takes a function which combines five
--   elements, as well as five lists and returns a list of their point-wise
--   combination, analogous to zipWith. It is capable of list
--   fusion, but it is restricted to its first list argument and its
--   resulting list.
zipWith5 :: (a -> b -> c -> d -> e -> f) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f]

-- | The zipWith6 function takes a function which combines six
--   elements, as well as six lists and returns a list of their point-wise
--   combination, analogous to zipWith. It is capable of list
--   fusion, but it is restricted to its first list argument and its
--   resulting list.
zipWith6 :: (a -> b -> c -> d -> e -> f -> g) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g]

-- | The zipWith7 function takes a function which combines seven
--   elements, as well as seven lists and returns a list of their
--   point-wise combination, analogous to zipWith. It is capable of
--   list fusion, but it is restricted to its first list argument and its
--   resulting list.
zipWith7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [h]

-- | The unzip4 function takes a list of quadruples and returns four
--   lists, analogous to unzip.
unzip4 :: [(a, b, c, d)] -> ([a], [b], [c], [d])

-- | The unzip5 function takes a list of five-tuples and returns
--   five lists, analogous to unzip.
unzip5 :: [(a, b, c, d, e)] -> ([a], [b], [c], [d], [e])

-- | The unzip6 function takes a list of six-tuples and returns six
--   lists, analogous to unzip.
unzip6 :: [(a, b, c, d, e, f)] -> ([a], [b], [c], [d], [e], [f])

-- | The unzip7 function takes a list of seven-tuples and returns
--   seven lists, analogous to unzip.
unzip7 :: [(a, b, c, d, e, f, g)] -> ([a], [b], [c], [d], [e], [f], [g])

-- | The deleteFirstsBy function takes a predicate and two lists and
--   returns the first list with the first occurrence of each element of
--   the second list removed. This is the non-overloaded version of
--   (\\).
--   
--   
--   (\\) == deleteFirstsBy (==)
--   
--   
--   The second list must be finite, but the first may be infinite.
--   
--   
Examples
--   
--   
--   >>> deleteFirstsBy (>) [1..10] [3, 4, 5]
--   [4,5,6,7,8,9,10]
--   
--   
--   
--   >>> deleteFirstsBy (/=) [1..10] [1, 3, 5]
--   [4,5,6,7,8,9,10]
--   
deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]

-- | The group function takes a list and returns a list of lists
--   such that the concatenation of the result is equal to the argument.
--   Moreover, each sublist in the result is non-empty, all elements are
--   equal to the first one, and consecutive equal elements of the input
--   end up in the same element of the output list.
--   
--   group is a special case of groupBy, which allows the
--   programmer to supply their own equality test.
--   
--   It's often preferable to use Data.List.NonEmpty.group,
--   which provides type-level guarantees of non-emptiness of inner lists.
--   A common idiom to squash repeating elements map head
--   . group is better served by map
--   Data.List.NonEmpty.head .
--   Data.List.NonEmpty.group because it avoids partial
--   functions.
--   
--   
Examples
--   
--   
--   >>> group "Mississippi"
--   ["M","i","ss","i","ss","i","pp","i"]
--   
--   
--   
--   >>> group [1, 1, 1, 2, 2, 3, 4, 5, 5]
--   [[1,1,1],[2,2],[3],[4],[5,5]]
--   
group :: Eq a => [a] -> [[a]]

-- | The groupBy function is the non-overloaded version of
--   group.
--   
--   When a supplied relation is not transitive, it is important to
--   remember that equality is checked against the first element in the
--   group, not against the nearest neighbour:
--   
--   
--   >>> groupBy (\a b -> b - a < 5) [0..19]
--   [[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14],[15,16,17,18,19]]
--   
--   
--   It's often preferable to use
--   Data.List.NonEmpty.groupBy, which provides type-level
--   guarantees of non-emptiness of inner lists.
--   
--   
Examples
--   
--   
--   >>> groupBy (/=) [1, 1, 1, 2, 3, 1, 4, 4, 5]
--   [[1],[1],[1,2,3],[1,4,4,5]]
--   
--   
--   
--   >>> groupBy (>) [1, 3, 5, 1, 4, 2, 6, 5, 4]
--   [[1],[3],[5,1,4,2],[6,5,4]]
--   
--   
--   
--   >>> groupBy (const not) [True, False, True, False, False, False, True]
--   [[True,False],[True,False,False,False],[True]]
--   
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

-- | The inits function returns all initial segments of the
--   argument, shortest first.
--   
--   inits is semantically equivalent to map
--   reverse . scanl (flip (:)) [], but under the
--   hood uses a queue to amortize costs of reverse.
--   
--   
Laziness
--   
--   Note that inits has the following strictness property:
--   inits (xs ++ _|_) = inits xs ++ _|_
--   
--   In particular, inits _|_ = [] : _|_
--   
--   
Examples
--   
--   
--   >>> inits "abc"
--   ["","a","ab","abc"]
--   
--   
--   
--   >>> inits []
--   [[]]
--   
--   
--   inits is productive on infinite lists:
--   
--   
--   >>> take 5 $ inits [1..]
--   [[],[1],[1,2],[1,2,3],[1,2,3,4]]
--   
inits :: [a] -> [[a]]

-- | <math>. The tails function returns all final segments of
--   the argument, longest first.
--   
--   
Laziness
--   
--   Note that tails has the following strictness property:
--   tails _|_ = _|_ : _|_
--   
--   
--   >>> tails undefined
--   [*** Exception: Prelude.undefined
--   
--   
--   
--   >>> drop 1 (tails [undefined, 1, 2])
--   [[1, 2], [2], []]
--   
--   
--   
Examples
--   
--   
--   >>> tails "abc"
--   ["abc","bc","c",""]
--   
--   
--   
--   >>> tails [1, 2, 3]
--   [[1,2,3],[2,3],[3],[]]
--   
--   
--   
--   >>> tails []
--   [[]]
--   
tails :: [a] -> [[a]]

-- | The subsequences function returns the list of all subsequences
--   of the argument.
--   
--   
Laziness
--   
--   subsequences does not look ahead unless it must:
--   
--   
--   >>> take 1 (subsequences undefined)
--   [[]]
--   
--   >>> take 2 (subsequences ('a' : undefined))
--   ["","a"]
--   
--   
--   
Examples
--   
--   
--   >>> subsequences "abc"
--   ["","a","b","ab","c","ac","bc","abc"]
--   
--   
--   This function is productive on infinite inputs:
--   
--   
--   >>> take 8 $ subsequences ['a'..]
--   ["","a","b","ab","c","ac","bc","abc"]
--   
subsequences :: [a] -> [[a]]

-- | The permutations function returns the list of all permutations
--   of the argument.
--   
--   Note that the order of permutations is not lexicographic. It satisfies
--   the following property:
--   
--   
--   map (take n) (take (product [1..n]) (permutations ([1..n] ++ undefined))) == permutations [1..n]
--   
--   
--   
Laziness
--   
--   The permutations function is maximally lazy: for each
--   n, the value of permutations xs starts with
--   those permutations that permute take n xs and keep
--   drop n xs.
--   
--   
Examples
--   
--   
--   >>> permutations "abc"
--   ["abc","bac","cba","bca","cab","acb"]
--   
--   
--   
--   >>> permutations [1, 2]
--   [[1,2],[2,1]]
--   
--   
--   
--   >>> permutations []
--   [[]]
--   
--   
--   This function is productive on infinite inputs:
--   
--   
--   >>> take 6 $ map (take 3) $ permutations ['a'..]
--   ["abc","bac","cba","bca","cab","acb"]
--   
permutations :: [a] -> [[a]]

-- | The sort function implements a stable sorting algorithm. It is
--   a special case of sortBy, which allows the programmer to supply
--   their own comparison function.
--   
--   Elements are arranged from lowest to highest, keeping duplicates in
--   the order they appeared in the input.
--   
--   The argument must be finite.
--   
--   
Examples
--   
--   
--   >>> sort [1,6,4,3,2,5]
--   [1,2,3,4,5,6]
--   
--   
--   
--   >>> sort "haskell"
--   "aehklls"
--   
--   
--   
--   >>> import Data.Semigroup(Arg(..))
--   
--   >>> sort [Arg ":)" 0, Arg ":D" 0, Arg ":)" 1, Arg ":3" 0, Arg ":D" 1]
--   [Arg ":)" 0,Arg ":)" 1,Arg ":3" 0,Arg ":D" 0,Arg ":D" 1]
--   
sort :: Ord a => [a] -> [a]

-- | Construct a list from a single element.
--   
--   
Examples
--   
--   
--   >>> singleton True
--   [True]
--   
--   
--   
--   >>> singleton [1, 2, 3]
--   [[1,2,3]]
--   
--   
--   
--   >>> singleton 'c'
--   "c"
--   
singleton :: a -> [a]

-- | The mapAccumL function behaves like a combination of
--   fmap and foldl; it applies a function to each element of
--   a structure, passing an accumulating parameter from left to right, and
--   returning a final value of this accumulator together with the new
--   structure.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> mapAccumL (\a b -> (a + b, a)) 0 [1..10]
--   (55,[0,1,3,6,10,15,21,28,36,45])
--   
--   
--   
--   >>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5]
--   ("012345",["0","01","012","0123","01234"])
--   
mapAccumL :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)

-- | The mapAccumR function behaves like a combination of
--   fmap and foldr; it applies a function to each element of
--   a structure, passing an accumulating parameter from right to left, and
--   returning a final value of this accumulator together with the new
--   structure.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> mapAccumR (\a b -> (a + b, a)) 0 [1..10]
--   (55,[54,52,49,45,40,34,27,19,10,0])
--   
--   
--   
--   >>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5]
--   ("054321",["05432","0543","054","05","0"])
--   
mapAccumR :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)

-- | The isSubsequenceOf function takes two lists and returns
--   True if all the elements of the first list occur, in order, in
--   the second. The elements do not have to occur consecutively.
--   
--   isSubsequenceOf x y is equivalent to x
--   `<a>elem</a>` (subsequences y).
--   
--   Note: isSubsequenceOf is often used in infix form.
--   
--   
Examples
--   
--   
--   >>> "GHC" `isSubsequenceOf` "The Glorious Haskell Compiler"
--   True
--   
--   
--   
--   >>> ['a','d'..'z'] `isSubsequenceOf` ['a'..'z']
--   True
--   
--   
--   
--   >>> [1..10] `isSubsequenceOf` [10,9..0]
--   False
--   
--   
--   For the result to be True, the first list must be finite; for
--   the result to be False, the second list must be finite:
--   
--   
--   >>> [0,2..10] `isSubsequenceOf` [0..]
--   True
--   
--   
--   
--   >>> [0..] `isSubsequenceOf` [0,2..10]
--   False
--   
--   
--   
--   >>> [0,2..] `isSubsequenceOf` [0..]
--   * Hangs forever*
--   
isSubsequenceOf :: Eq a => [a] -> [a] -> Bool

-- | The Monad class defines the basic operations over a
--   monad, a concept from a branch of mathematics known as
--   category theory. From the perspective of a Haskell programmer,
--   however, it is best to think of a monad as an abstract datatype
--   of actions. Haskell's do expressions provide a convenient
--   syntax for writing monadic expressions.
--   
--   Instances of Monad should satisfy the following:
--   
--   
--   
- Left identity return a >>= k = k
--   a
--   
- Right identity m >>= return =
--   m
--   
- Associativity m >>= (\x -> k x
--   >>= h) = (m >>= k) >>=
--   h
--   
--   
--   Furthermore, the Monad and Applicative operations should
--   relate as follows:
--   
--   
--   
- 
pure = return

--   
- 
m1 <*> m2 = m1 >>= (\x1 -> m2
--   >>= (\x2 -> return (x1 x2)))

--   
--   
--   The above laws imply:
--   
--   
--   
- 
fmap f xs = xs >>= return .
--   f

--   
- 
(>>) = (*>)

--   
--   
--   and that pure and (<*>) satisfy the applicative
--   functor laws.
--   
--   The instances of Monad for List, Maybe and
--   IO defined in the Prelude satisfy these laws.
class Applicative m => Monad (m :: Type -> Type)

-- | Sequentially compose two actions, passing any value produced by the
--   first as an argument to the second.
--   
--   'as >>= bs' can be understood as the do
--   expression
--   
--   
--   do a <- as
--      bs a
--   
--   
--   An alternative name for this function is 'bind', but some people may
--   refer to it as 'flatMap', which results from it being equivialent to
--   
--   
--   \x f -> join (fmap f x) :: Monad m => m a -> (a -> m b) -> m b
--   
--   
--   which can be seen as mapping a value with Monad m => m a ->
--   m (m b) and then 'flattening' m (m b) to m b
--   using join.
(>>=) :: Monad m => m a -> (a -> m b) -> m b

-- | Sequentially compose two actions, discarding any value produced by the
--   first, like sequencing operators (such as the semicolon) in imperative
--   languages.
--   
--   'as >> bs' can be understood as the do
--   expression
--   
--   
--   do as
--      bs
--   
--   
--   or in terms of (>>=) as
--   
--   
--   as >>= const bs
--   
(>>) :: Monad m => m a -> m b -> m b

-- | Inject a value into the monadic type. This function should not
--   be different from its default implementation as pure. The
--   justification for the existence of this function is merely historic.
return :: Monad m => a -> m a
infixl 1 >>=
infixl 1 >>

-- | A type f is a Functor if it provides a function fmap
--   which, given any types a and b lets you apply any
--   function from (a -> b) to turn an f a into an
--   f b, preserving the structure of f. Furthermore
--   f needs to adhere to the following:
--   
--   
--   
- Identity fmap id == id
--   
- Composition fmap (f . g) == fmap f .
--   fmap g
--   
--   
--   Note, that the second law follows from the free theorem of the type
--   fmap and the first law, so you need only check that the former
--   condition holds. See these articles by School of Haskell or
--   David Luposchainsky for an explanation.
class Functor (f :: Type -> Type)

-- | fmap is used to apply a function of type (a -> b)
--   to a value of type f a, where f is a functor, to produce a
--   value of type f b. Note that for any type constructor with
--   more than one parameter (e.g., Either), only the last type
--   parameter can be modified with fmap (e.g., b in
--   `Either a b`).
--   
--   Some type constructors with two parameters or more have a
--   Bifunctor instance that allows both the last and the
--   penultimate parameters to be mapped over.
--   
--   
Examples
--   
--   Convert from a Maybe Int to a Maybe String
--   using show:
--   
--   
--   >>> fmap show Nothing
--   Nothing
--   
--   >>> fmap show (Just 3)
--   Just "3"
--   
--   
--   Convert from an Either Int Int to an Either Int
--   String using show:
--   
--   
--   >>> fmap show (Left 17)
--   Left 17
--   
--   >>> fmap show (Right 17)
--   Right "17"
--   
--   
--   Double each element of a list:
--   
--   
--   >>> fmap (*2) [1,2,3]
--   [2,4,6]
--   
--   
--   Apply even to the second element of a pair:
--   
--   
--   >>> fmap even (2,2)
--   (2,True)
--   
--   
--   It may seem surprising that the function is only applied to the last
--   element of the tuple compared to the list example above which applies
--   it to every element in the list. To understand, remember that tuples
--   are type constructors with multiple type parameters: a tuple of 3
--   elements (a,b,c) can also be written (,,) a b c and
--   its Functor instance is defined for Functor ((,,) a
--   b) (i.e., only the third parameter is free to be mapped over with
--   fmap).
--   
--   It explains why fmap can be used with tuples containing
--   values of different types as in the following example:
--   
--   
--   >>> fmap even ("hello", 1.0, 4)
--   ("hello",1.0,True)
--   
fmap :: Functor f => (a -> b) -> f a -> f b

-- | Replace all locations in the input with the same value. The default
--   definition is fmap . const, but this may be
--   overridden with a more efficient version.
--   
--   
Examples
--   
--   Perform a computation with Maybe and replace the result with a
--   constant value if it is Just:
--   
--   
--   >>> 'a' <$ Just 2
--   Just 'a'
--   
--   >>> 'a' <$ Nothing
--   Nothing
--   
(<$) :: Functor f => a -> f b -> f a
infixl 4 <$

-- | When a value is bound in do-notation, the pattern on the left
--   hand side of <- might not match. In this case, this class
--   provides a function to recover.
--   
--   A Monad without a MonadFail instance may only be used in
--   conjunction with pattern that always match, such as newtypes, tuples,
--   data types with only a single data constructor, and irrefutable
--   patterns (~pat).
--   
--   Instances of MonadFail should satisfy the following law:
--   fail s should be a left zero for >>=,
--   
--   
--   fail s >>= f  =  fail s
--   
--   
--   If your Monad is also MonadPlus, a popular definition is
--   
--   
--   fail _ = mzero
--   
--   
--   fail s should be an action that runs in the monad itself, not
--   an exception (except in instances of MonadIO). In particular,
--   fail should not be implemented in terms of error.
class Monad m => MonadFail (m :: Type -> Type)
fail :: MonadFail m => String -> m a

-- | Conditional failure of Alternative computations. Defined by
--   
--   
--   guard True  = pure ()
--   guard False = empty
--   
--   
--   
Examples
--   
--   Common uses of guard include conditionally signalling an error
--   in an error monad and conditionally rejecting the current choice in an
--   Alternative-based parser.
--   
--   As an example of signalling an error in the error monad Maybe,
--   consider a safe division function safeDiv x y that returns
--   Nothing when the denominator y is zero and
--   Just (x `div` y) otherwise. For example:
--   
--   
--   >>> safeDiv 4 0
--   Nothing
--   
--   
--   
--   >>> safeDiv 4 2
--   Just 2
--   
--   
--   A definition of safeDiv using guards, but not guard:
--   
--   
--   safeDiv :: Int -> Int -> Maybe Int
--   safeDiv x y | y /= 0    = Just (x `div` y)
--               | otherwise = Nothing
--   
--   
--   A definition of safeDiv using guard and Monad
--   do-notation:
--   
--   
--   safeDiv :: Int -> Int -> Maybe Int
--   safeDiv x y = do
--     guard (y /= 0)
--     return (x `div` y)
--   
guard :: Alternative f => Bool -> f ()

-- | The join function is the conventional monad join operator. It
--   is used to remove one level of monadic structure, projecting its bound
--   argument into the outer level.
--   
--   'join bss' can be understood as the do
--   expression
--   
--   
--   do bs <- bss
--      bs
--   
--   
--   
Examples
--   
--   
--   >>> join [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
--   [1,2,3,4,5,6,7,8,9]
--   
--   
--   
--   >>> join (Just (Just 3))
--   Just 3
--   
--   
--   A common use of join is to run an IO computation
--   returned from an STM transaction, since STM transactions
--   can't perform IO directly. Recall that
--   
--   
--   atomically :: STM a -> IO a
--   
--   
--   is used to run STM transactions atomically. So, by specializing
--   the types of atomically and join to
--   
--   
--   atomically :: STM (IO b) -> IO (IO b)
--   join       :: IO (IO b)  -> IO b
--   
--   
--   we can compose them as
--   
--   
--   join . atomically :: STM (IO b) -> IO b
--   
--   
--   to run an STM transaction and the IO action it returns.
join :: Monad m => m (m a) -> m a

-- | Monads that also support choice and failure.
class (Alternative m, Monad m) => MonadPlus (m :: Type -> Type)

-- | The identity of mplus. It should also satisfy the equations
--   
--   
--   mzero >>= f  =  mzero
--   v >> mzero   =  mzero
--   
--   
--   The default definition is
--   
--   
--   mzero = empty
--   
mzero :: MonadPlus m => m a

-- | An associative operation. The default definition is
--   
--   
--   mplus = (<|>)
--   
mplus :: MonadPlus m => m a -> m a -> m a

-- | Same as >>=, but with the arguments interchanged.
--   
--   
--   as >>= f == f =<< as
--   
(=<<) :: Monad m => (a -> m b) -> m a -> m b
infixr 1 =<<

-- | Conditional execution of Applicative expressions. For example,
--   
--   
Examples
--   
--   
--   when debug (putStrLn "Debugging")
--   
--   
--   will output the string Debugging if the Boolean value
--   debug is True, and otherwise do nothing.
--   
--   
--   >>> putStr "pi:" >> when False (print 3.14159)
--   pi:
--   
when :: Applicative f => Bool -> f () -> f ()

-- | Promote a function to a monad. This is equivalent to fmap but
--   specialised to Monads.
liftM :: Monad m => (a1 -> r) -> m a1 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right.
--   
--   
Examples
--   
--   
--   >>> liftM2 (+) [0,1] [0,2]
--   [0,2,1,3]
--   
--   
--   
--   >>> liftM2 (+) (Just 1) Nothing
--   Nothing
--   
--   
--   
--   >>> liftM2 (+) (+ 3) (* 2) 5
--   18
--   
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right (cf. liftM2).
liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right (cf. liftM2).
liftM4 :: Monad m => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right (cf. liftM2).
liftM5 :: Monad m => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r

-- | In many situations, the liftM operations can be replaced by
--   uses of ap, which promotes function application.
--   
--   
--   return f `ap` x1 `ap` ... `ap` xn
--   
--   
--   is equivalent to
--   
--   
--   liftM<n> f x1 x2 ... xn
--   
--   
--   
Examples
--   
--   
--   >>> pure (\x y z -> x + y * z) `ap` Just 1 `ap` Just 5 `ap` Just 10
--   Just 51
--   
ap :: Monad m => m (a -> b) -> m a -> m b

-- | void value discards or ignores the result of
--   evaluation, such as the return value of an IO action.
--   
--   
Examples
--   
--   Replace the contents of a Maybe Int with unit:
--   
--   
--   >>> void Nothing
--   Nothing
--   
--   
--   
--   >>> void (Just 3)
--   Just ()
--   
--   
--   Replace the contents of an Either Int
--   Int with unit, resulting in an Either
--   Int ():
--   
--   
--   >>> void (Left 8675309)
--   Left 8675309
--   
--   
--   
--   >>> void (Right 8675309)
--   Right ()
--   
--   
--   Replace every element of a list with unit:
--   
--   
--   >>> void [1,2,3]
--   [(),(),()]
--   
--   
--   Replace the second element of a pair with unit:
--   
--   
--   >>> void (1,2)
--   (1,())
--   
--   
--   Discard the result of an IO action:
--   
--   
--   >>> mapM print [1,2]
--   1
--   2
--   [(),()]
--   
--   
--   
--   >>> void $ mapM print [1,2]
--   1
--   2
--   
void :: Functor f => f a -> f ()

-- | Map each element of a structure to a monadic action, evaluate these
--   actions from left to right, and ignore the results. For a version that
--   doesn't ignore the results see mapM.
--   
--   mapM_ is just like traverse_, but specialised to monadic
--   actions.
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()

-- | forM_ is mapM_ with its arguments flipped. For a version
--   that doesn't ignore the results see forM.
--   
--   forM_ is just like for_, but specialised to monadic
--   actions.
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()

-- | Evaluate each monadic action in the structure from left to right, and
--   ignore the results. For a version that doesn't ignore the results see
--   sequence.
--   
--   sequence_ is just like sequenceA_, but specialised to
--   monadic actions.
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()

-- | The sum of a collection of actions using (<|>),
--   generalizing concat.
--   
--   msum is just like asum, but specialised to
--   MonadPlus.
--   
--   
Examples
--   
--   Basic usage, using the MonadPlus instance for Maybe:
--   
--   
--   >>> msum [Just "Hello", Nothing, Just "World"]
--   Just "Hello"
--   
msum :: (Foldable t, MonadPlus m) => t (m a) -> m a

-- | forM is mapM with its arguments flipped. For a version
--   that ignores the results see forM_.
forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)

-- | This generalizes the list-based filter function.
--   
--   
--   runIdentity (filterM (Identity . p) xs) == filter p xs
--   
--   
--   
Examples
--   
--   
--   >>> filterM (\x -> do
--         putStrLn ("Keep: " ++ show x ++ "?")
--         answer <- getLine
--         pure (answer == "y"))
--       [1, 2, 3]
--   Keep: 1?
--   y
--   Keep: 2?
--   n
--   Keep: 3?
--   y
--   [1,3]
--   
--   
--   
--   >>> filterM (\x -> do
--         putStr (show x)
--         x' <- readLn
--         pure (x == x'))
--       [1, 2, 3]
--   12
--   22
--   33
--   [2,3]
--   
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]

-- | Left-to-right composition of Kleisli arrows.
--   
--   '(bs >=> cs) a' can be understood as the
--   do expression
--   
--   
--   do b <- bs a
--      cs b
--   
--   
--   or in terms of (>>=) as
--   
--   
--   bs a >>= cs
--   
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
infixr 1 >=>

-- | Right-to-left composition of Kleisli arrows.
--   (>=>), with the arguments flipped.
--   
--   Note how this operator resembles function composition
--   (.):
--   
--   
--   (.)   ::            (b ->   c) -> (a ->   b) -> a ->   c
--   (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
--   
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
infixr 1 <=<

-- | Repeat an action indefinitely.
--   
--   
Examples
--   
--   A common use of forever is to process input from network
--   sockets, Handles, and channels (e.g. MVar and
--   Chan).
--   
--   For example, here is how we might implement an echo server,
--   using forever both to listen for client connections on a
--   network socket and to echo client input on client connection handles:
--   
--   
--   echoServer :: Socket -> IO ()
--   echoServer socket = forever $ do
--     client <- accept socket
--     forkFinally (echo client) (\_ -> hClose client)
--     where
--       echo :: Handle -> IO ()
--       echo client = forever $
--         hGetLine client >>= hPutStrLn client
--   
--   
--   Note that "forever" isn't necessarily non-terminating. If the action
--   is in a MonadPlus and short-circuits after some number
--   of iterations. then forever actually returns
--   mzero, effectively short-circuiting its caller.
forever :: Applicative f => f a -> f b

-- | The mapAndUnzipM function maps its first argument over a list,
--   returning the result as a pair of lists. This function is mainly used
--   with complicated data structures or a state monad.
mapAndUnzipM :: Applicative m => (a -> m (b, c)) -> [a] -> m ([b], [c])

-- | The zipWithM function generalizes zipWith to arbitrary
--   applicative functors.
zipWithM :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m [c]

-- | zipWithM_ is the extension of zipWithM which ignores the
--   final result.
zipWithM_ :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m ()

-- | The foldM function is analogous to foldl, except that
--   its result is encapsulated in a monad. Note that foldM works
--   from left-to-right over the list arguments. This could be an issue
--   where (>>) and the `folded function' are not
--   commutative.
--   
--   
--   foldM f a1 [x1, x2, ..., xm]
--   
--   ==
--   
--   do
--     a2 <- f a1 x1
--     a3 <- f a2 x2
--     ...
--     f am xm
--   
--   
--   If right-to-left evaluation is required, the input list should be
--   reversed.
--   
--   Note: foldM is the same as foldlM
foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

-- | Like foldM, but discards the result.
foldM_ :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m ()

-- | replicateM n act performs the action act
--   n times, and then returns the list of results.
--   
--   
--   replicateM n (pure x) == replicate n x
--   
--   
--   
Examples
--   
--   
--   >>> replicateM 3 getLine
--   hi
--   heya
--   hiya
--   ["hi","heya","hiya"]
--   
--   
--   
--   >>> import Control.Monad.State
--   
--   >>> runState (replicateM 3 $ state $ \s -> (s, s + 1)) 1
--   ([1,2,3],4)
--   
replicateM :: Applicative m => Int -> m a -> m [a]

-- | Like replicateM, but discards the result.
--   
--   
Examples
--   
--   
--   >>> replicateM_ 3 (putStr "a")
--   aaa
--   
replicateM_ :: Applicative m => Int -> m a -> m ()

-- | The reverse of when.
--   
--   
Examples
--   
--   
--   >>> do x <- getLine
--          unless (x == "hi") (putStrLn "hi!")
--   comingupwithexamplesisdifficult
--   hi!
--   
--   
--   
--   >>> unless (pi > exp 1) Nothing
--   Just ()
--   
unless :: Applicative f => Bool -> f () -> f ()

-- | Strict version of <$>.
(<$!>) :: Monad m => (a -> b) -> m a -> m b
infixl 4 <$!>

-- | Direct MonadPlus equivalent of filter.
--   
--   
Examples
--   
--   The filter function is just mfilter specialized to the
--   list monad:
--   
--   
--   filter = ( mfilter :: (a -> Bool) -> [a] -> [a] )
--   
--   
--   An example using mfilter with the Maybe monad:
--   
--   
--   >>> mfilter odd (Just 1)
--   Just 1
--   
--   >>> mfilter odd (Just 2)
--   Nothing
--   
mfilter :: MonadPlus m => (a -> Bool) -> m a -> m a

-- | The Foldable class represents data structures that can be reduced to a
--   summary value one element at a time. Strict left-associative folds are
--   a good fit for space-efficient reduction, while lazy right-associative
--   folds are a good fit for corecursive iteration, or for folds that
--   short-circuit after processing an initial subsequence of the
--   structure's elements.
--   
--   Instances can be derived automatically by enabling the
--   DeriveFoldable extension. For example, a derived instance for
--   a binary tree might be:
--   
--   
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   
--   
--   A more detailed description can be found in the Overview
--   section of Data.Foldable#overview.
--   
--   For the class laws see the Laws section of
--   Data.Foldable#laws.
class Foldable (t :: Type -> Type)

-- | Map each element of the structure into a monoid, and combine the
--   results with (<>). This fold is
--   right-associative and lazy in the accumulator. For strict
--   left-associative folds consider foldMap' instead.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> foldMap Sum [1, 3, 5]
--   Sum {getSum = 9}
--   
--   
--   
--   >>> foldMap Product [1, 3, 5]
--   Product {getProduct = 15}
--   
--   
--   
--   >>> foldMap (replicate 3) [1, 2, 3]
--   [1,1,1,2,2,2,3,3,3]
--   
--   
--   When a Monoid's (<>) is lazy in its second
--   argument, foldMap can return a result even from an unbounded
--   structure. For example, lazy accumulation enables
--   Data.ByteString.Builder to efficiently serialise large data
--   structures and produce the output incrementally:
--   
--   
--   >>> import qualified Data.ByteString.Lazy as L
--   
--   >>> import qualified Data.ByteString.Builder as B
--   
--   >>> let bld :: Int -> B.Builder; bld i = B.intDec i <> B.word8 0x20
--   
--   >>> let lbs = B.toLazyByteString $ foldMap bld [0..]
--   
--   >>> L.take 64 lbs
--   "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24"
--   
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

-- | Right-associative fold of a structure, lazy in the accumulator.
--   
--   In the case of lists, foldr, when applied to a binary operator,
--   a starting value (typically the right-identity of the operator), and a
--   list, reduces the list using the binary operator, from right to left:
--   
--   
--   foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
--   
--   
--   Note that since the head of the resulting expression is produced by an
--   application of the operator to the first element of the list, given an
--   operator lazy in its right argument, foldr can produce a
--   terminating expression from an unbounded list.
--   
--   For a general Foldable structure this should be semantically
--   identical to,
--   
--   
--   foldr f z = foldr f z . toList
--   
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> foldr (||) False [False, True, False]
--   True
--   
--   
--   
--   >>> foldr (||) False []
--   False
--   
--   
--   
--   >>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
--   "foodcba"
--   
--   
--   
Infinite structures
--   
--   ⚠️ Applying foldr to infinite structures usually doesn't
--   terminate.
--   
--   It may still terminate under one of the following conditions:
--   
--   
--   
- the folding function is short-circuiting
--   
- the folding function is lazy on its second argument
--   
--   
--   
Short-circuiting
--   
--   (||) short-circuits on True values, so the
--   following terminates because there is a True value finitely far
--   from the left side:
--   
--   
--   >>> foldr (||) False (True : repeat False)
--   True
--   
--   
--   But the following doesn't terminate:
--   
--   
--   >>> foldr (||) False (repeat False ++ [True])
--   * Hangs forever *
--   
--   
--   
Laziness in the second argument
--   
--   Applying foldr to infinite structures terminates when the
--   operator is lazy in its second argument (the initial accumulator is
--   never used in this case, and so could be left undefined, but
--   [] is more clear):
--   
--   
--   >>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)
--   [1,4,7,10,13]
--   
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

-- | foldr' is a variant of foldr that performs strict
--   reduction from right to left, i.e. starting with the right-most
--   element. The input structure must be finite, otherwise
--   foldr' runs out of space (diverges).
--   
--   If you want a strict right fold in constant space, you need a
--   structure that supports faster than O(n) access to the
--   right-most element, such as Seq from the containers
--   package.
--   
--   This method does not run in constant space for structures such as
--   lists that don't support efficient right-to-left iteration and so
--   require O(n) space to perform right-to-left reduction. Use of
--   this method with such a structure is a hint that the chosen structure
--   may be a poor fit for the task at hand. If the order in which the
--   elements are combined is not important, use foldl' instead.
foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b

-- | Left-associative fold of a structure, lazy in the accumulator. This is
--   rarely what you want, but can work well for structures with efficient
--   right-to-left sequencing and an operator that is lazy in its left
--   argument.
--   
--   In the case of lists, foldl, when applied to a binary operator,
--   a starting value (typically the left-identity of the operator), and a
--   list, reduces the list using the binary operator, from left to right:
--   
--   
--   foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--   
--   
--   Note that to produce the outermost application of the operator the
--   entire input list must be traversed. Like all left-associative folds,
--   foldl will diverge if given an infinite list.
--   
--   If you want an efficient strict left-fold, you probably want to use
--   foldl' instead of foldl. The reason for this is that the
--   latter does not force the inner results (e.g. z `f` x1
--   in the above example) before applying them to the operator (e.g. to
--   (`f` x2)). This results in a thunk chain O(n) elements
--   long, which then must be evaluated from the outside-in.
--   
--   For a general Foldable structure this should be semantically
--   identical to:
--   
--   
--   foldl f z = foldl f z . toList
--   
--   
--   
Examples
--   
--   The first example is a strict fold, which in practice is best
--   performed with foldl'.
--   
--   
--   >>> foldl (+) 42 [1,2,3,4]
--   52
--   
--   
--   Though the result below is lazy, the input is reversed before
--   prepending it to the initial accumulator, so corecursion begins only
--   after traversing the entire input string.
--   
--   
--   >>> foldl (\acc c -> c : acc) "abcd" "efgh"
--   "hgfeabcd"
--   
--   
--   A left fold of a structure that is infinite on the right cannot
--   terminate, even when for any finite input the fold just returns the
--   initial accumulator:
--   
--   
--   >>> foldl (\a _ -> a) 0 $ repeat 1
--   * Hangs forever *
--   
--   
--   WARNING: When it comes to lists, you always want to use either
--   foldl' or foldr instead.
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

-- | Left-associative fold of a structure but with strict application of
--   the operator.
--   
--   This ensures that each step of the fold is forced to Weak Head Normal
--   Form before being applied, avoiding the collection of thunks that
--   would otherwise occur. This is often what you want to strictly reduce
--   a finite structure to a single strict result (e.g. sum).
--   
--   For a general Foldable structure this should be semantically
--   identical to,
--   
--   
--   foldl' f z = foldl' f z . toList
--   
foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

-- | A variant of foldr that has no base case, and thus may only be
--   applied to non-empty structures.
--   
--   This function is non-total and will raise a runtime exception if the
--   structure happens to be empty.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> foldr1 (+) [1..4]
--   10
--   
--   
--   
--   >>> foldr1 (+) []
--   Exception: Prelude.foldr1: empty list
--   
--   
--   
--   >>> foldr1 (+) Nothing
--   *** Exception: foldr1: empty structure
--   
--   
--   
--   >>> foldr1 (-) [1..4]
--   -2
--   
--   
--   
--   >>> foldr1 (&&) [True, False, True, True]
--   False
--   
--   
--   
--   >>> foldr1 (||) [False, False, True, True]
--   True
--   
--   
--   
--   >>> foldr1 (+) [1..]
--   * Hangs forever *
--   
foldr1 :: Foldable t => (a -> a -> a) -> t a -> a

-- | A variant of foldl that has no base case, and thus may only be
--   applied to non-empty structures.
--   
--   This function is non-total and will raise a runtime exception if the
--   structure happens to be empty.
--   
--   
--   foldl1 f = foldl1 f . toList
--   
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> foldl1 (+) [1..4]
--   10
--   
--   
--   
--   >>> foldl1 (+) []
--   *** Exception: Prelude.foldl1: empty list
--   
--   
--   
--   >>> foldl1 (+) Nothing
--   *** Exception: foldl1: empty structure
--   
--   
--   
--   >>> foldl1 (-) [1..4]
--   -8
--   
--   
--   
--   >>> foldl1 (&&) [True, False, True, True]
--   False
--   
--   
--   
--   >>> foldl1 (||) [False, False, True, True]
--   True
--   
--   
--   
--   >>> foldl1 (+) [1..]
--   * Hangs forever *
--   
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a

-- | Does the element occur in the structure?
--   
--   Note: elem is often used in infix form.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> 3 `elem` []
--   False
--   
--   
--   
--   >>> 3 `elem` [1,2]
--   False
--   
--   
--   
--   >>> 3 `elem` [1,2,3,4,5]
--   True
--   
--   
--   For infinite structures, the default implementation of elem
--   terminates if the sought-after value exists at a finite distance from
--   the left side of the structure:
--   
--   
--   >>> 3 `elem` [1..]
--   True
--   
--   
--   
--   >>> 3 `elem` ([4..] ++ [3])
--   * Hangs forever *
--   
elem :: (Foldable t, Eq a) => a -> t a -> Bool
infix 4 `elem`

-- | The largest element of a non-empty structure.
--   
--   This function is non-total and will raise a runtime exception if the
--   structure happens to be empty. A structure that supports random access
--   and maintains its elements in order should provide a specialised
--   implementation to return the maximum in faster than linear time.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> maximum [1..10]
--   10
--   
--   
--   
--   >>> maximum []
--   *** Exception: Prelude.maximum: empty list
--   
--   
--   
--   >>> maximum Nothing
--   *** Exception: maximum: empty structure
--   
--   
--   WARNING: This function is partial for possibly-empty structures like
--   lists.
maximum :: (Foldable t, Ord a) => t a -> a

-- | The least element of a non-empty structure.
--   
--   This function is non-total and will raise a runtime exception if the
--   structure happens to be empty. A structure that supports random access
--   and maintains its elements in order should provide a specialised
--   implementation to return the minimum in faster than linear time.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> minimum [1..10]
--   1
--   
--   
--   
--   >>> minimum []
--   *** Exception: Prelude.minimum: empty list
--   
--   
--   
--   >>> minimum Nothing
--   *** Exception: minimum: empty structure
--   
--   
--   WARNING: This function is partial for possibly-empty structures like
--   lists.
minimum :: (Foldable t, Ord a) => t a -> a

-- | Map each element of a structure to an Applicative action,
--   evaluate these actions from left to right, and ignore the results. For
--   a version that doesn't ignore the results see traverse.
--   
--   traverse_ is just like mapM_, but generalised to
--   Applicative actions.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> traverse_ print ["Hello", "world", "!"]
--   "Hello"
--   "world"
--   "!"
--   
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

-- | Evaluate each action in the structure from left to right, and ignore
--   the results. For a version that doesn't ignore the results see
--   sequenceA.
--   
--   sequenceA_ is just like sequence_, but generalised to
--   Applicative actions.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> sequenceA_ [print "Hello", print "world", print "!"]
--   "Hello"
--   "world"
--   "!"
--   
sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()

-- | for_ is traverse_ with its arguments flipped. For a
--   version that doesn't ignore the results see for. This is
--   forM_ generalised to Applicative actions.
--   
--   for_ is just like forM_, but generalised to
--   Applicative actions.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> for_ [1..4] print
--   1
--   2
--   3
--   4
--   
for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()

-- | The largest element of a non-empty structure with respect to the given
--   comparison function.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> maximumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
--   "Longest"
--   
--   
--   WARNING: This function is partial for possibly-empty structures like
--   lists.
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a

-- | The least element of a non-empty structure with respect to the given
--   comparison function.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> minimumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
--   "!"
--   
--   
--   WARNING: This function is partial for possibly-empty structures like
--   lists.
minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a

-- | Functors representing data structures that can be transformed to
--   structures of the same shape by performing an
--   Applicative (or, therefore, Monad) action on each
--   element from left to right.
--   
--   A more detailed description of what same shape means, the
--   various methods, how traversals are constructed, and example advanced
--   use-cases can be found in the Overview section of
--   Data.Traversable#overview.
--   
--   For the class laws see the Laws section of
--   Data.Traversable#laws.
class (Functor t, Foldable t) => Traversable (t :: Type -> Type)

-- | Map each element of a structure to an action, evaluate these actions
--   from left to right, and collect the results. For a version that
--   ignores the results see traverse_.
--   
--   
Examples
--   
--   Basic usage:
--   
--   In the first two examples we show each evaluated action mapping to the
--   output structure.
--   
--   
--   >>> traverse Just [1,2,3,4]
--   Just [1,2,3,4]
--   
--   
--   
--   >>> traverse id [Right 1, Right 2, Right 3, Right 4]
--   Right [1,2,3,4]
--   
--   
--   In the next examples, we show that Nothing and Left
--   values short circuit the created structure.
--   
--   
--   >>> traverse (const Nothing) [1,2,3,4]
--   Nothing
--   
--   
--   
--   >>> traverse (\x -> if odd x then Just x else Nothing)  [1,2,3,4]
--   Nothing
--   
--   
--   
--   >>> traverse id [Right 1, Right 2, Right 3, Right 4, Left 0]
--   Left 0
--   
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

-- | Evaluate each action in the structure from left to right, and collect
--   the results. For a version that ignores the results see
--   sequenceA_.
--   
--   
Examples
--   
--   Basic usage:
--   
--   For the first two examples we show sequenceA fully evaluating a a
--   structure and collecting the results.
--   
--   
--   >>> sequenceA [Just 1, Just 2, Just 3]
--   Just [1,2,3]
--   
--   
--   
--   >>> sequenceA [Right 1, Right 2, Right 3]
--   Right [1,2,3]
--   
--   
--   The next two example show Nothing and Just will short
--   circuit the resulting structure if present in the input. For more
--   context, check the Traversable instances for Either and
--   Maybe.
--   
--   
--   >>> sequenceA [Just 1, Just 2, Just 3, Nothing]
--   Nothing
--   
--   
--   
--   >>> sequenceA [Right 1, Right 2, Right 3, Left 4]
--   Left 4
--   
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

-- | Map each element of a structure to a monadic action, evaluate these
--   actions from left to right, and collect the results. For a version
--   that ignores the results see mapM_.
--   
--   
Examples
--   
--   mapM is literally a traverse with a type signature
--   restricted to Monad. Its implementation may be more efficient
--   due to additional power of Monad.
mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

-- | Evaluate each monadic action in the structure from left to right, and
--   collect the results. For a version that ignores the results see
--   sequence_.
--   
--   
Examples
--   
--   Basic usage:
--   
--   The first two examples are instances where the input and and output of
--   sequence are isomorphic.
--   
--   
--   >>> sequence $ Right [1,2,3,4]
--   [Right 1,Right 2,Right 3,Right 4]
--   
--   
--   
--   >>> sequence $ [Right 1,Right 2,Right 3,Right 4]
--   Right [1,2,3,4]
--   
--   
--   The following examples demonstrate short circuit behavior for
--   sequence.
--   
--   
--   >>> sequence $ Left [1,2,3,4]
--   Left [1,2,3,4]
--   
--   
--   
--   >>> sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
--   Left 0
--   
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

-- | for is traverse with its arguments flipped. For a
--   version that ignores the results see for_.
for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)

-- | 
--   map = fmap
--   
map :: Functor f => (a -> b) -> f a -> f b

-- | 
--   empty = mempty
--   

-- | Deprecated: Use mempty
empty :: Monoid w => w

-- | 
--   (++) = mappend
--   
(++) :: Monoid w => w -> w -> w
infixr 5 ++

-- | 
--   concat = mconcat
--   
concat :: Monoid w => [w] -> w

-- | 
--   intercalate = mconcat .: intersperse
--   
intercalate :: Monoid w => w -> [w] -> w

-- | Compute the sum of a finite list of numbers.
sum :: (Foldable f, Num a) => f a -> a

-- | Compute the product of a finite list of numbers.
product :: (Foldable f, Num a) => f a -> a

-- | Convert a value to readable Text
tshow :: Show a => a -> Text

-- | Convert a value to readable IsString
--   
--   Since 0.3.12
fromShow :: (Show a, IsString b) => a -> b

-- | Parse Text to a value
read :: Read a => Text -> a

-- | The readIO function is similar to read except that it signals parse
--   failure to the IO monad instead of terminating the program.
readIO :: (MonadIO m, Read a) => Text -> m a

-- | Read a file and return the contents of the file as Text. The entire
--   file is read strictly.
readFile :: MonadIO m => FilePath -> m Text

-- | Write Text to a file. The file is truncated to zero length before
--   writing begins.
writeFile :: MonadIO m => FilePath -> Text -> m ()

-- | Write Text to the end of a file.
appendFile :: MonadIO m => FilePath -> Text -> m ()

-- | O(n) Breaks a Text up into a list of Texts at
--   newline characters '\n' (LF, line feed). The resulting
--   strings do not contain newlines.
--   
--   lines does not treat '\r' (CR, carriage return)
--   as a newline character.
lines :: Text -> [Text]

-- | O(n) Breaks a Text up into a list of words, delimited by
--   Chars representing white space.
words :: Text -> [Text]

-- | O(n) Joins lines, after appending a terminating newline to
--   each.
unlines :: [Text] -> Text

-- | O(n) Joins words using single space characters.
unwords :: [Text] -> Text
textToString :: Text -> String
ltextToString :: LText -> String

-- | This function assumes file paths are encoded in UTF8. If it cannot
--   decode the FilePath, the result is just an approximation.
--   
--   Since 0.3.13

-- | Deprecated: Use Data.Text.pack
fpToText :: FilePath -> Text

-- | Since 0.3.13

-- | Deprecated: Use Data.Text.unpack
fpFromText :: Text -> FilePath

-- | Since 0.3.13

-- | Deprecated: Use id
fpToString :: FilePath -> String

-- | Encode text using UTF-8 encoding.
encodeUtf8 :: Text -> ByteString

-- | Note that this is not the standard
--   Data.Text.Encoding.decodeUtf8. That function will throw
--   impure exceptions on any decoding errors. This function instead uses
--   decodeLenient.
decodeUtf8 :: ByteString -> Text

getLine :: MonadIO m => m Text

getContents :: MonadIO m => m LText

interact :: MonadIO m => (LText -> LText) -> m ()

-- | gcd x y is the non-negative factor of both x
--   and y of which every common factor of x and
--   y is also a factor; for example gcd 4 2 = 2,
--   gcd (-4) 6 = 2, gcd 0 4 = 4.
--   gcd 0 0 = 0. (That is, the common divisor
--   that is "greatest" in the divisibility preordering.)
--   
--   Note: Since for signed fixed-width integer types, abs
--   minBound < 0, the result may be negative if one of the
--   arguments is minBound (and necessarily is if the other
--   is 0 or minBound) for such types.
gcd :: Integral a => a -> a -> a

-- | lcm x y is the smallest positive integer that both
--   x and y divide.
lcm :: Integral a => a -> a -> a

-- | Conversion of values to readable Strings.
--   
--   Derived instances of Show have the following properties, which
--   are compatible with derived instances of Read:
--   
--   
--   
- The result of show is a syntactically correct Haskell
--   expression containing only constants, given the fixity declarations in
--   force at the point where the type is declared. It contains only the
--   constructor names defined in the data type, parentheses, and spaces.
--   When labelled constructor fields are used, braces, commas, field
--   names, and equal signs are also used.
--   
- If the constructor is defined to be an infix operator, then
--   showsPrec will produce infix applications of the
--   constructor.
--   
- the representation will be enclosed in parentheses if the
--   precedence of the top-level constructor in x is less than
--   d (associativity is ignored). Thus, if d is
--   0 then the result is never surrounded in parentheses; if
--   d is 11 it is always surrounded in parentheses,
--   unless it is an atomic expression.
--   
- If the constructor is defined using record syntax, then
--   show will produce the record-syntax form, with the fields given
--   in the same order as the original declaration.
--   
--   
--   For example, given the declarations
--   
--   
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--   
--   
--   the derived instance of Show is equivalent to
--   
--   
--   instance (Show a) => Show (Tree a) where
--   
--          showsPrec d (Leaf m) = showParen (d > app_prec) $
--               showString "Leaf " . showsPrec (app_prec+1) m
--            where app_prec = 10
--   
--          showsPrec d (u :^: v) = showParen (d > up_prec) $
--               showsPrec (up_prec+1) u .
--               showString " :^: "      .
--               showsPrec (up_prec+1) v
--            where up_prec = 5
--   
--   
--   Note that right-associativity of :^: is ignored. For example,
--   
--   
--   
- show (Leaf 1 :^: Leaf 2 :^: Leaf 3) produces the
--   string "Leaf 1 :^: (Leaf 2 :^: Leaf 3)".
--   
class Show a

-- | Convert a value to a readable String.
--   
--   showsPrec should satisfy the law
--   
--   
--   showsPrec d x r ++ s  ==  showsPrec d x (r ++ s)
--   
--   
--   Derived instances of Read and Show satisfy the
--   following:
--   
--   
--   
- (x,"") is an element of (readsPrec d
--   (showsPrec d x "")).
--   
--   
--   That is, readsPrec parses the string produced by
--   showsPrec, and delivers the value that showsPrec started
--   with.
showsPrec :: Show a => Int -> a -> ShowS

-- | A specialised variant of showsPrec, using precedence context
--   zero, and returning an ordinary String.
show :: Show a => a -> String

-- | The method showList is provided to allow the programmer to give
--   a specialised way of showing lists of values. For example, this is
--   used by the predefined Show instance of the Char type,
--   where values of type String should be shown in double quotes,
--   rather than between square brackets.
showList :: Show a => [a] -> ShowS

-- | The shows functions return a function that prepends the
--   output String to an existing String. This allows
--   constant-time concatenation of results using function composition.
type ShowS = String -> String

-- | equivalent to showsPrec with a precedence of 0.
shows :: Show a => a -> ShowS

-- | utility function converting a Char to a show function that
--   simply prepends the character unchanged.
showChar :: Char -> ShowS

-- | utility function converting a String to a show function that
--   simply prepends the string unchanged.
showString :: String -> ShowS

-- | utility function that surrounds the inner show function with
--   parentheses when the Bool parameter is True.
showParen :: Bool -> ShowS -> ShowS

-- | A parser for a type a, represented as a function that takes a
--   String and returns a list of possible parses as
--   (a,String) pairs.
--   
--   Note that this kind of backtracking parser is very inefficient;
--   reading a large structure may be quite slow (cf ReadP).
type ReadS a = String -> [(a, String)]

-- | attempts to parse a value from the front of the string, returning a
--   list of (parsed value, remaining string) pairs. If there is no
--   successful parse, the returned list is empty.
--   
--   Derived instances of Read and Show satisfy the
--   following:
--   
--   
--   
- (x,"") is an element of (readsPrec d
--   (showsPrec d x "")).
--   
--   
--   That is, readsPrec parses the string produced by
--   showsPrec, and delivers the value that showsPrec started
--   with.
readsPrec :: Read a => Int -> ReadS a

-- | The method readList is provided to allow the programmer to give
--   a specialised way of parsing lists of values. For example, this is
--   used by the predefined Read instance of the Char type,
--   where values of type String are expected to use double quotes,
--   rather than square brackets.
readList :: Read a => ReadS [a]

-- | equivalent to readsPrec with a precedence of 0.
reads :: Read a => ReadS a

-- | readParen True p parses what p parses,
--   but surrounded with parentheses.
--   
--   readParen False p parses what p
--   parses, but optionally surrounded with parentheses.
readParen :: Bool -> ReadS a -> ReadS a

-- | The lex function reads a single lexeme from the input,
--   discarding initial white space, and returning the characters that
--   constitute the lexeme. If the input string contains only white space,
--   lex returns a single successful `lexeme' consisting of the
--   empty string. (Thus lex "" = [("","")].) If there is
--   no legal lexeme at the beginning of the input string, lex fails
--   (i.e. returns []).
--   
--   This lexer is not completely faithful to the Haskell lexical syntax in
--   the following respects:
--   
--   
--   
- Qualified names are not handled properly
--   
- Octal and hexadecimal numerics are not recognized as a single
--   token
--   
- Comments are not treated properly
--   
lex :: ReadS String
readMay :: Read a => Text -> Maybe a

getChar :: MonadIO m => m Char

putChar :: MonadIO m => Char -> m ()

-- | The readLn function combines getLine and readIO.
readLn :: (MonadIO m, Read a) => m a
