-- 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
--   <a>https://github.com/snoyberg/basic-prelude#readme</a>
@package basic-prelude
@version 0.7.0

module CorePrelude

-- | <tt><a>($)</a></tt> is the <b>function application</b> operator.
--   
--   Applying <tt><a>($)</a></tt> to a function <tt>f</tt> and an argument
--   <tt>x</tt> gives the same result as applying <tt>f</tt> to <tt>x</tt>
--   directly. The definition is akin to this:
--   
--   <pre>
--   ($) :: (a -&gt; b) -&gt; a -&gt; b
--   ($) f x = f x
--   </pre>
--   
--   This is <tt><a>id</a></tt> specialized from <tt>a -&gt; a</tt> to
--   <tt>(a -&gt; b) -&gt; (a -&gt; b)</tt> which by the associativity of
--   <tt>(-&gt;)</tt> is the same as <tt>(a -&gt; b) -&gt; a -&gt; b</tt>.
--   
--   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 <tt>($)</tt> 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:
--   
--   <pre>
--   expr = min 5 1 + 5
--   expr = ((min 5) 1) + 5
--   </pre>
--   
--   <tt>($)</tt> has precedence 0 (the lowest) and associates to the
--   right, so these are equivalent:
--   
--   <pre>
--   expr = min 5 $ 1 + 5
--   expr = (min 5) (1 + 5)
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   A common use cases of <tt>($)</tt> is to avoid parentheses in complex
--   expressions.
--   
--   For example, instead of using nested parentheses in the following
--   Haskell function:
--   
--   <pre>
--   -- | Sum numbers in a string: strSum "100  5 -7" == 98
--   strSum :: <a>String</a> -&gt; <a>Int</a>
--   strSum s = <tt>sum</tt> (<a>mapMaybe</a> <a>readMaybe</a> (<tt>words</tt> s))
--   </pre>
--   
--   we can deploy the function application operator:
--   
--   <pre>
--   -- | Sum numbers in a string: strSum "100  5 -7" == 98
--   strSum :: <a>String</a> -&gt; <a>Int</a>
--   strSum s = <tt>sum</tt> <a>$</a> <a>mapMaybe</a> <a>readMaybe</a> <a>$</a> <tt>words</tt> s
--   </pre>
--   
--   <tt>($)</tt> 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
--   <tt>5</tt> to a list of functions:
--   
--   <pre>
--   applyFive :: [Int]
--   applyFive = map ($ 5) [(+1), (2^)]
--   &gt;&gt;&gt; [6, 32]
--   </pre>
--   
--   <h4><b>Technical Remark (Representation Polymorphism)</b></h4>
--   
--   <tt>($)</tt> is fully representation-polymorphic. This allows it to
--   also be used with arguments of unlifted and even unboxed kinds, such
--   as unboxed integers:
--   
--   <pre>
--   fastMod :: Int -&gt; Int -&gt; Int
--   fastMod (I# x) (I# m) = I# $ remInt# x m
--   </pre>
($) :: (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

-- | <a>otherwise</a> is defined as the value <a>True</a>. It helps to make
--   guards more readable. eg.
--   
--   <pre>
--   f x | x &lt; 0     = ...
--       | otherwise = ...
--   </pre>
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 <a>maybe</a> function takes a default value, a function, and a
--   <a>Maybe</a> value. If the <a>Maybe</a> value is <a>Nothing</a>, the
--   function returns the default value. Otherwise, it applies the function
--   to the value inside the <a>Just</a> and returns the result.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; maybe False odd (Just 3)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; maybe False odd Nothing
--   False
--   </pre>
--   
--   Read an integer from a string using <a>readMaybe</a>. If we succeed,
--   return twice the integer; that is, apply <tt>(*2)</tt> to it. If
--   instead we fail to parse an integer, return <tt>0</tt> by default:
--   
--   <pre>
--   &gt;&gt;&gt; import GHC.Internal.Text.Read ( readMaybe )
--   
--   &gt;&gt;&gt; maybe 0 (*2) (readMaybe "5")
--   10
--   
--   &gt;&gt;&gt; maybe 0 (*2) (readMaybe "")
--   0
--   </pre>
--   
--   Apply <a>show</a> to a <tt>Maybe Int</tt>. If we have <tt>Just n</tt>,
--   we want to show the underlying <a>Int</a> <tt>n</tt>. But if we have
--   <a>Nothing</a>, we return the empty string instead of (for example)
--   "Nothing":
--   
--   <pre>
--   &gt;&gt;&gt; maybe "" show (Just 5)
--   "5"
--   
--   &gt;&gt;&gt; maybe "" show Nothing
--   ""
--   </pre>
maybe :: b -> (a -> b) -> Maybe a -> b

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

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

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

-- | <a>error</a> 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]

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

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

-- | Convert an uncurried function to a curried function.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; curry fst 1 2
--   1
--   </pre>
curry :: ((a, b) -> c) -> a -> b -> c

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

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

-- | <a>asTypeOf</a> is a type-restricted version of <a>const</a>. 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 <a>error</a>. It is expected that compilers will
--   recognize this and insert error messages which are more appropriate to
--   the context in which <a>undefined</a> appears.
undefined :: HasCallStack => a

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

-- | The <a>Ord</a> class is used for totally ordered datatypes.
--   
--   Instances of <a>Ord</a> can be derived for any user-defined datatype
--   whose constituent types are in <a>Ord</a>. The declared order of the
--   constructors in the data declaration determines the ordering in
--   derived <a>Ord</a> instances. The <a>Ordering</a> datatype allows a
--   single comparison to determine the precise ordering of two objects.
--   
--   <a>Ord</a>, as defined by the Haskell report, implements a total order
--   and has the following properties:
--   
--   <ul>
--   <li><i><b>Comparability</b></i> <tt>x &lt;= y || y &lt;= x</tt> =
--   <a>True</a></li>
--   <li><i><b>Transitivity</b></i> if <tt>x &lt;= y &amp;&amp; y &lt;=
--   z</tt> = <a>True</a>, then <tt>x &lt;= z</tt> = <a>True</a></li>
--   <li><i><b>Reflexivity</b></i> <tt>x &lt;= x</tt> = <a>True</a></li>
--   <li><i><b>Antisymmetry</b></i> if <tt>x &lt;= y &amp;&amp; y &lt;=
--   x</tt> = <a>True</a>, then <tt>x == y</tt> = <a>True</a></li>
--   </ul>
--   
--   The following operator interactions are expected to hold:
--   
--   <ol>
--   <li><tt>x &gt;= y</tt> = <tt>y &lt;= x</tt></li>
--   <li><tt>x &lt; y</tt> = <tt>x &lt;= y &amp;&amp; x /= y</tt></li>
--   <li><tt>x &gt; y</tt> = <tt>y &lt; x</tt></li>
--   <li><tt>x &lt; y</tt> = <tt>compare x y == LT</tt></li>
--   <li><tt>x &gt; y</tt> = <tt>compare x y == GT</tt></li>
--   <li><tt>x == y</tt> = <tt>compare x y == EQ</tt></li>
--   <li><tt>min x y == if x &lt;= y then x else y</tt> = <a>True</a></li>
--   <li><tt>max x y == if x &gt;= y then x else y</tt> = <a>True</a></li>
--   </ol>
--   
--   Note that (7.) and (8.) do <i>not</i> require <a>min</a> and
--   <a>max</a> to return either of their arguments. The result is merely
--   required to <i>equal</i> one of the arguments in terms of <a>(==)</a>.
--   
--   Minimal complete definition: either <a>compare</a> or <a>&lt;=</a>.
--   Using <a>compare</a> 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 <a>Eq</a> class defines equality (<a>==</a>) and inequality
--   (<a>/=</a>). All the basic datatypes exported by the <a>Prelude</a>
--   are instances of <a>Eq</a>, and <a>Eq</a> may be derived for any
--   datatype whose constituents are also instances of <a>Eq</a>.
--   
--   The Haskell Report defines no laws for <a>Eq</a>. However, instances
--   are encouraged to follow these properties:
--   
--   <ul>
--   <li><i><b>Reflexivity</b></i> <tt>x == x</tt> = <a>True</a></li>
--   <li><i><b>Symmetry</b></i> <tt>x == y</tt> = <tt>y == x</tt></li>
--   <li><i><b>Transitivity</b></i> if <tt>x == y &amp;&amp; y == z</tt> =
--   <a>True</a>, then <tt>x == z</tt> = <a>True</a></li>
--   <li><i><b>Extensionality</b></i> if <tt>x == y</tt> = <a>True</a> and
--   <tt>f</tt> is a function whose return type is an instance of
--   <a>Eq</a>, then <tt>f x == f y</tt> = <a>True</a></li>
--   <li><i><b>Negation</b></i> <tt>x /= y</tt> = <tt>not (x ==
--   y)</tt></li>
--   </ul>
class Eq a
(==) :: Eq a => a -> a -> Bool
(/=) :: Eq a => a -> a -> Bool
infix 4 ==
infix 4 /=

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

-- | Class <a>Enum</a> defines operations on sequentially ordered types.
--   
--   The <tt>enumFrom</tt>... methods are used in Haskell's translation of
--   arithmetic sequences.
--   
--   Instances of <a>Enum</a> 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 <a>fromEnum</a> from
--   <tt>0</tt> through <tt>n-1</tt>. See Chapter 10 of the <i>Haskell
--   Report</i> for more details.
--   
--   For any type that is an instance of class <a>Bounded</a> as well as
--   <a>Enum</a>, the following should hold:
--   
--   <ul>
--   <li>The calls <tt><a>succ</a> <a>maxBound</a></tt> and <tt><a>pred</a>
--   <a>minBound</a></tt> should result in a runtime error.</li>
--   <li><a>fromEnum</a> and <a>toEnum</a> should give a runtime error if
--   the result value is not representable in the result type. For example,
--   <tt><a>toEnum</a> 7 :: <a>Bool</a></tt> is an error.</li>
--   <li><a>enumFrom</a> and <a>enumFromThen</a> should be defined with an
--   implicit bound, thus:</li>
--   </ul>
--   
--   <pre>
--   enumFrom     x   = enumFromTo     x maxBound
--   enumFromThen x y = enumFromThenTo x y bound
--     where
--       bound | fromEnum y &gt;= fromEnum x = maxBound
--             | otherwise                = minBound
--   </pre>
class Enum a

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

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

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

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

-- | Used in Haskell's translation of <tt>[n..]</tt> with <tt>[n..] =
--   enumFrom n</tt>, a possible implementation being <tt>enumFrom n = n :
--   enumFrom (succ n)</tt>.
--   
--   <h4><b>Examples</b></h4>
--   
--   <ul>
--   <li><pre>enumFrom 4 :: [Integer] = [4,5,6,7,...]</pre></li>
--   <li><pre>enumFrom 6 :: [Int] = [6,7,8,9,...,maxBound ::
--   Int]</pre></li>
--   </ul>
enumFrom :: Enum a => a -> [a]

-- | Used in Haskell's translation of <tt>[n,n'..]</tt> with <tt>[n,n'..] =
--   enumFromThen n n'</tt>, a possible implementation being
--   <tt>enumFromThen n n' = n : n' : worker (f x) (f x n')</tt>,
--   <tt>worker s v = v : worker s (s v)</tt>, <tt>x = fromEnum n' -
--   fromEnum n</tt> and
--   
--   <pre>
--   f n y
--     | n &gt; 0 = f (n - 1) (succ y)
--     | n &lt; 0 = f (n + 1) (pred y)
--     | otherwise = y
--   
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <ul>
--   <li><pre>enumFromThen 4 6 :: [Integer] = [4,6,8,10...]</pre></li>
--   <li><pre>enumFromThen 6 2 :: [Int] = [6,2,-2,-6,...,minBound ::
--   Int]</pre></li>
--   </ul>
enumFromThen :: Enum a => a -> a -> [a]

-- | Used in Haskell's translation of <tt>[n..m]</tt> with <tt>[n..m] =
--   enumFromTo n m</tt>, a possible implementation being
--   
--   <pre>
--   enumFromTo n m
--      | n &lt;= m = n : enumFromTo (succ n) m
--      | otherwise = []
--   
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <ul>
--   <li><pre>enumFromTo 6 10 :: [Int] = [6,7,8,9,10]</pre></li>
--   <li><pre>enumFromTo 42 1 :: [Integer] = []</pre></li>
--   </ul>
enumFromTo :: Enum a => a -> a -> [a]

-- | Used in Haskell's translation of <tt>[n,n'..m]</tt> with <tt>[n,n'..m]
--   = enumFromThenTo n n' m</tt>, a possible implementation being
--   <tt>enumFromThenTo n n' m = worker (f x) (c x) n m</tt>, <tt>x =
--   fromEnum n' - fromEnum n</tt>, <tt>c x = bool (&gt;=) (<a>(x</a>
--   0)</tt>
--   
--   <pre>
--   f n y
--      | n &gt; 0 = f (n - 1) (succ y)
--      | n &lt; 0 = f (n + 1) (pred y)
--      | otherwise = y
--   
--   </pre>
--   
--   and
--   
--   <pre>
--   worker s c v m
--      | c v m = v : worker s c (s v) m
--      | otherwise = []
--   
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <ul>
--   <li><pre>enumFromThenTo 4 2 -6 :: [Integer] =
--   [4,2,0,-2,-4,-6]</pre></li>
--   <li><pre>enumFromThenTo 6 8 2 :: [Int] = []</pre></li>
--   </ul>
enumFromThenTo :: Enum a => a -> a -> a -> [a]

-- | Conversion of values to readable <a>String</a>s.
--   
--   Derived instances of <a>Show</a> have the following properties, which
--   are compatible with derived instances of <a>Read</a>:
--   
--   <ul>
--   <li>The result of <a>show</a> 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.</li>
--   <li>If the constructor is defined to be an infix operator, then
--   <a>showsPrec</a> will produce infix applications of the
--   constructor.</li>
--   <li>the representation will be enclosed in parentheses if the
--   precedence of the top-level constructor in <tt>x</tt> is less than
--   <tt>d</tt> (associativity is ignored). Thus, if <tt>d</tt> is
--   <tt>0</tt> then the result is never surrounded in parentheses; if
--   <tt>d</tt> is <tt>11</tt> it is always surrounded in parentheses,
--   unless it is an atomic expression.</li>
--   <li>If the constructor is defined using record syntax, then
--   <a>show</a> will produce the record-syntax form, with the fields given
--   in the same order as the original declaration.</li>
--   </ul>
--   
--   For example, given the declarations
--   
--   <pre>
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--   </pre>
--   
--   the derived instance of <a>Show</a> is equivalent to
--   
--   <pre>
--   instance (Show a) =&gt; Show (Tree a) where
--   
--          showsPrec d (Leaf m) = showParen (d &gt; app_prec) $
--               showString "Leaf " . showsPrec (app_prec+1) m
--            where app_prec = 10
--   
--          showsPrec d (u :^: v) = showParen (d &gt; up_prec) $
--               showsPrec (up_prec+1) u .
--               showString " :^: "      .
--               showsPrec (up_prec+1) v
--            where up_prec = 5
--   </pre>
--   
--   Note that right-associativity of <tt>:^:</tt> is ignored. For example,
--   
--   <ul>
--   <li><tt><a>show</a> (Leaf 1 :^: Leaf 2 :^: Leaf 3)</tt> produces the
--   string <tt>"Leaf 1 :^: (Leaf 2 :^: Leaf 3)"</tt>.</li>
--   </ul>
class Show a

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

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

-- | <a>fmap</a> is used to apply a function of type <tt>(a -&gt; b)</tt>
--   to a value of type <tt>f a</tt>, where f is a functor, to produce a
--   value of type <tt>f b</tt>. Note that for any type constructor with
--   more than one parameter (e.g., <tt>Either</tt>), only the last type
--   parameter can be modified with <a>fmap</a> (e.g., <tt>b</tt> in
--   `Either a b`).
--   
--   Some type constructors with two parameters or more have a
--   <tt><a>Bifunctor</a></tt> instance that allows both the last and the
--   penultimate parameters to be mapped over.
--   
--   <h4><b>Examples</b></h4>
--   
--   Convert from a <tt><a>Maybe</a> Int</tt> to a <tt>Maybe String</tt>
--   using <a>show</a>:
--   
--   <pre>
--   &gt;&gt;&gt; fmap show Nothing
--   Nothing
--   
--   &gt;&gt;&gt; fmap show (Just 3)
--   Just "3"
--   </pre>
--   
--   Convert from an <tt><a>Either</a> Int Int</tt> to an <tt>Either Int
--   String</tt> using <a>show</a>:
--   
--   <pre>
--   &gt;&gt;&gt; fmap show (Left 17)
--   Left 17
--   
--   &gt;&gt;&gt; fmap show (Right 17)
--   Right "17"
--   </pre>
--   
--   Double each element of a list:
--   
--   <pre>
--   &gt;&gt;&gt; fmap (*2) [1,2,3]
--   [2,4,6]
--   </pre>
--   
--   Apply <a>even</a> to the second element of a pair:
--   
--   <pre>
--   &gt;&gt;&gt; fmap even (2,2)
--   (2,True)
--   </pre>
--   
--   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 <tt>(a,b,c)</tt> can also be written <tt>(,,) a b c</tt> and
--   its <tt>Functor</tt> instance is defined for <tt>Functor ((,,) a
--   b)</tt> (i.e., only the third parameter is free to be mapped over with
--   <tt>fmap</tt>).
--   
--   It explains why <tt>fmap</tt> can be used with tuples containing
--   values of different types as in the following example:
--   
--   <pre>
--   &gt;&gt;&gt; fmap even ("hello", 1.0, 4)
--   ("hello",1.0,True)
--   </pre>
fmap :: Functor f => (a -> b) -> f a -> f b

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

-- | The <a>Monad</a> class defines the basic operations over a
--   <i>monad</i>, a concept from a branch of mathematics known as
--   <i>category theory</i>. From the perspective of a Haskell programmer,
--   however, it is best to think of a monad as an <i>abstract datatype</i>
--   of actions. Haskell's <tt>do</tt> expressions provide a convenient
--   syntax for writing monadic expressions.
--   
--   Instances of <a>Monad</a> should satisfy the following:
--   
--   <ul>
--   <li><i>Left identity</i> <tt><a>return</a> a <a>&gt;&gt;=</a> k = k
--   a</tt></li>
--   <li><i>Right identity</i> <tt>m <a>&gt;&gt;=</a> <a>return</a> =
--   m</tt></li>
--   <li><i>Associativity</i> <tt>m <a>&gt;&gt;=</a> (\x -&gt; k x
--   <a>&gt;&gt;=</a> h) = (m <a>&gt;&gt;=</a> k) <a>&gt;&gt;=</a>
--   h</tt></li>
--   </ul>
--   
--   Furthermore, the <a>Monad</a> and <a>Applicative</a> operations should
--   relate as follows:
--   
--   <ul>
--   <li><pre><a>pure</a> = <a>return</a></pre></li>
--   <li><pre>m1 <a>&lt;*&gt;</a> m2 = m1 <a>&gt;&gt;=</a> (\x1 -&gt; m2
--   <a>&gt;&gt;=</a> (\x2 -&gt; <a>return</a> (x1 x2)))</pre></li>
--   </ul>
--   
--   The above laws imply:
--   
--   <ul>
--   <li><pre><a>fmap</a> f xs = xs <a>&gt;&gt;=</a> <a>return</a> .
--   f</pre></li>
--   <li><pre>(<a>&gt;&gt;</a>) = (<a>*&gt;</a>)</pre></li>
--   </ul>
--   
--   and that <a>pure</a> and (<a>&lt;*&gt;</a>) satisfy the applicative
--   functor laws.
--   
--   The instances of <a>Monad</a> for <a>List</a>, <a>Maybe</a> and
--   <a>IO</a> defined in the <a>Prelude</a> 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.
--   
--   '<tt>as <a>&gt;&gt;=</a> bs</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do a &lt;- as
--      bs a
--   </pre>
--   
--   An alternative name for this function is 'bind', but some people may
--   refer to it as 'flatMap', which results from it being equivialent to
--   
--   <pre>
--   \x f -&gt; <a>join</a> (<a>fmap</a> f x) :: Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b
--   </pre>
--   
--   which can be seen as mapping a value with <tt>Monad m =&gt; m a -&gt;
--   m (m b)</tt> and then 'flattening' <tt>m (m b)</tt> to <tt>m b</tt>
--   using <a>join</a>.
(>>=) :: 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.
--   
--   '<tt>as <a>&gt;&gt;</a> bs</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do as
--      bs
--   </pre>
--   
--   or in terms of <tt><a>(&gt;&gt;=)</a></tt> as
--   
--   <pre>
--   as &gt;&gt;= const bs
--   </pre>
(>>) :: Monad m => m a -> m b -> m b

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

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

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

-- | Basic numeric class.
--   
--   The Haskell Report defines no laws for <a>Num</a>. However,
--   <tt>(<a>+</a>)</tt> and <tt>(<a>*</a>)</tt> are customarily expected
--   to define a ring and have the following properties:
--   
--   <ul>
--   <li><i><b>Associativity of <tt>(<a>+</a>)</tt></b></i> <tt>(x + y) +
--   z</tt> = <tt>x + (y + z)</tt></li>
--   <li><i><b>Commutativity of <tt>(<a>+</a>)</tt></b></i> <tt>x + y</tt>
--   = <tt>y + x</tt></li>
--   <li><i><b><tt><a>fromInteger</a> 0</tt> is the additive
--   identity</b></i> <tt>x + fromInteger 0</tt> = <tt>x</tt></li>
--   <li><i><b><a>negate</a> gives the additive inverse</b></i> <tt>x +
--   negate x</tt> = <tt>fromInteger 0</tt></li>
--   <li><i><b>Associativity of <tt>(<a>*</a>)</tt></b></i> <tt>(x * y) *
--   z</tt> = <tt>x * (y * z)</tt></li>
--   <li><i><b><tt><a>fromInteger</a> 1</tt> is the multiplicative
--   identity</b></i> <tt>x * fromInteger 1</tt> = <tt>x</tt> and
--   <tt>fromInteger 1 * x</tt> = <tt>x</tt></li>
--   <li><i><b>Distributivity of <tt>(<a>*</a>)</tt> with respect to
--   <tt>(<a>+</a>)</tt></b></i> <tt>a * (b + c)</tt> = <tt>(a * b) + (a *
--   c)</tt> and <tt>(b + c) * a</tt> = <tt>(b * a) + (c * a)</tt></li>
--   <li><i><b>Coherence with <tt>toInteger</tt></b></i> if the type also
--   implements <a>Integral</a>, then <a>fromInteger</a> is a left inverse
--   for <a>toInteger</a>, i.e. <tt>fromInteger (toInteger i) ==
--   i</tt></li>
--   </ul>
--   
--   Note that it <i>isn't</i> customarily expected that a type instance of
--   both <a>Num</a> and <a>Ord</a> implement an ordered ring. Indeed, in
--   <tt>base</tt> only <a>Integer</a> and <a>Rational</a> 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 <a>abs</a> and <a>signum</a> should
--   satisfy the law:
--   
--   <pre>
--   abs x * signum x == x
--   </pre>
--   
--   For real numbers, the <a>signum</a> is either <tt>-1</tt> (negative),
--   <tt>0</tt> (zero) or <tt>1</tt> (positive).
signum :: Num a => a -> a

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

-- | Real numbers.
--   
--   The Haskell report defines no laws for <a>Real</a>, however
--   <a>Real</a> instances are customarily expected to adhere to the
--   following law:
--   
--   <ul>
--   <li><i><b>Coherence with <a>fromRational</a></b></i> if the type also
--   implements <a>Fractional</a>, then <a>fromRational</a> is a left
--   inverse for <a>toRational</a>, i.e. <tt>fromRational (toRational i) =
--   i</tt></li>
--   </ul>
--   
--   The law does not hold for <a>Float</a>, <a>Double</a>, <a>CFloat</a>,
--   <a>CDouble</a>, etc., because these types contain non-finite values,
--   which cannot be roundtripped through <a>Rational</a>.
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 <a>Integral</a>. However,
--   <a>Integral</a> instances are customarily expected to define a
--   Euclidean domain and have the following properties for the
--   <a>div</a>/<a>mod</a> and <a>quot</a>/<a>rem</a> pairs, given suitable
--   Euclidean functions <tt>f</tt> and <tt>g</tt>:
--   
--   <ul>
--   <li><tt>x</tt> = <tt>y * quot x y + rem x y</tt> with <tt>rem x y</tt>
--   = <tt>fromInteger 0</tt> or <tt>g (rem x y)</tt> &lt; <tt>g
--   y</tt></li>
--   <li><tt>x</tt> = <tt>y * div x y + mod x y</tt> with <tt>mod x y</tt>
--   = <tt>fromInteger 0</tt> or <tt>f (mod x y)</tt> &lt; <tt>f
--   y</tt></li>
--   </ul>
--   
--   An example of a suitable Euclidean function, for <a>Integer</a>'s
--   instance, is <a>abs</a>.
--   
--   In addition, <tt>toInteger</tt> should be total, and
--   <a>fromInteger</a> should be a left inverse for it, i.e.
--   <tt>fromInteger (toInteger i) = i</tt>.
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 <tt>base</tt>.
quot :: Integral a => a -> a -> a

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

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

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

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

-- | Conversion to <a>Integer</a>.
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 <a>Fractional</a>. However,
--   <tt>(<a>+</a>)</tt> and <tt>(<a>*</a>)</tt> are customarily expected
--   to define a division ring and have the following properties:
--   
--   <ul>
--   <li><i><b><a>recip</a> gives the multiplicative inverse</b></i> <tt>x
--   * recip x</tt> = <tt>recip x * x</tt> = <tt>fromInteger 1</tt></li>
--   <li><i><b>Totality of <a>toRational</a></b></i> <a>toRational</a> is
--   total</li>
--   <li><i><b>Coherence with <a>toRational</a></b></i> if the type also
--   implements <a>Real</a>, then <a>fromRational</a> is a left inverse for
--   <a>toRational</a>, i.e. <tt>fromRational (toRational i) = i</tt></li>
--   </ul>
--   
--   Note that it <i>isn't</i> customarily expected that a type instance of
--   <a>Fractional</a> implement a field. However, all instances in
--   <tt>base</tt> do.
class Num a => Fractional a

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

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

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

-- | Trigonometric and hyperbolic functions and related functions.
--   
--   The Haskell Report defines no laws for <a>Floating</a>. However,
--   <tt>(<a>+</a>)</tt>, <tt>(<a>*</a>)</tt> and <a>exp</a> are
--   customarily expected to define an exponential field and have the
--   following properties:
--   
--   <ul>
--   <li><tt>exp (a + b)</tt> = <tt>exp a * exp b</tt></li>
--   <li><tt>exp (fromInteger 0)</tt> = <tt>fromInteger 1</tt></li>
--   </ul>
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 <a>properFraction</a> takes a real fractional number
--   <tt>x</tt> and returns a pair <tt>(n,f)</tt> such that <tt>x =
--   n+f</tt>, and:
--   
--   <ul>
--   <li><tt>n</tt> is an integral number with the same sign as <tt>x</tt>;
--   and</li>
--   <li><tt>f</tt> is a fraction with the same type and sign as
--   <tt>x</tt>, and with absolute value less than <tt>1</tt>.</li>
--   </ul>
--   
--   The default definitions of the <a>ceiling</a>, <a>floor</a>,
--   <a>truncate</a> and <a>round</a> functions are in terms of
--   <a>properFraction</a>.
properFraction :: (RealFrac a, Integral b) => a -> (b, a)

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

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

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

-- | <tt><a>floor</a> x</tt> returns the greatest integer not greater than
--   <tt>x</tt>
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
--   <tt>2</tt>)
floatRadix :: RealFloat a => a -> Integer

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

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

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

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

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

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

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

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

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

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

-- | The <a>Maybe</a> type encapsulates an optional value. A value of type
--   <tt><a>Maybe</a> a</tt> either contains a value of type <tt>a</tt>
--   (represented as <tt><a>Just</a> a</tt>), or it is empty (represented
--   as <a>Nothing</a>). Using <a>Maybe</a> is a good way to deal with
--   errors or exceptional cases without resorting to drastic measures such
--   as <a>error</a>.
--   
--   The <a>Maybe</a> type is also a monad. It is a simple kind of error
--   monad, where all errors are represented by <a>Nothing</a>. A richer
--   error monad can be built using the <a>Either</a> 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 <a>Char</a> represents Unicode codespace and its
--   elements are code points as in definitions <a>D9 and D10 of the
--   Unicode Standard</a>.
--   
--   Character literals in Haskell are single-quoted: <tt>'Q'</tt>,
--   <tt>'Я'</tt> or <tt>'Ω'</tt>. To represent a single quote itself use
--   <tt>'\''</tt>, and to represent a backslash use <tt>'\\'</tt>. The
--   full grammar can be found in the section 2.6 of the <a>Haskell 2010
--   Language Report</a>.
--   
--   To specify a character by its code point one can use decimal,
--   hexadecimal or octal notation: <tt>'\65'</tt>, <tt>'\x41'</tt> and
--   <tt>'\o101'</tt> are all alternative forms of <tt>'A'</tt>. The
--   largest code point is <tt>'\x10ffff'</tt>.
--   
--   There is a special escape syntax for ASCII control characters:
--   
--   TODO: table
--   
--   <a>Data.Char</a> provides utilities to work with <a>Char</a>.
data Char

-- | A value of type <tt><a>IO</a> a</tt> is a computation which, when
--   performed, does some I/O before returning a value of type <tt>a</tt>.
--   
--   There is really only one way to "perform" an I/O action: bind it to
--   <tt>Main.main</tt> 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 <a>IO</a> monad and
--   called at some point, directly or indirectly, from <tt>Main.main</tt>.
--   
--   <a>IO</a> is a monad, so <a>IO</a> actions can be combined using
--   either the do-notation or the <a>&gt;&gt;</a> and <a>&gt;&gt;=</a>
--   operations from the <a>Monad</a> class.
data IO a

-- | The <a>Either</a> type represents values with two possibilities: a
--   value of type <tt><a>Either</a> a b</tt> is either <tt><a>Left</a>
--   a</tt> or <tt><a>Right</a> b</tt>.
--   
--   The <a>Either</a> type is sometimes used to represent a value which is
--   either correct or an error; by convention, the <a>Left</a> constructor
--   is used to hold an error value and the <a>Right</a> constructor is
--   used to hold a correct value (mnemonic: "right" also means "correct").
--   
--   <h4><b>Examples</b></h4>
--   
--   The type <tt><a>Either</a> <a>String</a> <a>Int</a></tt> is the type
--   of values which can be either a <a>String</a> or an <a>Int</a>. The
--   <a>Left</a> constructor can be used only on <a>String</a>s, and the
--   <a>Right</a> constructor can be used only on <a>Int</a>s:
--   
--   <pre>
--   &gt;&gt;&gt; let s = Left "foo" :: Either String Int
--   
--   &gt;&gt;&gt; s
--   Left "foo"
--   
--   &gt;&gt;&gt; let n = Right 3 :: Either String Int
--   
--   &gt;&gt;&gt; n
--   Right 3
--   
--   &gt;&gt;&gt; :type s
--   s :: Either String Int
--   
--   &gt;&gt;&gt; :type n
--   n :: Either String Int
--   </pre>
--   
--   The <a>fmap</a> from our <a>Functor</a> instance will ignore
--   <a>Left</a> values, but will apply the supplied function to values
--   contained in a <a>Right</a>:
--   
--   <pre>
--   &gt;&gt;&gt; let s = Left "foo" :: Either String Int
--   
--   &gt;&gt;&gt; let n = Right 3 :: Either String Int
--   
--   &gt;&gt;&gt; fmap (*2) s
--   Left "foo"
--   
--   &gt;&gt;&gt; fmap (*2) n
--   Right 6
--   </pre>
--   
--   The <a>Monad</a> instance for <a>Either</a> 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 <a>Int</a> from a <a>Char</a>, or fail.
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Char ( digitToInt, isDigit )
--   
--   &gt;&gt;&gt; :{
--       let parseEither :: Char -&gt; Either String Int
--           parseEither c
--             | isDigit c = Right (digitToInt c)
--             | otherwise = Left "parse error"
--   
--   &gt;&gt;&gt; :}
--   </pre>
--   
--   The following should work, since both <tt>'1'</tt> and <tt>'2'</tt>
--   can be parsed as <a>Int</a>s.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x &lt;- parseEither '1'
--             y &lt;- parseEither '2'
--             return (x + y)
--   
--   &gt;&gt;&gt; :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; parseMultiple
--   Right 3
--   </pre>
--   
--   But the following should fail overall, since the first operation where
--   we attempt to parse <tt>'m'</tt> as an <a>Int</a> will fail:
--   
--   <pre>
--   &gt;&gt;&gt; :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x &lt;- parseEither 'm'
--             y &lt;- parseEither '2'
--             return (x + y)
--   
--   &gt;&gt;&gt; :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; parseMultiple
--   Left "parse error"
--   </pre>
data Either a b
Left :: a -> Either a b
Right :: b -> Either a b

-- | A space-efficient representation of a <a>Word8</a> vector, supporting
--   many efficient operations.
--   
--   A <a>ByteString</a> contains 8-bit bytes, or by using the operations
--   from <a>Data.ByteString.Char8</a> 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 <tt>k</tt> to values <tt>a</tt>.
--   
--   The <a>Semigroup</a> operation for <a>Map</a> is <a>union</a>, which
--   prefers values from the left operand. If <tt>m1</tt> maps a key
--   <tt>k</tt> to a value <tt>a1</tt>, and <tt>m2</tt> maps the same key
--   to a different value <tt>a2</tt>, then their union <tt>m1 &lt;&gt;
--   m2</tt> maps <tt>k</tt> to <tt>a1</tt>.
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 <tt>a</tt>.
data IntMap a

-- | A set of values <tt>a</tt>.
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 <tt><a>Ptr</a>
--   a</tt>, for some <tt>a</tt> which is an instance of class
--   <a>Storable</a>. The type argument to <a>Ptr</a> 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 <a>Storable</a> facilitates this manipulation
--   on all types for which it is instantiated, which are the standard
--   basic types of Haskell, the fixed size <tt>Int</tt> types
--   (<a>Int8</a>, <a>Int16</a>, <a>Int32</a>, <a>Int64</a>), the fixed
--   size <tt>Word</tt> types (<a>Word8</a>, <a>Word16</a>, <a>Word32</a>,
--   <a>Word64</a>), <a>StablePtr</a>, all types from
--   <a>Foreign.C.Types</a>, as well as <a>Ptr</a>.
class Storable a

-- | The class of types that can be converted to a hash value.
--   
--   Minimal implementation: <a>hashWithSalt</a>.
--   
--   <a>Hashable</a> is intended exclusively for use in in-memory data
--   structures. . <a>Hashable</a> does <i>not</i> 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,
--   <a>Hashable</a> is not recommended for use other than in-memory
--   datastructures. Specifically, <a>Hashable</a> 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 <a>Hashable</a> instance in <tt>time</tt>
--   package, check <a>time-compat</a>
class Eq a => Hashable a

-- | A <a>Word</a> is an unsigned integral type, with the same size as
--   <a>Int</a>.
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 <tt>[-2^29 ..
--   2^29-1]</tt>. The exact range for a given implementation can be
--   determined by using <a>minBound</a> and <a>maxBound</a> from the
--   <a>Bounded</a> 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 <a>Int</a>, the <a>Integer</a> 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 <a>Int</a>), the <a>IS</a>
--   constructor is used. Otherwise <a>IP</a> and <a>IN</a> constructors
--   are used to store a <a>BigNat</a> representing the positive or the
--   negative value magnitude, respectively.
--   
--   Invariant: <a>IP</a> and <a>IN</a> are used iff the value does not fit
--   in <a>IS</a>.
data Integer

-- | Arbitrary-precision rational numbers, represented as a ratio of two
--   <a>Integer</a> values. A rational number may be constructed using the
--   <a>%</a> 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 <tt><a>flip</a> (<a>-</a>)</tt>.
--   
--   Because <tt>-</tt> is treated specially in the Haskell grammar,
--   <tt>(-</tt> <i>e</i><tt>)</tt> is not a section, but an application of
--   prefix negation. However, <tt>(<a>subtract</a></tt>
--   <i>exp</i><tt>)</tt> is equivalent to the disallowed section.
subtract :: Num a => a -> a -> a

-- | General coercion from <a>Integral</a> 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 <a>Fractional</a> types.
--   
--   WARNING: This function goes through the <a>Rational</a> type, which
--   does not have values for <tt>NaN</tt> for example. This means it does
--   not round-trip.
--   
--   For <a>Double</a> it also behaves differently with or without -O0:
--   
--   <pre>
--   Prelude&gt; realToFrac nan -- With -O0
--   -Infinity
--   Prelude&gt; realToFrac nan
--   NaN
--   </pre>
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:
--   
--   <ul>
--   <li><i>Right identity</i> <tt>x <a>&lt;&gt;</a> <a>mempty</a> =
--   x</tt></li>
--   <li><i>Left identity</i> <tt><a>mempty</a> <a>&lt;&gt;</a> x =
--   x</tt></li>
--   <li><i>Associativity</i> <tt>x <a>&lt;&gt;</a> (y <a>&lt;&gt;</a> z) =
--   (x <a>&lt;&gt;</a> y) <a>&lt;&gt;</a> z</tt> (<a>Semigroup</a>
--   law)</li>
--   <li><i>Concatenation</i> <tt><a>mconcat</a> = <a>foldr</a>
--   (<a>&lt;&gt;</a>) <a>mempty</a></tt></li>
--   </ul>
--   
--   You can alternatively define <a>mconcat</a> instead of <a>mempty</a>,
--   in which case the laws are:
--   
--   <ul>
--   <li><i>Unit</i> <tt><a>mconcat</a> (<a>pure</a> x) = x</tt></li>
--   <li><i>Multiplication</i> <tt><a>mconcat</a> (<a>join</a> xss) =
--   <a>mconcat</a> (<a>fmap</a> <a>mconcat</a> xss)</tt></li>
--   <li><i>Subclass</i> <tt><a>mconcat</a> (<tt>toList</tt> xs) =
--   <a>sconcat</a> xs</tt></li>
--   </ul>
--   
--   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
--   <tt>newtype</tt>s and make those instances of <a>Monoid</a>, e.g.
--   <a>Sum</a> and <a>Product</a>.
--   
--   <b>NOTE</b>: <a>Semigroup</a> is a superclass of <a>Monoid</a> since
--   <i>base-4.11.0.0</i>.
class Semigroup a => Monoid a

-- | Identity of <a>mappend</a>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; "Hello world" &lt;&gt; mempty
--   "Hello world"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; mempty &lt;&gt; [1, 2, 3]
--   [1,2,3]
--   </pre>
mempty :: Monoid a => a

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

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

-- | An associative operation.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; [1,2,3] &lt;&gt; [4,5,6]
--   [1,2,3,4,5,6]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Just [1, 2, 3] &lt;&gt; Just [4, 5, 6]
--   Just [1,2,3,4,5,6]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putStr "Hello, " &lt;&gt; putStrLn "World!"
--   Hello, World!
--   </pre>
(<>) :: 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
--   <tt>DeriveFoldable</tt> extension. For example, a derived instance for
--   a binary tree might be:
--   
--   <pre>
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   </pre>
--   
--   A more detailed description can be found in the <b>Overview</b>
--   section of <a>Data.Foldable#overview</a>.
--   
--   For the class laws see the <b>Laws</b> section of
--   <a>Data.Foldable#laws</a>.
class Foldable (t :: Type -> Type)

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

-- | Functors representing data structures that can be transformed to
--   structures of the <i>same shape</i> by performing an
--   <a>Applicative</a> (or, therefore, <a>Monad</a>) action on each
--   element from left to right.
--   
--   A more detailed description of what <i>same shape</i> means, the
--   various methods, how traversals are constructed, and example advanced
--   use-cases can be found in the <b>Overview</b> section of
--   <a>Data.Traversable#overview</a>.
--   
--   For the class laws see the <b>Laws</b> section of
--   <a>Data.Traversable#laws</a>.
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 <a>first</a>.
--   
--   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 <a>Bool</a> type. <tt><a>bool</a> f t p</tt>
--   evaluates to <tt>f</tt> when <tt>p</tt> is <a>False</a>, and evaluates
--   to <tt>t</tt> when <tt>p</tt> is <a>True</a>.
--   
--   This is equivalent to <tt>if p then t else f</tt>; that is, one can
--   think of it as an if-then-else construct with its arguments reordered.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; bool "foo" "bar" True
--   "bar"
--   
--   &gt;&gt;&gt; bool "foo" "bar" False
--   "foo"
--   </pre>
--   
--   Confirm that <tt><a>bool</a> f t p</tt> and <tt>if p then t else
--   f</tt> are equivalent:
--   
--   <pre>
--   &gt;&gt;&gt; let p = True; f = "bar"; t = "foo"
--   
--   &gt;&gt;&gt; bool f t p == if p then t else f
--   True
--   
--   &gt;&gt;&gt; let p = False
--   
--   &gt;&gt;&gt; bool f t p == if p then t else f
--   True
--   </pre>
bool :: a -> a -> Bool -> a

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

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

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

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

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

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

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

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

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

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

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

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

-- | The <a>Down</a> type allows you to reverse sort order conveniently. A
--   value of type <tt><a>Down</a> a</tt> contains a value of type
--   <tt>a</tt> (represented as <tt><a>Down</a> a</tt>).
--   
--   If <tt>a</tt> has an <tt><a>Ord</a></tt> 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: <tt>then sortWith by
--   <a>Down</a> x</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; compare True False
--   GT
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; compare (Down True) (Down False)
--   LT
--   </pre>
--   
--   If <tt>a</tt> has a <tt><a>Bounded</a></tt> instance then the wrapped
--   instance also respects the reversed ordering by exchanging the values
--   of <tt><a>minBound</a></tt> and <tt><a>maxBound</a></tt>.
--   
--   <pre>
--   &gt;&gt;&gt; minBound :: Int
--   -9223372036854775808
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; minBound :: Down Int
--   Down 9223372036854775807
--   </pre>
--   
--   All other instances of <tt><a>Down</a> a</tt> behave as they do for
--   <tt>a</tt>.
newtype Down a
Down :: a -> Down a

[getDown] :: Down a -> a

-- | A functor with application, providing operations to
--   
--   <ul>
--   <li>embed pure expressions (<a>pure</a>), and</li>
--   <li>sequence computations and combine their results (<a>&lt;*&gt;</a>
--   and <a>liftA2</a>).</li>
--   </ul>
--   
--   A minimal complete definition must include implementations of
--   <a>pure</a> and of either <a>&lt;*&gt;</a> or <a>liftA2</a>. If it
--   defines both, then they must behave the same as their default
--   definitions:
--   
--   <pre>
--   (<a>&lt;*&gt;</a>) = <a>liftA2</a> <a>id</a>
--   </pre>
--   
--   <pre>
--   <a>liftA2</a> f x y = f <a>&lt;$&gt;</a> x <a>&lt;*&gt;</a> y
--   </pre>
--   
--   Further, any definition must satisfy the following:
--   
--   <ul>
--   <li><i>Identity</i> <pre><a>pure</a> <a>id</a> <a>&lt;*&gt;</a> v =
--   v</pre></li>
--   <li><i>Composition</i> <pre><a>pure</a> (.) <a>&lt;*&gt;</a> u
--   <a>&lt;*&gt;</a> v <a>&lt;*&gt;</a> w = u <a>&lt;*&gt;</a> (v
--   <a>&lt;*&gt;</a> w)</pre></li>
--   <li><i>Homomorphism</i> <pre><a>pure</a> f <a>&lt;*&gt;</a>
--   <a>pure</a> x = <a>pure</a> (f x)</pre></li>
--   <li><i>Interchange</i> <pre>u <a>&lt;*&gt;</a> <a>pure</a> y =
--   <a>pure</a> (<a>$</a> y) <a>&lt;*&gt;</a> u</pre></li>
--   </ul>
--   
--   The other methods have the following default definitions, which may be
--   overridden with equivalent specialized implementations:
--   
--   <ul>
--   <li><pre>u <a>*&gt;</a> v = (<a>id</a> <a>&lt;$</a> u)
--   <a>&lt;*&gt;</a> v</pre></li>
--   <li><pre>u <a>&lt;*</a> v = <a>liftA2</a> <a>const</a> u v</pre></li>
--   </ul>
--   
--   As a consequence of these laws, the <a>Functor</a> instance for
--   <tt>f</tt> will satisfy
--   
--   <ul>
--   <li><pre><a>fmap</a> f x = <a>pure</a> f <a>&lt;*&gt;</a> x</pre></li>
--   </ul>
--   
--   It may be useful to note that supposing
--   
--   <pre>
--   forall x y. p (q x y) = f x . g y
--   </pre>
--   
--   it follows from the above that
--   
--   <pre>
--   <a>liftA2</a> p (<a>liftA2</a> q u v) = <a>liftA2</a> f u . <a>liftA2</a> g v
--   </pre>
--   
--   If <tt>f</tt> is also a <a>Monad</a>, it should satisfy
--   
--   <ul>
--   <li><pre><a>pure</a> = <a>return</a></pre></li>
--   <li><pre>m1 <a>&lt;*&gt;</a> m2 = m1 <a>&gt;&gt;=</a> (\x1 -&gt; m2
--   <a>&gt;&gt;=</a> (\x2 -&gt; <a>return</a> (x1 x2)))</pre></li>
--   <li><pre>(<a>*&gt;</a>) = (<a>&gt;&gt;</a>)</pre></li>
--   </ul>
--   
--   (which implies that <a>pure</a> and <a>&lt;*&gt;</a> satisfy the
--   applicative functor laws).
class Functor f => Applicative (f :: Type -> Type)

-- | Lift a value into the Structure.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; pure 1 :: Maybe Int
--   Just 1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; pure 'z' :: [Char]
--   "z"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; pure (pure ":D") :: Maybe [String]
--   Just [":D"]
--   </pre>
pure :: Applicative f => a -> f a

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

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

-- | Sequence actions, discarding the value of the first argument.
--   
--   <h4><b>Examples</b></h4>
--   
--   If used in conjunction with the Applicative instance for <a>Maybe</a>,
--   you can chain Maybe computations, with a possible "early return" in
--   case of <a>Nothing</a>.
--   
--   <pre>
--   &gt;&gt;&gt; Just 2 *&gt; Just 3
--   Just 3
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Nothing *&gt; Just 3
--   Nothing
--   </pre>
--   
--   Of course a more interesting use case would be to have effectful
--   computations instead of just returning pure values.
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Char
--   
--   &gt;&gt;&gt; import GHC.Internal.Text.ParserCombinators.ReadP
--   
--   &gt;&gt;&gt; let p = string "my name is " *&gt; munch1 isAlpha &lt;* eof
--   
--   &gt;&gt;&gt; readP_to_S p "my name is Simon"
--   [("Simon","")]
--   </pre>
(*>) :: 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 <a>fmap</a>.
--   
--   The name of this operator is an allusion to <a>$</a>. Note the
--   similarities between their types:
--   
--   <pre>
--    ($)  ::              (a -&gt; b) -&gt;   a -&gt;   b
--   (&lt;$&gt;) :: Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b
--   </pre>
--   
--   Whereas <a>$</a> is function application, <a>&lt;$&gt;</a> is function
--   application lifted over a <a>Functor</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   Convert from a <tt><a>Maybe</a> <a>Int</a></tt> to a <tt><a>Maybe</a>
--   <a>String</a></tt> using <a>show</a>:
--   
--   <pre>
--   &gt;&gt;&gt; show &lt;$&gt; Nothing
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; show &lt;$&gt; Just 3
--   Just "3"
--   </pre>
--   
--   Convert from an <tt><a>Either</a> <a>Int</a> <a>Int</a></tt> to an
--   <tt><a>Either</a> <a>Int</a></tt> <a>String</a> using <a>show</a>:
--   
--   <pre>
--   &gt;&gt;&gt; show &lt;$&gt; Left 17
--   Left 17
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; show &lt;$&gt; Right 17
--   Right "17"
--   </pre>
--   
--   Double each element of a list:
--   
--   <pre>
--   &gt;&gt;&gt; (*2) &lt;$&gt; [1,2,3]
--   [2,4,6]
--   </pre>
--   
--   Apply <a>even</a> to the second element of a pair:
--   
--   <pre>
--   &gt;&gt;&gt; even &lt;$&gt; (2,2)
--   (2,True)
--   </pre>
(<$>) :: 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 <a>Kleisli</a> arrows.
--   
--   '<tt>(bs <a>&gt;=&gt;</a> cs) a</tt>' can be understood as the
--   <tt>do</tt> expression
--   
--   <pre>
--   do b &lt;- bs a
--      cs b
--   </pre>
--   
--   or in terms of <tt><a>(&gt;&gt;=)</a></tt> as
--   
--   <pre>
--   bs a &gt;&gt;= cs
--   </pre>
(>=>) :: 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 <a>IO</a> computations may be embedded. Any monad
--   built by applying a sequence of monad transformers to the <a>IO</a>
--   monad will be an instance of this class.
--   
--   Instances should satisfy the following laws, which state that
--   <a>liftIO</a> is a transformer of monads:
--   
--   <ul>
--   <li><pre><a>liftIO</a> . <a>return</a> = <a>return</a></pre></li>
--   <li><pre><a>liftIO</a> (m &gt;&gt;= f) = <a>liftIO</a> m &gt;&gt;=
--   (<a>liftIO</a> . f)</pre></li>
--   </ul>
class Monad m => MonadIO (m :: Type -> Type)

-- | Lift a computation from the <a>IO</a> monad. This allows us to run IO
--   computations in any monadic stack, so long as it supports these kinds
--   of operations (i.e. <a>IO</a> is the base monad for the stack).
--   
--   <h3><b>Example</b></h3>
--   
--   <pre>
--   import Control.Monad.Trans.State -- from the "transformers" library
--   
--   printState :: Show s =&gt; StateT s IO ()
--   printState = do
--     state &lt;- get
--     liftIO $ print state
--   </pre>
--   
--   Had we omitted <tt><a>liftIO</a></tt>, we would have ended up with
--   this error:
--   
--   <pre>
--   • Couldn't match type ‘IO’ with ‘StateT s IO’
--    Expected type: StateT s IO ()
--      Actual type: IO ()
--   </pre>
--   
--   The important part here is the mismatch between <tt>StateT s IO
--   ()</tt> and <tt><a>IO</a> ()</tt>.
--   
--   Luckily, we know of a function that takes an <tt><a>IO</a> a</tt> and
--   returns an <tt>(m a)</tt>: <tt><a>liftIO</a></tt>, enabling us to run
--   the program and see the expected results:
--   
--   <pre>
--   &gt; evalStateT printState "hello"
--   "hello"
--   
--   &gt; evalStateT printState 3
--   3
--   </pre>
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 <tt>Exception</tt> class. The simplest case is a new
--   exception type directly below the root:
--   
--   <pre>
--   data MyException = ThisException | ThatException
--       deriving Show
--   
--   instance Exception MyException
--   </pre>
--   
--   The default method definitions in the <tt>Exception</tt> class do what
--   we need in this case. You can now throw and catch
--   <tt>ThisException</tt> and <tt>ThatException</tt> as exceptions:
--   
--   <pre>
--   *Main&gt; throw ThisException `catch` \e -&gt; putStrLn ("Caught " ++ show (e :: MyException))
--   Caught ThisException
--   </pre>
--   
--   In more complicated examples, you may wish to define a whole hierarchy
--   of exceptions:
--   
--   <pre>
--   ---------------------------------------------------------------------
--   -- Make the root exception type for all the exceptions in a compiler
--   
--   data SomeCompilerException = forall e . Exception e =&gt; SomeCompilerException e
--   
--   instance Show SomeCompilerException where
--       show (SomeCompilerException e) = show e
--   
--   instance Exception SomeCompilerException
--   
--   compilerExceptionToException :: Exception e =&gt; e -&gt; SomeException
--   compilerExceptionToException = toException . SomeCompilerException
--   
--   compilerExceptionFromException :: Exception e =&gt; SomeException -&gt; Maybe e
--   compilerExceptionFromException x = do
--       SomeCompilerException a &lt;- fromException x
--       cast a
--   
--   ---------------------------------------------------------------------
--   -- Make a subhierarchy for exceptions in the frontend of the compiler
--   
--   data SomeFrontendException = forall e . Exception e =&gt; SomeFrontendException e
--   
--   instance Show SomeFrontendException where
--       show (SomeFrontendException e) = show e
--   
--   instance Exception SomeFrontendException where
--       toException = compilerExceptionToException
--       fromException = compilerExceptionFromException
--   
--   frontendExceptionToException :: Exception e =&gt; e -&gt; SomeException
--   frontendExceptionToException = toException . SomeFrontendException
--   
--   frontendExceptionFromException :: Exception e =&gt; SomeException -&gt; Maybe e
--   frontendExceptionFromException x = do
--       SomeFrontendException a &lt;- 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
--   </pre>
--   
--   We can now catch a <tt>MismatchedParentheses</tt> exception as
--   <tt>MismatchedParentheses</tt>, <tt>SomeFrontendException</tt> or
--   <tt>SomeCompilerException</tt>, but not other types, e.g.
--   <tt>IOException</tt>:
--   
--   <pre>
--   *Main&gt; throw MismatchedParentheses `catch` \e -&gt; putStrLn ("Caught " ++ show (e :: MismatchedParentheses))
--   Caught MismatchedParentheses
--   *Main&gt; throw MismatchedParentheses `catch` \e -&gt; putStrLn ("Caught " ++ show (e :: SomeFrontendException))
--   Caught MismatchedParentheses
--   *Main&gt; throw MismatchedParentheses `catch` \e -&gt; putStrLn ("Caught " ++ show (e :: SomeCompilerException))
--   Caught MismatchedParentheses
--   *Main&gt; throw MismatchedParentheses `catch` \e -&gt; putStrLn ("Caught " ++ show (e :: IOException))
--   *** Exception: MismatchedParentheses
--   </pre>
class (Typeable e, Show e) => Exception e

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

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

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

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

-- | Exceptions that occur in the <tt>IO</tt> monad. An
--   <tt>IOException</tt> 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 <a>String</a>, 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 <tt>readFile (dir <a>&lt;/&gt;</a> file)</tt>
--   will access the same file as <tt>setCurrentDirectory dir; readFile
--   file</tt>.
--   
--   <pre>
--   Posix:   "/directory" &lt;/&gt; "file.ext" == "/directory/file.ext"
--   Windows: "/directory" &lt;/&gt; "file.ext" == "/directory\\file.ext"
--            "directory" &lt;/&gt; "/file.ext" == "/file.ext"
--   Valid x =&gt; (takeDirectory x &lt;/&gt; takeFileName x) `equalFilePath` x
--   </pre>
--   
--   Combined:
--   
--   <pre>
--   Posix:   "/" &lt;/&gt; "test" == "/test"
--   Posix:   "home" &lt;/&gt; "bob" == "home/bob"
--   Posix:   "x:" &lt;/&gt; "foo" == "x:/foo"
--   Windows: "C:\\foo" &lt;/&gt; "bar" == "C:\\foo\\bar"
--   Windows: "home" &lt;/&gt; "bob" == "home\\bob"
--   </pre>
--   
--   Not combined:
--   
--   <pre>
--   Posix:   "home" &lt;/&gt; "/bob" == "/bob"
--   Windows: "home" &lt;/&gt; "C:\\bob" == "C:\\bob"
--   </pre>
--   
--   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
--   <a>&lt;/&gt;</a> is to never combine these forms.
--   
--   <pre>
--   Windows: "home" &lt;/&gt; "/bob" == "/bob"
--   Windows: "home" &lt;/&gt; "\\bob" == "\\bob"
--   Windows: "C:\\home" &lt;/&gt; "\\bob" == "\\bob"
--   </pre>
--   
--   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 <a>&lt;/&gt;</a> is to
--   never combine these forms.
--   
--   <pre>
--   Windows: "D:\\foo" &lt;/&gt; "C:bar" == "C:bar"
--   Windows: "C:\\foo" &lt;/&gt; "C:bar" == "C:bar"
--   </pre>
(</>) :: FilePath -> FilePath -> FilePath
infixr 5 </>

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

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

-- | Like <a>hashWithSalt</a>, but no salt is used. The default
--   implementation uses <a>hashWithSalt</a> 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 <a>hashWithSalt</a> is:
--   
--   <ul>
--   <li>If two values are equal according to the <a>==</a> method, then
--   applying the <a>hashWithSalt</a> method on each of the two values
--   <i>must</i> produce the same integer result if the same salt is used
--   in each case.</li>
--   <li>It is <i>not</i> required that if two values are unequal according
--   to the <a>==</a> method, then applying the <a>hashWithSalt</a> 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.</li>
--   <li>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
--   <a>hashWithSalt</a> <i>must</i> make use of the salt in its
--   implementation.</li>
--   <li><a>hashWithSalt</a> may return negative <a>Int</a> values.</li>
--   </ul>
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
--   <a>Nothing</a> if the index is out of bounds
--   
--   This is the total variant of the partial <a>!!</a> operator.
--   
--   WARNING: This function takes linear time in the index.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !? 0
--   Just 'a'
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !? 2
--   Just 'c'
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !? 3
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !? (-1)
--   Nothing
--   </pre>
(!?) :: [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 &lt;math&gt; access. Instead, they are
--   intended to be traversed.
--   
--   You can use <tt>List a</tt> or <tt>[a]</tt> in type signatures:
--   
--   <pre>
--   length :: [a] -&gt; Int
--   </pre>
--   
--   or
--   
--   <pre>
--   length :: List a -&gt; Int
--   </pre>
--   
--   They are fully equivalent, and <tt>List a</tt> will be normalised to
--   <tt>[a]</tt>.
--   
--   <h4>Usage</h4>
--   
--   Lists are constructed recursively using the right-associative
--   constructor operator (or <i>cons</i>) <tt>(:) :: a -&gt; [a] -&gt;
--   [a]</tt>, which prepends an element to a list, and the empty list
--   <tt>[]</tt>.
--   
--   <pre>
--   (1 : 2 : 3 : []) == (1 : (2 : (3 : []))) == [1, 2, 3]
--   </pre>
--   
--   Lists can also be constructed using list literals of the form
--   <tt>[x_1, x_2, ..., x_n]</tt> which are syntactic sugar and, unless
--   <tt>-XOverloadedLists</tt> is enabled, are translated into uses of
--   <tt>(:)</tt> and <tt>[]</tt>
--   
--   <a>String</a> literals, like <tt>"I 💜 hs"</tt>, are translated into
--   Lists of characters, <tt>['I', ' ', '💜', ' ', 'h', 's']</tt>.
--   
--   <h4><b>Implementation</b></h4>
--   
--   Internally and in memory, all the above are represented like this,
--   with arrows being pointers to locations in memory.
--   
--   <pre>
--   ╭───┬───┬──╮   ╭───┬───┬──╮   ╭───┬───┬──╮   ╭────╮
--   │(:)│   │ ─┼──&gt;│(:)│   │ ─┼──&gt;│(:)│   │ ─┼──&gt;│ [] │
--   ╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰────╯
--         v              v              v
--         1              2              3
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; ['H', 'a', 's', 'k', 'e', 'l', 'l']
--   "Haskell"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 1 : [4, 1, 5, 9]
--   [1,4,1,5,9]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; [] : [] : []
--   [[],[]]
--   </pre>
data [] a

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

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

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

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

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

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

-- | &lt;math&gt;. <a>zip</a> takes two lists and returns a list of
--   corresponding pairs.
--   
--   <a>zip</a> is right-lazy:
--   
--   <pre>
--   &gt;&gt;&gt; zip [] undefined
--   []
--   
--   &gt;&gt;&gt; zip undefined []
--   *** Exception: Prelude.undefined
--   ...
--   </pre>
--   
--   <a>zip</a> is capable of list fusion, but it is restricted to its
--   first list argument and its resulting list.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; zip [1, 2, 3] ['a', 'b', 'c']
--   [(1,'a'),(2,'b'),(3,'c')]
--   </pre>
--   
--   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:
--   
--   <pre>
--   &gt;&gt;&gt; zip [1] ['a', 'b']
--   [(1,'a')]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; zip [1, 2] ['a']
--   [(1,'a')]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; zip [] [1..]
--   []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; zip [1..] []
--   []
--   </pre>
zip :: [a] -> [b] -> [(a, b)]

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

-- | &lt;math&gt;. Decompose a list into its <a>head</a> and <a>tail</a>.
--   
--   <ul>
--   <li>If the list is empty, returns <a>Nothing</a>.</li>
--   <li>If the list is non-empty, returns <tt><a>Just</a> (x, xs)</tt>,
--   where <tt>x</tt> is the <a>head</a> of the list and <tt>xs</tt> its
--   <a>tail</a>.</li>
--   </ul>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; uncons []
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; uncons [1]
--   Just (1,[])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; uncons [1, 2, 3]
--   Just (1,[2,3])
--   </pre>
uncons :: [a] -> Maybe (a, [a])

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

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

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

-- | &lt;math&gt;. Return all the elements of a list except the last one.
--   The list must be non-empty.
--   
--   WARNING: This function is partial. Consider using <a>unsnoc</a>
--   instead.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; init [1, 2, 3]
--   [1,2]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; init [1]
--   []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; init []
--   *** Exception: Prelude.init: empty list
--   </pre>
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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; null []
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; null [1]
--   False
--   </pre>
--   
--   <a>null</a> 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).
--   
--   <pre>
--   &gt;&gt;&gt; null [1..]
--   False
--   </pre>
null :: Foldable t => t a -> Bool

-- | Returns the size/length of a finite structure as an <a>Int</a>. 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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; length []
--   0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; length ['a', 'b', 'c']
--   3
--   
--   &gt;&gt;&gt; length [1..]
--   * Hangs forever *
--   </pre>
length :: Foldable t => t a -> Int

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

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

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

-- | &lt;math&gt;. A strict version of <a>scanl</a>.
scanl' :: (b -> a -> b) -> b -> [a] -> [b]

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

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

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

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

-- | <a>repeat</a> <tt>x</tt> is an infinite list, with <tt>x</tt> the
--   value of every element.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; take 10 $ repeat 17
--   [17,17,17,17,17,17,17,17,17, 17]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; repeat undefined
--   [*** Exception: Prelude.undefined
--   </pre>
repeat :: a -> [a]

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

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

-- | <a>dropWhile</a> <tt>p xs</tt> returns the suffix remaining after
--   <a>takeWhile</a> <tt>p xs</tt>.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; dropWhile (&lt; 3) [1,2,3,4,5,1,2,3]
--   [3,4,5,1,2,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; dropWhile (&lt; 9) [1,2,3]
--   []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; dropWhile (&lt; 0) [1,2,3]
--   [1,2,3]
--   </pre>
dropWhile :: (a -> Bool) -> [a] -> [a]

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

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

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

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

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

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

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

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

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

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

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

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

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

-- | List index (subscript) operator, starting from 0. It is an instance of
--   the more general <a>genericIndex</a>, 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 <a>!?</a>.
--   
--   WARNING: This function takes linear time in the index.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! 0
--   'a'
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! 2
--   'c'
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! 3
--   *** Exception: Prelude.!!: index too large
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! (-1)
--   *** Exception: Prelude.!!: negative index
--   </pre>
(!!) :: HasCallStack => [a] -> Int -> a
infixl 9 !!

-- | <a>zip3</a> takes three lists and returns a list of triples, analogous
--   to <a>zip</a>. 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)]

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

-- | &lt;math&gt;. The <a>zipWith3</a> 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
--   <a>zipWith</a>. It is capable of list fusion, but it is restricted to
--   its first list argument and its resulting list.
--   
--   <pre>
--   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..]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; zipWith3 (\x y z -&gt; [x, y, z]) "123" "abc" "xyz"
--   ["1ax","2by","3cz"]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; zipWith3 (\x y z -&gt; (x * y) + z) [1, 2, 3] [4, 5, 6] [7, 8, 9]
--   [11,18,27]
--   </pre>
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- | The <a>union</a> function returns the list union of the two lists. It
--   is a special case of <a>unionBy</a>, which allows the programmer to
--   supply their own equality test.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; "dog" `union` "cow"
--   "dogcw"
--   </pre>
--   
--   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:
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Semigroup(Arg(..))
--   
--   &gt;&gt;&gt; union [Arg () "dog"] [Arg () "cow"]
--   [Arg () "dog"]
--   
--   &gt;&gt;&gt; union [] [Arg () "dog", Arg () "cow"]
--   [Arg () "dog"]
--   </pre>
--   
--   However if the first list contains duplicates, so will the result:
--   
--   <pre>
--   &gt;&gt;&gt; "coot" `union` "duck"
--   "cootduk"
--   
--   &gt;&gt;&gt; "duck" `union` "coot"
--   "duckot"
--   </pre>
--   
--   <a>union</a> is productive even if both arguments are infinite.
--   
--   <pre>
--   &gt;&gt;&gt; [0, 2 ..] `union` [1, 3 ..]
--   [0,2,4,6,8,10,12..
--   </pre>
union :: Eq a => [a] -> [a] -> [a]

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

-- | The <a>intersect</a> function takes the list intersection of two
--   lists. It is a special case of <a>intersectBy</a>, which allows the
--   programmer to supply their own equality test.
--   
--   <h5><b>Examples</b></h5>
--   
--   <pre>
--   &gt;&gt;&gt; [1,2,3,4] `intersect` [2,4,6,8]
--   [2,4]
--   </pre>
--   
--   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:
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Semigroup
--   
--   &gt;&gt;&gt; intersect [Arg () "dog"] [Arg () "cow", Arg () "cat"]
--   [Arg () "dog"]
--   </pre>
--   
--   However if the first list contains duplicates, so will the result.
--   
--   <pre>
--   &gt;&gt;&gt; "coot" `intersect` "heron"
--   "oo"
--   
--   &gt;&gt;&gt; "heron" `intersect` "coot"
--   "o"
--   </pre>
--   
--   If the second list is infinite, <a>intersect</a> either hangs or
--   returns its first argument in full. Otherwise if the first list is
--   infinite, <a>intersect</a> might be productive:
--   
--   <pre>
--   &gt;&gt;&gt; intersect [100..] [0..]
--   [100,101,102,103...
--   
--   &gt;&gt;&gt; intersect [0] [1..]
--   * Hangs forever *
--   
--   &gt;&gt;&gt; intersect [1..] [0]
--   * Hangs forever *
--   
--   &gt;&gt;&gt; intersect (cycle [1..3]) [2]
--   [2,2,2,2...
--   </pre>
intersect :: Eq a => [a] -> [a] -> [a]

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

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

-- | The <a>partition</a> 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.,
--   
--   <pre>
--   partition p xs == (filter p xs, filter (not . p) xs)
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; partition (`elem` "aeiou") "Hello World!"
--   ("eoo","Hll Wrld!")
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; partition even [1..10]
--   ([2,4,6,8,10],[1,3,5,7,9])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; partition (&lt; 5) [1..10]
--   ([1,2,3,4],[5,6,7,8,9,10])
--   </pre>
partition :: (a -> Bool) -> [a] -> ([a], [a])

-- | &lt;math&gt;. The <a>insert</a> 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 <a>insertBy</a>, which allows the programmer to supply
--   their own comparison function.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; insert (-1) [1, 2, 3]
--   [-1,1,2,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; insert 'd' "abcefg"
--   "abcdefg"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; insert 4 [1, 2, 3, 5, 6, 7]
--   [1,2,3,4,5,6,7]
--   </pre>
insert :: Ord a => a -> [a] -> [a]

-- | &lt;math&gt;. The non-overloaded version of <a>insert</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; insertBy (\x y -&gt; 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]]
--   </pre>
insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]

-- | &lt;math&gt;. The <a>genericLength</a> function is an overloaded
--   version of <a>length</a>. In particular, instead of returning an
--   <a>Int</a>, it returns any type which is an instance of <a>Num</a>. It
--   is, however, less efficient than <a>length</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; genericLength [1, 2, 3] :: Int
--   3
--   
--   &gt;&gt;&gt; genericLength [1, 2, 3] :: Float
--   3.0
--   </pre>
--   
--   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 <tt>(+)</tt> implementation in
--   the selected <a>Num</a> instance. The following example overflows
--   because the actual list length of 200 lies outside of the
--   <tt>Int8</tt> range of <tt>-128..127</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; genericLength [1..200] :: Int8
--   -56
--   </pre>
genericLength :: Num i => [a] -> i

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

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

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

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

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

-- | The <a>zip4</a> function takes four lists and returns a list of
--   quadruples, analogous to <a>zip</a>. 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 <a>zip5</a> function takes five lists and returns a list of
--   five-tuples, analogous to <a>zip</a>. 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 <a>zip6</a> function takes six lists and returns a list of
--   six-tuples, analogous to <a>zip</a>. 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 <a>zip7</a> function takes seven lists and returns a list of
--   seven-tuples, analogous to <a>zip</a>. 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 <a>zipWith4</a> function takes a function which combines four
--   elements, as well as four lists and returns a list of their point-wise
--   combination, analogous to <a>zipWith</a>. 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 <a>zipWith5</a> function takes a function which combines five
--   elements, as well as five lists and returns a list of their point-wise
--   combination, analogous to <a>zipWith</a>. 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 <a>zipWith6</a> function takes a function which combines six
--   elements, as well as six lists and returns a list of their point-wise
--   combination, analogous to <a>zipWith</a>. 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 <a>zipWith7</a> function takes a function which combines seven
--   elements, as well as seven lists and returns a list of their
--   point-wise combination, analogous to <a>zipWith</a>. 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 <a>unzip4</a> function takes a list of quadruples and returns four
--   lists, analogous to <a>unzip</a>.
unzip4 :: [(a, b, c, d)] -> ([a], [b], [c], [d])

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

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

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

-- | The <a>deleteFirstsBy</a> 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
--   <a>(\\)</a>.
--   
--   <pre>
--   (\\) == deleteFirstsBy (==)
--   </pre>
--   
--   The second list must be finite, but the first may be infinite.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; deleteFirstsBy (&gt;) [1..10] [3, 4, 5]
--   [4,5,6,7,8,9,10]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; deleteFirstsBy (/=) [1..10] [1, 3, 5]
--   [4,5,6,7,8,9,10]
--   </pre>
deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]

-- | The <a>group</a> 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.
--   
--   <a>group</a> is a special case of <a>groupBy</a>, which allows the
--   programmer to supply their own equality test.
--   
--   It's often preferable to use <tt>Data.List.NonEmpty.</tt><a>group</a>,
--   which provides type-level guarantees of non-emptiness of inner lists.
--   A common idiom to squash repeating elements <a>map</a> <a>head</a>
--   <a>.</a> <a>group</a> is better served by <a>map</a>
--   <tt>Data.List.NonEmpty.</tt><a>head</a> <a>.</a>
--   <tt>Data.List.NonEmpty.</tt><a>group</a> because it avoids partial
--   functions.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; group "Mississippi"
--   ["M","i","ss","i","ss","i","pp","i"]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; group [1, 1, 1, 2, 2, 3, 4, 5, 5]
--   [[1,1,1],[2,2],[3],[4],[5,5]]
--   </pre>
group :: Eq a => [a] -> [[a]]

-- | The <a>groupBy</a> function is the non-overloaded version of
--   <a>group</a>.
--   
--   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:
--   
--   <pre>
--   &gt;&gt;&gt; groupBy (\a b -&gt; b - a &lt; 5) [0..19]
--   [[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14],[15,16,17,18,19]]
--   </pre>
--   
--   It's often preferable to use
--   <tt>Data.List.NonEmpty.</tt><a>groupBy</a>, which provides type-level
--   guarantees of non-emptiness of inner lists.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; groupBy (/=) [1, 1, 1, 2, 3, 1, 4, 4, 5]
--   [[1],[1],[1,2,3],[1,4,4,5]]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; groupBy (&gt;) [1, 3, 5, 1, 4, 2, 6, 5, 4]
--   [[1],[3],[5,1,4,2],[6,5,4]]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; groupBy (const not) [True, False, True, False, False, False, True]
--   [[True,False],[True,False,False,False],[True]]
--   </pre>
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

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

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

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

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

-- | The <a>sort</a> function implements a stable sorting algorithm. It is
--   a special case of <a>sortBy</a>, 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.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; sort [1,6,4,3,2,5]
--   [1,2,3,4,5,6]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sort "haskell"
--   "aehklls"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Semigroup(Arg(..))
--   
--   &gt;&gt;&gt; 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]
--   </pre>
sort :: Ord a => [a] -> [a]

-- | Construct a list from a single element.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; singleton True
--   [True]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; singleton [1, 2, 3]
--   [[1,2,3]]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; singleton 'c'
--   "c"
--   </pre>
singleton :: a -> [a]

-- | The <a>mapAccumL</a> function behaves like a combination of
--   <a>fmap</a> and <a>foldl</a>; 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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; mapAccumL (\a b -&gt; (a + b, a)) 0 [1..10]
--   (55,[0,1,3,6,10,15,21,28,36,45])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; mapAccumL (\a b -&gt; (a &lt;&gt; show b, a)) "0" [1..5]
--   ("012345",["0","01","012","0123","01234"])
--   </pre>
mapAccumL :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)

-- | The <a>mapAccumR</a> function behaves like a combination of
--   <a>fmap</a> and <a>foldr</a>; 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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; mapAccumR (\a b -&gt; (a + b, a)) 0 [1..10]
--   (55,[54,52,49,45,40,34,27,19,10,0])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; mapAccumR (\a b -&gt; (a &lt;&gt; show b, a)) "0" [1..5]
--   ("054321",["05432","0543","054","05","0"])
--   </pre>
mapAccumR :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)

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

-- | The <a>Monad</a> class defines the basic operations over a
--   <i>monad</i>, a concept from a branch of mathematics known as
--   <i>category theory</i>. From the perspective of a Haskell programmer,
--   however, it is best to think of a monad as an <i>abstract datatype</i>
--   of actions. Haskell's <tt>do</tt> expressions provide a convenient
--   syntax for writing monadic expressions.
--   
--   Instances of <a>Monad</a> should satisfy the following:
--   
--   <ul>
--   <li><i>Left identity</i> <tt><a>return</a> a <a>&gt;&gt;=</a> k = k
--   a</tt></li>
--   <li><i>Right identity</i> <tt>m <a>&gt;&gt;=</a> <a>return</a> =
--   m</tt></li>
--   <li><i>Associativity</i> <tt>m <a>&gt;&gt;=</a> (\x -&gt; k x
--   <a>&gt;&gt;=</a> h) = (m <a>&gt;&gt;=</a> k) <a>&gt;&gt;=</a>
--   h</tt></li>
--   </ul>
--   
--   Furthermore, the <a>Monad</a> and <a>Applicative</a> operations should
--   relate as follows:
--   
--   <ul>
--   <li><pre><a>pure</a> = <a>return</a></pre></li>
--   <li><pre>m1 <a>&lt;*&gt;</a> m2 = m1 <a>&gt;&gt;=</a> (\x1 -&gt; m2
--   <a>&gt;&gt;=</a> (\x2 -&gt; <a>return</a> (x1 x2)))</pre></li>
--   </ul>
--   
--   The above laws imply:
--   
--   <ul>
--   <li><pre><a>fmap</a> f xs = xs <a>&gt;&gt;=</a> <a>return</a> .
--   f</pre></li>
--   <li><pre>(<a>&gt;&gt;</a>) = (<a>*&gt;</a>)</pre></li>
--   </ul>
--   
--   and that <a>pure</a> and (<a>&lt;*&gt;</a>) satisfy the applicative
--   functor laws.
--   
--   The instances of <a>Monad</a> for <a>List</a>, <a>Maybe</a> and
--   <a>IO</a> defined in the <a>Prelude</a> 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.
--   
--   '<tt>as <a>&gt;&gt;=</a> bs</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do a &lt;- as
--      bs a
--   </pre>
--   
--   An alternative name for this function is 'bind', but some people may
--   refer to it as 'flatMap', which results from it being equivialent to
--   
--   <pre>
--   \x f -&gt; <a>join</a> (<a>fmap</a> f x) :: Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b
--   </pre>
--   
--   which can be seen as mapping a value with <tt>Monad m =&gt; m a -&gt;
--   m (m b)</tt> and then 'flattening' <tt>m (m b)</tt> to <tt>m b</tt>
--   using <a>join</a>.
(>>=) :: 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.
--   
--   '<tt>as <a>&gt;&gt;</a> bs</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do as
--      bs
--   </pre>
--   
--   or in terms of <tt><a>(&gt;&gt;=)</a></tt> as
--   
--   <pre>
--   as &gt;&gt;= const bs
--   </pre>
(>>) :: Monad m => m a -> m b -> m b

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

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

-- | <a>fmap</a> is used to apply a function of type <tt>(a -&gt; b)</tt>
--   to a value of type <tt>f a</tt>, where f is a functor, to produce a
--   value of type <tt>f b</tt>. Note that for any type constructor with
--   more than one parameter (e.g., <tt>Either</tt>), only the last type
--   parameter can be modified with <a>fmap</a> (e.g., <tt>b</tt> in
--   `Either a b`).
--   
--   Some type constructors with two parameters or more have a
--   <tt><a>Bifunctor</a></tt> instance that allows both the last and the
--   penultimate parameters to be mapped over.
--   
--   <h4><b>Examples</b></h4>
--   
--   Convert from a <tt><a>Maybe</a> Int</tt> to a <tt>Maybe String</tt>
--   using <a>show</a>:
--   
--   <pre>
--   &gt;&gt;&gt; fmap show Nothing
--   Nothing
--   
--   &gt;&gt;&gt; fmap show (Just 3)
--   Just "3"
--   </pre>
--   
--   Convert from an <tt><a>Either</a> Int Int</tt> to an <tt>Either Int
--   String</tt> using <a>show</a>:
--   
--   <pre>
--   &gt;&gt;&gt; fmap show (Left 17)
--   Left 17
--   
--   &gt;&gt;&gt; fmap show (Right 17)
--   Right "17"
--   </pre>
--   
--   Double each element of a list:
--   
--   <pre>
--   &gt;&gt;&gt; fmap (*2) [1,2,3]
--   [2,4,6]
--   </pre>
--   
--   Apply <a>even</a> to the second element of a pair:
--   
--   <pre>
--   &gt;&gt;&gt; fmap even (2,2)
--   (2,True)
--   </pre>
--   
--   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 <tt>(a,b,c)</tt> can also be written <tt>(,,) a b c</tt> and
--   its <tt>Functor</tt> instance is defined for <tt>Functor ((,,) a
--   b)</tt> (i.e., only the third parameter is free to be mapped over with
--   <tt>fmap</tt>).
--   
--   It explains why <tt>fmap</tt> can be used with tuples containing
--   values of different types as in the following example:
--   
--   <pre>
--   &gt;&gt;&gt; fmap even ("hello", 1.0, 4)
--   ("hello",1.0,True)
--   </pre>
fmap :: Functor f => (a -> b) -> f a -> f b

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

-- | When a value is bound in <tt>do</tt>-notation, the pattern on the left
--   hand side of <tt>&lt;-</tt> might not match. In this case, this class
--   provides a function to recover.
--   
--   A <a>Monad</a> without a <a>MonadFail</a> 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 (<tt>~pat</tt>).
--   
--   Instances of <a>MonadFail</a> should satisfy the following law:
--   <tt>fail s</tt> should be a left zero for <a>&gt;&gt;=</a>,
--   
--   <pre>
--   fail s &gt;&gt;= f  =  fail s
--   </pre>
--   
--   If your <a>Monad</a> is also <a>MonadPlus</a>, a popular definition is
--   
--   <pre>
--   fail _ = mzero
--   </pre>
--   
--   <tt>fail s</tt> should be an action that runs in the monad itself, not
--   an exception (except in instances of <tt>MonadIO</tt>). In particular,
--   <tt>fail</tt> should not be implemented in terms of <tt>error</tt>.
class Monad m => MonadFail (m :: Type -> Type)
fail :: MonadFail m => String -> m a

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

-- | The <a>join</a> 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.
--   
--   '<tt><a>join</a> bss</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do bs &lt;- bss
--      bs
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; join [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
--   [1,2,3,4,5,6,7,8,9]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; join (Just (Just 3))
--   Just 3
--   </pre>
--   
--   A common use of <a>join</a> is to run an <a>IO</a> computation
--   returned from an <a>STM</a> transaction, since <a>STM</a> transactions
--   can't perform <a>IO</a> directly. Recall that
--   
--   <pre>
--   <a>atomically</a> :: STM a -&gt; IO a
--   </pre>
--   
--   is used to run <a>STM</a> transactions atomically. So, by specializing
--   the types of <a>atomically</a> and <a>join</a> to
--   
--   <pre>
--   <a>atomically</a> :: STM (IO b) -&gt; IO (IO b)
--   <a>join</a>       :: IO (IO b)  -&gt; IO b
--   </pre>
--   
--   we can compose them as
--   
--   <pre>
--   <a>join</a> . <a>atomically</a> :: STM (IO b) -&gt; IO b
--   </pre>
--   
--   to run an <a>STM</a> transaction and the <a>IO</a> 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 <a>mplus</a>. It should also satisfy the equations
--   
--   <pre>
--   mzero &gt;&gt;= f  =  mzero
--   v &gt;&gt; mzero   =  mzero
--   </pre>
--   
--   The default definition is
--   
--   <pre>
--   mzero = <a>empty</a>
--   </pre>
mzero :: MonadPlus m => m a

-- | An associative operation. The default definition is
--   
--   <pre>
--   mplus = (<a>&lt;|&gt;</a>)
--   </pre>
mplus :: MonadPlus m => m a -> m a -> m a

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

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

-- | Promote a function to a monad. This is equivalent to <a>fmap</a> 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.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; liftM2 (+) [0,1] [0,2]
--   [0,2,1,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; liftM2 (+) (Just 1) Nothing
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; liftM2 (+) (+ 3) (* 2) 5
--   18
--   </pre>
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. <a>liftM2</a>).
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. <a>liftM2</a>).
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. <a>liftM2</a>).
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 <a>liftM</a> operations can be replaced by
--   uses of <a>ap</a>, which promotes function application.
--   
--   <pre>
--   return f `ap` x1 `ap` ... `ap` xn
--   </pre>
--   
--   is equivalent to
--   
--   <pre>
--   liftM&lt;n&gt; f x1 x2 ... xn
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; pure (\x y z -&gt; x + y * z) `ap` Just 1 `ap` Just 5 `ap` Just 10
--   Just 51
--   </pre>
ap :: Monad m => m (a -> b) -> m a -> m b

-- | <tt><a>void</a> value</tt> discards or ignores the result of
--   evaluation, such as the return value of an <a>IO</a> action.
--   
--   <h4><b>Examples</b></h4>
--   
--   Replace the contents of a <tt><a>Maybe</a> <a>Int</a></tt> with unit:
--   
--   <pre>
--   &gt;&gt;&gt; void Nothing
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; void (Just 3)
--   Just ()
--   </pre>
--   
--   Replace the contents of an <tt><a>Either</a> <a>Int</a>
--   <a>Int</a></tt> with unit, resulting in an <tt><a>Either</a>
--   <a>Int</a> <tt>()</tt></tt>:
--   
--   <pre>
--   &gt;&gt;&gt; void (Left 8675309)
--   Left 8675309
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; void (Right 8675309)
--   Right ()
--   </pre>
--   
--   Replace every element of a list with unit:
--   
--   <pre>
--   &gt;&gt;&gt; void [1,2,3]
--   [(),(),()]
--   </pre>
--   
--   Replace the second element of a pair with unit:
--   
--   <pre>
--   &gt;&gt;&gt; void (1,2)
--   (1,())
--   </pre>
--   
--   Discard the result of an <a>IO</a> action:
--   
--   <pre>
--   &gt;&gt;&gt; mapM print [1,2]
--   1
--   2
--   [(),()]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; void $ mapM print [1,2]
--   1
--   2
--   </pre>
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 <a>mapM</a>.
--   
--   <a>mapM_</a> is just like <a>traverse_</a>, but specialised to monadic
--   actions.
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()

-- | <a>forM_</a> is <a>mapM_</a> with its arguments flipped. For a version
--   that doesn't ignore the results see <a>forM</a>.
--   
--   <a>forM_</a> is just like <a>for_</a>, 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
--   <a>sequence</a>.
--   
--   <a>sequence_</a> is just like <a>sequenceA_</a>, but specialised to
--   monadic actions.
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()

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

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

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

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

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

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

-- | The <a>mapAndUnzipM</a> 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 <a>zipWithM</a> function generalizes <a>zipWith</a> to arbitrary
--   applicative functors.
zipWithM :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m [c]

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

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

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

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

-- | Like <a>replicateM</a>, but discards the result.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; replicateM_ 3 (putStr "a")
--   aaa
--   </pre>
replicateM_ :: Applicative m => Int -> m a -> m ()

-- | The reverse of <a>when</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; do x &lt;- getLine
--          unless (x == "hi") (putStrLn "hi!")
--   comingupwithexamplesisdifficult
--   hi!
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; unless (pi &gt; exp 1) Nothing
--   Just ()
--   </pre>
unless :: Applicative f => Bool -> f () -> f ()

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

-- | Direct <a>MonadPlus</a> equivalent of <a>filter</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   The <a>filter</a> function is just <a>mfilter</a> specialized to the
--   list monad:
--   
--   <pre>
--   <a>filter</a> = ( <a>mfilter</a> :: (a -&gt; Bool) -&gt; [a] -&gt; [a] )
--   </pre>
--   
--   An example using <a>mfilter</a> with the <a>Maybe</a> monad:
--   
--   <pre>
--   &gt;&gt;&gt; mfilter odd (Just 1)
--   Just 1
--   
--   &gt;&gt;&gt; mfilter odd (Just 2)
--   Nothing
--   </pre>
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
--   <tt>DeriveFoldable</tt> extension. For example, a derived instance for
--   a binary tree might be:
--   
--   <pre>
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   </pre>
--   
--   A more detailed description can be found in the <b>Overview</b>
--   section of <a>Data.Foldable#overview</a>.
--   
--   For the class laws see the <b>Laws</b> section of
--   <a>Data.Foldable#laws</a>.
class Foldable (t :: Type -> Type)

-- | Map each element of the structure into a monoid, and combine the
--   results with <tt>(<a>&lt;&gt;</a>)</tt>. This fold is
--   right-associative and lazy in the accumulator. For strict
--   left-associative folds consider <a>foldMap'</a> instead.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; foldMap Sum [1, 3, 5]
--   Sum {getSum = 9}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldMap Product [1, 3, 5]
--   Product {getProduct = 15}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldMap (replicate 3) [1, 2, 3]
--   [1,1,1,2,2,2,3,3,3]
--   </pre>
--   
--   When a Monoid's <tt>(<a>&lt;&gt;</a>)</tt> is lazy in its second
--   argument, <a>foldMap</a> can return a result even from an unbounded
--   structure. For example, lazy accumulation enables
--   <a>Data.ByteString.Builder</a> to efficiently serialise large data
--   structures and produce the output incrementally:
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Data.ByteString.Lazy as L
--   
--   &gt;&gt;&gt; import qualified Data.ByteString.Builder as B
--   
--   &gt;&gt;&gt; let bld :: Int -&gt; B.Builder; bld i = B.intDec i &lt;&gt; B.word8 0x20
--   
--   &gt;&gt;&gt; let lbs = B.toLazyByteString $ foldMap bld [0..]
--   
--   &gt;&gt;&gt; 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"
--   </pre>
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, <a>foldr</a>, 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:
--   
--   <pre>
--   foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
--   </pre>
--   
--   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, <a>foldr</a> can produce a
--   terminating expression from an unbounded list.
--   
--   For a general <a>Foldable</a> structure this should be semantically
--   identical to,
--   
--   <pre>
--   foldr f z = <a>foldr</a> f z . <a>toList</a>
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; foldr (||) False [False, True, False]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr (||) False []
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr (\c acc -&gt; acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
--   "foodcba"
--   </pre>
--   
--   <h5>Infinite structures</h5>
--   
--   ⚠️ Applying <a>foldr</a> to infinite structures usually doesn't
--   terminate.
--   
--   It may still terminate under one of the following conditions:
--   
--   <ul>
--   <li>the folding function is short-circuiting</li>
--   <li>the folding function is lazy on its second argument</li>
--   </ul>
--   
--   <h6>Short-circuiting</h6>
--   
--   <tt>(<a>||</a>)</tt> short-circuits on <a>True</a> values, so the
--   following terminates because there is a <a>True</a> value finitely far
--   from the left side:
--   
--   <pre>
--   &gt;&gt;&gt; foldr (||) False (True : repeat False)
--   True
--   </pre>
--   
--   But the following doesn't terminate:
--   
--   <pre>
--   &gt;&gt;&gt; foldr (||) False (repeat False ++ [True])
--   * Hangs forever *
--   </pre>
--   
--   <h6>Laziness in the second argument</h6>
--   
--   Applying <a>foldr</a> 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 <a>undefined</a>, but
--   <tt>[]</tt> is more clear):
--   
--   <pre>
--   &gt;&gt;&gt; take 5 $ foldr (\i acc -&gt; i : fmap (+3) acc) [] (repeat 1)
--   [1,4,7,10,13]
--   </pre>
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

-- | <a>foldr'</a> is a variant of <a>foldr</a> that performs strict
--   reduction from right to left, i.e. starting with the right-most
--   element. The input structure <i>must</i> be finite, otherwise
--   <a>foldr'</a> runs out of space (<i>diverges</i>).
--   
--   If you want a strict right fold in constant space, you need a
--   structure that supports faster than <i>O(n)</i> access to the
--   right-most element, such as <tt>Seq</tt> from the <tt>containers</tt>
--   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 <i>O(n)</i> 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 <a>foldl'</a> 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, <a>foldl</a>, 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:
--   
--   <pre>
--   foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--   </pre>
--   
--   Note that to produce the outermost application of the operator the
--   entire input list must be traversed. Like all left-associative folds,
--   <a>foldl</a> will diverge if given an infinite list.
--   
--   If you want an efficient strict left-fold, you probably want to use
--   <a>foldl'</a> instead of <a>foldl</a>. The reason for this is that the
--   latter does not force the <i>inner</i> results (e.g. <tt>z `f` x1</tt>
--   in the above example) before applying them to the operator (e.g. to
--   <tt>(`f` x2)</tt>). This results in a thunk chain <i>O(n)</i> elements
--   long, which then must be evaluated from the outside-in.
--   
--   For a general <a>Foldable</a> structure this should be semantically
--   identical to:
--   
--   <pre>
--   foldl f z = <a>foldl</a> f z . <a>toList</a>
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   The first example is a strict fold, which in practice is best
--   performed with <a>foldl'</a>.
--   
--   <pre>
--   &gt;&gt;&gt; foldl (+) 42 [1,2,3,4]
--   52
--   </pre>
--   
--   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.
--   
--   <pre>
--   &gt;&gt;&gt; foldl (\acc c -&gt; c : acc) "abcd" "efgh"
--   "hgfeabcd"
--   </pre>
--   
--   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:
--   
--   <pre>
--   &gt;&gt;&gt; foldl (\a _ -&gt; a) 0 $ repeat 1
--   * Hangs forever *
--   </pre>
--   
--   WARNING: When it comes to lists, you always want to use either
--   <a>foldl'</a> or <a>foldr</a> 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. <a>sum</a>).
--   
--   For a general <a>Foldable</a> structure this should be semantically
--   identical to,
--   
--   <pre>
--   foldl' f z = <a>foldl'</a> f z . <a>toList</a>
--   </pre>
foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

-- | A variant of <a>foldr</a> 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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; foldr1 (+) [1..4]
--   10
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr1 (+) []
--   Exception: Prelude.foldr1: empty list
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr1 (+) Nothing
--   *** Exception: foldr1: empty structure
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr1 (-) [1..4]
--   -2
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr1 (&amp;&amp;) [True, False, True, True]
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr1 (||) [False, False, True, True]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldr1 (+) [1..]
--   * Hangs forever *
--   </pre>
foldr1 :: Foldable t => (a -> a -> a) -> t a -> a

-- | A variant of <a>foldl</a> 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.
--   
--   <pre>
--   <a>foldl1</a> f = <a>foldl1</a> f . <a>toList</a>
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; foldl1 (+) [1..4]
--   10
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldl1 (+) []
--   *** Exception: Prelude.foldl1: empty list
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldl1 (+) Nothing
--   *** Exception: foldl1: empty structure
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldl1 (-) [1..4]
--   -8
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldl1 (&amp;&amp;) [True, False, True, True]
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldl1 (||) [False, False, True, True]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldl1 (+) [1..]
--   * Hangs forever *
--   </pre>
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a

-- | Does the element occur in the structure?
--   
--   Note: <a>elem</a> is often used in infix form.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; 3 `elem` []
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 3 `elem` [1,2]
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 3 `elem` [1,2,3,4,5]
--   True
--   </pre>
--   
--   For infinite structures, the default implementation of <a>elem</a>
--   terminates if the sought-after value exists at a finite distance from
--   the left side of the structure:
--   
--   <pre>
--   &gt;&gt;&gt; 3 `elem` [1..]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 3 `elem` ([4..] ++ [3])
--   * Hangs forever *
--   </pre>
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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; maximum [1..10]
--   10
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; maximum []
--   *** Exception: Prelude.maximum: empty list
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; maximum Nothing
--   *** Exception: maximum: empty structure
--   </pre>
--   
--   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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; minimum [1..10]
--   1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; minimum []
--   *** Exception: Prelude.minimum: empty list
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; minimum Nothing
--   *** Exception: minimum: empty structure
--   </pre>
--   
--   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 <a>Applicative</a> action,
--   evaluate these actions from left to right, and ignore the results. For
--   a version that doesn't ignore the results see <a>traverse</a>.
--   
--   <a>traverse_</a> is just like <a>mapM_</a>, but generalised to
--   <a>Applicative</a> actions.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; traverse_ print ["Hello", "world", "!"]
--   "Hello"
--   "world"
--   "!"
--   </pre>
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
--   <a>sequenceA</a>.
--   
--   <a>sequenceA_</a> is just like <a>sequence_</a>, but generalised to
--   <a>Applicative</a> actions.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; sequenceA_ [print "Hello", print "world", print "!"]
--   "Hello"
--   "world"
--   "!"
--   </pre>
sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()

-- | <a>for_</a> is <a>traverse_</a> with its arguments flipped. For a
--   version that doesn't ignore the results see <a>for</a>. This is
--   <a>forM_</a> generalised to <a>Applicative</a> actions.
--   
--   <a>for_</a> is just like <a>forM_</a>, but generalised to
--   <a>Applicative</a> actions.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; for_ [1..4] print
--   1
--   2
--   3
--   4
--   </pre>
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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; maximumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
--   "Longest"
--   </pre>
--   
--   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.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; minimumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
--   "!"
--   </pre>
--   
--   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 <i>same shape</i> by performing an
--   <a>Applicative</a> (or, therefore, <a>Monad</a>) action on each
--   element from left to right.
--   
--   A more detailed description of what <i>same shape</i> means, the
--   various methods, how traversals are constructed, and example advanced
--   use-cases can be found in the <b>Overview</b> section of
--   <a>Data.Traversable#overview</a>.
--   
--   For the class laws see the <b>Laws</b> section of
--   <a>Data.Traversable#laws</a>.
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 <a>traverse_</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   In the first two examples we show each evaluated action mapping to the
--   output structure.
--   
--   <pre>
--   &gt;&gt;&gt; traverse Just [1,2,3,4]
--   Just [1,2,3,4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; traverse id [Right 1, Right 2, Right 3, Right 4]
--   Right [1,2,3,4]
--   </pre>
--   
--   In the next examples, we show that <a>Nothing</a> and <a>Left</a>
--   values short circuit the created structure.
--   
--   <pre>
--   &gt;&gt;&gt; traverse (const Nothing) [1,2,3,4]
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; traverse (\x -&gt; if odd x then Just x else Nothing)  [1,2,3,4]
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; traverse id [Right 1, Right 2, Right 3, Right 4, Left 0]
--   Left 0
--   </pre>
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
--   <a>sequenceA_</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   For the first two examples we show sequenceA fully evaluating a a
--   structure and collecting the results.
--   
--   <pre>
--   &gt;&gt;&gt; sequenceA [Just 1, Just 2, Just 3]
--   Just [1,2,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sequenceA [Right 1, Right 2, Right 3]
--   Right [1,2,3]
--   </pre>
--   
--   The next two example show <a>Nothing</a> and <a>Just</a> will short
--   circuit the resulting structure if present in the input. For more
--   context, check the <a>Traversable</a> instances for <a>Either</a> and
--   <a>Maybe</a>.
--   
--   <pre>
--   &gt;&gt;&gt; sequenceA [Just 1, Just 2, Just 3, Nothing]
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sequenceA [Right 1, Right 2, Right 3, Left 4]
--   Left 4
--   </pre>
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 <a>mapM_</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   <a>mapM</a> is literally a <a>traverse</a> with a type signature
--   restricted to <a>Monad</a>. Its implementation may be more efficient
--   due to additional power of <a>Monad</a>.
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
--   <a>sequence_</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   The first two examples are instances where the input and and output of
--   <a>sequence</a> are isomorphic.
--   
--   <pre>
--   &gt;&gt;&gt; sequence $ Right [1,2,3,4]
--   [Right 1,Right 2,Right 3,Right 4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sequence $ [Right 1,Right 2,Right 3,Right 4]
--   Right [1,2,3,4]
--   </pre>
--   
--   The following examples demonstrate short circuit behavior for
--   <a>sequence</a>.
--   
--   <pre>
--   &gt;&gt;&gt; sequence $ Left [1,2,3,4]
--   Left [1,2,3,4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
--   Left 0
--   </pre>
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

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

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

-- | <pre>
--   empty = mempty
--   </pre>

-- | <i>Deprecated: Use mempty</i>
empty :: Monoid w => w

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

-- | <pre>
--   concat = mconcat
--   </pre>
concat :: Monoid w => [w] -> w

-- | <pre>
--   intercalate = mconcat .: intersperse
--   </pre>
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 ()

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

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

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

-- | <i>O(n)</i> 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 <a>FilePath</a>, the result is just an approximation.
--   
--   Since 0.3.13

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

-- | Since 0.3.13

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

-- | Since 0.3.13

-- | <i>Deprecated: Use id</i>
fpToString :: FilePath -> String

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

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

getLine :: MonadIO m => m Text

getContents :: MonadIO m => m LText

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

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

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

-- | Conversion of values to readable <a>String</a>s.
--   
--   Derived instances of <a>Show</a> have the following properties, which
--   are compatible with derived instances of <a>Read</a>:
--   
--   <ul>
--   <li>The result of <a>show</a> 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.</li>
--   <li>If the constructor is defined to be an infix operator, then
--   <a>showsPrec</a> will produce infix applications of the
--   constructor.</li>
--   <li>the representation will be enclosed in parentheses if the
--   precedence of the top-level constructor in <tt>x</tt> is less than
--   <tt>d</tt> (associativity is ignored). Thus, if <tt>d</tt> is
--   <tt>0</tt> then the result is never surrounded in parentheses; if
--   <tt>d</tt> is <tt>11</tt> it is always surrounded in parentheses,
--   unless it is an atomic expression.</li>
--   <li>If the constructor is defined using record syntax, then
--   <a>show</a> will produce the record-syntax form, with the fields given
--   in the same order as the original declaration.</li>
--   </ul>
--   
--   For example, given the declarations
--   
--   <pre>
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--   </pre>
--   
--   the derived instance of <a>Show</a> is equivalent to
--   
--   <pre>
--   instance (Show a) =&gt; Show (Tree a) where
--   
--          showsPrec d (Leaf m) = showParen (d &gt; app_prec) $
--               showString "Leaf " . showsPrec (app_prec+1) m
--            where app_prec = 10
--   
--          showsPrec d (u :^: v) = showParen (d &gt; up_prec) $
--               showsPrec (up_prec+1) u .
--               showString " :^: "      .
--               showsPrec (up_prec+1) v
--            where up_prec = 5
--   </pre>
--   
--   Note that right-associativity of <tt>:^:</tt> is ignored. For example,
--   
--   <ul>
--   <li><tt><a>show</a> (Leaf 1 :^: Leaf 2 :^: Leaf 3)</tt> produces the
--   string <tt>"Leaf 1 :^: (Leaf 2 :^: Leaf 3)"</tt>.</li>
--   </ul>
class Show a

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

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

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

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

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

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

-- | utility function converting a <a>String</a> 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 <a>Bool</a> parameter is <a>True</a>.
showParen :: Bool -> ShowS -> ShowS

-- | A parser for a type <tt>a</tt>, represented as a function that takes a
--   <a>String</a> and returns a list of possible parses as
--   <tt>(a,<a>String</a>)</tt> pairs.
--   
--   Note that this kind of backtracking parser is very inefficient;
--   reading a large structure may be quite slow (cf <a>ReadP</a>).
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 <a>Read</a> and <a>Show</a> satisfy the
--   following:
--   
--   <ul>
--   <li><tt>(x,"")</tt> is an element of <tt>(<a>readsPrec</a> d
--   (<a>showsPrec</a> d x ""))</tt>.</li>
--   </ul>
--   
--   That is, <a>readsPrec</a> parses the string produced by
--   <a>showsPrec</a>, and delivers the value that <a>showsPrec</a> started
--   with.
readsPrec :: Read a => Int -> ReadS a

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

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

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

-- | The <a>lex</a> 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,
--   <a>lex</a> returns a single successful `lexeme' consisting of the
--   empty string. (Thus <tt><a>lex</a> "" = [("","")]</tt>.) If there is
--   no legal lexeme at the beginning of the input string, <a>lex</a> fails
--   (i.e. returns <tt>[]</tt>).
--   
--   This lexer is not completely faithful to the Haskell lexical syntax in
--   the following respects:
--   
--   <ul>
--   <li>Qualified names are not handled properly</li>
--   <li>Octal and hexadecimal numerics are not recognized as a single
--   token</li>
--   <li>Comments are not treated properly</li>
--   </ul>
lex :: ReadS String
readMay :: Read a => Text -> Maybe a

getChar :: MonadIO m => m Char

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

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