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


-- | "Fixed Prelude" - Mostly total and safe, provides Text and Monad transformers
--   
--   Intro is a modern Prelude which provides safe alternatives for most of
--   the partial functions and follows other best practices, e.g., Text is
--   preferred over String. For String overloading the extension
--   <a>OverloadedStrings</a> should be used. Container types and Monad
--   transformers are provided.
--   
--   Most important - this Prelude tries to keep things simple. This means
--   it just reexports from base and commonly used libraries and adds only
--   very few additional functions. Everything is exported explicitly to
--   provide a stable interface and to improve the quality of the
--   documentation.
@package intro
@version 0.3.2.0


-- | Intro is a modern Prelude which provides safe alternatives for most of
--   the partial functions and follows other best practices, e.g., Text is
--   preferred over String. For String overloading the extension
--   <tt>OverloadedStrings</tt> should be used. Container types and Monad
--   transformers are provided.
--   
--   Most important - this Prelude tries to keep things simple. This means
--   it just reexports from base and commonly used libraries and adds only
--   very few additional functions.
--   
--   List of design decisions:
--   
--   <ul>
--   <li>Keep everything at one place (There are only three modules and
--   Intro.Trustworthy is only there for Safe Haskell)</li>
--   <li>Conservative extension over the base Prelude</li>
--   <li>Rely only on very common external libraries</li>
--   <li>Avoid writing custom functions</li>
--   <li>Export everything explicitly to provide a stable interface and for
--   good documentation</li>
--   <li>Export only total functions or provide safe alternatives (Very few
--   exceptions like div etc.)</li>
--   <li>Prefer Text over String, provide <a>ConvertString</a> and
--   <a>EncodeString</a></li>
--   <li>Provide Monad transformers</li>
--   <li>Provide container types</li>
--   <li>Prefer generic functions</li>
--   <li>Debugging functions, like <a>trace</a> and <a>undefined</a> are
--   available but produce compile time warnings</li>
--   <li>Don't provide error, only panic instead</li>
--   <li>Compatibility with unqualified import of Control.Lens</li>
--   </ul>
--   
--   Some <tt>Prelude</tt> functions are missing from <tt>Intro</tt>. More
--   general variants are available for the following functions:
--   
--   <ul>
--   <li><tt>&gt;&gt;</tt> = <a>*&gt;</a></li>
--   <li><tt>++</tt> = <a>&lt;&gt;</a></li>
--   <li><tt>concat</tt> = <a>mconcat</a></li>
--   <li><a>fmap</a> is replaced by generalized <a>map</a></li>
--   <li><tt>mapM</tt> = <a>traverse</a></li>
--   <li><tt>mapM_</tt> = <a>traverse_</a></li>
--   <li><tt>return</tt> = <a>pure</a></li>
--   <li><tt>sequence</tt> = <a>sequenceA</a></li>
--   <li><tt>sequence_</tt> = <a>sequenceA_</a></li>
--   </ul>
--   
--   Unsafe functions are not provided. Use the '*May' or '*Def'
--   alternatives instead.
--   
--   <ul>
--   <li><tt>cycle</tt>, <tt>head</tt>, <tt>tail</tt>, <tt>init</tt>,
--   <tt>last</tt></li>
--   <li><tt>foldl1</tt>, <tt>foldr1</tt>, <tt>maximum</tt>,
--   <tt>minimum</tt></li>
--   <li><tt>toEnum</tt>, <tt>pred</tt>, <tt>succ</tt></li>
--   <li><tt>read</tt> is replaced by <a>readMaybe</a></li>
--   </ul>
--   
--   These functions are not provided for various reasons:
--   
--   <ul>
--   <li><tt>!!</tt> is unsafe and <i>O(n)</i>. Use a <a>Map</a>
--   instead.</li>
--   <li><tt>lines</tt>, <tt>unlines</tt>, <tt>words</tt> and
--   <tt>unwords</tt> are not provided. Use qualified <a>Text</a> import
--   instead.</li>
--   <li>Instead of <tt>foldl</tt>, it is recommended to use
--   <a>foldl'</a>.</li>
--   <li><tt>lex</tt> is not commonly used. Use a parser combinator library
--   instead.</li>
--   <li><tt>gcd</tt> and <tt>lcm</tt> are not commonly used.</li>
--   <li><tt>error</tt> and <tt>errorWithoutStackTrace</tt> are not
--   provided. Use <a>panic</a> instead.</li>
--   <li><tt>ioError</tt> and <tt>userError</tt> are not provided. Import
--   modules for exception handling separately if needed.</li>
--   <li>Some <a>Read</a> and <a>Show</a> class functions are not provided.
--   Don't write these instances yourself.</li>
--   </ul>
--   
--   Additional types and functions:
--   
--   <ul>
--   <li><a>LText</a> alias for lazy <a>Text</a></li>
--   <li><a>LByteString</a> alias for lazy <a>ByteString</a></li>
--   <li><a>fromFoldable</a> to convert from <a>Foldable</a> to an
--   <a>IsList</a> type</li>
--   <li><a>convertList</a> to convert between two <a>IsList</a> types.
--   This function can be used instead of the <a>toList</a> function
--   originally provided by the <a>IsList</a> class.</li>
--   <li><a>showT</a> and <a>showS</a> are monomorphic <a>show</a>
--   functions.</li>
--   <li><a>&lt;&gt;^</a> lifted composition</li>
--   <li><a>.:</a> function composition</li>
--   <li><a>?:</a> as an alias for <a>fromMaybe</a></li>
--   <li><a>skip</a> as an alias for <tt>pure ()</tt></li>
--   <li><a>panic</a> as a replacement for <tt>error</tt></li>
--   </ul>
module Intro

-- | <tt>const x</tt> is a unary function which evaluates to <tt>x</tt> for
--   all inputs.
--   
--   <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

-- | <tt><a>flip</a> f</tt> takes its (first) two arguments in the reverse
--   order of <tt>f</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; flip (++) "hello" "world"
--   "worldhello"
--   </pre>
flip :: () => a -> b -> c -> b -> a -> c

-- | Application operator. This operator is redundant, since ordinary
--   application <tt>(f x)</tt> means the same as <tt>(f <a>$</a> x)</tt>.
--   However, <a>$</a> has low, right-associative binding precedence, so it
--   sometimes allows parentheses to be omitted; for example:
--   
--   <pre>
--   f $ g $ h x  =  f (g (h x))
--   </pre>
--   
--   It is also useful in higher-order situations, such as <tt><a>map</a>
--   (<a>$</a> 0) xs</tt>, or <tt><a>zipWith</a> (<a>$</a>) fs xs</tt>.
($) :: () => 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 $!

-- | <a>&amp;</a> is a reverse application operator. This provides
--   notational convenience. Its precedence is one higher than that of the
--   forward application operator <a>$</a>, which allows <a>&amp;</a> to be
--   nested in <a>$</a>.
--   
--   <pre>
--   &gt;&gt;&gt; 5 &amp; (+1) &amp; show
--   "6"
--   </pre>
(&) :: () => a -> a -> b -> b
infixl 1 &

-- | <tt><a>fix</a> f</tt> is the least fixed point of the function
--   <tt>f</tt>, i.e. the least defined <tt>x</tt> such that <tt>f x =
--   x</tt>.
--   
--   For example, we can write the factorial function using direct
--   recursion as
--   
--   <pre>
--   &gt;&gt;&gt; let fac n = if n &lt;= 1 then 1 else n * fac (n-1) in fac 5
--   120
--   </pre>
--   
--   This uses the fact that Haskell’s <tt>let</tt> introduces recursive
--   bindings. We can rewrite this definition using <a>fix</a>,
--   
--   <pre>
--   &gt;&gt;&gt; fix (\rec n -&gt; if n &lt;= 1 then 1 else n * rec (n-1)) 5
--   120
--   </pre>
--   
--   Instead of making a recursive call, we introduce a dummy parameter
--   <tt>rec</tt>; when used within <a>fix</a>, this parameter then refers
--   to <tt>fix'</tt> argument, hence the recursion is reintroduced.
fix :: () => a -> a -> a
on :: () => b -> b -> c -> a -> b -> a -> a -> c
infixl 0 `on`

-- | Compose functions with one argument with function with two arguments.
--   
--   <tt>f .: g = \x y -&gt; f (g x y)</tt>.
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
infixr 8 .:

-- | <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

-- | The value of <tt>seq 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). <tt>seq</tt> is
--   usually introduced to improve performance by avoiding unneeded
--   laziness.
--   
--   A note on evaluation order: the expression <tt>seq a b</tt> does
--   <i>not</i> guarantee that <tt>a</tt> will be evaluated before
--   <tt>b</tt>. The only guarantee given by <tt>seq</tt> is that the both
--   <tt>a</tt> and <tt>b</tt> will be evaluated before <tt>seq</tt>
--   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

-- | Uninhabited data type
data Void
data Bool
False :: Bool
True :: Bool

-- | Boolean "and"
(&&) :: Bool -> Bool -> Bool
infixr 3 &&

-- | Boolean "or"
(||) :: Bool -> Bool -> Bool
infixr 2 ||

-- | Case analysis for the <a>Bool</a> type. <tt><a>bool</a> x y p</tt>
--   evaluates to <tt>x</tt> when <tt>p</tt> is <a>False</a>, and evaluates
--   to <tt>y</tt> when <tt>p</tt> is <a>True</a>.
--   
--   This is equivalent to <tt>if p then y else x</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> x y p</tt> and <tt>if p then y else
--   x</tt> are equivalent:
--   
--   <pre>
--   &gt;&gt;&gt; let p = True; x = "bar"; y = "foo"
--   
--   &gt;&gt;&gt; bool x y p == if p then y else x
--   True
--   
--   &gt;&gt;&gt; let p = False
--   
--   &gt;&gt;&gt; bool x y p == if p then y else x
--   True
--   </pre>
bool :: () => a -> a -> Bool -> a

-- | 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

-- | 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

-- | 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 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 and
--   <a>Maybe</a> value. If the <a>Maybe</a> is <a>Nothing</a>, it returns
--   the default values; 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 <tt>readMaybe</tt>. If we fail to
--   parse an integer, we want to return <tt>0</tt> by default:
--   
--   <pre>
--   &gt;&gt;&gt; import Text.Read ( readMaybe )
--   
--   &gt;&gt;&gt; fromMaybe 0 (readMaybe "5")
--   5
--   
--   &gt;&gt;&gt; fromMaybe 0 (readMaybe "")
--   0
--   </pre>
fromMaybe :: () => a -> Maybe a -> a

-- | An infix form of <a>fromMaybe</a> with arguments flipped.
(?:) :: Maybe a -> a -> a
infix 1 ?:

-- | 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>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 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>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 <tt>readMaybe</tt>. 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 Text.Read ( readMaybe )
--   
--   &gt;&gt;&gt; maybe 0 (*2) (readMaybe "5")
--   10
--   
--   &gt;&gt;&gt; maybe 0 (*2) (readMaybe "")
--   0
--   </pre>
--   
--   Apply <tt>show</tt> 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

-- | The <a>IsList</a> class and its methods are intended to be used in
--   conjunction with the OverloadedLists extension.
class IsList l where {
    type family Item l :: *;
}

-- | The <a>fromList</a> function constructs the structure <tt>l</tt> from
--   the given list of <tt>Item l</tt>
fromList :: IsList l => [Item l] -> l

-- | Convert between two different <a>IsList</a> types. This function can
--   be used instead of the <a>toList</a> function originally provided by
--   the <a>IsList</a> class.
convertList :: (IsList a, IsList b, Item a ~ Item b) => a -> b

-- | Convert from <a>Foldable</a> to an <a>IsList</a> type.
fromFoldable :: (Foldable f, IsList a) => f (Item 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:
--   
--   <pre>
--   break (&gt; 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
--   break (&lt; 9) [1,2,3] == ([],[1,2,3])
--   break (&gt; 9) [1,2,3] == ([1,2,3],[])
--   </pre>
--   
--   <a>break</a> <tt>p</tt> is equivalent to <tt><a>span</a> (<a>not</a> .
--   p)</tt>.
break :: () => a -> Bool -> [a] -> ([a], [a])

-- | Find the first instance of <tt>needle</tt> in <tt>haystack</tt>. The
--   first element of the returned tuple is the prefix of <tt>haystack</tt>
--   before <tt>needle</tt> is matched. The second is the remainder of
--   <tt>haystack</tt>, starting with the match. If you want the remainder
--   <i>without</i> the match, use <a>stripInfix</a>.
--   
--   <pre>
--   breakOn "::" "a::b::c" == ("a", "::b::c")
--   breakOn "/" "foobar"   == ("foobar", "")
--   \needle haystack -&gt; let (prefix,match) = breakOn needle haystack in prefix ++ match == haystack
--   </pre>
breakOn :: Eq a => [a] -> [a] -> ([a], [a])

-- | Similar to <a>breakOn</a>, but searches from the end of the string.
--   
--   The first element of the returned tuple is the prefix of
--   <tt>haystack</tt> up to and including the last match of
--   <tt>needle</tt>. The second is the remainder of <tt>haystack</tt>,
--   following the match.
--   
--   <pre>
--   breakOnEnd "::" "a::b::c" == ("a::b::", "c")
--   </pre>
breakOnEnd :: Eq a => [a] -> [a] -> ([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>:
--   
--   <pre>
--   drop 6 "Hello World!" == "World!"
--   drop 3 [1,2,3,4,5] == [4,5]
--   drop 3 [1,2] == []
--   drop 3 [] == []
--   drop (-1) [1,2] == [1,2]
--   drop 0 [1,2] == [1,2]
--   </pre>
--   
--   It is an instance of the more general <a>genericDrop</a>, in which
--   <tt>n</tt> may be of any integral type.
drop :: () => Int -> [a] -> [a]

-- | Drop a number of elements from the end of the list.
--   
--   <pre>
--   dropEnd 3 "hello"  == "he"
--   dropEnd 5 "bye"    == ""
--   dropEnd (-1) "bye" == "bye"
--   \i xs -&gt; dropEnd i xs `isPrefixOf` xs
--   \i xs -&gt; length (dropEnd i xs) == max 0 (length xs - max 0 i)
--   \i -&gt; take 3 (dropEnd 5 [i..]) == take 3 [i..]
--   </pre>
dropEnd :: () => Int -> [a] -> [a]

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

-- | The <a>dropWhileEnd</a> function drops the largest suffix of a list in
--   which the given predicate holds for all elements. For example:
--   
--   <pre>
--   &gt;&gt;&gt; dropWhileEnd isSpace "foo\n"
--   "foo"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; dropWhileEnd isSpace "foo bar"
--   "foo bar"
--   </pre>
--   
--   <pre>
--   dropWhileEnd isSpace ("foo\n" ++ undefined) == "foo" ++ undefined
--   </pre>
dropWhileEnd :: () => a -> Bool -> [a] -> [a]

-- | <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>
filter :: () => a -> Bool -> [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 contains only equal elements. For
--   example,
--   
--   <pre>
--   &gt;&gt;&gt; group "Mississippi"
--   ["M","i","ss","i","ss","i","pp","i"]
--   </pre>
--   
--   It is a special case of <a>groupBy</a>, which allows the programmer to
--   supply their own equality test.
group :: Eq a => [a] -> [[a]]

-- | The <a>groupBy</a> function is the non-overloaded version of
--   <a>group</a>.
groupBy :: () => a -> a -> Bool -> [a] -> [[a]]

-- | A version of <a>group</a> where the equality is done on some extracted
--   value.
groupOn :: Eq b => a -> b -> [a] -> [[a]]

-- | A combination of <a>group</a> and <a>sort</a>.
--   
--   <pre>
--   groupSort [(1,'t'),(3,'t'),(2,'e'),(2,'s')] == [(1,"t"),(2,"es"),(3,"t")]
--   \xs -&gt; map fst (groupSort xs) == sort (nub (map fst xs))
--   \xs -&gt; concatMap snd (groupSort xs) == map snd (sortOn fst xs)
--   </pre>
groupSort :: Ord k => [(k, v)] -> [(k, [v])]

-- | A combination of <a>group</a> and <a>sort</a>, using a predicate to
--   compare on.
--   
--   <pre>
--   groupSortBy (compare `on` length) ["test","of","sized","item"] == [["of"],["test","item"],["sized"]]
--   </pre>
groupSortBy :: () => a -> a -> Ordering -> [a] -> [[a]]

-- | A combination of <a>group</a> and <a>sort</a>, using a part of the
--   value to compare on.
--   
--   <pre>
--   groupSortOn length ["test","of","sized","item"] == [["of"],["test","item"],["sized"]]
--   </pre>
groupSortOn :: Ord b => a -> b -> [a] -> [[a]]

-- | The <a>inits</a> function returns all initial segments of the
--   argument, shortest first. For example,
--   
--   <pre>
--   &gt;&gt;&gt; inits "abc"
--   ["","a","ab","abc"]
--   </pre>
--   
--   Note that <a>inits</a> has the following strictness property:
--   <tt>inits (xs ++ _|_) = inits xs ++ _|_</tt>
--   
--   In particular, <tt>inits _|_ = [] : _|_</tt>
inits :: () => [a] -> [[a]]

-- | <a>intercalate</a> <tt>xs xss</tt> is equivalent to <tt>(<a>concat</a>
--   (<a>intersperse</a> xs xss))</tt>. It inserts the list <tt>xs</tt> in
--   between the lists in <tt>xss</tt> and concatenates the result.
--   
--   <pre>
--   &gt;&gt;&gt; intercalate ", " ["Lorem", "ipsum", "dolor"]
--   "Lorem, ipsum, dolor"
--   </pre>
intercalate :: () => [a] -> [[a]] -> [a]

-- | The <a>intersperse</a> function takes an element and a list and
--   `intersperses' that element between the elements of the list. For
--   example,
--   
--   <pre>
--   &gt;&gt;&gt; intersperse ',' "abcde"
--   "a,b,c,d,e"
--   </pre>
intersperse :: () => a -> [a] -> [a]

-- | The <a>isPrefixOf</a> function takes two lists and returns <a>True</a>
--   iff the first list is a prefix of the second.
--   
--   <pre>
--   &gt;&gt;&gt; "Hello" `isPrefixOf` "Hello World!"
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; "Hello" `isPrefixOf` "Wello Horld!"
--   False
--   </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. The second list must be
--   finite.
--   
--   <pre>
--   &gt;&gt;&gt; "ld!" `isSuffixOf` "Hello World!"
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; "World" `isSuffixOf` "Hello World!"
--   False
--   </pre>
isSuffixOf :: Eq a => [a] -> [a] -> Bool

-- | <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>
--   
--   Note that <a>iterate</a> is lazy, potentially leading to thunk
--   build-up if the consumer doesn't force each iterate. See 'iterate\''
--   for a strict variant of this function.
iterate :: () => a -> a -> a -> [a]

-- | 'iterate\'' is the strict version of <a>iterate</a>.
--   
--   It ensures that the result of each application of force to weak head
--   normal form before proceeding.
iterate' :: () => a -> a -> a -> [a]

-- | <a>lookup</a> <tt>key assocs</tt> looks up a key in an association
--   list.
lookup :: Eq a => a -> [(a, b)] -> Maybe b

-- | <i>O(n log n)</i>. The <a>nubOrd</a> function removes duplicate
--   elements from a list. In particular, it keeps only the first
--   occurrence of each element. Unlike the standard <a>nub</a> operator,
--   this version requires an <a>Ord</a> instance and consequently runs
--   asymptotically faster.
--   
--   <pre>
--   nubOrd "this is a test" == "this ae"
--   nubOrd (take 4 ("this" ++ undefined)) == "this"
--   \xs -&gt; nubOrd xs == nub xs
--   </pre>
nubOrd :: Ord a => [a] -> [a]

-- | A version of <a>nubOrd</a> with a custom predicate.
--   
--   <pre>
--   nubOrdBy (compare `on` length) ["a","test","of","this"] == ["a","test","of"]
--   </pre>
nubOrdBy :: () => a -> a -> Ordering -> [a] -> [a]

-- | A version of <a>nubOrd</a> which operates on a portion of the value.
--   
--   <pre>
--   nubOrdOn length ["a","test","of","this"] == ["a","test","of"]
--   </pre>
nubOrdOn :: Ord b => a -> b -> [a] -> [a]

-- | The <a>permutations</a> function returns the list of all permutations
--   of the argument.
--   
--   <pre>
--   &gt;&gt;&gt; permutations "abc"
--   ["abc","bac","cba","bca","cab","acb"]
--   </pre>
permutations :: () => [a] -> [[a]]

-- | <a>repeat</a> <tt>x</tt> is an infinite list, with <tt>x</tt> the
--   value of every element.
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.
replicate :: () => Int -> a -> [a]

-- | <a>reverse</a> <tt>xs</tt> returns the elements of <tt>xs</tt> in
--   reverse order. <tt>xs</tt> must be finite.
reverse :: () => [a] -> [a]

-- | <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>
scanl :: () => b -> a -> b -> b -> [a] -> [b]

-- | <a>scanr</a> is the right-to-left dual of <a>scanl</a>. Note that
--   
--   <pre>
--   head (scanr f z xs) == foldr f z xs.
--   </pre>
scanr :: () => a -> b -> b -> b -> [a] -> [b]

-- | 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 from lowest to highest, keeping duplicates
--   in the order they appeared in the input.
--   
--   <pre>
--   &gt;&gt;&gt; sort [1,6,4,3,2,5]
--   [1,2,3,4,5,6]
--   </pre>
sort :: Ord a => [a] -> [a]

-- | The <a>sortBy</a> function is the non-overloaded version of
--   <a>sort</a>.
--   
--   <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]

-- | Sort a list by comparing the results of a key function applied to each
--   element. <tt>sortOn f</tt> is equivalent to <tt>sortBy (comparing
--   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 Schwartzian transform.
--   
--   Elements are arranged from from lowest to highest, keeping duplicates
--   in the order they appeared in the input.
--   
--   <pre>
--   &gt;&gt;&gt; sortOn fst [(2, "world"), (4, "!"), (1, "Hello")]
--   [(1,"Hello"),(2,"world"),(4,"!")]
--   </pre>
sortOn :: Ord b => a -> b -> [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 longest prefix (possibly empty)
--   of <tt>xs</tt> of elements that satisfy <tt>p</tt> and second element
--   is the remainder of the list:
--   
--   <pre>
--   span (&lt; 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
--   span (&lt; 9) [1,2,3] == ([1,2,3],[])
--   span (&lt; 0) [1,2,3] == ([],[1,2,3])
--   </pre>
--   
--   <a>span</a> <tt>p xs</tt> is equivalent to <tt>(<a>takeWhile</a> p xs,
--   <a>dropWhile</a> p xs)</tt>
span :: () => a -> Bool -> [a] -> ([a], [a])

-- | Span, but from the end.
--   
--   <pre>
--   spanEnd isUpper "youRE" == ("you","RE")
--   spanEnd (not . isSpace) "x y z" == ("x y ","z")
--   \f xs -&gt; uncurry (++) (spanEnd f xs) == xs
--   \f xs -&gt; spanEnd f xs == swap (both reverse (span f (reverse xs)))
--   </pre>
spanEnd :: () => a -> Bool -> [a] -> ([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:
--   
--   <pre>
--   splitAt 6 "Hello World!" == ("Hello ","World!")
--   splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5])
--   splitAt 1 [1,2,3] == ([1],[2,3])
--   splitAt 3 [1,2,3] == ([1,2,3],[])
--   splitAt 4 [1,2,3] == ([1,2,3],[])
--   splitAt 0 [1,2,3] == ([],[1,2,3])
--   splitAt (-1) [1,2,3] == ([],[1,2,3])
--   </pre>
--   
--   It is equivalent to <tt>(<a>take</a> n xs, <a>drop</a> n xs)</tt> when
--   <tt>n</tt> is not <tt>_|_</tt> (<tt>splitAt _|_ xs = _|_</tt>).
--   <a>splitAt</a> is an instance of the more general
--   <a>genericSplitAt</a>, in which <tt>n</tt> may be of any integral
--   type.
splitAt :: () => Int -> [a] -> ([a], [a])

-- | Splits a list into components delimited by separators, where the
--   predicate returns True for a separator element. The resulting
--   components do not contain the separators. Two adjacent separators
--   result in an empty component in the output.
--   
--   <pre>
--   split (== 'a') "aabbaca" == ["","","bb","c",""]
--   split (== 'a') ""        == [""]
--   split (== ':') "::xyz:abc::123::" == ["","","xyz","abc","","123","",""]
--   split (== ',') "my,list,here" == ["my","list","here"]
--   </pre>
split :: () => a -> Bool -> [a] -> [[a]]

-- | Break a list into pieces separated by the first list argument,
--   consuming the delimiter. An empty delimiter is invalid, and will cause
--   an error to be raised.
--   
--   <pre>
--   splitOn "\r\n" "a\r\nb\r\nd\r\ne" == ["a","b","d","e"]
--   splitOn "aaa"  "aaaXaaaXaaaXaaa"  == ["","X","X","X",""]
--   splitOn "x"    "x"                == ["",""]
--   splitOn "x"    ""                 == [""]
--   \s x -&gt; s /= "" ==&gt; intercalate s (splitOn s x) == x
--   \c x -&gt; splitOn [c] x                           == split (==c) x
--   </pre>
splitOn :: (Partial, Eq a) => [a] -> [a] -> [[a]]

-- | The <a>subsequences</a> function returns the list of all subsequences
--   of the argument.
--   
--   <pre>
--   &gt;&gt;&gt; subsequences "abc"
--   ["","a","b","ab","c","ac","bc","abc"]
--   </pre>
subsequences :: () => [a] -> [[a]]

-- | The <a>tails</a> function returns all final segments of the argument,
--   longest first. For example,
--   
--   <pre>
--   &gt;&gt;&gt; tails "abc"
--   ["abc","bc","c",""]
--   </pre>
--   
--   Note that <a>tails</a> has the following strictness property:
--   <tt>tails _|_ = _|_ : _|_</tt>
tails :: () => [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>:
--   
--   <pre>
--   take 5 "Hello World!" == "Hello"
--   take 3 [1,2,3,4,5] == [1,2,3]
--   take 3 [1,2] == [1,2]
--   take 3 [] == []
--   take (-1) [1,2] == []
--   take 0 [1,2] == []
--   </pre>
--   
--   It is an instance of the more general <a>genericTake</a>, in which
--   <tt>n</tt> may be of any integral type.
take :: () => Int -> [a] -> [a]

-- | Take a number of elements from the end of the list.
--   
--   <pre>
--   takeEnd 3 "hello"  == "llo"
--   takeEnd 5 "bye"    == "bye"
--   takeEnd (-1) "bye" == ""
--   \i xs -&gt; takeEnd i xs `isSuffixOf` xs
--   \i xs -&gt; length (takeEnd i xs) == min (max 0 i) (length xs)
--   </pre>
takeEnd :: () => 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>:
--   
--   <pre>
--   takeWhile (&lt; 3) [1,2,3,4,1,2,3,4] == [1,2]
--   takeWhile (&lt; 9) [1,2,3] == [1,2,3]
--   takeWhile (&lt; 0) [1,2,3] == []
--   </pre>
takeWhile :: () => a -> Bool -> [a] -> [a]

-- | The <a>transpose</a> function transposes the rows and columns of its
--   argument. For example,
--   
--   <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>
transpose :: () => [[a]] -> [[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>
--   
--   A simple use of unfoldr:
--   
--   <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>
unfoldr :: () => b -> Maybe (a, b) -> b -> [a]

-- | <a>unzip</a> transforms a list of pairs into a list of first
--   components and a list of second components.
unzip :: () => [(a, b)] -> ([a], [b])

-- | The <a>unzip3</a> function takes a list of triples and returns three
--   lists, analogous to <a>unzip</a>.
unzip3 :: () => [(a, b, c)] -> ([a], [b], [c])

-- | <a>zip</a> takes two lists and returns a list of corresponding pairs.
--   If one input list is short, excess elements of the longer list are
--   discarded.
--   
--   <a>zip</a> is right-lazy:
--   
--   <pre>
--   zip [] _|_ = []
--   </pre>
zip :: () => [a] -> [b] -> [(a, b)]

-- | <a>zip3</a> takes three lists and returns a list of triples, analogous
--   to <a>zip</a>.
zip3 :: () => [a] -> [b] -> [c] -> [(a, b, c)]

-- | <a>zipWith</a> generalises <a>zip</a> by zipping with the function
--   given as the first argument, instead of a tupling function. For
--   example, <tt><a>zipWith</a> (+)</tt> is applied to two lists to
--   produce the list of corresponding sums.
--   
--   <a>zipWith</a> is right-lazy:
--   
--   <pre>
--   zipWith f [] _|_ = []
--   </pre>
zipWith :: () => a -> b -> c -> [a] -> [b] -> [c]

-- | The <a>zipWith3</a> function takes a function which combines three
--   elements, as well as three lists and returns a list of their
--   point-wise combination, analogous to <a>zipWith</a>.
zipWith3 :: () => a -> b -> c -> d -> [a] -> [b] -> [c] -> [d]
headDef :: () => a -> [a] -> a
headMay :: () => [a] -> Maybe a
initDef :: () => [a] -> [a] -> [a]
initMay :: () => [a] -> Maybe [a]
lastDef :: () => a -> [a] -> a
lastMay :: () => [a] -> Maybe a

-- | <pre>
--   tailDef [12] [] = [12]
--   tailDef [12] [1,3,4] = [3,4]
--   </pre>
tailDef :: () => [a] -> [a] -> [a]

-- | <pre>
--   tailMay [] = Nothing
--   tailMay [1,3,4] = Just [3,4]
--   </pre>
tailMay :: () => [a] -> Maybe [a]
cycleMay :: () => [a] -> Maybe [a]
cycleDef :: () => [a] -> [a] -> [a]

-- | Non-empty (and non-strict) list type.
data NonEmpty a
(:|) :: a -> [a] -> NonEmpty a

-- | <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, x1 `f` (x2 `f` x3), ...]
--   </pre>
scanl1 :: () => a -> a -> a -> NonEmpty a -> NonEmpty a

-- | <a>scanr1</a> is a variant of <a>scanr</a> that has no starting value
--   argument.
scanr1 :: () => a -> a -> a -> NonEmpty a -> NonEmpty a

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

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

-- | <a>curry</a> converts 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

-- | <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

-- | Swap the components of a pair.
swap :: () => (a, b) -> (b, 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

-- | 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
--   <tt>length</tt> 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

-- | Return the contents of a <a>Left</a>-value or a default value
--   otherwise.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; fromLeft 1 (Left 3)
--   3
--   
--   &gt;&gt;&gt; fromLeft 1 (Right "foo")
--   1
--   </pre>
fromLeft :: () => a -> Either a b -> a

-- | Return the contents of a <a>Right</a>-value or a default value
--   otherwise.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; fromRight 1 (Right 3)
--   3
--   
--   &gt;&gt;&gt; fromRight 1 (Left "foo")
--   1
--   </pre>
fromRight :: () => b -> Either a b -> b

-- | Return <a>True</a> if the given value is a <a>Left</a>-value,
--   <a>False</a> otherwise.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; isLeft (Left "foo")
--   True
--   
--   &gt;&gt;&gt; isLeft (Right 3)
--   False
--   </pre>
--   
--   Assuming a <a>Left</a> value signifies some sort of error, we can use
--   <a>isLeft</a> to write a very simple error-reporting function that
--   does absolutely nothing in the case of success, and outputs "ERROR" if
--   any error occurred.
--   
--   This example shows how <a>isLeft</a> might be used to avoid pattern
--   matching when one does not care about the value contained in the
--   constructor:
--   
--   <pre>
--   &gt;&gt;&gt; import Control.Monad ( when )
--   
--   &gt;&gt;&gt; let report e = when (isLeft e) $ putStrLn "ERROR"
--   
--   &gt;&gt;&gt; report (Right 1)
--   
--   &gt;&gt;&gt; report (Left "parse error")
--   ERROR
--   </pre>
isLeft :: () => Either a b -> Bool

-- | Return <a>True</a> if the given value is a <a>Right</a>-value,
--   <a>False</a> otherwise.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; isRight (Left "foo")
--   False
--   
--   &gt;&gt;&gt; isRight (Right 3)
--   True
--   </pre>
--   
--   Assuming a <a>Left</a> value signifies some sort of error, we can use
--   <a>isRight</a> to write a very simple reporting function that only
--   outputs "SUCCESS" when a computation has succeeded.
--   
--   This example shows how <a>isRight</a> might be used to avoid pattern
--   matching when one does not care about the value contained in the
--   constructor:
--   
--   <pre>
--   &gt;&gt;&gt; import Control.Monad ( when )
--   
--   &gt;&gt;&gt; let report e = when (isRight e) $ putStrLn "SUCCESS"
--   
--   &gt;&gt;&gt; report (Left "parse error")
--   
--   &gt;&gt;&gt; report (Right 1)
--   SUCCESS
--   </pre>
isRight :: () => Either a b -> Bool

-- | 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]

-- | 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])

-- | Given an <a>Either</a>, convert it to a <a>Maybe</a>, where
--   <a>Left</a> becomes <a>Nothing</a>.
--   
--   <pre>
--   \x -&gt; eitherToMaybe (Left x) == Nothing
--   \x -&gt; eitherToMaybe (Right x) == Just x
--   </pre>
eitherToMaybe :: () => Either a b -> Maybe b

-- | Given a <a>Maybe</a>, convert it to an <a>Either</a>, providing a
--   suitable value for the <a>Left</a> should the value be <a>Nothing</a>.
--   
--   <pre>
--   \a b -&gt; maybeToEither a (Just b) == Right b
--   \a -&gt; maybeToEither a Nothing == Left a
--   </pre>
maybeToEither :: () => a -> Maybe b -> Either a b

-- | The character type <a>Char</a> is an enumeration whose values
--   represent Unicode (or equivalently ISO/IEC 10646) code points (i.e.
--   characters, see <a>http://www.unicode.org/</a> for details). This set
--   extends the ISO 8859-1 (Latin-1) character set (the first 256
--   characters), which is itself an extension of the ASCII character set
--   (the first 128 characters). A character literal in Haskell has type
--   <a>Char</a>.
--   
--   To convert a <a>Char</a> to or from the corresponding <a>Int</a> value
--   defined by Unicode, use <a>toEnum</a> and <a>fromEnum</a> from the
--   <a>Enum</a> class respectively (or equivalently <tt>ord</tt> and
--   <tt>chr</tt>).
data Char

-- | A <a>String</a> is a list of characters. String constants in Haskell
--   are values of type <a>String</a>.
type String = [Char]

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

-- | Alias for lazy <a>Text</a>
type LText = Text

-- | 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

-- | Alias for lazy <a>ByteString</a>
type LByteString = ByteString

-- | A compact representation of a <a>Word8</a> vector.
--   
--   It has a lower memory overhead than a <a>ByteString</a> and and does
--   not contribute to heap fragmentation. It can be converted to or from a
--   <a>ByteString</a> (at the cost of copying the string data). It
--   supports very few other operations.
--   
--   It is suitable for use as an internal representation for code that
--   needs to keep many short strings in memory, but it <i>should not</i>
--   be used as an interchange type. That is, it should not generally be
--   used in public APIs. The <a>ByteString</a> type is usually more
--   suitable for use in interfaces; it is more flexible and it supports a
--   wide range of operations.
data ShortByteString

-- | Class for string-like datastructures; used by the overloaded string
--   extension (-XOverloadedStrings in GHC).
class IsString a
fromString :: IsString a => String -> a

-- | Conversion of strings to other string types
--   
--   <pre>
--   (<a>convertString</a> :: b -&gt; a)         . (<a>convertString</a> :: a -&gt; b) ≡ (<a>id</a>      :: a -&gt; a)
--   (<a>convertString</a> :: b -&gt; <a>Maybe</a> a)   . (<a>convertString</a> :: a -&gt; b) ≡ (<tt>Just</tt>    :: a -&gt; <a>Maybe</a> a)
--   (<a>convertString</a> :: b -&gt; <a>Lenient</a> a) . (<a>convertString</a> :: a -&gt; b) ≡ (<a>Lenient</a> :: a -&gt; <a>Lenient</a> a)
--   </pre>
class ConvertString a b

-- | Convert a string to another string type
convertString :: ConvertString a b => a -> b

-- | Encode and decode strings as a byte sequence
--   
--   <pre>
--   <a>decodeString</a>        . <a>encodeString</a> ≡ <tt>Just</tt>
--   <a>decodeStringLenient</a> . <a>encodeString</a> ≡ <a>id</a>
--   </pre>
class (ConvertString a b, ConvertString b (Maybe a), ConvertString b (Lenient a)) => EncodeString a b

-- | Encode a string as a byte sequence
encodeString :: EncodeString a b => a -> b

-- | Lenient decoding of byte sequence
--   
--   Lenient means that invalid characters are replaced by the Unicode
--   replacement character '\FFFD'.
decodeStringLenient :: EncodeString a b => b -> a

-- | Decode byte sequence
--   
--   If the decoding fails, return Nothing.
decodeString :: EncodeString a b => b -> Maybe a

-- | Newtype wrapper for a string which was decoded leniently.
newtype Lenient a
Lenient :: a -> Lenient a
[getLenient] :: Lenient a -> a

-- | A Map from keys <tt>k</tt> to values <tt>a</tt>.
data Map k a

-- | A set of values <tt>a</tt>.
data Set a

-- | A map of integers to values <tt>a</tt>.
data IntMap a

-- | A set of integers.
data IntSet

-- | 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 set of values. A set cannot contain duplicate values.
data HashSet a

-- | The class of types that can be converted to a hash value.
--   
--   Minimal implementation: <a>hashWithSalt</a>.
class Hashable a

-- | 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>
--   </ul>
hashWithSalt :: Hashable a => Int -> a -> Int

-- | 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
class Hashable1 (t :: * -> *)
class Hashable2 (t :: * -> * -> *)

-- | A difference list is a function that, given a list, returns the
--   original contents of the difference list prepended to the given list.
--   
--   This structure supports <i>O(1)</i> append and snoc operations on
--   lists, making it very useful for append-heavy uses (esp. left-nested
--   uses of <a>++</a>), such as logging and pretty printing.
--   
--   Here is an example using DList as the state type when printing a tree
--   with the Writer monad:
--   
--   <pre>
--   import Control.Monad.Writer
--   import Data.DList
--   
--   data Tree a = Leaf a | Branch (Tree a) (Tree a)
--   
--   flatten_writer :: Tree x -&gt; DList x
--   flatten_writer = snd . runWriter . flatten
--       where
--         flatten (Leaf x)     = tell (singleton x)
--         flatten (Branch x y) = flatten x &gt;&gt; flatten y
--   </pre>
data DList a

-- | General-purpose finite sequences.
data Seq a

-- | Invariant: <a>Jn#</a> and <a>Jp#</a> are used iff value doesn't fit in
--   <a>S#</a>
--   
--   Useful properties resulting from the invariants:
--   
--   <ul>
--   <li><pre>abs (<a>S#</a> _) &lt;= abs (<a>Jp#</a> _)</pre></li>
--   <li><pre>abs (<a>S#</a> _) &lt; abs (<a>Jn#</a> _)</pre></li>
--   </ul>
data Integer

-- | Type representing arbitrary-precision non-negative integers.
--   
--   <pre>
--   &gt;&gt;&gt; 2^20 :: Natural
--   1267650600228229401496703205376
--   </pre>
--   
--   Operations whose result would be negative <tt><tt>throw</tt>
--   (<tt>Underflow</tt> :: <tt>ArithException</tt>)</tt>,
--   
--   <pre>
--   &gt;&gt;&gt; -1 :: Natural
--   *** Exception: arithmetic underflow
--   </pre>
data Natural

-- | 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

-- | 8-bit signed integer type
data Int8

-- | 16-bit signed integer type
data Int16

-- | 32-bit signed integer type
data Int32

-- | 64-bit signed integer type
data Int64

-- | 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

-- | 16-bit unsigned integer type
data Word16

-- | 32-bit unsigned integer type
data Word32

-- | 64-bit unsigned integer type
data Word64

-- | 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

-- | Rational numbers, with numerator and denominator of some
--   <a>Integral</a> type.
data Ratio a

-- | 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

-- | Forms the ratio of two integral numbers.
(%) :: Integral a => a -> a -> Ratio a
infixl 7 %

-- | Extract the numerator of the ratio in reduced form: the numerator and
--   denominator have no common factor and the denominator is positive.
numerator :: () => Ratio a -> a

-- | Extract the denominator of the ratio in reduced form: the numerator
--   and denominator have no common factor and the denominator is positive.
denominator :: () => Ratio a -> a

-- | <a>approxRational</a>, applied to two real fractional numbers
--   <tt>x</tt> and <tt>epsilon</tt>, returns the simplest rational number
--   within <tt>epsilon</tt> of <tt>x</tt>. A rational number <tt>y</tt> is
--   said to be <i>simpler</i> than another <tt>y'</tt> if
--   
--   <ul>
--   <li><tt><a>abs</a> (<a>numerator</a> y) &lt;= <a>abs</a>
--   (<a>numerator</a> y')</tt>, and</li>
--   <li><tt><a>denominator</a> y &lt;= <a>denominator</a> y'</tt>.</li>
--   </ul>
--   
--   Any real interval contains a unique simplest rational; in particular,
--   note that <tt>0/1</tt> is the simplest rational of all.
approxRational :: RealFrac a => a -> a -> Rational

-- | Basic numeric class.
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

-- | 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

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

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

-- | general coercion to fractional types
realToFrac :: (Real a, Fractional b) => a -> b

-- | Integral numbers, supporting integer division.
class (Real a, Enum a) => Integral a

-- | integer division truncated toward zero
quot :: Integral a => a -> a -> a

-- | integer remainder, satisfying
--   
--   <pre>
--   (x `quot` y)*y + (x `rem` y) == x
--   </pre>
rem :: Integral a => a -> a -> a

-- | integer division truncated toward negative infinity
div :: Integral a => a -> a -> a

-- | integer modulus, satisfying
--   
--   <pre>
--   (x `div` y)*y + (x `mod` y) == x
--   </pre>
mod :: Integral a => a -> a -> a

-- | simultaneous <a>quot</a> and <a>rem</a>
quotRem :: Integral a => a -> a -> (a, a)

-- | simultaneous <a>div</a> and <a>mod</a>
divMod :: Integral a => a -> a -> (a, a)

-- | conversion to <a>Integer</a>
toInteger :: Integral a => a -> Integer

-- | general coercion from integral types
fromIntegral :: (Integral a, Num b) => a -> b
even :: Integral a => a -> Bool
odd :: Integral a => a -> Bool

-- | Fractional numbers, supporting real division.
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

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

-- | Trigonometric and hyperbolic functions and related functions.
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

-- | 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><tt>uncurry</tt> <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>Bits</a> class defines bitwise operations over integral types.
--   
--   <ul>
--   <li>Bits are numbered from 0 with bit 0 being the least significant
--   bit.</li>
--   </ul>
class Eq a => Bits a

-- | Bitwise "and"
(.&.) :: Bits a => a -> a -> a

-- | Bitwise "or"
(.|.) :: Bits a => a -> a -> a

-- | Bitwise "xor"
xor :: Bits a => a -> a -> a

-- | Reverse all the bits in the argument
complement :: Bits a => a -> a

-- | <tt><a>shift</a> x i</tt> shifts <tt>x</tt> left by <tt>i</tt> bits if
--   <tt>i</tt> is positive, or right by <tt>-i</tt> bits otherwise. Right
--   shifts perform sign extension on signed number types; i.e. they fill
--   the top bits with 1 if the <tt>x</tt> is negative and with 0
--   otherwise.
--   
--   An instance can define either this unified <a>shift</a> or
--   <a>shiftL</a> and <a>shiftR</a>, depending on which is more convenient
--   for the type in question.
shift :: Bits a => a -> Int -> a

-- | <tt><a>rotate</a> x i</tt> rotates <tt>x</tt> left by <tt>i</tt> bits
--   if <tt>i</tt> is positive, or right by <tt>-i</tt> bits otherwise.
--   
--   For unbounded types like <a>Integer</a>, <a>rotate</a> is equivalent
--   to <a>shift</a>.
--   
--   An instance can define either this unified <a>rotate</a> or
--   <a>rotateL</a> and <a>rotateR</a>, depending on which is more
--   convenient for the type in question.
rotate :: Bits a => a -> Int -> a

-- | <a>zeroBits</a> is the value with all bits unset.
--   
--   The following laws ought to hold (for all valid bit indices
--   <tt><i>n</i></tt>):
--   
--   <ul>
--   <li><pre><a>clearBit</a> <a>zeroBits</a> <i>n</i> ==
--   <a>zeroBits</a></pre></li>
--   <li><pre><a>setBit</a> <a>zeroBits</a> <i>n</i> == <a>bit</a>
--   <i>n</i></pre></li>
--   <li><pre><a>testBit</a> <a>zeroBits</a> <i>n</i> == False</pre></li>
--   <li><pre><a>popCount</a> <a>zeroBits</a> == 0</pre></li>
--   </ul>
--   
--   This method uses <tt><a>clearBit</a> (<a>bit</a> 0) 0</tt> as its
--   default implementation (which ought to be equivalent to
--   <a>zeroBits</a> for types which possess a 0th bit).
zeroBits :: Bits a => a

-- | <tt>bit <i>i</i></tt> is a value with the <tt><i>i</i></tt>th bit set
--   and all other bits clear.
--   
--   Can be implemented using <a>bitDefault</a> if <tt>a</tt> is also an
--   instance of <a>Num</a>.
--   
--   See also <a>zeroBits</a>.
bit :: Bits a => Int -> a

-- | <tt>x `setBit` i</tt> is the same as <tt>x .|. bit i</tt>
setBit :: Bits a => a -> Int -> a

-- | <tt>x `clearBit` i</tt> is the same as <tt>x .&amp;. complement (bit
--   i)</tt>
clearBit :: Bits a => a -> Int -> a

-- | <tt>x `complementBit` i</tt> is the same as <tt>x `xor` bit i</tt>
complementBit :: Bits a => a -> Int -> a

-- | Return <a>True</a> if the <tt>n</tt>th bit of the argument is 1
--   
--   Can be implemented using <a>testBitDefault</a> if <tt>a</tt> is also
--   an instance of <a>Num</a>.
testBit :: Bits a => a -> Int -> Bool

-- | Return <a>True</a> if the argument is a signed type. The actual value
--   of the argument is ignored
isSigned :: Bits a => a -> Bool

-- | Rotate the argument left by the specified number of bits (which must
--   be non-negative).
--   
--   An instance can define either this and <a>rotateR</a> or the unified
--   <a>rotate</a>, depending on which is more convenient for the type in
--   question.
rotateL :: Bits a => a -> Int -> a

-- | Rotate the argument right by the specified number of bits (which must
--   be non-negative).
--   
--   An instance can define either this and <a>rotateL</a> or the unified
--   <a>rotate</a>, depending on which is more convenient for the type in
--   question.
rotateR :: Bits a => a -> Int -> a

-- | Return the number of set bits in the argument. This number is known as
--   the population count or the Hamming weight.
--   
--   Can be implemented using <a>popCountDefault</a> if <tt>a</tt> is also
--   an instance of <a>Num</a>.
popCount :: Bits a => a -> Int

-- | The <a>FiniteBits</a> class denotes types with a finite, fixed number
--   of bits.
class Bits b => FiniteBits b

-- | Return the number of bits in the type of the argument. The actual
--   value of the argument is ignored. Moreover, <a>finiteBitSize</a> is
--   total, in contrast to the deprecated <a>bitSize</a> function it
--   replaces.
--   
--   <pre>
--   <a>finiteBitSize</a> = <a>bitSize</a>
--   <a>bitSizeMaybe</a> = <a>Just</a> . <a>finiteBitSize</a>
--   </pre>
finiteBitSize :: FiniteBits b => b -> Int

-- | Count number of zero bits preceding the most significant set bit.
--   
--   <pre>
--   <a>countLeadingZeros</a> (<a>zeroBits</a> :: a) = finiteBitSize (<a>zeroBits</a> :: a)
--   </pre>
--   
--   <a>countLeadingZeros</a> can be used to compute log base 2 via
--   
--   <pre>
--   logBase2 x = <a>finiteBitSize</a> x - 1 - <a>countLeadingZeros</a> x
--   </pre>
--   
--   Note: The default implementation for this method is intentionally
--   naive. However, the instances provided for the primitive integral
--   types are implemented using CPU specific machine instructions.
countLeadingZeros :: FiniteBits b => b -> Int

-- | Count number of zero bits following the least significant set bit.
--   
--   <pre>
--   <a>countTrailingZeros</a> (<a>zeroBits</a> :: a) = finiteBitSize (<a>zeroBits</a> :: a)
--   <a>countTrailingZeros</a> . <a>negate</a> = <a>countTrailingZeros</a>
--   </pre>
--   
--   The related <a>find-first-set operation</a> can be expressed in terms
--   of <a>countTrailingZeros</a> as follows
--   
--   <pre>
--   findFirstSet x = 1 + <a>countTrailingZeros</a> x
--   </pre>
--   
--   Note: The default implementation for this method is intentionally
--   naive. However, the instances provided for the primitive integral
--   types are implemented using CPU specific machine instructions.
countTrailingZeros :: FiniteBits b => b -> Int

-- | 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

-- | Lifting of the <a>Show</a> class to unary type constructors.
class Show1 (f :: * -> *)

-- | Lifting of the <a>Show</a> class to binary type constructors.
class Show2 (f :: * -> * -> *)

-- | Convert a value to a readable string type supported by
--   <a>ConvertString</a> using the <a>Show</a> instance.
show :: (Show a, ConvertString String s) => a -> s

-- | Convert a value to a readable <a>Text</a> using the <a>Show</a>
--   instance.
showT :: Show a => a -> Text

-- | Convert a value to a readable <a>String</a> using the <a>Show</a>
--   instance.
showS :: Show a => a -> String

-- | 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

-- | Lifting of the <a>Read</a> class to unary type constructors.
--   
--   Both <a>liftReadsPrec</a> and <a>liftReadPrec</a> exist to match the
--   interface provided in the <a>Read</a> type class, but it is
--   recommended to implement <a>Read1</a> instances using
--   <a>liftReadPrec</a> as opposed to <a>liftReadsPrec</a>, since the
--   former is more efficient than the latter. For example:
--   
--   <pre>
--   instance <a>Read1</a> T where
--     <a>liftReadPrec</a>     = ...
--     <a>liftReadListPrec</a> = <a>liftReadListPrecDefault</a>
--   </pre>
--   
--   For more information, refer to the documentation for the <a>Read</a>
--   class.
class Read1 (f :: * -> *)

-- | Lifting of the <a>Read</a> class to binary type constructors.
--   
--   Both <a>liftReadsPrec2</a> and <a>liftReadPrec2</a> exist to match the
--   interface provided in the <a>Read</a> type class, but it is
--   recommended to implement <a>Read2</a> instances using
--   <a>liftReadPrec2</a> as opposed to <a>liftReadsPrec2</a>, since the
--   former is more efficient than the latter. For example:
--   
--   <pre>
--   instance <a>Read2</a> T where
--     <a>liftReadPrec2</a>     = ...
--     <a>liftReadListPrec2</a> = <a>liftReadListPrec2Default</a>
--   </pre>
--   
--   For more information, refer to the documentation for the <a>Read</a>
--   class. @since 4.9.0.0
class Read2 (f :: * -> * -> *)

-- | Parse a string type using the <a>Read</a> instance. Succeeds if there
--   is exactly one valid result.
readMaybe :: (Read b, ConvertString a String) => a -> Maybe b

-- | 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>.
--   
--   Minimal complete definition: either <a>==</a> or <a>/=</a>.
class Eq a
(==) :: Eq a => a -> a -> Bool
(/=) :: Eq a => a -> a -> Bool

-- | Lifting of the <a>Eq</a> class to unary type constructors.
class Eq1 (f :: * -> *)

-- | Lifting of the <a>Eq</a> class to binary type constructors.
class Eq2 (f :: * -> * -> *)

-- | 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.
--   
--   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

-- | Lifting of the <a>Ord</a> class to unary type constructors.
class Eq1 f => Ord1 (f :: * -> *)

-- | Lifting of the <a>Ord</a> class to binary type constructors.
class Eq2 f => Ord2 (f :: * -> * -> *)
data Ordering
LT :: Ordering
EQ :: Ordering
GT :: Ordering

-- | 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>
newtype Down a
Down :: a -> Down a

-- | <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

-- | 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

-- | 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>.
enumFrom :: Enum a => a -> [a]

-- | Used in Haskell's translation of <tt>[n,n'..]</tt>.
enumFromThen :: Enum a => a -> a -> [a]

-- | Used in Haskell's translation of <tt>[n..m]</tt>.
enumFromTo :: Enum a => a -> a -> [a]

-- | Used in Haskell's translation of <tt>[n,n'..m]</tt>.
enumFromThenTo :: Enum a => a -> a -> a -> [a]
toEnumMay :: (Enum a, Bounded a) => Int -> Maybe a
toEnumDef :: (Enum a, Bounded a) => a -> Int -> a
predMay :: (Enum a, Eq a, Bounded a) => a -> Maybe a
predDef :: (Enum a, Eq a, Bounded a) => a -> a -> a
succMay :: (Enum a, Eq a, Bounded a) => a -> Maybe a
succDef :: (Enum a, Eq a, Bounded a) => a -> a -> a

-- | 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

-- | A class for categories. Instances should satisfy the laws
--   
--   <pre>
--   f <a>.</a> <a>id</a>  =  f  -- (right identity)
--   <a>id</a> <a>.</a> f  =  f  -- (left identity)
--   f <a>.</a> (g <a>.</a> h)  =  (f <a>.</a> g) <a>.</a> h  -- (associativity)
--   </pre>
class Category (cat :: k -> k -> *)

-- | the identity morphism
id :: Category cat => cat a a

-- | morphism composition
(.) :: Category cat => cat b c -> cat a b -> cat a c

-- | Right-to-left composition
(<<<) :: Category cat => cat b c -> cat a b -> cat a c
infixr 1 <<<

-- | Left-to-right composition
(>>>) :: Category cat => cat a b -> cat b c -> cat a c
infixr 1 >>>

-- | The class of semigroups (types with an associative binary operation).
--   
--   Instances should satisfy the associativity law:
--   
--   <ul>
--   <li><pre>x <a>&lt;&gt;</a> (y <a>&lt;&gt;</a> z) = (x <a>&lt;&gt;</a>
--   y) <a>&lt;&gt;</a> z</pre></li>
--   </ul>
class Semigroup a

-- | An associative operation.
(<>) :: Semigroup a => a -> a -> a

-- | Reduce a non-empty list with <tt>&lt;&gt;</tt>
--   
--   The default definition should be sufficient, but this can be
--   overridden for efficiency.
sconcat :: Semigroup a => NonEmpty a -> a

-- | Repeat a value <tt>n</tt> times.
--   
--   Given that this works on a <a>Semigroup</a> it is allowed to fail if
--   you request 0 or fewer repetitions, and the default definition will do
--   so.
--   
--   By making this a member of the class, idempotent semigroups and
--   monoids can upgrade this to execute in <i>O(1)</i> by picking
--   <tt>stimes = <tt>stimesIdempotent</tt></tt> or <tt>stimes =
--   <a>stimesIdempotentMonoid</a></tt> respectively.
stimes :: (Semigroup a, Integral b) => b -> a -> a

-- | Use <tt><a>Option</a> (<a>First</a> a)</tt> to get the behavior of
--   <a>First</a> from <a>Data.Monoid</a>.
newtype First a
First :: a -> First a
[getFirst] :: First a -> a

-- | Use <tt><a>Option</a> (<a>Last</a> a)</tt> to get the behavior of
--   <a>Last</a> from <a>Data.Monoid</a>
newtype Last a
Last :: a -> Last a
[getLast] :: Last a -> a
newtype Min a
Min :: a -> Min a
[getMin] :: Min a -> a
newtype Max a
Max :: a -> Max a
[getMax] :: Max a -> a

-- | <a>Option</a> is effectively <a>Maybe</a> with a better instance of
--   <a>Monoid</a>, built off of an underlying <a>Semigroup</a> instead of
--   an underlying <a>Monoid</a>.
--   
--   Ideally, this type would not exist at all and we would just fix the
--   <a>Monoid</a> instance of <a>Maybe</a>
newtype Option a
Option :: Maybe a -> Option a
[getOption] :: Option a -> Maybe a

-- | The class of monoids (types with an associative binary operation that
--   has an identity). Instances should satisfy the following laws:
--   
--   <ul>
--   <li><pre>x <a>&lt;&gt;</a> <a>mempty</a> = x</pre></li>
--   <li><pre><a>mempty</a> <a>&lt;&gt;</a> x = x</pre></li>
--   <li><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><pre><a>mconcat</a> = <a>foldr</a> '(&lt;&gt;)'
--   <a>mempty</a></pre></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.
--   <tt>Sum</tt> and <tt>Product</tt>.
--   
--   <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>
mempty :: Monoid a => a

-- | An associative operation
--   
--   <b>NOTE</b>: This method is redundant and has the default
--   implementation <tt><a>mappend</a> = '(&lt;&gt;)'</tt> since
--   <i>base-4.11.0.0</i>.
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.
mconcat :: Monoid a => [a] -> a

-- | The dual of a <a>Monoid</a>, obtained by swapping the arguments of
--   <a>mappend</a>.
--   
--   <pre>
--   &gt;&gt;&gt; getDual (mappend (Dual "Hello") (Dual "World"))
--   "WorldHello"
--   </pre>
newtype Dual a
Dual :: a -> Dual a
[getDual] :: Dual a -> a

-- | The monoid of endomorphisms under composition.
--   
--   <pre>
--   &gt;&gt;&gt; let computation = Endo ("Hello, " ++) &lt;&gt; Endo (++ "!")
--   
--   &gt;&gt;&gt; appEndo computation "Haskell"
--   "Hello, Haskell!"
--   </pre>
newtype Endo a
Endo :: a -> a -> Endo a
[appEndo] :: Endo a -> a -> a

-- | Boolean monoid under conjunction (<a>&amp;&amp;</a>).
--   
--   <pre>
--   &gt;&gt;&gt; getAll (All True &lt;&gt; mempty &lt;&gt; All False)
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; getAll (mconcat (map (\x -&gt; All (even x)) [2,4,6,7,8]))
--   False
--   </pre>
newtype All
All :: Bool -> All
[getAll] :: All -> Bool

-- | Boolean monoid under disjunction (<a>||</a>).
--   
--   <pre>
--   &gt;&gt;&gt; getAny (Any True &lt;&gt; mempty &lt;&gt; Any False)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; getAny (mconcat (map (\x -&gt; Any (even x)) [2,4,6,7,8]))
--   True
--   </pre>
newtype Any
Any :: Bool -> Any
[getAny] :: Any -> Bool

-- | Monoid under <a>&lt;|&gt;</a>.
newtype Alt (f :: k -> *) (a :: k) :: forall k. () => k -> * -> k -> *
Alt :: f a -> Alt
[getAlt] :: Alt -> f a

-- | The <a>Functor</a> class is used for types that can be mapped over.
--   Instances of <a>Functor</a> should satisfy the following laws:
--   
--   <pre>
--   fmap id  ==  id
--   fmap (f . g)  ==  fmap f . fmap g
--   </pre>
--   
--   The instances of <a>Functor</a> for lists, <a>Maybe</a> and <a>IO</a>
--   satisfy these laws.
class Functor (f :: * -> *)

-- | 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.
(<$) :: Functor f => a -> f b -> f a

-- | Flipped version of <a>&lt;$</a>.
--   
--   <h4><b>Examples</b></h4>
--   
--   Replace the contents of a <tt><tt>Maybe</tt> <tt>Int</tt></tt> with a
--   constant <tt>String</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; Nothing $&gt; "foo"
--   Nothing
--   
--   &gt;&gt;&gt; Just 90210 $&gt; "foo"
--   Just "foo"
--   </pre>
--   
--   Replace the contents of an <tt><tt>Either</tt> <tt>Int</tt>
--   <tt>Int</tt></tt> with a constant <tt>String</tt>, resulting in an
--   <tt><tt>Either</tt> <tt>Int</tt> <tt>String</tt></tt>:
--   
--   <pre>
--   &gt;&gt;&gt; Left 8675309 $&gt; "foo"
--   Left 8675309
--   
--   &gt;&gt;&gt; Right 8675309 $&gt; "foo"
--   Right "foo"
--   </pre>
--   
--   Replace each element of a list with a constant <tt>String</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; [1,2,3] $&gt; "foo"
--   ["foo","foo","foo"]
--   </pre>
--   
--   Replace the second element of a pair with a constant <tt>String</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; (1,2) $&gt; "foo"
--   (1,"foo")
--   </pre>
($>) :: Functor f => f a -> b -> f b
infixl 4 $>

-- | An infix synonym for <a>fmap</a>.
--   
--   The name of this operator is an allusion to <tt>$</tt>. 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 <tt>$</tt> 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><tt>Maybe</tt> <tt>Int</tt></tt> to a
--   <tt><tt>Maybe</tt> <tt>String</tt></tt> using <tt>show</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; show &lt;$&gt; Nothing
--   Nothing
--   
--   &gt;&gt;&gt; show &lt;$&gt; Just 3
--   Just "3"
--   </pre>
--   
--   Convert from an <tt><tt>Either</tt> <tt>Int</tt> <tt>Int</tt></tt> to
--   an <tt><tt>Either</tt> <tt>Int</tt></tt> <tt>String</tt> using
--   <tt>show</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; show &lt;$&gt; Left 17
--   Left 17
--   
--   &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 <tt>even</tt> 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 <$>

-- | Flipped version of <a>&lt;$&gt;</a>.
--   
--   <pre>
--   (<a>&lt;&amp;&gt;</a>) = <a>flip</a> <a>fmap</a>
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   Apply <tt>(+1)</tt> to a list, a <a>Just</a> and a <a>Right</a>:
--   
--   <pre>
--   &gt;&gt;&gt; Just 2 &lt;&amp;&gt; (+1)
--   Just 3
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; [1,2,3] &lt;&amp;&gt; (+1)
--   [2,3,4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Right 3 &lt;&amp;&gt; (+1)
--   Right 4
--   </pre>
(<&>) :: Functor f => f a -> a -> b -> f b
infixl 1 <&>

-- | A synonym for <a>fmap</a>.
--   
--   <pre>
--   map = <a>fmap</a>
--   </pre>
map :: Functor f => (a -> b) -> f a -> f 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><tt>Maybe</tt> <tt>Int</tt></tt> with
--   unit:
--   
--   <pre>
--   &gt;&gt;&gt; void Nothing
--   Nothing
--   
--   &gt;&gt;&gt; void (Just 3)
--   Just ()
--   </pre>
--   
--   Replace the contents of an <tt><tt>Either</tt> <tt>Int</tt>
--   <tt>Int</tt></tt> with unit, resulting in an <tt><tt>Either</tt>
--   <tt>Int</tt> '()'</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; void (Left 8675309)
--   Left 8675309
--   
--   &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
--   [(),()]
--   
--   &gt;&gt;&gt; void $ mapM print [1,2]
--   1
--   2
--   </pre>
void :: Functor f => f a -> f ()

-- | The <a>Const</a> functor.
newtype Const a (b :: k) :: forall k. () => * -> k -> *
Const :: a -> Const a
[getConst] :: Const a -> a

-- | Identity functor and monad. (a non-strict monad)
newtype Identity a
Identity :: a -> Identity a
[runIdentity] :: Identity a -> a

-- | Data structures that can be folded.
--   
--   For example, given a data type
--   
--   <pre>
--   data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--   </pre>
--   
--   a suitable instance would be
--   
--   <pre>
--   instance Foldable Tree where
--      foldMap f Empty = mempty
--      foldMap f (Leaf x) = f x
--      foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--   </pre>
--   
--   This is suitable even for abstract types, as the monoid is assumed to
--   satisfy the monoid laws. Alternatively, one could define
--   <tt>foldr</tt>:
--   
--   <pre>
--   instance Foldable Tree where
--      foldr f z Empty = z
--      foldr f z (Leaf x) = f x z
--      foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
--   </pre>
--   
--   <tt>Foldable</tt> instances are expected to satisfy the following
--   laws:
--   
--   <pre>
--   foldr f z t = appEndo (foldMap (Endo . f) t ) z
--   </pre>
--   
--   <pre>
--   foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
--   </pre>
--   
--   <pre>
--   fold = foldMap id
--   </pre>
--   
--   <pre>
--   length = getSum . foldMap (Sum . const  1)
--   </pre>
--   
--   <tt>sum</tt>, <tt>product</tt>, <tt>maximum</tt>, and <tt>minimum</tt>
--   should all be essentially equivalent to <tt>foldMap</tt> forms, such
--   as
--   
--   <pre>
--   sum = getSum . foldMap Sum
--   </pre>
--   
--   but may be less defined.
--   
--   If the type is also a <a>Functor</a> instance, it should satisfy
--   
--   <pre>
--   foldMap f = fold . fmap f
--   </pre>
--   
--   which implies that
--   
--   <pre>
--   foldMap f . fmap g = foldMap (f . g)
--   </pre>
class Foldable (t :: * -> *)

-- | Combine the elements of a structure using a monoid.
fold :: (Foldable t, Monoid m) => t m -> m

-- | Map each element of the structure to a monoid, and combine the
--   results.
foldMap :: (Foldable t, Monoid m) => a -> m -> t a -> m

-- | Right-associative fold of a structure.
--   
--   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,
--   <a>foldr</a> can produce a terminating expression from an infinite
--   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>
foldr :: Foldable t => a -> b -> b -> b -> t a -> b

-- | Right-associative fold of a structure, but with strict application of
--   the operator.
foldr' :: Foldable t => a -> b -> 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 list to a single, monolithic result (e.g. <a>length</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

-- | List of elements of a structure, from left to right.
toList :: Foldable t => t a -> [a]

-- | Does the element occur in the structure?
elem :: (Foldable t, Eq a) => a -> t a -> Bool

-- | The <a>sum</a> function computes the sum of the numbers of a
--   structure.
sum :: (Foldable t, Num a) => t a -> a

-- | The <a>product</a> function computes the product of the numbers of a
--   structure.
product :: (Foldable t, Num a) => t a -> a

-- | Test whether the structure is empty. The default implementation is
--   optimized for structures that are similar to cons-lists, because there
--   is no general way to do better.
null :: Foldable t => t a -> Bool

-- | Returns the size/length of a finite structure as an <a>Int</a>. The
--   default implementation is optimized for structures that are similar to
--   cons-lists, because there is no general way to do better.
length :: Foldable t => t a -> Int

-- | Monadic fold over the elements of a structure, associating to the
--   right, i.e. from right to left.
foldrM :: (Foldable t, Monad m) => a -> b -> m b -> b -> t a -> m b

-- | Monadic fold over the elements of a structure, associating to the
--   left, i.e. from left to right.
foldlM :: (Foldable t, Monad m) => b -> a -> m b -> b -> t a -> m b

-- | Map each element of a structure to an 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>.
traverse_ :: (Foldable t, Applicative f) => a -> f b -> t 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>.
--   
--   <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 sum of a collection of actions, generalizing <a>concat</a>.
--   
--   asum [Just <a>Hello</a>, Nothing, Just <a>World</a>] Just <a>Hello</a>
asum :: (Foldable t, Alternative f) => t f a -> f a

-- | Map a function over all the elements of a container and concatenate
--   the resulting lists.
concatMap :: Foldable t => a -> [b] -> t a -> [b]

-- | Determines whether all elements of the structure satisfy the
--   predicate.
all :: Foldable t => a -> Bool -> t a -> Bool

-- | Determines whether any element of the structure satisfies the
--   predicate.
any :: Foldable t => a -> Bool -> t a -> 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.
or :: Foldable t => t Bool -> Bool

-- | <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.
and :: Foldable t => t Bool -> Bool

-- | 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.
find :: Foldable t => a -> Bool -> t a -> Maybe a

-- | <a>notElem</a> is the negation of <a>elem</a>.
notElem :: (Foldable t, Eq a) => a -> t a -> Bool
infix 4 `notElem`

-- | 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>.
sequenceA_ :: (Foldable t, Applicative f) => t f a -> f ()
foldl1May :: Foldable t => a -> a -> a -> t a -> Maybe a
foldl1Def :: Foldable t => a -> a -> a -> a -> t a -> a
foldr1May :: Foldable t => a -> a -> a -> t a -> Maybe a
foldr1Def :: Foldable t => a -> a -> a -> a -> t a -> a
maximumByMay :: Foldable t => a -> a -> Ordering -> t a -> Maybe a
maximumByDef :: Foldable t => a -> a -> a -> Ordering -> t a -> a
minimumByMay :: Foldable t => a -> a -> Ordering -> t a -> Maybe a
minimumByDef :: Foldable t => a -> a -> a -> Ordering -> t a -> a
maximumMay :: (Foldable t, Ord a) => t a -> Maybe a
maximumDef :: (Foldable t, Ord a) => a -> t a -> a
minimumMay :: (Foldable t, Ord a) => t a -> Maybe a
minimumDef :: (Foldable t, Ord a) => a -> t a -> a

-- | Functors representing data structures that can be traversed from left
--   to right.
--   
--   A definition of <a>traverse</a> must satisfy the following laws:
--   
--   <ul>
--   <li><i><i>naturality</i></i> <tt>t . <a>traverse</a> f =
--   <a>traverse</a> (t . f)</tt> for every applicative transformation
--   <tt>t</tt></li>
--   <li><i><i>identity</i></i> <tt><a>traverse</a> Identity =
--   Identity</tt></li>
--   <li><i><i>composition</i></i> <tt><a>traverse</a> (Compose .
--   <a>fmap</a> g . f) = Compose . <a>fmap</a> (<a>traverse</a> g) .
--   <a>traverse</a> f</tt></li>
--   </ul>
--   
--   A definition of <a>sequenceA</a> must satisfy the following laws:
--   
--   <ul>
--   <li><i><i>naturality</i></i> <tt>t . <a>sequenceA</a> =
--   <a>sequenceA</a> . <a>fmap</a> t</tt> for every applicative
--   transformation <tt>t</tt></li>
--   <li><i><i>identity</i></i> <tt><a>sequenceA</a> . <a>fmap</a> Identity
--   = Identity</tt></li>
--   <li><i><i>composition</i></i> <tt><a>sequenceA</a> . <a>fmap</a>
--   Compose = Compose . <a>fmap</a> <a>sequenceA</a> .
--   <a>sequenceA</a></tt></li>
--   </ul>
--   
--   where an <i>applicative transformation</i> is a function
--   
--   <pre>
--   t :: (Applicative f, Applicative g) =&gt; f a -&gt; g a
--   </pre>
--   
--   preserving the <a>Applicative</a> operations, i.e.
--   
--   <ul>
--   <li><pre>t (<a>pure</a> x) = <a>pure</a> x</pre></li>
--   <li><pre>t (x <a>&lt;*&gt;</a> y) = t x <a>&lt;*&gt;</a> t
--   y</pre></li>
--   </ul>
--   
--   and the identity functor <tt>Identity</tt> and composition of functors
--   <tt>Compose</tt> are defined as
--   
--   <pre>
--   newtype Identity a = Identity a
--   
--   instance Functor Identity where
--     fmap f (Identity x) = Identity (f x)
--   
--   instance Applicative Identity where
--     pure x = Identity x
--     Identity f &lt;*&gt; Identity x = Identity (f x)
--   
--   newtype Compose f g a = Compose (f (g a))
--   
--   instance (Functor f, Functor g) =&gt; Functor (Compose f g) where
--     fmap f (Compose x) = Compose (fmap (fmap f) x)
--   
--   instance (Applicative f, Applicative g) =&gt; Applicative (Compose f g) where
--     pure x = Compose (pure (pure x))
--     Compose f &lt;*&gt; Compose x = Compose ((&lt;*&gt;) &lt;$&gt; f &lt;*&gt; x)
--   </pre>
--   
--   (The naturality law is implied by parametricity.)
--   
--   Instances are similar to <a>Functor</a>, e.g. given a data type
--   
--   <pre>
--   data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--   </pre>
--   
--   a suitable instance would be
--   
--   <pre>
--   instance Traversable Tree where
--      traverse f Empty = pure Empty
--      traverse f (Leaf x) = Leaf &lt;$&gt; f x
--      traverse f (Node l k r) = Node &lt;$&gt; traverse f l &lt;*&gt; f k &lt;*&gt; traverse f r
--   </pre>
--   
--   This is suitable even for abstract types, as the laws for
--   <a>&lt;*&gt;</a> imply a form of associativity.
--   
--   The superclass instances should satisfy the following:
--   
--   <ul>
--   <li>In the <a>Functor</a> instance, <a>fmap</a> should be equivalent
--   to traversal with the identity applicative functor
--   (<a>fmapDefault</a>).</li>
--   <li>In the <a>Foldable</a> instance, <a>foldMap</a> should be
--   equivalent to traversal with a constant applicative functor
--   (<a>foldMapDefault</a>).</li>
--   </ul>
class (Functor t, Foldable t) => Traversable (t :: * -> *)

-- | 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>.
traverse :: (Traversable t, Applicative f) => a -> f b -> t a -> f t b

-- | Evaluate each action in the structure from left to right, and and
--   collect the results. For a version that ignores the results see
--   <a>sequenceA_</a>.
sequenceA :: (Traversable t, Applicative f) => t f a -> f 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

-- | The <a>mapAccumL</a> function behaves like a combination of
--   <a>fmap</a> and <tt>foldl</tt>; 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.
mapAccumL :: Traversable t => a -> b -> (a, c) -> a -> t b -> (a, t c)

-- | The <a>mapAccumR</a> function behaves like a combination of
--   <a>fmap</a> and <tt>foldr</tt>; 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.
mapAccumR :: Traversable t => a -> b -> (a, c) -> a -> t b -> (a, t c)

-- | 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 <tt>&lt;$&gt;</tt> x <a>&lt;*&gt;</a> y
--   </pre>
--   
--   Further, any definition must satisfy the following:
--   
--   <ul>
--   <li><i><i>identity</i></i> <pre><a>pure</a> <a>id</a> <a>&lt;*&gt;</a>
--   v = v</pre></li>
--   <li><i><i>composition</i></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><i>homomorphism</i></i> <pre><a>pure</a> f <a>&lt;*&gt;</a>
--   <a>pure</a> x = <a>pure</a> (f x)</pre></li>
--   <li><i><i>interchange</i></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>(<a>&lt;*&gt;</a>) = <a>ap</a></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 :: * -> *)

-- | Lift a value.
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.
(<*>) :: Applicative f => f a -> b -> f a -> f b

-- | Sequence actions, discarding the value of the first argument.
(*>) :: 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

-- | Lists, but with an <a>Applicative</a> functor based on zipping.
newtype ZipList a
ZipList :: [a] -> ZipList a
[getZipList] :: ZipList a -> [a]

-- | A variant of <a>&lt;*&gt;</a> with the arguments reversed.
(<**>) :: Applicative f => f a -> f a -> b -> f b
infixl 4 <**>

-- | 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>.
liftA2 :: Applicative f => a -> b -> c -> f a -> f b -> f c

-- | Lift a ternary function to actions.
liftA3 :: Applicative f => a -> b -> c -> d -> f a -> f b -> f c -> f d

-- | <tt>()</tt> lifted to an <a>Applicative</a>.
--   
--   <pre>
--   skip = <a>pure</a> ()
--   </pre>
skip :: Applicative m => m ()

-- | <a>&lt;&gt;</a> lifted to <a>Applicative</a>
(<>^) :: (Applicative f, Semigroup a) => f a -> f a -> f a
infixr 6 <>^

-- | A monoid on applicative functors.
--   
--   If defined, <a>some</a> and <a>many</a> should be the least solutions
--   of the equations:
--   
--   <ul>
--   <li><pre><a>some</a> v = (:) <tt>&lt;$&gt;</tt> v <a>&lt;*&gt;</a>
--   <a>many</a> v</pre></li>
--   <li><pre><a>many</a> v = <a>some</a> v <a>&lt;|&gt;</a> <a>pure</a>
--   []</pre></li>
--   </ul>
class Applicative f => Alternative (f :: * -> *)

-- | The identity of <a>&lt;|&gt;</a>
empty :: Alternative f => f a

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

-- | Zero or more.
many :: Alternative f => f a -> f [a]

-- | One or none.
optional :: Alternative f => f a -> f Maybe a

-- | <tt><a>some1</a> x</tt> sequences <tt>x</tt> one or more times.
some1 :: Alternative f => f a -> f NonEmpty a

-- | 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 laws:
--   
--   <ul>
--   <li><pre><a>return</a> a <a>&gt;&gt;=</a> k = k a</pre></li>
--   <li><pre>m <a>&gt;&gt;=</a> <a>return</a> = m</pre></li>
--   <li><pre>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</pre></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>(<a>&lt;*&gt;</a>) = <a>ap</a></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 lists, <a>Maybe</a> and <a>IO</a>
--   defined in the <a>Prelude</a> satisfy these laws.
class Applicative m => Monad (m :: * -> *)

-- | Sequentially compose two actions, passing any value produced by the
--   first as an argument to the second.
(>>=) :: Monad m => m a -> a -> m b -> m b

-- | Monads having fixed points with a 'knot-tying' semantics. Instances of
--   <a>MonadFix</a> should satisfy the following laws:
--   
--   <ul>
--   <li><i><i>purity</i></i> <tt><a>mfix</a> (<tt>return</tt> . h) =
--   <tt>return</tt> (<a>fix</a> h)</tt></li>
--   <li><i><i>left shrinking</i> (or <i>tightening</i>)</i>
--   <tt><a>mfix</a> (\x -&gt; a &gt;&gt;= \y -&gt; f x y) = a &gt;&gt;= \y
--   -&gt; <a>mfix</a> (\x -&gt; f x y)</tt></li>
--   <li><i><i>sliding</i></i> <tt><a>mfix</a> (<a>liftM</a> h . f) =
--   <a>liftM</a> h (<a>mfix</a> (f . h))</tt>, for strict <tt>h</tt>.</li>
--   <li><i><i>nesting</i></i> <tt><a>mfix</a> (\x -&gt; <a>mfix</a> (\y
--   -&gt; f x y)) = <a>mfix</a> (\x -&gt; f x x)</tt></li>
--   </ul>
--   
--   This class is used in the translation of the recursive <tt>do</tt>
--   notation supported by GHC and Hugs.
class Monad m => MonadFix (m :: * -> *)

-- | The fixed point of a monadic computation. <tt><a>mfix</a> f</tt>
--   executes the action <tt>f</tt> only once, with the eventual output fed
--   back as the input. Hence <tt>f</tt> should not be strict, for then
--   <tt><a>mfix</a> f</tt> would diverge.
mfix :: MonadFix m => a -> m a -> m a

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

-- | Right-to-left Kleisli composition of monads.
--   <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 <=<

-- | Left-to-right Kleisli composition of monads.
(>=>) :: Monad m => a -> m b -> b -> m c -> a -> m c
infixr 1 >=>

-- | 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.
join :: Monad m => m m a -> 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 signaling an error
--   in an error monad and conditionally rejecting the current choice in an
--   <a>Alternative</a>-based parser.
--   
--   As an example of signaling 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
--   &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 ()

-- | Conditional execution of <a>Applicative</a> expressions. For example,
--   
--   <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.
when :: Applicative f => Bool -> f () -> f ()

-- | The reverse of <a>when</a>.
unless :: Applicative f => Bool -> f () -> f ()

-- | <tt><a>replicateM</a> n act</tt> performs the action <tt>n</tt> times,
--   gathering the results.
replicateM :: Applicative m => Int -> m a -> m [a]

-- | Like <a>replicateM</a>, but discards the result.
replicateM_ :: Applicative m => Int -> m a -> m ()

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

-- | Like <a>when</a>, but where the test can be monadic.
whenM :: Monad m => m Bool -> m () -> m ()

-- | Like <a>unless</a>, but where the test can be monadic.
unlessM :: Monad m => m Bool -> m () -> m ()

-- | Like <tt>if</tt>, but where the test can be monadic.
ifM :: Monad m => m Bool -> m a -> m a -> m a

-- | A version of <a>all</a> lifted to a monad. Retains the
--   short-circuiting behaviour.
--   
--   <pre>
--   allM Just [True,False,undefined] == Just False
--   allM Just [True,True ,undefined] == undefined
--   \(f :: Int -&gt; Maybe Bool) xs -&gt; anyM f xs == orM (map f xs)
--   </pre>
allM :: Monad m => a -> m Bool -> [a] -> m Bool

-- | A version of <a>any</a> lifted to a monad. Retains the
--   short-circuiting behaviour.
--   
--   <pre>
--   anyM Just [False,True ,undefined] == Just True
--   anyM Just [False,False,undefined] == undefined
--   \(f :: Int -&gt; Maybe Bool) xs -&gt; anyM f xs == orM (map f xs)
--   </pre>
anyM :: Monad m => a -> m Bool -> [a] -> m Bool

-- | A version of <a>and</a> lifted to a monad. Retains the
--   short-circuiting behaviour.
--   
--   <pre>
--   andM [Just True,Just False,undefined] == Just False
--   andM [Just True,Just True ,undefined] == undefined
--   \xs -&gt; Just (and xs) == andM (map Just xs)
--   </pre>
andM :: Monad m => [m Bool] -> m Bool

-- | A version of <a>or</a> lifted to a monad. Retains the short-circuiting
--   behaviour.
--   
--   <pre>
--   orM [Just False,Just True ,undefined] == Just True
--   orM [Just False,Just False,undefined] == undefined
--   \xs -&gt; Just (or xs) == orM (map Just xs)
--   </pre>
orM :: Monad m => [m Bool] -> m Bool

-- | A version of <a>concatMap</a> that works with a monadic predicate.
concatMapM :: Monad m => a -> m [b] -> [a] -> m [b]

-- | The lazy <a>&amp;&amp;</a> operator lifted to a monad. If the first
--   argument evaluates to <a>False</a> the second argument will not be
--   evaluated.
--   
--   <pre>
--   Just False &amp;&amp;^ undefined  == Just False
--   Just True  &amp;&amp;^ Just True  == Just True
--   Just True  &amp;&amp;^ Just False == Just False
--   </pre>
(&&^) :: Monad m => m Bool -> m Bool -> m Bool

-- | The lazy <a>||</a> operator lifted to a monad. If the first argument
--   evaluates to <a>True</a> the second argument will not be evaluated.
--   
--   <pre>
--   Just True  ||^ undefined  == Just True
--   Just False ||^ Just True  == Just True
--   Just False ||^ Just False == Just False
--   </pre>
(||^) :: Monad m => m Bool -> m Bool -> m Bool

-- | A bifunctor is a type constructor that takes two type arguments and is
--   a functor in <i>both</i> arguments. That is, unlike with
--   <a>Functor</a>, a type constructor such as <a>Either</a> does not need
--   to be partially applied for a <a>Bifunctor</a> instance, and the
--   methods in this class permit mapping functions over the <a>Left</a>
--   value or the <a>Right</a> value, or both at the same time.
--   
--   Formally, the class <a>Bifunctor</a> represents a bifunctor from
--   <tt>Hask</tt> -&gt; <tt>Hask</tt>.
--   
--   Intuitively it is a bifunctor where both the first and second
--   arguments are covariant.
--   
--   You can define a <a>Bifunctor</a> by either defining <a>bimap</a> or
--   by defining both <a>first</a> and <a>second</a>.
--   
--   If you supply <a>bimap</a>, you should ensure that:
--   
--   <pre>
--   <a>bimap</a> <a>id</a> <a>id</a> ≡ <a>id</a>
--   </pre>
--   
--   If you supply <a>first</a> and <a>second</a>, ensure:
--   
--   <pre>
--   <a>first</a> <a>id</a> ≡ <a>id</a>
--   <a>second</a> <a>id</a> ≡ <a>id</a>
--   </pre>
--   
--   If you supply both, you should also ensure:
--   
--   <pre>
--   <a>bimap</a> f g ≡ <a>first</a> f <a>.</a> <a>second</a> g
--   </pre>
--   
--   These ensure by parametricity:
--   
--   <pre>
--   <a>bimap</a>  (f <a>.</a> g) (h <a>.</a> i) ≡ <a>bimap</a> f h <a>.</a> <a>bimap</a> g i
--   <a>first</a>  (f <a>.</a> g) ≡ <a>first</a>  f <a>.</a> <a>first</a>  g
--   <a>second</a> (f <a>.</a> g) ≡ <a>second</a> f <a>.</a> <a>second</a> g
--   </pre>
class Bifunctor (p :: * -> * -> *)

-- | Map over both arguments at the same time.
--   
--   <pre>
--   <a>bimap</a> f g ≡ <a>first</a> f <a>.</a> <a>second</a> g
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; bimap toUpper (+1) ('j', 3)
--   ('J',4)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; bimap toUpper (+1) (Left 'j')
--   Left 'J'
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; bimap toUpper (+1) (Right 3)
--   Right 4
--   </pre>
bimap :: Bifunctor p => a -> b -> c -> d -> p a c -> p b d

-- | Map covariantly over the first argument.
--   
--   <pre>
--   <a>first</a> f ≡ <a>bimap</a> f <a>id</a>
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; first toUpper ('j', 3)
--   ('J',3)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; first toUpper (Left 'j')
--   Left 'J'
--   </pre>
first :: Bifunctor p => a -> b -> p a c -> p b c

-- | Map covariantly over the second argument.
--   
--   <pre>
--   <a>second</a> ≡ <a>bimap</a> <a>id</a>
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; second (+1) ('j', 3)
--   ('j',4)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; second (+1) (Right 3)
--   Right 4
--   </pre>
second :: Bifunctor p => b -> c -> p a b -> p a c

-- | <a>Bifoldable</a> identifies foldable structures with two different
--   varieties of elements (as opposed to <a>Foldable</a>, which has one
--   variety of element). Common examples are <a>Either</a> and '(,)':
--   
--   <pre>
--   instance Bifoldable Either where
--     bifoldMap f _ (Left  a) = f a
--     bifoldMap _ g (Right b) = g b
--   
--   instance Bifoldable (,) where
--     bifoldr f g z (a, b) = f a (g b z)
--   </pre>
--   
--   A minimal <a>Bifoldable</a> definition consists of either
--   <a>bifoldMap</a> or <a>bifoldr</a>. When defining more than this
--   minimal set, one should ensure that the following identities hold:
--   
--   <pre>
--   <a>bifold</a> ≡ <a>bifoldMap</a> <a>id</a> <a>id</a>
--   <a>bifoldMap</a> f g ≡ <a>bifoldr</a> (<a>mappend</a> . f) (<a>mappend</a> . g) <a>mempty</a>
--   <a>bifoldr</a> f g z t ≡ <a>appEndo</a> (<a>bifoldMap</a> (Endo . f) (Endo . g) t) z
--   </pre>
--   
--   If the type is also a <tt>Bifunctor</tt> instance, it should satisfy:
--   
--   <pre>
--   'bifoldMap' f g ≡ 'bifold' . 'bimap' f g
--   </pre>
--   
--   which implies that
--   
--   <pre>
--   'bifoldMap' f g . 'bimap' h i ≡ 'bifoldMap' (f . h) (g . i)
--   </pre>
class Bifoldable (p :: * -> * -> *)

-- | Combines the elements of a structure, given ways of mapping them to a
--   common monoid.
--   
--   <pre>
--   <a>bifoldMap</a> f g
--        ≡ <a>bifoldr</a> (<a>mappend</a> . f) (<a>mappend</a> . g) <a>mempty</a>
--   </pre>
bifoldMap :: (Bifoldable p, Monoid m) => a -> m -> b -> m -> p a b -> m

-- | Combines the elements of a structure in a right associative manner.
--   Given a hypothetical function <tt>toEitherList :: p a b -&gt; [Either
--   a b]</tt> yielding a list of all elements of a structure in order, the
--   following would hold:
--   
--   <pre>
--   <a>bifoldr</a> f g z ≡ <a>foldr</a> (<a>either</a> f g) z . toEitherList
--   </pre>
bifoldr :: Bifoldable p => a -> c -> c -> b -> c -> c -> c -> p a b -> c

-- | As <a>bifoldl</a>, but strict in the result of the reduction functions
--   at each step.
--   
--   This ensures that each step of the bifold 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, monolithic result (e.g.,
--   <a>bilength</a>).
bifoldl' :: Bifoldable t => a -> b -> a -> a -> c -> a -> a -> t b c -> a

-- | As <a>bifoldr</a>, but strict in the result of the reduction functions
--   at each step.
bifoldr' :: Bifoldable t => a -> c -> c -> b -> c -> c -> c -> t a b -> c

-- | Map each element of a structure using one of two actions, evaluate
--   these actions from left to right, and ignore the results. For a
--   version that doesn't ignore the results, see <a>bitraverse</a>.
bitraverse_ :: (Bifoldable t, Applicative f) => a -> f c -> b -> f d -> t a b -> f ()

-- | Alias for <a>bisequence_</a>.
bisequenceA_ :: (Bifoldable t, Applicative f) => t f a f b -> f ()

-- | As <a>bitraverse_</a>, but with the structure as the primary argument.
--   For a version that doesn't ignore the results, see <a>bifor</a>.
--   
--   <pre>
--   &gt;&gt;&gt; &gt; bifor_ ('a', "bc") print (print . reverse)
--   'a'
--   "cb"
--   </pre>
bifor_ :: (Bifoldable t, Applicative f) => t a b -> a -> f c -> b -> f d -> f ()

-- | <a>Bitraversable</a> identifies bifunctorial data structures whose
--   elements can be traversed in order, performing <a>Applicative</a> or
--   <a>Monad</a> actions at each element, and collecting a result
--   structure with the same shape.
--   
--   As opposed to <a>Traversable</a> data structures, which have one
--   variety of element on which an action can be performed,
--   <a>Bitraversable</a> data structures have two such varieties of
--   elements.
--   
--   A definition of <a>bitraverse</a> must satisfy the following laws:
--   
--   <ul>
--   <li><i><i>naturality</i></i> <tt><a>bitraverse</a> (t . f) (t . g) ≡ t
--   . <a>bitraverse</a> f g</tt> for every applicative transformation
--   <tt>t</tt></li>
--   <li><i><i>identity</i></i> <tt><a>bitraverse</a> <a>Identity</a>
--   <a>Identity</a> ≡ <a>Identity</a></tt></li>
--   <li><i><i>composition</i></i> <tt><tt>Compose</tt> . <a>fmap</a>
--   (<a>bitraverse</a> g1 g2) . <a>bitraverse</a> f1 f2 ≡ <a>traverse</a>
--   (<tt>Compose</tt> . <a>fmap</a> g1 . f1) (<tt>Compose</tt> .
--   <a>fmap</a> g2 . f2)</tt></li>
--   </ul>
--   
--   where an <i>applicative transformation</i> is a function
--   
--   <pre>
--   t :: (<a>Applicative</a> f, <a>Applicative</a> g) =&gt; f a -&gt; g a
--   </pre>
--   
--   preserving the <a>Applicative</a> operations:
--   
--   <pre>
--   t (<a>pure</a> x) = <a>pure</a> x
--   t (f <a>&lt;*&gt;</a> x) = t f <a>&lt;*&gt;</a> t x
--   </pre>
--   
--   and the identity functor <a>Identity</a> and composition functors
--   <tt>Compose</tt> are defined as
--   
--   <pre>
--   newtype Identity a = Identity { runIdentity :: a }
--   
--   instance Functor Identity where
--     fmap f (Identity x) = Identity (f x)
--   
--   instance Applicative Identity where
--     pure = Identity
--     Identity f &lt;*&gt; Identity x = Identity (f x)
--   
--   newtype Compose f g a = Compose (f (g a))
--   
--   instance (Functor f, Functor g) =&gt; Functor (Compose f g) where
--     fmap f (Compose x) = Compose (fmap (fmap f) x)
--   
--   instance (Applicative f, Applicative g) =&gt; Applicative (Compose f g) where
--     pure = Compose . pure . pure
--     Compose f &lt;*&gt; Compose x = Compose ((&lt;*&gt;) &lt;$&gt; f &lt;*&gt; x)
--   </pre>
--   
--   Some simple examples are <a>Either</a> and '(,)':
--   
--   <pre>
--   instance Bitraversable Either where
--     bitraverse f _ (Left x) = Left &lt;$&gt; f x
--     bitraverse _ g (Right y) = Right &lt;$&gt; g y
--   
--   instance Bitraversable (,) where
--     bitraverse f g (x, y) = (,) &lt;$&gt; f x &lt;*&gt; g y
--   </pre>
--   
--   <a>Bitraversable</a> relates to its superclasses in the following
--   ways:
--   
--   <pre>
--   <a>bimap</a> f g ≡ <a>runIdentity</a> . <a>bitraverse</a> (<a>Identity</a> . f) (<a>Identity</a> . g)
--   <a>bifoldMap</a> f g = <a>getConst</a> . <a>bitraverse</a> (<a>Const</a> . f) (<a>Const</a> . g)
--   </pre>
--   
--   These are available as <a>bimapDefault</a> and <a>bifoldMapDefault</a>
--   respectively.
class (Bifunctor t, Bifoldable t) => Bitraversable (t :: * -> * -> *)

-- | Evaluates the relevant functions at each element in the structure,
--   running the action, and builds a new structure with the same shape,
--   using the results produced from sequencing the actions.
--   
--   <pre>
--   <a>bitraverse</a> f g ≡ <a>bisequenceA</a> . <a>bimap</a> f g
--   </pre>
--   
--   For a version that ignores the results, see <a>bitraverse_</a>.
bitraverse :: (Bitraversable t, Applicative f) => a -> f c -> b -> f d -> t a b -> f t c d

-- | <a>bifor</a> is <a>bitraverse</a> with the structure as the first
--   argument. For a version that ignores the results, see <a>bifor_</a>.
bifor :: (Bitraversable t, Applicative f) => t a b -> a -> f c -> b -> f d -> f t c d

-- | Alias for <a>bisequence</a>.
bisequenceA :: (Bitraversable t, Applicative f) => t f a f b -> f t a b

-- | The class of monad transformers. Instances should satisfy the
--   following laws, which state that <a>lift</a> is a monad
--   transformation:
--   
--   <ul>
--   <li><pre><a>lift</a> . <a>return</a> = <a>return</a></pre></li>
--   <li><pre><a>lift</a> (m &gt;&gt;= f) = <a>lift</a> m &gt;&gt;=
--   (<a>lift</a> . f)</pre></li>
--   </ul>
class MonadTrans (t :: * -> * -> * -> *)

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

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

-- | The parameterizable maybe monad, obtained by composing an arbitrary
--   monad with the <a>Maybe</a> monad.
--   
--   Computations are actions that may produce a value or exit.
--   
--   The <a>return</a> function yields a computation that produces that
--   value, while <tt>&gt;&gt;=</tt> sequences two subcomputations, exiting
--   if either computation does.
newtype MaybeT (m :: * -> *) a
MaybeT :: m Maybe a -> MaybeT a
[runMaybeT] :: MaybeT a -> m Maybe a

-- | Transform the computation inside a <tt>MaybeT</tt>.
--   
--   <ul>
--   <li><pre><a>runMaybeT</a> (<a>mapMaybeT</a> f m) = f (<a>runMaybeT</a>
--   m)</pre></li>
--   </ul>
mapMaybeT :: () => m Maybe a -> n Maybe b -> MaybeT m a -> MaybeT n b

-- | The strategy of combining computations that can throw exceptions by
--   bypassing bound functions from the point an exception is thrown to the
--   point that it is handled.
--   
--   Is parameterized over the type of error information and the monad type
--   constructor. It is common to use <tt><a>Either</a> String</tt> as the
--   monad type constructor for an error monad in which error descriptions
--   take the form of strings. In that case and many other common cases the
--   resulting monad is already defined as an instance of the
--   <a>MonadError</a> class. You can also define your own error type
--   and/or use a monad type constructor other than <tt><a>Either</a>
--   <tt>String</tt></tt> or <tt><a>Either</a> <tt>IOError</tt></tt>. In
--   these cases you will have to explicitly define instances of the
--   <a>MonadError</a> class. (If you are using the deprecated
--   <a>Control.Monad.Error</a> or <a>Control.Monad.Trans.Error</a>, you
--   may also have to define an <a>Error</a> instance.)
class Monad m => MonadError e (m :: * -> *) | m -> e

-- | Is used within a monadic computation to begin exception processing.
throwError :: MonadError e m => e -> m a

-- | A handler function to handle previous errors and return to normal
--   execution. A common idiom is:
--   
--   <pre>
--   do { action1; action2; action3 } `catchError` handler
--   </pre>
--   
--   where the <tt>action</tt> functions can call <a>throwError</a>. Note
--   that <tt>handler</tt> and the do-block must have the same return type.
catchError :: MonadError e m => m a -> e -> m a -> m a

-- | The parameterizable exception monad.
--   
--   Computations are either exceptions or normal values.
--   
--   The <a>return</a> function returns a normal value, while
--   <tt>&gt;&gt;=</tt> exits on the first exception. For a variant that
--   continues after an error and collects all the errors, see
--   <a>Errors</a>.
type Except e = ExceptT e Identity

-- | Extractor for computations in the exception monad. (The inverse of
--   <a>except</a>).
runExcept :: () => Except e a -> Either e a

-- | Map the unwrapped computation using the given function.
--   
--   <ul>
--   <li><pre><a>runExcept</a> (<a>mapExcept</a> f m) = f (<a>runExcept</a>
--   m)</pre></li>
--   </ul>
mapExcept :: () => Either e a -> Either e' b -> Except e a -> Except e' b

-- | Transform any exceptions thrown by the computation using the given
--   function (a specialization of <a>withExceptT</a>).
withExcept :: () => e -> e' -> Except e a -> Except e' a

-- | A monad transformer that adds exceptions to other monads.
--   
--   <tt>ExceptT</tt> constructs a monad parameterized over two things:
--   
--   <ul>
--   <li>e - The exception type.</li>
--   <li>m - The inner monad.</li>
--   </ul>
--   
--   The <a>return</a> function yields a computation that produces the
--   given value, while <tt>&gt;&gt;=</tt> sequences two subcomputations,
--   exiting on the first exception.
newtype ExceptT e (m :: * -> *) a
ExceptT :: m Either e a -> ExceptT e a

-- | The inverse of <a>ExceptT</a>.
runExceptT :: () => ExceptT e m a -> m Either e a

-- | Map the unwrapped computation using the given function.
--   
--   <ul>
--   <li><pre><a>runExceptT</a> (<a>mapExceptT</a> f m) = f
--   (<a>runExceptT</a> m)</pre></li>
--   </ul>
mapExceptT :: () => m Either e a -> n Either e' b -> ExceptT e m a -> ExceptT e' n b

-- | Transform any exceptions thrown by the computation using the given
--   function.
withExceptT :: Functor m => e -> e' -> ExceptT e m a -> ExceptT e' m a

-- | See examples in <a>Control.Monad.Reader</a>. Note, the partially
--   applied function type <tt>(-&gt;) r</tt> is a simple reader monad. See
--   the <tt>instance</tt> declaration below.
class Monad m => MonadReader r (m :: * -> *) | m -> r

-- | Retrieves the monad environment.
ask :: MonadReader r m => m r

-- | Executes a computation in a modified environment.
local :: MonadReader r m => r -> r -> m a -> m a

-- | Retrieves a function of the current environment.
reader :: MonadReader r m => r -> a -> m a

-- | Retrieves a function of the current environment.
asks :: MonadReader r m => r -> a -> m a

-- | The parameterizable reader monad.
--   
--   Computations are functions of a shared environment.
--   
--   The <a>return</a> function ignores the environment, while
--   <tt>&gt;&gt;=</tt> passes the inherited environment to both
--   subcomputations.
type Reader r = ReaderT r Identity

-- | Runs a <tt>Reader</tt> and extracts the final value from it. (The
--   inverse of <a>reader</a>.)
runReader :: () => Reader r a -> r -> a

-- | Transform the value returned by a <tt>Reader</tt>.
--   
--   <ul>
--   <li><pre><a>runReader</a> (<a>mapReader</a> f m) = f .
--   <a>runReader</a> m</pre></li>
--   </ul>
mapReader :: () => a -> b -> Reader r a -> Reader r b

-- | Execute a computation in a modified environment (a specialization of
--   <a>withReaderT</a>).
--   
--   <ul>
--   <li><pre><a>runReader</a> (<a>withReader</a> f m) = <a>runReader</a> m
--   . f</pre></li>
--   </ul>
withReader :: () => r' -> r -> Reader r a -> Reader r' a

-- | The reader monad transformer, which adds a read-only environment to
--   the given monad.
--   
--   The <a>return</a> function ignores the environment, while
--   <tt>&gt;&gt;=</tt> passes the inherited environment to both
--   subcomputations.
newtype ReaderT r (m :: k -> *) (a :: k) :: forall k. () => * -> k -> * -> k -> *
ReaderT :: r -> m a -> ReaderT r
[runReaderT] :: ReaderT r -> r -> m a

-- | Transform the computation inside a <tt>ReaderT</tt>.
--   
--   <ul>
--   <li><pre><a>runReaderT</a> (<a>mapReaderT</a> f m) = f .
--   <a>runReaderT</a> m</pre></li>
--   </ul>
mapReaderT :: () => m a -> n b -> ReaderT r m a -> ReaderT r n b

-- | Execute a computation in a modified environment (a more general
--   version of <a>local</a>).
--   
--   <ul>
--   <li><pre><a>runReaderT</a> (<a>withReaderT</a> f m) =
--   <a>runReaderT</a> m . f</pre></li>
--   </ul>
withReaderT :: () => r' -> r -> ReaderT r m a -> ReaderT r' m a
class (Monoid w, Monad m) => MonadWriter w (m :: * -> *) | m -> w

-- | <tt><a>writer</a> (a,w)</tt> embeds a simple writer action.
writer :: MonadWriter w m => (a, w) -> m a

-- | <tt><a>tell</a> w</tt> is an action that produces the output
--   <tt>w</tt>.
tell :: MonadWriter w m => w -> m ()

-- | <tt><a>listen</a> m</tt> is an action that executes the action
--   <tt>m</tt> and adds its output to the value of the computation.
listen :: MonadWriter w m => m a -> m (a, w)

-- | <tt><a>pass</a> m</tt> is an action that executes the action
--   <tt>m</tt>, which returns a value and a function, and returns the
--   value, applying the function to the output.
pass :: MonadWriter w m => m (a, w -> w) -> m a

-- | A writer monad parameterized by the type <tt>w</tt> of output to
--   accumulate.
--   
--   The <a>return</a> function produces the output <a>mempty</a>, while
--   <a>&gt;&gt;=</a> combines the outputs of the subcomputations using
--   <a>mappend</a>.
type Writer w = WriterT w Identity

-- | Unwrap a writer computation as a (result, output) pair. (The inverse
--   of <a>writer</a>.)
runWriter :: Monoid w => Writer w a -> (a, w)

-- | Extract the output from a writer computation.
--   
--   <ul>
--   <li><pre><a>execWriter</a> m = <a>snd</a> (<a>runWriter</a>
--   m)</pre></li>
--   </ul>
execWriter :: Monoid w => Writer w a -> w

-- | Map both the return value and output of a computation using the given
--   function.
--   
--   <ul>
--   <li><pre><a>runWriter</a> (<a>mapWriter</a> f m) = f (<a>runWriter</a>
--   m)</pre></li>
--   </ul>
mapWriter :: (Monoid w, Monoid w') => (a, w) -> (b, w') -> Writer w a -> Writer w' b

-- | A writer monad parameterized by:
--   
--   <ul>
--   <li><tt>w</tt> - the output to accumulate.</li>
--   <li><tt>m</tt> - The inner monad.</li>
--   </ul>
--   
--   The <a>return</a> function produces the output <a>mempty</a>, while
--   <a>&gt;&gt;=</a> combines the outputs of the subcomputations using
--   <a>mappend</a>.
data WriterT w (m :: * -> *) a

-- | The WriterT constructor is deliberately not exported in the CPS module
--   to avoid exposing the hidden state w. writerT provides a safe way to
--   construct a WriterT with the same api as the original WriterT.
writerT :: (Functor m, Monoid w) => m (a, w) -> WriterT w m a

-- | Unwrap a writer computation.
runWriterT :: Monoid w => WriterT w m a -> m (a, w)

-- | Extract the output from a writer computation.
--   
--   <ul>
--   <li><pre><a>execWriterT</a> m = <a>liftM</a> <a>snd</a>
--   (<a>runWriterT</a> m)</pre></li>
--   </ul>
execWriterT :: (Monad m, Monoid w) => WriterT w m a -> m w

-- | Map both the return value and output of a computation using the given
--   function.
--   
--   <ul>
--   <li><pre><a>runWriterT</a> (<a>mapWriterT</a> f m) = f
--   (<a>runWriterT</a> m)</pre></li>
--   </ul>
mapWriterT :: (Monad n, Monoid w, Monoid w') => m (a, w) -> n (b, w') -> WriterT w m a -> WriterT w' n b

-- | Minimal definition is either both of <tt>get</tt> and <tt>put</tt> or
--   just <tt>state</tt>
class Monad m => MonadState s (m :: * -> *) | m -> s

-- | Return the state from the internals of the monad.
get :: MonadState s m => m s

-- | Replace the state inside the monad.
put :: MonadState s m => s -> m ()

-- | Embed a simple state action into the monad.
state :: MonadState s m => s -> (a, s) -> m a

-- | A state monad parameterized by the type <tt>s</tt> of the state to
--   carry.
--   
--   The <a>return</a> function leaves the state unchanged, while
--   <tt>&gt;&gt;=</tt> uses the final state of the first computation as
--   the initial state of the second.
type State s = StateT s Identity

-- | Gets specific component of the state, using a projection function
--   supplied.
gets :: MonadState s m => s -> a -> m a

-- | Monadic state transformer.
--   
--   Maps an old state to a new state inside a state monad. The old state
--   is thrown away.
--   
--   <pre>
--   Main&gt; :t modify ((+1) :: Int -&gt; Int)
--   modify (...) :: (MonadState Int a) =&gt; a ()
--   </pre>
--   
--   This says that <tt>modify (+1)</tt> acts over any Monad that is a
--   member of the <tt>MonadState</tt> class, with an <tt>Int</tt> state.
modify :: MonadState s m => s -> s -> m ()

-- | A variant of <a>modify</a> in which the computation is strict in the
--   new state.
modify' :: MonadState s m => s -> s -> m ()

-- | Unwrap a state monad computation as a function. (The inverse of
--   <a>state</a>.)
runState :: () => State s a -> s -> (a, s)

-- | Evaluate a state computation with the given initial state and return
--   the final value, discarding the final state.
--   
--   <ul>
--   <li><pre><a>evalState</a> m s = <a>fst</a> (<a>runState</a> m
--   s)</pre></li>
--   </ul>
evalState :: () => State s a -> s -> a

-- | Evaluate a state computation with the given initial state and return
--   the final state, discarding the final value.
--   
--   <ul>
--   <li><pre><a>execState</a> m s = <a>snd</a> (<a>runState</a> m
--   s)</pre></li>
--   </ul>
execState :: () => State s a -> s -> s

-- | Map both the return value and final state of a computation using the
--   given function.
--   
--   <ul>
--   <li><pre><a>runState</a> (<a>mapState</a> f m) = f . <a>runState</a>
--   m</pre></li>
--   </ul>
mapState :: () => (a, s) -> (b, s) -> State s a -> State s b

-- | <tt><a>withState</a> f m</tt> executes action <tt>m</tt> on a state
--   modified by applying <tt>f</tt>.
--   
--   <ul>
--   <li><pre><a>withState</a> f m = <a>modify</a> f &gt;&gt; m</pre></li>
--   </ul>
withState :: () => s -> s -> State s a -> State s a

-- | A state transformer monad parameterized by:
--   
--   <ul>
--   <li><tt>s</tt> - The state.</li>
--   <li><tt>m</tt> - The inner monad.</li>
--   </ul>
--   
--   The <a>return</a> function leaves the state unchanged, while
--   <tt>&gt;&gt;=</tt> uses the final state of the first computation as
--   the initial state of the second.
newtype StateT s (m :: * -> *) a
StateT :: s -> m (a, s) -> StateT s a
[runStateT] :: StateT s a -> s -> m (a, s)

-- | Evaluate a state computation with the given initial state and return
--   the final value, discarding the final state.
--   
--   <ul>
--   <li><pre><a>evalStateT</a> m s = <a>liftM</a> <a>fst</a>
--   (<a>runStateT</a> m s)</pre></li>
--   </ul>
evalStateT :: Monad m => StateT s m a -> s -> m a

-- | Evaluate a state computation with the given initial state and return
--   the final state, discarding the final value.
--   
--   <ul>
--   <li><pre><a>execStateT</a> m s = <a>liftM</a> <a>snd</a>
--   (<a>runStateT</a> m s)</pre></li>
--   </ul>
execStateT :: Monad m => StateT s m a -> s -> m s

-- | Map both the return value and final state of a computation using the
--   given function.
--   
--   <ul>
--   <li><pre><a>runStateT</a> (<a>mapStateT</a> f m) = f .
--   <a>runStateT</a> m</pre></li>
--   </ul>
mapStateT :: () => m (a, s) -> n (b, s) -> StateT s m a -> StateT s n b

-- | <tt><a>withStateT</a> f m</tt> executes action <tt>m</tt> on a state
--   modified by applying <tt>f</tt>.
--   
--   <ul>
--   <li><pre><a>withStateT</a> f m = <a>modify</a> f &gt;&gt; m</pre></li>
--   </ul>
withStateT :: () => s -> s -> StateT s m a -> StateT s m a
class (Monoid w, MonadReader r m, MonadWriter w m, MonadState s m) => MonadRWS r w s (m :: * -> *) | m -> r, m -> w, m -> s

-- | A monad containing an environment of type <tt>r</tt>, output of type
--   <tt>w</tt> and an updatable state of type <tt>s</tt>.
type RWS r w s = RWST r w s Identity

-- | Construct an RWS computation from a function. (The inverse of
--   <a>runRWS</a>.)
rws :: Monoid w => r -> s -> (a, s, w) -> RWS r w s a

-- | Unwrap an RWS computation as a function. (The inverse of <a>rws</a>.)
runRWS :: Monoid w => RWS r w s a -> r -> s -> (a, s, w)

-- | Evaluate a computation with the given initial state and environment,
--   returning the final value and output, discarding the final state.
evalRWS :: Monoid w => RWS r w s a -> r -> s -> (a, w)

-- | Evaluate a computation with the given initial state and environment,
--   returning the final state and output, discarding the final value.
execRWS :: Monoid w => RWS r w s a -> r -> s -> (s, w)

-- | Map the return value, final state and output of a computation using
--   the given function.
--   
--   <ul>
--   <li><pre><a>runRWS</a> (<a>mapRWS</a> f m) r s = f (<a>runRWS</a> m r
--   s)</pre></li>
--   </ul>
mapRWS :: (Monoid w, Monoid w') => (a, s, w) -> (b, s, w') -> RWS r w s a -> RWS r w' s b

-- | A monad transformer adding reading an environment of type <tt>r</tt>,
--   collecting an output of type <tt>w</tt> and updating a state of type
--   <tt>s</tt> to an inner monad <tt>m</tt>.
data RWST r w s (m :: * -> *) a

-- | The RWST constructor is deliberately not exported in the CPS module to
--   avoid exposing the hidden state w. rwsT provides a safe way to
--   construct a RWST with the same api as the original RWST.
rwsT :: (Functor m, Monoid w) => r -> s -> m (a, s, w) -> RWST r w s m a

-- | Unwrap an RWST computation as a function.
runRWST :: Monoid w => RWST r w s m a -> r -> s -> m (a, s, w)

-- | Evaluate a computation with the given initial state and environment,
--   returning the final value and output, discarding the final state.
evalRWST :: (Monad m, Monoid w) => RWST r w s m a -> r -> s -> m (a, w)

-- | Evaluate a computation with the given initial state and environment,
--   returning the final state and output, discarding the final value.
execRWST :: (Monad m, Monoid w) => RWST r w s m a -> r -> s -> m (s, w)

-- | Map the inner computation using the given function.
--   
--   <ul>
--   <li><tt><a>runRWST</a> (<a>mapRWST</a> f m) r s = f (<a>runRWST</a> m
--   r s)</tt> mapRWST :: (m (a, s, w) -&gt; n (b, s, w')) -&gt; RWST r w s
--   m a -&gt; RWST r w' s n b</li>
--   </ul>
mapRWST :: (Monad n, Monoid w, Monoid w') => m (a, s, w) -> n (b, s, w') -> RWST r w s m a -> RWST r w' s n b

-- | Representable types of kind <tt>*</tt>. This class is derivable in GHC
--   with the <tt>DeriveGeneric</tt> flag on.
--   
--   A <a>Generic</a> instance must satisfy the following laws:
--   
--   <pre>
--   <a>from</a> . <a>to</a> ≡ <tt>id</tt>
--   <a>to</a> . <a>from</a> ≡ <tt>id</tt>
--   </pre>
class Generic a

-- | Representable types of kind <tt>* -&gt; *</tt> (or kind <tt>k -&gt;
--   *</tt>, when <tt>PolyKinds</tt> is enabled). This class is derivable
--   in GHC with the <tt>DeriveGeneric</tt> flag on.
--   
--   A <a>Generic1</a> instance must satisfy the following laws:
--   
--   <pre>
--   <a>from1</a> . <a>to1</a> ≡ <tt>id</tt>
--   <a>to1</a> . <a>from1</a> ≡ <tt>id</tt>
--   </pre>
class Generic1 (f :: k -> *)

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

-- | The <a>Binary</a> class provides <a>put</a> and <a>get</a>, methods to
--   encode and decode a Haskell value to a lazy <a>ByteString</a>. It
--   mirrors the <a>Read</a> and <a>Show</a> classes for textual
--   representation of Haskell types, and is suitable for serialising
--   Haskell values to disk, over the network.
--   
--   For decoding and generating simple external binary formats (e.g. C
--   structures), Binary may be used, but in general is not suitable for
--   complex protocols. Instead use the <a>Put</a> and <a>Get</a>
--   primitives directly.
--   
--   Instances of Binary should satisfy the following property:
--   
--   <pre>
--   decode . encode == id
--   </pre>
--   
--   That is, the <a>get</a> and <a>put</a> methods should be the inverse
--   of each other. A range of instances are provided for basic Haskell
--   types.
class Binary t

-- | A class of types that can be fully evaluated.
class NFData a

-- | A class of functors that can be fully evaluated.
class NFData1 (f :: * -> *)

-- | A class of bifunctors that can be fully evaluated.
class NFData2 (p :: * -> * -> *)

-- | The kind of types with values. For example <tt>Int :: Type</tt>.
type Type = *

-- | The kind of constraints, like <tt>Show a</tt>
data Constraint

-- | <a>Proxy</a> is a type that holds no data, but has a phantom parameter
--   of arbitrary type (or even kind). Its use is to provide type
--   information, even though there is no value available of that type (or
--   it may be too costly to create one).
--   
--   Historically, <tt><a>Proxy</a> :: <a>Proxy</a> a</tt> is a safer
--   alternative to the <tt>'undefined :: a'</tt> idiom.
--   
--   <pre>
--   &gt;&gt;&gt; Proxy :: Proxy (Void, Int -&gt; Int)
--   Proxy
--   </pre>
--   
--   Proxy can even hold types of higher kinds,
--   
--   <pre>
--   &gt;&gt;&gt; Proxy :: Proxy Either
--   Proxy
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Proxy :: Proxy Functor
--   Proxy
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Proxy :: Proxy complicatedStructure
--   Proxy
--   </pre>
data Proxy (t :: k) :: forall k. () => k -> *
Proxy :: Proxy

-- | 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 <tt>&gt;&gt;</tt> and <tt>&gt;&gt;=</tt>
--   operations from the <tt>Monad</tt> class.
data IO 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 :: * -> *)

-- | Lift a computation from the <a>IO</a> monad.
liftIO :: MonadIO m => IO a -> m a

-- | Read a character from the standard input device.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
getChar :: MonadIO m => m Char

-- | The <a>getContents</a> operation returns all user input as a strict
--   <a>Text</a>.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
getContents :: MonadIO m => m Text

-- | Read a line from the standard input device as a strict <a>Text</a>.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
getLine :: MonadIO m => m Text

-- | The <a>print</a> function outputs a value of any printable type to the
--   standard output device. Printable types are those that are instances
--   of class <a>Show</a>; <a>print</a> converts values to strings for
--   output using the <a>show</a> operation and adds a newline.
--   
--   For example, a program to print the first 20 integers and their powers
--   of 2 could be written as:
--   
--   <pre>
--   main = print ([(n, 2^n) | n &lt;- [0..19]])
--   </pre>
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
print :: (MonadIO m, Show a) => a -> m ()

-- | Write a character to the standard output device.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
putChar :: MonadIO m => Char -> m ()

-- | Write a strict <a>Text</a> to the standard output device.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
putStr :: MonadIO m => Text -> m ()

-- | The same as <a>putStr</a>, but adds a newline character.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
putStrLn :: MonadIO m => Text -> m ()

-- | 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

-- | Read an entire file strictly into a <a>ByteString</a>.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
readFile :: MonadIO m => FilePath -> m ByteString

-- | Write a <a>ByteString</a> to a file.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
writeFile :: MonadIO m => FilePath -> ByteString -> m ()

-- | Append a <a>ByteString</a> to a file.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
appendFile :: MonadIO m => FilePath -> ByteString -> m ()

-- | Read an entire file strictly into a <a>Text</a> using UTF-8 encoding.
--   The decoding is done using <a>decodeStringLenient</a>. Invalid
--   characters are replaced by the Unicode replacement character '\FFFD'.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
readFileUtf8 :: MonadIO m => FilePath -> m Text

-- | Write a <a>Text</a> to a file using UTF-8 encoding.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
writeFileUtf8 :: MonadIO m => FilePath -> Text -> m ()

-- | Append a <a>Text</a> to a file using UTF-8 encoding.
--   
--   <b>Note</b>: This function is lifted to the <a>MonadIO</a> class.
appendFileUtf8 :: MonadIO m => FilePath -> Text -> m ()

-- | Request a CallStack.
--   
--   NOTE: The implicit parameter <tt>?callStack :: CallStack</tt> is an
--   implementation detail and <b>should not</b> be considered part of the
--   <a>CallStack</a> API, we may decide to change the implementation in
--   the future.
type HasCallStack = ?callStack :: CallStack

-- | 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 <tt>&gt;&gt;=</tt>,
--   
--   <pre>
--   fail s &gt;&gt;= f  =  fail s
--   </pre>
--   
--   If your <a>Monad</a> is also <tt>MonadPlus</tt>, a popular definition
--   is
--   
--   <pre>
--   fail _ = mzero
--   </pre>
class Monad m => MonadFail (m :: * -> *)

-- | Monad fail function from the <a>MonadFail</a> class.
--   
--   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 <tt>Monad</tt> without a <tt>MonadFail</tt> 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 <tt>MonadFail</tt> should satisfy the following law:
--   <tt>fail s</tt> should be a left zero for <tt>&gt;&gt;=</tt>,
--   
--   <pre>
--   fail s &gt;&gt;= f  =  fail s
--   </pre>
--   
--   If your <tt>Monad</tt> is also <tt>MonadPlus</tt>, a popular
--   definition is
--   
--   <pre>
--   fail _ = mzero
--   </pre>
fail :: MonadFail m => Text -> m a

-- | Throw an unhandled error to terminate the program in case of a logic
--   error at runtime. Use this function instead of <a>error</a>. A stack
--   trace will be provided.
--   
--   In general, prefer total functions. You can use <a>Maybe</a>,
--   <a>Either</a>, <a>ExceptT</a> or <a>MonadError</a> for error handling.
panic :: HasCallStack => Text -> a

-- | Throw an undefined error. Use only for debugging.

-- | <i>Warning: <a>undefined</a> should be used only for debugging</i>
undefined :: HasCallStack => a

-- | The <a>trace</a> function outputs the trace message given as its first
--   argument, before returning the second argument as its result.
--   
--   For example, this returns the value of <tt>f x</tt> but first outputs
--   the message.
--   
--   <pre>
--   trace ("calling f with x = " ++ show x) (f x)
--   </pre>
--   
--   The <a>trace</a> function should <i>only</i> be used for debugging, or
--   for monitoring execution. The function is not referentially
--   transparent: its type indicates that it is a pure function but it has
--   the side effect of outputting the trace message.

-- | <i>Warning: <a>trace</a> should be used only for debugging</i>
trace :: Text -> a -> a

-- | The <a>traceIO</a> function outputs the trace message from the IO
--   monad. This sequences the output with respect to other IO actions.

-- | <i>Warning: <a>traceIO</a> should be used only for debugging</i>
traceIO :: MonadIO m => Text -> m ()

-- | Like <a>trace</a> but returns the message instead of a third value.

-- | <i>Warning: <a>traceId</a> should be used only for debugging</i>
traceId :: Text -> Text

-- | Like <a>trace</a> but returning unit in an arbitrary
--   <a>Applicative</a> context. Allows for convenient use in do-notation.
--   
--   Note that the application of <a>traceM</a> is not an action in the
--   <a>Applicative</a> context, as <a>traceIO</a> is in the <a>MonadIO</a>
--   type. While the fresh bindings in the following example will force the
--   <a>traceM</a> expressions to be reduced every time the
--   <tt>do</tt>-block is executed, <tt>traceM "not crashed"</tt> would
--   only be reduced once, and the message would only be printed once. If
--   your monad is in <a>MonadIO</a>, <tt>traceIO</tt> may be a better
--   option.
--   
--   <pre>
--   ... = do
--     x &lt;- ...
--     traceM $ "x: " ++ show x
--     y &lt;- ...
--     traceM $ "y: " ++ show y
--   </pre>

-- | <i>Warning: <a>traceM</a> should be used only for debugging</i>
traceM :: Applicative m => Text -> m ()

-- | Like <a>trace</a>, but uses <tt>show</tt> on the argument to convert
--   it to a <tt>String</tt>.
--   
--   This makes it convenient for printing the values of interesting
--   variables or expressions inside a function. For example here we print
--   the value of the variables <tt>x</tt> and <tt>z</tt>:
--   
--   <pre>
--   f x y =
--       traceShow (x, z) $ result
--     where
--       z = ...
--       ...
--   </pre>

-- | <i>Warning: <a>traceShow</a> should be used only for debugging</i>
traceShow :: Show a => a -> b -> b

-- | Like <a>traceShow</a> but returns the shown value instead of a third
--   value.

-- | <i>Warning: <a>traceShowId</a> should be used only for debugging</i>
traceShowId :: Show a => a -> a

-- | Like <a>traceM</a>, but uses <tt>show</tt> on the argument to convert
--   it to a <tt>String</tt>.
--   
--   <pre>
--   ... = do
--     x &lt;- ...
--     traceShowM $ x
--     y &lt;- ...
--     traceShowM $ x + y
--   </pre>

-- | <i>Warning: <a>traceShowM</a> should be used only for debugging</i>
traceShowM :: (Show a, Applicative m) => a -> m ()
