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


-- | The command-line interface for Cabal and Hackage.
--   
--   The solver component used in cabal-install command-line program
@package cabal-install-solver
@version 3.10.3.0

module Distribution.Client.Utils.Assertion

-- | Like <tt>assert</tt>, but only enabled with
--   -fdebug-expensive-assertions. This function can be used for expensive
--   assertions that should only be turned on during testing or debugging.
expensiveAssert :: Bool -> a -> a


-- | This module does two things:
--   
--   <ul>
--   <li>Acts as a compatibility layer, like <tt>base-compat</tt>.</li>
--   <li>Provides commonly used imports.</li>
--   </ul>
--   
--   This module is a superset of <a>Distribution.Compat.Prelude</a> (which
--   this module re-exports)
module Distribution.Solver.Compat.Prelude

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

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

-- | The <a>Data</a> class comprehends a fundamental primitive
--   <a>gfoldl</a> for folding over constructor applications, say terms.
--   This primitive can be instantiated in several ways to map over the
--   immediate subterms of a term; see the <tt>gmap</tt> combinators later
--   in this class. Indeed, a generic programmer does not necessarily need
--   to use the ingenious gfoldl primitive but rather the intuitive
--   <tt>gmap</tt> combinators. The <a>gfoldl</a> primitive is completed by
--   means to query top-level constructors, to turn constructor
--   representations into proper terms, and to list all possible datatype
--   constructors. This completion allows us to serve generic programming
--   scenarios like read, show, equality, term generation.
--   
--   The combinators <a>gmapT</a>, <a>gmapQ</a>, <a>gmapM</a>, etc are all
--   provided with default definitions in terms of <a>gfoldl</a>, leaving
--   open the opportunity to provide datatype-specific definitions. (The
--   inclusion of the <tt>gmap</tt> combinators as members of class
--   <a>Data</a> allows the programmer or the compiler to derive
--   specialised, and maybe more efficient code per datatype. <i>Note</i>:
--   <a>gfoldl</a> is more higher-order than the <tt>gmap</tt> combinators.
--   This is subject to ongoing benchmarking experiments. It might turn out
--   that the <tt>gmap</tt> combinators will be moved out of the class
--   <a>Data</a>.)
--   
--   Conceptually, the definition of the <tt>gmap</tt> combinators in terms
--   of the primitive <a>gfoldl</a> requires the identification of the
--   <a>gfoldl</a> function arguments. Technically, we also need to
--   identify the type constructor <tt>c</tt> for the construction of the
--   result type from the folded term type.
--   
--   In the definition of <tt>gmapQ</tt><i>x</i> combinators, we use
--   phantom type constructors for the <tt>c</tt> in the type of
--   <a>gfoldl</a> because the result type of a query does not involve the
--   (polymorphic) type of the term argument. In the definition of
--   <a>gmapQl</a> we simply use the plain constant type constructor
--   because <a>gfoldl</a> is left-associative anyway and so it is readily
--   suited to fold a left-associative binary operation over the immediate
--   subterms. In the definition of gmapQr, extra effort is needed. We use
--   a higher-order accumulation trick to mediate between left-associative
--   constructor application vs. right-associative binary operation (e.g.,
--   <tt>(:)</tt>). When the query is meant to compute a value of type
--   <tt>r</tt>, then the result type within generic folding is <tt>r -&gt;
--   r</tt>. So the result of folding is a function to which we finally
--   pass the right unit.
--   
--   With the <tt>-XDeriveDataTypeable</tt> option, GHC can generate
--   instances of the <a>Data</a> class automatically. For example, given
--   the declaration
--   
--   <pre>
--   data T a b = C1 a b | C2 deriving (Typeable, Data)
--   </pre>
--   
--   GHC will generate an instance that is equivalent to
--   
--   <pre>
--   instance (Data a, Data b) =&gt; Data (T a b) where
--       gfoldl k z (C1 a b) = z C1 `k` a `k` b
--       gfoldl k z C2       = z C2
--   
--       gunfold k z c = case constrIndex c of
--                           1 -&gt; k (k (z C1))
--                           2 -&gt; z C2
--   
--       toConstr (C1 _ _) = con_C1
--       toConstr C2       = con_C2
--   
--       dataTypeOf _ = ty_T
--   
--   con_C1 = mkConstr ty_T "C1" [] Prefix
--   con_C2 = mkConstr ty_T "C2" [] Prefix
--   ty_T   = mkDataType "Module.T" [con_C1, con_C2]
--   </pre>
--   
--   This is suitable for datatypes that are exported transparently.
class Typeable a => Data a

-- | 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> ≡ <a>id</a>
--   <a>to</a> . <a>from</a> ≡ <a>id</a>
--   </pre>
class () => Generic a

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

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

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

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

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

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

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

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

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

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

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

-- | List of elements of a structure, from left to right. If the entire
--   list is intended to be reduced via a fold, just fold the structure
--   directly bypassing the list.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; toList Nothing
--   []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toList (Just 42)
--   [42]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toList (Left "foo")
--   []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toList (Node (Leaf 5) 17 (Node Empty 12 (Leaf 8)))
--   [5,17,12,8]
--   </pre>
--   
--   For lists, <a>toList</a> is the identity:
--   
--   <pre>
--   &gt;&gt;&gt; toList [1, 2, 3]
--   [1,2,3]
--   </pre>
toList :: Foldable t => t a -> [a]

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

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

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

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

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

-- | The <a>sum</a> function computes the sum of the numbers of a
--   structure.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; sum []
--   0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sum [42]
--   42
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sum [1..10]
--   55
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sum [4.1, 2.0, 1.7]
--   7.8
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sum [1..]
--   * Hangs forever *
--   </pre>
sum :: (Foldable t, Num a) => t a -> a

-- | The <a>product</a> function computes the product of the numbers of a
--   structure.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; product []
--   1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; product [42]
--   42
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; product [1..10]
--   3628800
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; product [4.1, 2.0, 1.7]
--   13.939999999999998
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; product [1..]
--   * Hangs forever *
--   </pre>
product :: (Foldable t, Num a) => t a -> a
infix 4 `elem`

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- | conversion to <a>Integer</a>
toInteger :: Integral a => a -> Integer
infixl 7 `quot`
infixl 7 `rem`
infixl 7 `div`
infixl 7 `mod`

-- | The <a>Monad</a> class defines the basic operations over a
--   <i>monad</i>, a concept from a branch of mathematics known as
--   <i>category theory</i>. From the perspective of a Haskell programmer,
--   however, it is best to think of a monad as an <i>abstract datatype</i>
--   of actions. Haskell's <tt>do</tt> expressions provide a convenient
--   syntax for writing monadic expressions.
--   
--   Instances of <a>Monad</a> should satisfy the following:
--   
--   <ul>
--   <li><i>Left identity</i> <tt><a>return</a> a <a>&gt;&gt;=</a> k = k
--   a</tt></li>
--   <li><i>Right identity</i> <tt>m <a>&gt;&gt;=</a> <a>return</a> =
--   m</tt></li>
--   <li><i>Associativity</i> <tt>m <a>&gt;&gt;=</a> (\x -&gt; k x
--   <a>&gt;&gt;=</a> h) = (m <a>&gt;&gt;=</a> k) <a>&gt;&gt;=</a>
--   h</tt></li>
--   </ul>
--   
--   Furthermore, the <a>Monad</a> and <a>Applicative</a> operations should
--   relate as follows:
--   
--   <ul>
--   <li><pre><a>pure</a> = <a>return</a></pre></li>
--   <li><pre>m1 <a>&lt;*&gt;</a> m2 = m1 <a>&gt;&gt;=</a> (\x1 -&gt; m2
--   <a>&gt;&gt;=</a> (\x2 -&gt; <a>return</a> (x1 x2)))</pre></li>
--   </ul>
--   
--   The above laws imply:
--   
--   <ul>
--   <li><pre><a>fmap</a> f xs = xs <a>&gt;&gt;=</a> <a>return</a> .
--   f</pre></li>
--   <li><pre>(<a>&gt;&gt;</a>) = (<a>*&gt;</a>)</pre></li>
--   </ul>
--   
--   and that <a>pure</a> and (<a>&lt;*&gt;</a>) satisfy the applicative
--   functor laws.
--   
--   The instances of <a>Monad</a> for lists, <a>Maybe</a> and <a>IO</a>
--   defined in the <a>Prelude</a> satisfy these laws.
class Applicative m => Monad (m :: Type -> Type)

-- | Sequentially compose two actions, passing any value produced by the
--   first as an argument to the second.
--   
--   '<tt>as <a>&gt;&gt;=</a> bs</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do a &lt;- as
--      bs a
--   </pre>
(>>=) :: Monad m => m a -> (a -> m b) -> m b

-- | Sequentially compose two actions, discarding any value produced by the
--   first, like sequencing operators (such as the semicolon) in imperative
--   languages.
--   
--   '<tt>as <a>&gt;&gt;</a> bs</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do as
--      bs
--   </pre>
(>>) :: Monad m => m a -> m b -> m b

-- | Inject a value into the monadic type.
return :: Monad m => a -> m a
infixl 1 >>=
infixl 1 >>

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

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

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

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

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

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

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

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

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

-- | Real numbers.
--   
--   The Haskell report defines no laws for <a>Real</a>, however
--   <a>Real</a> instances are customarily expected to adhere to the
--   following law:
--   
--   <ul>
--   <li><i><b>Coherence with <a>fromRational</a></b></i> if the type also
--   implements <a>Fractional</a>, then <a>fromRational</a> is a left
--   inverse for <a>toRational</a>, i.e. <tt>fromRational (toRational i) =
--   i</tt></li>
--   </ul>
class (Num a, Ord a) => Real a

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- | Lift a value.
pure :: Applicative f => a -> f a

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

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

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

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

-- | The class of semigroups (types with an associative binary operation).
--   
--   Instances should satisfy the following:
--   
--   <ul>
--   <li><i>Associativity</i> <tt>x <a>&lt;&gt;</a> (y <a>&lt;&gt;</a> z) =
--   (x <a>&lt;&gt;</a> y) <a>&lt;&gt;</a> z</tt></li>
--   </ul>
--   
--   You can alternatively define <a>sconcat</a> instead of
--   (<a>&lt;&gt;</a>), in which case the laws are:
--   
--   <ul>
--   <li><i>Unit</i> <tt><a>sconcat</a> (<a>pure</a> x) = x</tt></li>
--   <li><i>Multiplication</i> <tt><a>sconcat</a> (<a>join</a> xss) =
--   <a>sconcat</a> (<a>fmap</a> <a>sconcat</a> xss)</tt></li>
--   </ul>
class () => Semigroup a

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

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

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

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

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

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

-- | 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 <a>ord</a> and
--   <a>chr</a>).
data () => Char

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

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

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

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

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

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

-- | Lifted, homogeneous equality. By lifted, we mean that it can be bogus
--   (deferred type error). By homogeneous, the two types <tt>a</tt> and
--   <tt>b</tt> must have the same kinds.
class a ~# b => (a :: k) ~ (b :: k)
infix 4 ~

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

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

-- | Uninhabited data type
data () => Void

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

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

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

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

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

-- | 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 = (:) <a>&lt;$&gt;</a> 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 :: Type -> Type)

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

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

-- | One or more.
some :: Alternative f => f a -> f [a]

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

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

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

-- | <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><a>undefined</a> :: 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)
Proxy :: Proxy (t :: k)

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

-- | A quantified type representation.
type TypeRep = SomeTypeRep

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

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

-- | The Haskell 2010 type for exceptions in the <a>IO</a> monad. Any I/O
--   operation may raise an <a>IOException</a> instead of returning a
--   result. For a more general type of exception, including also those
--   that arise in pure code, see <a>Exception</a>.
--   
--   In Haskell 2010, this is an opaque type.
type IOError = IOException

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

-- | Defines the exit codes that a program can return.
data () => ExitCode

-- | indicates successful termination;
ExitSuccess :: ExitCode

-- | indicates program failure with an exit code. The exact interpretation
--   of the code is operating-system dependent. In particular, some values
--   may be prohibited (e.g. 0 on a POSIX-compliant system).
ExitFailure :: Int -> ExitCode

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

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

-- | Encode a value in the Put monad.
put :: Binary t => t -> Put

-- | Decode a value in the Get monad
get :: Binary t => Get t

-- | Encode a list of values in the Put monad. The default implementation
--   may be overridden to be more efficient but must still have the same
--   encoding format.
putList :: Binary t => [t] -> Put

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

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

-- | A class of types that can be fully evaluated.
class () => NFData a

-- | <a>rnf</a> should reduce its argument to normal form (that is, fully
--   evaluate all sub-components), and then return <tt>()</tt>.
--   
--   <h3><a>Generic</a> <a>NFData</a> deriving</h3>
--   
--   Starting with GHC 7.2, you can automatically derive instances for
--   types possessing a <a>Generic</a> instance.
--   
--   Note: <a>Generic1</a> can be auto-derived starting with GHC 7.4
--   
--   <pre>
--   {-# LANGUAGE DeriveGeneric #-}
--   
--   import GHC.Generics (Generic, Generic1)
--   import Control.DeepSeq
--   
--   data Foo a = Foo a String
--                deriving (Eq, Generic, Generic1)
--   
--   instance NFData a =&gt; NFData (Foo a)
--   instance NFData1 Foo
--   
--   data Colour = Red | Green | Blue
--                 deriving Generic
--   
--   instance NFData Colour
--   </pre>
--   
--   Starting with GHC 7.10, the example above can be written more
--   concisely by enabling the new <tt>DeriveAnyClass</tt> extension:
--   
--   <pre>
--   {-# LANGUAGE DeriveGeneric, DeriveAnyClass #-}
--   
--   import GHC.Generics (Generic)
--   import Control.DeepSeq
--   
--   data Foo a = Foo a String
--                deriving (Eq, Generic, Generic1, NFData, NFData1)
--   
--   data Colour = Red | Green | Blue
--                 deriving (Generic, NFData)
--   </pre>
--   
--   <h3>Compatibility with previous <tt>deepseq</tt> versions</h3>
--   
--   Prior to version 1.4.0.0, the default implementation of the <a>rnf</a>
--   method was defined as
--   
--   <pre>
--   <a>rnf</a> a = <a>seq</a> a ()
--   </pre>
--   
--   However, starting with <tt>deepseq-1.4.0.0</tt>, the default
--   implementation is based on <tt>DefaultSignatures</tt> allowing for
--   more accurate auto-derived <a>NFData</a> instances. If you need the
--   previously used exact default <a>rnf</a> method implementation
--   semantics, use
--   
--   <pre>
--   instance NFData Colour where rnf x = seq x ()
--   </pre>
--   
--   or alternatively
--   
--   <pre>
--   instance NFData Colour where rnf = rwhnf
--   </pre>
--   
--   or
--   
--   <pre>
--   {-# LANGUAGE BangPatterns #-}
--   instance NFData Colour where rnf !_ = ()
--   </pre>
rnf :: NFData a => a -> ()

-- | Class of types with a known <a>Structure</a>.
--   
--   For regular data types <a>Structured</a> can be derived generically.
--   
--   <pre>
--   data Record = Record { a :: Int, b :: Bool, c :: [Char] } deriving (<a>Generic</a>)
--   instance <a>Structured</a> Record
--   </pre>
class Typeable a => Structured a

data () => NonEmptySet a

-- | <a>deepseq</a>: fully evaluates the first argument, before returning
--   the second.
--   
--   The name <a>deepseq</a> is used to illustrate the relationship to
--   <a>seq</a>: where <a>seq</a> is shallow in the sense that it only
--   evaluates the top level of its argument, <a>deepseq</a> traverses the
--   entire data structure evaluating it completely.
--   
--   <a>deepseq</a> can be useful for forcing pending exceptions,
--   eradicating space leaks, or forcing lazy I/O to happen. It is also
--   useful in conjunction with parallel Strategies (see the
--   <tt>parallel</tt> package).
--   
--   There is no guarantee about the ordering of evaluation. The
--   implementation may evaluate the components of the structure in any
--   order or in parallel. To impose an actual order on evaluation, use
--   <tt>pseq</tt> from <a>Control.Parallel</a> in the <tt>parallel</tt>
--   package.
deepseq :: NFData a => a -> b -> b
infixr 0 `deepseq`

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

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

-- | Extract everything except the last element of the stream.
init :: NonEmpty a -> [a]

-- | &lt;math&gt;. The <a>nub</a> function removes duplicate elements from
--   a list. In particular, it keeps only the first occurrence of each
--   element. (The name <a>nub</a> means `essence'.) It is a special case
--   of <a>nubBy</a>, which allows the programmer to supply their own
--   equality test.
--   
--   <pre>
--   &gt;&gt;&gt; nub [1,2,3,4,3,2,1,2,4,3,5]
--   [1,2,3,4,5]
--   </pre>
--   
--   If the order of outputs does not matter and there exists <tt>instance
--   Ord a</tt>, it's faster to use <a>map</a>
--   <tt>Data.List.NonEmpty.</tt><a>head</a> .
--   <tt>Data.List.NonEmpty.</tt><a>group</a> . <a>sort</a>, which takes
--   only &lt;math&gt; time.
nub :: Eq a => [a] -> [a]

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

-- | Append two lists, i.e.,
--   
--   <pre>
--   [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
--   [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
--   </pre>
--   
--   If the first list is not finite, the result is the first list.
--   
--   WARNING: This function takes linear time in the number of elements of
--   the first list.
(++) :: [a] -> [a] -> [a]
infixr 5 ++

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

-- | &lt;math&gt;. <a>filter</a>, applied to a predicate and a list,
--   returns the list of those elements that satisfy the predicate; i.e.,
--   
--   <pre>
--   filter p xs = [ x | x &lt;- xs, p x]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; filter odd [1, 2, 3]
--   [1,3]
--   </pre>
filter :: (a -> Bool) -> [a] -> [a]

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

-- | 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>
print :: Show a => a -> IO ()

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

-- | &lt;math&gt;. <a>map</a> <tt>f xs</tt> is the list obtained by
--   applying <tt>f</tt> to each element of <tt>xs</tt>, i.e.,
--   
--   <pre>
--   map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
--   map f [x1, x2, ...] == [f x1, f x2, ...]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map (+1) [1, 2, 3]
--   [2,3,4]
--   </pre>
map :: (a -> b) -> [a] -> [b]

-- | 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>.
--   
--   Note that <tt>(<a>$</a>)</tt> is representation-polymorphic in its
--   result type, so that <tt>foo <a>$</a> True</tt> where <tt>foo :: Bool
--   -&gt; Int#</tt> is well-typed.
($) :: forall (r :: RuntimeRep) a (b :: TYPE r). (a -> b) -> a -> b
infixr 0 $

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

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

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

-- | 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
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; safeDiv 4 2
--   Just 2
--   </pre>
--   
--   A definition of <tt>safeDiv</tt> using guards, but not <a>guard</a>:
--   
--   <pre>
--   safeDiv :: Int -&gt; Int -&gt; Maybe Int
--   safeDiv x y | y /= 0    = Just (x `div` y)
--               | otherwise = Nothing
--   </pre>
--   
--   A definition of <tt>safeDiv</tt> using <a>guard</a> and <a>Monad</a>
--   <tt>do</tt>-notation:
--   
--   <pre>
--   safeDiv :: Int -&gt; Int -&gt; Maybe Int
--   safeDiv x y = do
--     guard (y /= 0)
--     return (x `div` y)
--   </pre>
guard :: Alternative f => Bool -> f ()

-- | The <a>join</a> function is the conventional monad join operator. It
--   is used to remove one level of monadic structure, projecting its bound
--   argument into the outer level.
--   
--   '<tt><a>join</a> bss</tt>' can be understood as the <tt>do</tt>
--   expression
--   
--   <pre>
--   do bs &lt;- bss
--      bs
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   A common use of <a>join</a> is to run an <a>IO</a> computation
--   returned from an <a>STM</a> transaction, since <a>STM</a> transactions
--   can't perform <a>IO</a> directly. Recall that
--   
--   <pre>
--   <a>atomically</a> :: STM a -&gt; IO a
--   </pre>
--   
--   is used to run <a>STM</a> transactions atomically. So, by specializing
--   the types of <a>atomically</a> and <a>join</a> to
--   
--   <pre>
--   <a>atomically</a> :: STM (IO b) -&gt; IO (IO b)
--   <a>join</a>       :: IO (IO b)  -&gt; IO b
--   </pre>
--   
--   we can compose them as
--   
--   <pre>
--   <a>join</a> . <a>atomically</a> :: STM (IO b) -&gt; IO b
--   </pre>
--   
--   to run an <a>STM</a> transaction and the <a>IO</a> action it returns.
join :: Monad m => m (m a) -> m a

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

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

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

-- | <a>error</a> stops execution and displays an error message.
error :: forall (r :: RuntimeRep) (a :: TYPE r). HasCallStack => [Char] -> a

-- | A variant of <a>error</a> that does not produce a stack trace.
errorWithoutStackTrace :: forall (r :: RuntimeRep) (a :: TYPE r). [Char] -> a

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

-- | Since <a>Void</a> values logically don't exist, this witnesses the
--   logical reasoning tool of "ex falso quodlibet".
--   
--   <pre>
--   &gt;&gt;&gt; let x :: Either Void Int; x = Right 5
--   
--   &gt;&gt;&gt; :{
--   case x of
--       Right r -&gt; r
--       Left l  -&gt; absurd l
--   :}
--   5
--   </pre>
absurd :: Void -> a

-- | If <a>Void</a> is uninhabited then any <a>Functor</a> that holds only
--   values of type <a>Void</a> is holding no values. It is implemented in
--   terms of <tt>fmap absurd</tt>.
vacuous :: Functor f => f Void -> f a

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

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

-- | Promote a function to a monad.
liftM :: Monad m => (a1 -> r) -> m a1 -> m r

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

-- | In many situations, the <a>liftM</a> operations can be replaced by
--   uses of <a>ap</a>, which promotes function application.
--   
--   <pre>
--   return f `ap` x1 `ap` ... `ap` xn
--   </pre>
--   
--   is equivalent to
--   
--   <pre>
--   liftMn f x1 x2 ... xn
--   </pre>
ap :: Monad m => m (a -> b) -> m a -> m b

-- | The <a>fromEnum</a> method restricted to the type <a>Char</a>.
ord :: Char -> Int

-- | Identity function.
--   
--   <pre>
--   id x = x
--   </pre>
id :: a -> a

-- | <tt>const x y</tt> always evaluates to <tt>x</tt>, ignoring its second
--   argument.
--   
--   <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

-- | Function composition.
(.) :: (b -> c) -> (a -> b) -> a -> c
infixr 9 .

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

-- | 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.
($!) :: forall (r :: RuntimeRep) a (b :: TYPE r). (a -> b) -> a -> b
infixr 0 $!

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

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

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

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

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

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

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

-- | &lt;math&gt;. <a>scanl1</a> is a variant of <a>scanl</a> that has no
--   starting value argument:
--   
--   <pre>
--   scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; scanl1 (+) [1..4]
--   [1,3,6,10]
--   
--   &gt;&gt;&gt; scanl1 (+) []
--   []
--   
--   &gt;&gt;&gt; scanl1 (-) [1..4]
--   [1,-1,-4,-8]
--   
--   &gt;&gt;&gt; scanl1 (&amp;&amp;) [True, False, True, True]
--   [True,False,False,False]
--   
--   &gt;&gt;&gt; scanl1 (||) [False, False, True, True]
--   [False,False,True,True]
--   
--   &gt;&gt;&gt; scanl1 (+) [1..]
--   * Hangs forever *
--   </pre>
scanl1 :: (a -> a -> a) -> [a] -> [a]

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

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

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

-- | <a>repeat</a> <tt>x</tt> is an infinite list, with <tt>x</tt> the
--   value of every element.
--   
--   <pre>
--   &gt;&gt;&gt; repeat 17
--   [17,17,17,17,17,17,17,17,17...
--   </pre>
repeat :: a -> [a]

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

-- | <a>cycle</a> ties a finite list into a circular one, or equivalently,
--   the infinite repetition of the original list. It is the identity on
--   infinite lists.
--   
--   <pre>
--   &gt;&gt;&gt; cycle []
--   *** Exception: Prelude.cycle: empty list
--   
--   &gt;&gt;&gt; cycle [42]
--   [42,42,42,42,42,42,42,42,42,42...
--   
--   &gt;&gt;&gt; cycle [2, 5, 7]
--   [2,5,7,2,5,7,2,5,7,2,5,7...
--   </pre>
cycle :: HasCallStack => [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>
--   &gt;&gt;&gt; takeWhile (&lt; 3) [1,2,3,4,1,2,3,4]
--   [1,2]
--   
--   &gt;&gt;&gt; takeWhile (&lt; 9) [1,2,3]
--   [1,2,3]
--   
--   &gt;&gt;&gt; takeWhile (&lt; 0) [1,2,3]
--   []
--   </pre>
takeWhile :: (a -> Bool) -> [a] -> [a]

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

-- | <a>take</a> <tt>n</tt>, applied to a list <tt>xs</tt>, returns the
--   prefix of <tt>xs</tt> of length <tt>n</tt>, or <tt>xs</tt> itself if
--   <tt>n &gt;= <a>length</a> xs</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; take 5 "Hello World!"
--   "Hello"
--   
--   &gt;&gt;&gt; take 3 [1,2,3,4,5]
--   [1,2,3]
--   
--   &gt;&gt;&gt; take 3 [1,2]
--   [1,2]
--   
--   &gt;&gt;&gt; take 3 []
--   []
--   
--   &gt;&gt;&gt; take (-1) [1,2]
--   []
--   
--   &gt;&gt;&gt; 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]

-- | <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>
--   &gt;&gt;&gt; drop 6 "Hello World!"
--   "World!"
--   
--   &gt;&gt;&gt; drop 3 [1,2,3,4,5]
--   [4,5]
--   
--   &gt;&gt;&gt; drop 3 [1,2]
--   []
--   
--   &gt;&gt;&gt; drop 3 []
--   []
--   
--   &gt;&gt;&gt; drop (-1) [1,2]
--   [1,2]
--   
--   &gt;&gt;&gt; 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]

-- | <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>
--   &gt;&gt;&gt; splitAt 6 "Hello World!"
--   ("Hello ","World!")
--   
--   &gt;&gt;&gt; splitAt 3 [1,2,3,4,5]
--   ([1,2,3],[4,5])
--   
--   &gt;&gt;&gt; splitAt 1 [1,2,3]
--   ([1],[2,3])
--   
--   &gt;&gt;&gt; splitAt 3 [1,2,3]
--   ([1,2,3],[])
--   
--   &gt;&gt;&gt; splitAt 4 [1,2,3]
--   ([1,2,3],[])
--   
--   &gt;&gt;&gt; splitAt 0 [1,2,3]
--   ([],[1,2,3])
--   
--   &gt;&gt;&gt; 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])

-- | <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>
--   &gt;&gt;&gt; span (&lt; 3) [1,2,3,4,1,2,3,4]
--   ([1,2],[3,4,1,2,3,4])
--   
--   &gt;&gt;&gt; span (&lt; 9) [1,2,3]
--   ([1,2,3],[])
--   
--   &gt;&gt;&gt; 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])

-- | <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>
--   &gt;&gt;&gt; break (&gt; 3) [1,2,3,4,1,2,3,4]
--   ([1,2,3],[4,1,2,3,4])
--   
--   &gt;&gt;&gt; break (&lt; 9) [1,2,3]
--   ([],[1,2,3])
--   
--   &gt;&gt;&gt; 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])

-- | <a>reverse</a> <tt>xs</tt> returns the elements of <tt>xs</tt> in
--   reverse order. <tt>xs</tt> must be finite.
--   
--   <pre>
--   &gt;&gt;&gt; reverse []
--   []
--   
--   &gt;&gt;&gt; reverse [42]
--   [42]
--   
--   &gt;&gt;&gt; reverse [2,5,7]
--   [7,5,2]
--   
--   &gt;&gt;&gt; reverse [1..]
--   * Hangs forever *
--   </pre>
reverse :: [a] -> [a]

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

-- | List index (subscript) operator, starting from 0. It is an instance of
--   the more general <a>genericIndex</a>, which takes an index of any
--   integral type.
--   
--   <pre>
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! 0
--   'a'
--   
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! 2
--   'c'
--   
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! 3
--   *** Exception: Prelude.!!: index too large
--   
--   &gt;&gt;&gt; ['a', 'b', 'c'] !! (-1)
--   *** Exception: Prelude.!!: negative index
--   </pre>
--   
--   WARNING: This function is partial. You can use <a>atMay</a> instead.
(!!) :: HasCallStack => [a] -> Int -> a
infixl 9 !!

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

-- | &lt;math&gt;. <a>zipWith</a> generalises <a>zip</a> by zipping with
--   the function given as the first argument, instead of a tupling
--   function.
--   
--   <pre>
--   zipWith (,) xs ys == zip xs ys
--   zipWith f [x1,x2,x3..] [y1,y2,y3..] == [f x1 y1, f x2 y2, f x3 y3..]
--   </pre>
--   
--   For example, <tt><a>zipWith</a> (+)</tt> is applied to two lists to
--   produce the list of corresponding sums:
--   
--   <pre>
--   &gt;&gt;&gt; zipWith (+) [1, 2, 3] [4, 5, 6]
--   [5,7,9]
--   </pre>
--   
--   <a>zipWith</a> is right-lazy:
--   
--   <pre>
--   &gt;&gt;&gt; let f = undefined
--   
--   &gt;&gt;&gt; zipWith f [] undefined
--   []
--   </pre>
--   
--   <a>zipWith</a> is capable of list fusion, but it is restricted to its
--   first list argument and its resulting list.
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 the function
--   applied to corresponding elements, analogous to <a>zipWith</a>. It is
--   capable of list fusion, but it is restricted to its first list
--   argument and its resulting list.
--   
--   <pre>
--   zipWith3 (,,) xs ys zs == zip3 xs ys zs
--   zipWith3 f [x1,x2,x3..] [y1,y2,y3..] [z1,z2,z3..] == [f x1 y1 z1, f x2 y2 z2, f x3 y3 z3..]
--   </pre>
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]

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

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

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

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

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

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

-- | The <a>toEnum</a> method restricted to the type <a>Char</a>.
chr :: Int -> Char
even :: Integral a => a -> Bool
odd :: Integral a => a -> Bool

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

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

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

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

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

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

-- | <tt><a>void</a> value</tt> discards or ignores the result of
--   evaluation, such as the return value of an <a>IO</a> action.
--   
--   <h4><b>Examples</b></h4>
--   
--   Replace the contents of a <tt><a>Maybe</a> <a>Int</a></tt> with unit:
--   
--   <pre>
--   &gt;&gt;&gt; void Nothing
--   Nothing
--   
--   &gt;&gt;&gt; void (Just 3)
--   Just ()
--   </pre>
--   
--   Replace the contents of an <tt><a>Either</a> <a>Int</a>
--   <a>Int</a></tt> with unit, resulting in an <tt><a>Either</a>
--   <a>Int</a> <tt>()</tt></tt>:
--   
--   <pre>
--   &gt;&gt;&gt; void (Left 8675309)
--   Left 8675309
--   
--   &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 ()

-- | <tt><a>on</a> b u x y</tt> runs the binary function <tt>b</tt>
--   <i>on</i> the results of applying unary function <tt>u</tt> to two
--   arguments <tt>x</tt> and <tt>y</tt>. From the opposite perspective, it
--   transforms two inputs and combines the outputs.
--   
--   <pre>
--   ((+) `<a>on</a>` f) x y = f x + f y
--   </pre>
--   
--   Typical usage: <tt><a>sortBy</a> (<a>compare</a> `on`
--   <a>fst</a>)</tt>.
--   
--   Algebraic properties:
--   
--   <ul>
--   <li><pre>(*) `on` <a>id</a> = (*) -- (if (*) ∉ {⊥, <a>const</a>
--   ⊥})</pre></li>
--   <li><pre>((*) `on` f) `on` g = (*) `on` (f . g)</pre></li>
--   <li><pre><a>flip</a> on f . <a>flip</a> on g = <a>flip</a> on (g .
--   f)</pre></li>
--   </ul>
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
infixl 0 `on`

-- | Returns <a>True</a> for any Unicode space character, and the control
--   characters <tt>\t</tt>, <tt>\n</tt>, <tt>\r</tt>, <tt>\f</tt>,
--   <tt>\v</tt>.
isSpace :: Char -> Bool

-- | Selects upper-case or title-case alphabetic Unicode characters
--   (letters). Title case is used by a small number of letter ligatures
--   like the single-character form of <i>Lj</i>.
--   
--   <b>Note:</b> this predicate does <i>not</i> work for letter-like
--   characters such as: <tt>'Ⓐ'</tt> (<tt>U+24B6</tt> circled Latin
--   capital letter A) and <tt>'Ⅳ'</tt> (<tt>U+2163</tt> Roman numeral
--   four). This is due to selecting only characters with the
--   <a>GeneralCategory</a> <a>UppercaseLetter</a> or
--   <a>TitlecaseLetter</a>.
--   
--   See <a>isUpperCase</a> for a more intuitive predicate. Note that
--   unlike <a>isUpperCase</a>, <a>isUpper</a> does select
--   <i>title-case</i> characters such as <tt>'ǅ'</tt> (<tt>U+01C5</tt>
--   Latin capital letter d with small letter z with caron) or <tt>'ᾯ'</tt>
--   (<tt>U+1FAF</tt> Greek capital letter omega with dasia and perispomeni
--   and prosgegrammeni).
isUpper :: Char -> Bool

-- | Selects alphabetic Unicode characters (lower-case, upper-case and
--   title-case letters, plus letters of caseless scripts and modifiers
--   letters). This function is equivalent to <a>isLetter</a>.
isAlpha :: Char -> Bool

-- | Selects alphabetic or numeric Unicode characters.
--   
--   Note that numeric digits outside the ASCII range, as well as numeric
--   characters which aren't digits, are selected by this function but not
--   by <a>isDigit</a>. Such characters may be part of identifiers but are
--   not used by the printer and reader to represent numbers.
isAlphaNum :: Char -> Bool

-- | Selects ASCII digits, i.e. <tt>'0'</tt>..<tt>'9'</tt>.
isDigit :: Char -> Bool

-- | Convert a letter to the corresponding upper-case letter, if any. Any
--   other character is returned unchanged.
toUpper :: Char -> Char

-- | Convert a letter to the corresponding lower-case letter, if any. Any
--   other character is returned unchanged.
toLower :: Char -> Char

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

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

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

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

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

-- | Parse a string using the <a>Read</a> instance. Succeeds if there is
--   exactly one valid result.
--   
--   <pre>
--   &gt;&gt;&gt; readMaybe "123" :: Maybe Int
--   Just 123
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; readMaybe "hello" :: Maybe Int
--   Nothing
--   </pre>
readMaybe :: Read a => String -> Maybe a

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

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

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

-- | The concatenation of all the elements of a container of lists.
--   
--   <h4><b>Examples</b></h4>
--   
--   Basic usage:
--   
--   <pre>
--   &gt;&gt;&gt; concat (Just [1, 2, 3])
--   [1,2,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; concat (Left 42)
--   []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; concat [[1, 2, 3], [4, 5], [6], []]
--   [1,2,3,4,5,6]
--   </pre>
concat :: Foldable t => t [a] -> [a]

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

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

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

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

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

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

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

-- | Takes a value of type <tt>a</tt> and returns a concrete representation
--   of that type.
typeRep :: forall {k} proxy (a :: k). Typeable a => proxy a -> TypeRep

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

-- | &lt;math&gt;. The <a>isPrefixOf</a> function takes two lists and
--   returns <a>True</a> iff the first list is a prefix of the second.
--   
--   <pre>
--   &gt;&gt;&gt; "Hello" `isPrefixOf` "Hello World!"
--   True
--   
--   &gt;&gt;&gt; "Hello" `isPrefixOf` "Wello Horld!"
--   False
--   </pre>
--   
--   For the result to be <a>True</a>, the first list must be finite;
--   <a>False</a>, however, results from any mismatch:
--   
--   <pre>
--   &gt;&gt;&gt; [0..] `isPrefixOf` [1..]
--   False
--   
--   &gt;&gt;&gt; [0..] `isPrefixOf` [0..99]
--   False
--   
--   &gt;&gt;&gt; [0..99] `isPrefixOf` [0..]
--   True
--   
--   &gt;&gt;&gt; [0..] `isPrefixOf` [0..]
--   * Hangs forever *
--   </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.
--   
--   <pre>
--   &gt;&gt;&gt; "ld!" `isSuffixOf` "Hello World!"
--   True
--   
--   &gt;&gt;&gt; "World" `isSuffixOf` "Hello World!"
--   False
--   </pre>
--   
--   The second list must be finite; however the first list may be
--   infinite:
--   
--   <pre>
--   &gt;&gt;&gt; [0..] `isSuffixOf` [0..99]
--   False
--   
--   &gt;&gt;&gt; [0..99] `isSuffixOf` [0..]
--   * Hangs forever *
--   </pre>
isSuffixOf :: Eq a => [a] -> [a] -> Bool

-- | &lt;math&gt;. 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>partition</a> function takes a predicate and a list, and
--   returns the pair of lists of elements which do and do not satisfy the
--   predicate, respectively; i.e.,
--   
--   <pre>
--   partition p xs == (filter p xs, filter (not . p) xs)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; partition (`elem` "aeiou") "Hello World!"
--   ("eoo","Hll Wrld!")
--   </pre>
partition :: (a -> Bool) -> [a] -> ([a], [a])

-- | The <a>sort</a> function implements a stable sorting algorithm. It is
--   a special case of <a>sortBy</a>, which allows the programmer to supply
--   their own comparison function.
--   
--   Elements are arranged from lowest to highest, keeping duplicates in
--   the order they appeared in the input.
--   
--   <pre>
--   &gt;&gt;&gt; sort [1,6,4,3,2,5]
--   [1,2,3,4,5,6]
--   </pre>
--   
--   The argument must be finite.
sort :: Ord a => [a] -> [a]

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

-- | Splits the argument into a list of <i>lines</i> stripped of their
--   terminating <tt>\n</tt> characters. The <tt>\n</tt> terminator is
--   optional in a final non-empty line of the argument string.
--   
--   For example:
--   
--   <pre>
--   &gt;&gt;&gt; lines ""           -- empty input contains no lines
--   []
--   
--   &gt;&gt;&gt; lines "\n"         -- single empty line
--   [""]
--   
--   &gt;&gt;&gt; lines "one"        -- single unterminated line
--   ["one"]
--   
--   &gt;&gt;&gt; lines "one\n"      -- single non-empty line
--   ["one"]
--   
--   &gt;&gt;&gt; lines "one\n\n"    -- second line is empty
--   ["one",""]
--   
--   &gt;&gt;&gt; lines "one\ntwo"   -- second line is unterminated
--   ["one","two"]
--   
--   &gt;&gt;&gt; lines "one\ntwo\n" -- two non-empty lines
--   ["one","two"]
--   </pre>
--   
--   When the argument string is empty, or ends in a <tt>\n</tt> character,
--   it can be recovered by passing the result of <a>lines</a> to the
--   <a>unlines</a> function. Otherwise, <a>unlines</a> appends the missing
--   terminating <tt>\n</tt>. This makes <tt>unlines . lines</tt>
--   <i>idempotent</i>:
--   
--   <pre>
--   (unlines . lines) . (unlines . lines) = (unlines . lines)
--   </pre>
lines :: String -> [String]

-- | Appends a <tt>\n</tt> character to each input string, then
--   concatenates the results. Equivalent to <tt><tt>foldMap</tt> (s -&gt;
--   s <a>++</a> "\n")</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; unlines ["Hello", "World", "!"]
--   "Hello\nWorld\n!\n"
--   </pre>
--   
--   Note that <tt><a>unlines</a> <a>.</a> <a>lines</a> <a>/=</a>
--   <a>id</a></tt> when the input is not <tt>\n</tt>-terminated:
--   
--   <pre>
--   &gt;&gt;&gt; unlines . lines $ "foo\nbar"
--   "foo\nbar\n"
--   </pre>
unlines :: [String] -> String

-- | <a>words</a> breaks a string up into a list of words, which were
--   delimited by white space (as defined by <a>isSpace</a>). This function
--   trims any white spaces at the beginning and at the end.
--   
--   <pre>
--   &gt;&gt;&gt; words "Lorem ipsum\ndolor"
--   ["Lorem","ipsum","dolor"]
--   
--   &gt;&gt;&gt; words " foo bar "
--   ["foo","bar"]
--   </pre>
words :: String -> [String]

-- | <a>unwords</a> joins words with separating spaces (U+0020 SPACE).
--   
--   <pre>
--   &gt;&gt;&gt; unwords ["Lorem", "ipsum", "dolor"]
--   "Lorem ipsum dolor"
--   </pre>
--   
--   <a>unwords</a> is neither left nor right inverse of <a>words</a>:
--   
--   <pre>
--   &gt;&gt;&gt; words (unwords [" "])
--   []
--   
--   &gt;&gt;&gt; unwords (words "foo\nbar")
--   "foo bar"
--   </pre>
unwords :: [String] -> String

-- | Construct an <a>IOException</a> value with a string describing the
--   error. The <tt>fail</tt> method of the <a>IO</a> instance of the
--   <a>Monad</a> class raises a <a>userError</a>, thus:
--   
--   <pre>
--   instance Monad IO where
--     ...
--     fail s = ioError (userError s)
--   </pre>
userError :: String -> IOError

-- | This is the simplest of the exception-catching functions. It takes a
--   single argument, runs it, and if an exception is raised the "handler"
--   is executed, with the value of the exception passed as an argument.
--   Otherwise, the result is returned as normal. For example:
--   
--   <pre>
--   catch (readFile f)
--         (\e -&gt; do let err = show (e :: IOException)
--                   hPutStr stderr ("Warning: Couldn't open " ++ f ++ ": " ++ err)
--                   return "")
--   </pre>
--   
--   Note that we have to give a type signature to <tt>e</tt>, or the
--   program will not typecheck as the type is ambiguous. While it is
--   possible to catch exceptions of any type, see the section "Catching
--   all exceptions" (in <a>Control.Exception</a>) for an explanation of
--   the problems with doing so.
--   
--   For catching exceptions in pure (non-<a>IO</a>) expressions, see the
--   function <a>evaluate</a>.
--   
--   Note that due to Haskell's unspecified evaluation order, an expression
--   may throw one of several possible exceptions: consider the expression
--   <tt>(error "urk") + (1 `div` 0)</tt>. Does the expression throw
--   <tt>ErrorCall "urk"</tt>, or <tt>DivideByZero</tt>?
--   
--   The answer is "it might throw either"; the choice is
--   non-deterministic. If you are catching any type of exception then you
--   might catch either. If you are calling <tt>catch</tt> with type <tt>IO
--   Int -&gt; (ArithException -&gt; IO Int) -&gt; IO Int</tt> then the
--   handler may get run with <tt>DivideByZero</tt> as an argument, or an
--   <tt>ErrorCall "urk"</tt> exception may be propagated further up. If
--   you call it again, you might get the opposite behaviour. This is ok,
--   because <a>catch</a> is an <a>IO</a> computation.
catch :: Exception e => IO a -> (e -> IO a) -> IO a

-- | A variant of <a>throw</a> that can only be used within the <a>IO</a>
--   monad.
--   
--   Although <a>throwIO</a> has a type that is an instance of the type of
--   <a>throw</a>, the two functions are subtly different:
--   
--   <pre>
--   throw e   `seq` ()  ===&gt; throw e
--   throwIO e `seq` ()  ===&gt; ()
--   </pre>
--   
--   The first example will cause the exception <tt>e</tt> to be raised,
--   whereas the second one won't. In fact, <a>throwIO</a> will only cause
--   an exception to be raised when it is used within the <a>IO</a> monad.
--   
--   The <a>throwIO</a> variant should be used in preference to
--   <a>throw</a> to raise an exception within the <a>IO</a> monad because
--   it guarantees ordering with respect to other operations, whereas
--   <a>throw</a> does not. We say that <a>throwIO</a> throws *precise*
--   exceptions and <a>throw</a>, <a>error</a>, etc. all throw *imprecise*
--   exceptions. For example
--   
--   <pre>
--   throw e + error "boom" ===&gt; error "boom"
--   throw e + error "boom" ===&gt; throw e
--   </pre>
--   
--   are both valid reductions and the compiler may pick any (loop, even),
--   whereas
--   
--   <pre>
--   throwIO e &gt;&gt; error "boom" ===&gt; throwIO e
--   </pre>
--   
--   will always throw <tt>e</tt> when executed.
--   
--   See also the <a>GHC wiki page on precise exceptions</a> for a more
--   technical introduction to how GHC optimises around precise vs.
--   imprecise exceptions.
throwIO :: Exception e => e -> IO a

-- | Evaluate the argument to weak head normal form.
--   
--   <a>evaluate</a> is typically used to uncover any exceptions that a
--   lazy value may contain, and possibly handle them.
--   
--   <a>evaluate</a> only evaluates to <i>weak head normal form</i>. If
--   deeper evaluation is needed, the <tt>force</tt> function from
--   <tt>Control.DeepSeq</tt> may be handy:
--   
--   <pre>
--   evaluate $ force x
--   </pre>
--   
--   There is a subtle difference between <tt><a>evaluate</a> x</tt> and
--   <tt><a>return</a> <a>$!</a> x</tt>, analogous to the difference
--   between <a>throwIO</a> and <a>throw</a>. If the lazy value <tt>x</tt>
--   throws an exception, <tt><a>return</a> <a>$!</a> x</tt> will fail to
--   return an <a>IO</a> action and will throw an exception instead.
--   <tt><a>evaluate</a> x</tt>, on the other hand, always produces an
--   <a>IO</a> action; that action will throw an exception upon
--   <i>execution</i> iff <tt>x</tt> throws an exception upon
--   <i>evaluation</i>.
--   
--   The practical implication of this difference is that due to the
--   <i>imprecise exceptions</i> semantics,
--   
--   <pre>
--   (return $! error "foo") &gt;&gt; error "bar"
--   </pre>
--   
--   may throw either <tt>"foo"</tt> or <tt>"bar"</tt>, depending on the
--   optimizations performed by the compiler. On the other hand,
--   
--   <pre>
--   evaluate (error "foo") &gt;&gt; error "bar"
--   </pre>
--   
--   is guaranteed to throw <tt>"foo"</tt>.
--   
--   The rule of thumb is to use <a>evaluate</a> to force or handle
--   exceptions in lazy values. If, on the other hand, you are forcing a
--   lazy value for efficiency reasons only and do not care about
--   exceptions, you may use <tt><a>return</a> <a>$!</a> x</tt>.
evaluate :: a -> IO a

-- | Raise an <a>IOException</a> in the <a>IO</a> monad.
ioError :: IOError -> IO a

-- | Write a character to the standard output device (same as
--   <a>hPutChar</a> <a>stdout</a>).
putChar :: Char -> IO ()

-- | Write a string to the standard output device (same as <a>hPutStr</a>
--   <a>stdout</a>).
putStr :: String -> IO ()

-- | The same as <a>putStr</a>, but adds a newline character.
putStrLn :: String -> IO ()

-- | Read a character from the standard input device (same as
--   <a>hGetChar</a> <a>stdin</a>).
getChar :: IO Char

-- | Read a line from the standard input device (same as <a>hGetLine</a>
--   <a>stdin</a>).
getLine :: IO String

-- | The <a>getContents</a> operation returns all user input as a single
--   string, which is read lazily as it is needed (same as
--   <a>hGetContents</a> <a>stdin</a>).
getContents :: IO String

-- | The <a>interact</a> function takes a function of type
--   <tt>String-&gt;String</tt> as its argument. The entire input from the
--   standard input device is passed to this function as its argument, and
--   the resulting string is output on the standard output device.
interact :: (String -> String) -> IO ()

-- | The <a>readFile</a> function reads a file and returns the contents of
--   the file as a string. The file is read lazily, on demand, as with
--   <a>getContents</a>.
readFile :: FilePath -> IO String

-- | The computation <a>writeFile</a> <tt>file str</tt> function writes the
--   string <tt>str</tt>, to the file <tt>file</tt>.
writeFile :: FilePath -> String -> IO ()

-- | The computation <a>appendFile</a> <tt>file str</tt> function appends
--   the string <tt>str</tt>, to the file <tt>file</tt>.
--   
--   Note that <a>writeFile</a> and <a>appendFile</a> write a literal
--   string to a file. To write a value of any printable type, as with
--   <a>print</a>, use the <a>show</a> function to convert the value to a
--   string first.
--   
--   <pre>
--   main = appendFile "squares" (show [(x,x*x) | x &lt;- [0,0.1..2]])
--   </pre>
appendFile :: FilePath -> String -> IO ()

-- | The <a>readLn</a> function combines <a>getLine</a> and <a>readIO</a>.
readLn :: Read a => IO a

-- | The <a>readIO</a> function is similar to <a>read</a> except that it
--   signals parse failure to the <a>IO</a> monad instead of terminating
--   the program.
readIO :: Read a => String -> IO 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)

-- | This generalizes the list-based <a>filter</a> function.
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]

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

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

-- | Computation <a>exitWith</a> <tt>code</tt> throws <a>ExitCode</a>
--   <tt>code</tt>. Normally this terminates the program, returning
--   <tt>code</tt> to the program's caller.
--   
--   On program termination, the standard <a>Handle</a>s <a>stdout</a> and
--   <a>stderr</a> are flushed automatically; any other buffered
--   <a>Handle</a>s need to be flushed manually, otherwise the buffered
--   data will be discarded.
--   
--   A program that fails in any other way is treated as if it had called
--   <a>exitFailure</a>. A program that terminates successfully without
--   calling <a>exitWith</a> explicitly is treated as if it had called
--   <a>exitWith</a> <a>ExitSuccess</a>.
--   
--   As an <a>ExitCode</a> is an <a>Exception</a>, it can be caught using
--   the functions of <a>Control.Exception</a>. This means that cleanup
--   computations added with <a>bracket</a> (from <a>Control.Exception</a>)
--   are also executed properly on <a>exitWith</a>.
--   
--   Note: in GHC, <a>exitWith</a> should be called from the main program
--   thread in order to exit the process. When called from another thread,
--   <a>exitWith</a> will throw an <a>ExitCode</a> as normal, but the
--   exception will not cause the process itself to exit.
exitWith :: ExitCode -> IO a

-- | The computation <a>exitFailure</a> is equivalent to <a>exitWith</a>
--   <tt>(</tt><a>ExitFailure</a> <i>exitfail</i><tt>)</tt>, where
--   <i>exitfail</i> is implementation-dependent.
exitFailure :: IO a

-- | The computation <a>exitSuccess</a> is equivalent to <a>exitWith</a>
--   <a>ExitSuccess</a>, It terminates the program successfully.
exitSuccess :: IO a

-- | <a>nonEmpty</a> efficiently turns a normal list into a <a>NonEmpty</a>
--   stream, producing <a>Nothing</a> if the input is empty.
nonEmpty :: [a] -> Maybe (NonEmpty a)

-- | Extract the first element of the stream.
head :: NonEmpty a -> a

-- | Extract the possibly-empty tail of the stream.
tail :: NonEmpty a -> [a]

-- | Extract the last element of the stream.
last :: NonEmpty a -> a

-- | a variant of <a>deepseq</a> that is useful in some circumstances:
--   
--   <pre>
--   force x = x `deepseq` x
--   </pre>
--   
--   <tt>force x</tt> fully evaluates <tt>x</tt>, and then returns it. Note
--   that <tt>force x</tt> only performs evaluation when the value of
--   <tt>force x</tt> itself is demanded, so essentially it turns shallow
--   evaluation into deep evaluation.
--   
--   <a>force</a> can be conveniently used in combination with
--   <tt>ViewPatterns</tt>:
--   
--   <pre>
--   {-# LANGUAGE BangPatterns, ViewPatterns #-}
--   import Control.DeepSeq
--   
--   someFun :: ComplexData -&gt; SomeResult
--   someFun (force -&gt; !arg) = {- 'arg' will be fully evaluated -}
--   </pre>
--   
--   Another useful application is to combine <a>force</a> with
--   <a>evaluate</a> in order to force deep evaluation relative to other
--   <a>IO</a> operations:
--   
--   <pre>
--   import Control.Exception (evaluate)
--   import Control.DeepSeq
--   
--   main = do
--     result &lt;- evaluate $ force $ pureComputation
--     {- 'result' will be fully evaluated at this point -}
--     return ()
--   </pre>
--   
--   Finally, here's an exception safe variant of the <tt>readFile'</tt>
--   example:
--   
--   <pre>
--   readFile' :: FilePath -&gt; IO String
--   readFile' fn = bracket (openFile fn ReadMode) hClose $ \h -&gt;
--                          evaluate . force =&lt;&lt; hGetContents h
--   </pre>
force :: NFData a => a -> a

-- | Beside, separated by space, unless one of the arguments is
--   <a>empty</a>. <a>&lt;+&gt;</a> is associative, with identity
--   <a>empty</a>.
(<+>) :: Doc -> Doc -> Doc
infixl 6 <+>

-- | Try <tt>IOException</tt>.
tryIO :: IO a -> IO (Either IOException a)

-- | Catch <tt>IOException</tt>.
catchIO :: IO a -> (IOException -> IO a) -> IO a

-- | Catch <a>ExitCode</a>
catchExit :: IO a -> (ExitCode -> IO a) -> IO a

-- | Generically generate a <a>Semigroup</a> (<a>&lt;&gt;</a>) operation
--   for any type implementing <a>Generic</a>. This operation will append
--   two values by point-wise appending their component fields. It is only
--   defined for product types.
--   
--   <pre>
--   <a>gmappend</a> a (<a>gmappend</a> b c) = <a>gmappend</a> (<a>gmappend</a> a b) c
--   </pre>
gmappend :: (Generic a, GSemigroup (Rep a)) => a -> a -> a

-- | Generically generate a <a>Monoid</a> <a>mempty</a> for any
--   product-like type implementing <a>Generic</a>.
--   
--   It is only defined for product types.
--   
--   <pre>
--   <a>gmappend</a> <a>gmempty</a> a = a = <a>gmappend</a> a <a>gmempty</a>
--   </pre>
gmempty :: (Generic a, GMonoid (Rep a)) => a

-- | New name for <a>&lt;&gt;</a>
(<<>>) :: Doc -> Doc -> Doc

-- | <a>GHC.Generics</a>-based <a>rnf</a> implementation
--   
--   This is needed in order to support <tt>deepseq &lt; 1.4</tt> which
--   didn't have a <a>Generic</a>-based default <a>rnf</a> implementation
--   yet.
--   
--   In order to define instances, use e.g.
--   
--   <pre>
--   instance NFData MyType where rnf = genericRnf
--   </pre>
--   
--   The implementation has been taken from <tt>deepseq-1.4.2</tt>'s
--   default <a>rnf</a> implementation.
genericRnf :: (Generic a, GNFData (Rep a)) => a -> ()
foldr1 :: (a -> a -> a) -> NonEmpty a -> a
foldl1 :: (a -> a -> a) -> NonEmpty a -> a
trace :: String -> a -> a
traceShowId :: Show a => a -> a
traceShow :: Show a => a -> b -> b

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


-- | Wrapper around Data.Graph with support for edge labels
module Distribution.Solver.Modular.LabeledGraph
type Graph e = Array Vertex [(e, Vertex)]

-- | Abstract representation of vertices.
type Vertex = Int

-- | Construct an edge-labeled graph
--   
--   This is a simple adaptation of the definition in Data.Graph
graphFromEdges :: forall key node edge. Ord key => [(node, key, [(edge, key)])] -> (Graph edge, Vertex -> (node, key, [(edge, key)]), key -> Maybe Vertex)
graphFromEdges' :: Ord key => [(node, key, [(edge, key)])] -> (Graph edge, Vertex -> (node, key, [(edge, key)]))
buildG :: Bounds -> [Edge e] -> Graph e
transposeG :: Graph e -> Graph e
vertices :: Graph e -> [Vertex]
edges :: Graph e -> [Edge e]
forgetLabels :: Graph e -> Graph
topSort :: Graph e -> [Vertex]


-- | Utility functions providing extra context to cabal error messages
module Distribution.Solver.Modular.MessageUtils
allKnownExtensions :: [String]
cutoffRange :: Int
mostSimilarElement :: String -> [String] -> String
showUnsupportedExtension :: Extension -> String
showUnsupportedLanguage :: Language -> String
withinRange :: Int -> String -> String -> Bool

module Distribution.Solver.Modular.PSQ
newtype PSQ k v
PSQ :: [(k, v)] -> PSQ k v
casePSQ :: PSQ k a -> r -> (k -> a -> PSQ k a -> r) -> r
cons :: k -> a -> PSQ k a -> PSQ k a
length :: PSQ k a -> Int
lookup :: Eq k => k -> PSQ k v -> Maybe v
filter :: (a -> Bool) -> PSQ k a -> PSQ k a

-- | Will partition the list according to the predicate. If there is any
--   element that satisfies the predicate, then only the elements
--   satisfying the predicate are returned. Otherwise, the rest is
--   returned.
filterIfAny :: (a -> Bool) -> PSQ k a -> PSQ k a

-- | Variant of <a>filterIfAny</a> that takes a predicate on the keys
--   rather than on the values.
filterIfAnyByKeys :: (k -> Bool) -> PSQ k a -> PSQ k a
filterKeys :: (k -> Bool) -> PSQ k a -> PSQ k a
firstOnly :: PSQ k a -> PSQ k a
fromList :: [(k, a)] -> PSQ k a
isZeroOrOne :: PSQ k a -> Bool
keys :: PSQ k v -> [k]
map :: (v1 -> v2) -> PSQ k v1 -> PSQ k v2
mapKeys :: (k1 -> k2) -> PSQ k1 v -> PSQ k2 v
mapWithKey :: (k -> a -> b) -> PSQ k a -> PSQ k b
maximumBy :: (k -> Int) -> PSQ k a -> (k, a)
minimumBy :: (a -> Int) -> PSQ k a -> PSQ k a
null :: PSQ k a -> Bool

-- | Sort the list so that values satisfying the predicate are first.
prefer :: (a -> Bool) -> PSQ k a -> PSQ k a

-- | Sort the list so that keys satisfying the predicate are first.
preferByKeys :: (k -> Bool) -> PSQ k a -> PSQ k a
snoc :: PSQ k a -> k -> a -> PSQ k a
sortBy :: (a -> a -> Ordering) -> PSQ k a -> PSQ k a
sortByKeys :: (k -> k -> Ordering) -> PSQ k a -> PSQ k a
toList :: PSQ k a -> [(k, a)]
union :: PSQ k a -> PSQ k a -> PSQ k a
instance Data.Traversable.Traversable (Distribution.Solver.Modular.PSQ.PSQ k)
instance Data.Foldable.Foldable (Distribution.Solver.Modular.PSQ.PSQ k)
instance GHC.Base.Functor (Distribution.Solver.Modular.PSQ.PSQ k)
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Distribution.Solver.Modular.PSQ.PSQ k v)
instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Distribution.Solver.Modular.PSQ.PSQ k v)

module Distribution.Solver.Modular.Version

-- | Preliminary type for versions.
type Ver = Version

-- | Version range. Consists of a lower and upper bound.
type VR = VersionRange

-- | Unconstrained version range.
anyVR :: VR

-- | Checking a version against a version range.
checkVR :: VR -> Ver -> Bool

-- | Version range fixing a single version.
eqVR :: Ver -> VR

-- | String representation of a version.
showVer :: Ver -> String

-- | String representation of a version range.
showVR :: VR -> String

-- | Simplify a version range.
simplifyVR :: VR -> VR

-- | Intersect two version ranges.
(.&&.) :: VR -> VR -> VR

-- | Union of two version ranges.
(.||.) :: VR -> VR -> VR

module Distribution.Solver.Modular.WeightedPSQ

-- | An association list that is sorted by weight.
--   
--   Each element has a key (<tt>k</tt>), value (<tt>v</tt>), and weight
--   (<tt>w</tt>). All operations that add elements or modify weights
--   stably sort the elements by weight.
data WeightedPSQ w k v

-- | <i>O(N log N)</i>.
fromList :: Ord w => [(w, k, v)] -> WeightedPSQ w k v

-- | <i>O(1)</i>. Return the elements in order.
toList :: WeightedPSQ w k v -> [(w, k, v)]

-- | <i>O(N)</i>. Return the keys in order.
keys :: WeightedPSQ w k v -> [k]

-- | <i>O(N)</i>. Return the weights in order.
weights :: WeightedPSQ w k v -> [w]

-- | <i>O(1)</i>. Return <tt>True</tt> if the <tt>WeightedPSQ</tt> contains
--   zero or one elements.
isZeroOrOne :: WeightedPSQ w k v -> Bool

-- | <i>O(N)</i>.
filter :: (v -> Bool) -> WeightedPSQ k w v -> WeightedPSQ k w v

-- | <i>O(N)</i>. Return the value associated with the first occurrence of
--   the give key, if it exists.
lookup :: Eq k => k -> WeightedPSQ w k v -> Maybe v

-- | <i>O(N)</i>. Update the values.
mapWithKey :: (k -> v1 -> v2) -> WeightedPSQ w k v1 -> WeightedPSQ w k v2

-- | <i>O(N log N)</i>. Update the weights.
mapWeightsWithKey :: Ord w2 => (k -> w1 -> w2) -> WeightedPSQ w1 k v -> WeightedPSQ w2 k v

-- | <i>O(N)</i>. Traverse and update values in some applicative functor.
traverseWithKey :: Applicative f => (k -> v -> f v') -> WeightedPSQ w k v -> f (WeightedPSQ w k v')

-- | <i>O((N + M) log (N + M))</i>. Combine two <tt>WeightedPSQ</tt>s,
--   preserving all elements. Elements from the first <tt>WeightedPSQ</tt>
--   come before elements in the second when they have the same weight.
union :: Ord w => WeightedPSQ w k v -> WeightedPSQ w k v -> WeightedPSQ w k v

-- | <i>O(N)</i>. Return the prefix of values ending with the first element
--   that satisfies p, or all elements if none satisfy p.
takeUntil :: forall w k v. (v -> Bool) -> WeightedPSQ w k v -> WeightedPSQ w k v
instance Data.Traversable.Traversable (Distribution.Solver.Modular.WeightedPSQ.WeightedPSQ w k)
instance Data.Foldable.Foldable (Distribution.Solver.Modular.WeightedPSQ.WeightedPSQ w k)
instance GHC.Base.Functor (Distribution.Solver.Modular.WeightedPSQ.WeightedPSQ w k)
instance (GHC.Show.Show w, GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Distribution.Solver.Modular.WeightedPSQ.WeightedPSQ w k v)
instance (GHC.Classes.Eq w, GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Distribution.Solver.Modular.WeightedPSQ.WeightedPSQ w k v)


-- | Fine-grained package dependencies
--   
--   Like many others, this module is meant to be "double-imported":
--   
--   <pre>
--   import Distribution.Solver.Types.ComponentDeps (
--       Component
--     , ComponentDep
--     , ComponentDeps
--     )
--   import qualified Distribution.Solver.Types.ComponentDeps as CD
--   </pre>
module Distribution.Solver.Types.ComponentDeps

-- | Component of a package.
data Component
ComponentLib :: Component
ComponentSubLib :: UnqualComponentName -> Component
ComponentFLib :: UnqualComponentName -> Component
ComponentExe :: UnqualComponentName -> Component
ComponentTest :: UnqualComponentName -> Component
ComponentBench :: UnqualComponentName -> Component
ComponentSetup :: Component
componentNameToComponent :: ComponentName -> Component

-- | Dependency for a single component.
type ComponentDep a = (Component, a)

-- | Fine-grained dependencies for a package.
--   
--   Typically used as <tt>ComponentDeps [Dependency]</tt>, to represent
--   the list of dependencies for each named component within a package.
data ComponentDeps a
empty :: ComponentDeps a
fromList :: Monoid a => [ComponentDep a] -> ComponentDeps a
singleton :: Component -> a -> ComponentDeps a
insert :: Monoid a => Component -> a -> ComponentDeps a -> ComponentDeps a

-- | Zip two <a>ComponentDeps</a> together by <a>Component</a>, using
--   <a>mempty</a> as the neutral element when a <a>Component</a> is
--   present only in one.
zip :: (Monoid a, Monoid b) => ComponentDeps a -> ComponentDeps b -> ComponentDeps (a, b)

-- | Keep only selected components (and their associated deps info).
filterDeps :: (Component -> a -> Bool) -> ComponentDeps a -> ComponentDeps a

-- | ComponentDeps containing library dependencies only
fromLibraryDeps :: a -> ComponentDeps a

-- | ComponentDeps containing setup dependencies only.
fromSetupDeps :: a -> ComponentDeps a

-- | ComponentDeps for installed packages.
--   
--   We assume that installed packages only record their library
--   dependencies.
fromInstalled :: a -> ComponentDeps a
toList :: ComponentDeps a -> [ComponentDep a]

-- | All dependencies of a package.
--   
--   This is just a synonym for <a>fold</a>, but perhaps a use of
--   <a>flatDeps</a> is more obvious than a use of <a>fold</a>, and
--   moreover this avoids introducing lots of <tt>#ifdef</tt>s for 7.10
--   just for the use of <a>fold</a>.
flatDeps :: Monoid a => ComponentDeps a -> a

-- | All dependencies except the setup dependencies.
--   
--   Prior to the introduction of setup dependencies in version 1.24 this
--   would have been _all_ dependencies.
nonSetupDeps :: Monoid a => ComponentDeps a -> a

-- | Library dependencies proper only. (Includes dependencies of internal
--   libraries.)
libraryDeps :: Monoid a => ComponentDeps a -> a

-- | Setup dependencies.
setupDeps :: Monoid a => ComponentDeps a -> a

-- | Select dependencies satisfying a given predicate.
select :: Monoid a => (Component -> Bool) -> ComponentDeps a -> a

-- | List components
components :: ComponentDeps a -> Set Component
instance GHC.Generics.Generic Distribution.Solver.Types.ComponentDeps.Component
instance GHC.Classes.Ord Distribution.Solver.Types.ComponentDeps.Component
instance GHC.Classes.Eq Distribution.Solver.Types.ComponentDeps.Component
instance GHC.Show.Show Distribution.Solver.Types.ComponentDeps.Component
instance GHC.Generics.Generic (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance GHC.Base.Functor Distribution.Solver.Types.ComponentDeps.ComponentDeps
instance GHC.Show.Show a => GHC.Show.Show (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance GHC.Base.Semigroup a => GHC.Base.Monoid (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance Data.Foldable.Foldable Distribution.Solver.Types.ComponentDeps.ComponentDeps
instance Data.Traversable.Traversable Distribution.Solver.Types.ComponentDeps.ComponentDeps
instance Data.Binary.Class.Binary a => Data.Binary.Class.Binary (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance Distribution.Utils.Structured.Structured a => Distribution.Utils.Structured.Structured (Distribution.Solver.Types.ComponentDeps.ComponentDeps a)
instance Data.Binary.Class.Binary Distribution.Solver.Types.ComponentDeps.Component
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.ComponentDeps.Component
instance Distribution.Pretty.Pretty Distribution.Solver.Types.ComponentDeps.Component

module Distribution.Solver.Types.ConstraintSource

-- | Source of a <tt>PackageConstraint</tt>.
data ConstraintSource

-- | Main config file, which is ~<i>.cabal</i>config by default.
ConstraintSourceMainConfig :: FilePath -> ConstraintSource

-- | Local cabal.project file
ConstraintSourceProjectConfig :: FilePath -> ConstraintSource

-- | User config file, which is ./cabal.config by default.
ConstraintSourceUserConfig :: FilePath -> ConstraintSource

-- | Flag specified on the command line.
ConstraintSourceCommandlineFlag :: ConstraintSource

-- | Target specified by the user, e.g., <tt>cabal install
--   package-0.1.0.0</tt> implies <tt>package==0.1.0.0</tt>.
ConstraintSourceUserTarget :: ConstraintSource

-- | Internal requirement to use installed versions of packages like
--   ghc-prim.
ConstraintSourceNonUpgradeablePackage :: ConstraintSource

-- | Internal constraint used by <tt>cabal freeze</tt>.
ConstraintSourceFreeze :: ConstraintSource

-- | Constraint specified by a config file, a command line flag, or a user
--   target, when a more specific source is not known.
ConstraintSourceConfigFlagOrTarget :: ConstraintSource

-- | The source of the constraint is not specified.
ConstraintSourceUnknown :: ConstraintSource

-- | An internal constraint due to compatibility issues with the Setup.hs
--   command line interface requires a minimum lower bound on Cabal
ConstraintSetupCabalMinVersion :: ConstraintSource

-- | An internal constraint due to compatibility issues with the Setup.hs
--   command line interface requires a maximum upper bound on Cabal
ConstraintSetupCabalMaxVersion :: ConstraintSource

-- | Description of a <a>ConstraintSource</a>.
showConstraintSource :: ConstraintSource -> String
instance GHC.Generics.Generic Distribution.Solver.Types.ConstraintSource.ConstraintSource
instance GHC.Show.Show Distribution.Solver.Types.ConstraintSource.ConstraintSource
instance GHC.Classes.Eq Distribution.Solver.Types.ConstraintSource.ConstraintSource
instance Data.Binary.Class.Binary Distribution.Solver.Types.ConstraintSource.ConstraintSource
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.ConstraintSource.ConstraintSource

module Distribution.Solver.Types.Flag
data FlagType
Manual :: FlagType
Automatic :: FlagType
instance GHC.Show.Show Distribution.Solver.Types.Flag.FlagType
instance GHC.Classes.Eq Distribution.Solver.Types.Flag.FlagType

module Distribution.Solver.Types.InstalledPreference

-- | Whether we prefer an installed version of a package or simply the
--   latest version.
data InstalledPreference
PreferInstalled :: InstalledPreference
PreferLatest :: InstalledPreference
PreferOldest :: InstalledPreference
instance GHC.Show.Show Distribution.Solver.Types.InstalledPreference.InstalledPreference

module Distribution.Solver.Types.OptionalStanza
data OptionalStanza
TestStanzas :: OptionalStanza
BenchStanzas :: OptionalStanza

-- | String representation of an OptionalStanza.
showStanza :: OptionalStanza -> String
showStanzas :: OptionalStanzaSet -> String

-- | Convert a list of <a>OptionalStanza</a> into the corresponding Cabal's
--   <a>ComponentRequestedSpec</a> which records what components are
--   enabled.
enableStanzas :: OptionalStanzaSet -> ComponentRequestedSpec
data OptionalStanzaSet
optStanzaSetFromList :: [OptionalStanza] -> OptionalStanzaSet
optStanzaSetToList :: OptionalStanzaSet -> [OptionalStanza]
optStanzaSetMember :: OptionalStanza -> OptionalStanzaSet -> Bool
optStanzaSetInsert :: OptionalStanza -> OptionalStanzaSet -> OptionalStanzaSet
optStanzaSetSingleton :: OptionalStanza -> OptionalStanzaSet
optStanzaSetIntersection :: OptionalStanzaSet -> OptionalStanzaSet -> OptionalStanzaSet
optStanzaSetNull :: OptionalStanzaSet -> Bool
optStanzaSetIsSubset :: OptionalStanzaSet -> OptionalStanzaSet -> Bool

-- | Note: this is total map.
data OptionalStanzaMap a
optStanzaTabulate :: (OptionalStanza -> a) -> OptionalStanzaMap a
optStanzaIndex :: OptionalStanzaMap a -> OptionalStanza -> a
optStanzaLookup :: OptionalStanza -> OptionalStanzaMap a -> a
optStanzaKeysFilteredByValue :: (a -> Bool) -> OptionalStanzaMap a -> OptionalStanzaSet
instance GHC.Generics.Generic Distribution.Solver.Types.OptionalStanza.OptionalStanza
instance GHC.Show.Show Distribution.Solver.Types.OptionalStanza.OptionalStanza
instance GHC.Enum.Bounded Distribution.Solver.Types.OptionalStanza.OptionalStanza
instance GHC.Enum.Enum Distribution.Solver.Types.OptionalStanza.OptionalStanza
instance GHC.Classes.Ord Distribution.Solver.Types.OptionalStanza.OptionalStanza
instance GHC.Classes.Eq Distribution.Solver.Types.OptionalStanza.OptionalStanza
instance GHC.Show.Show Distribution.Solver.Types.OptionalStanza.OptionalStanzaSet
instance GHC.Classes.Ord Distribution.Solver.Types.OptionalStanza.OptionalStanzaSet
instance GHC.Classes.Eq Distribution.Solver.Types.OptionalStanza.OptionalStanzaSet
instance GHC.Generics.Generic (Distribution.Solver.Types.OptionalStanza.OptionalStanzaMap a)
instance GHC.Show.Show a => GHC.Show.Show (Distribution.Solver.Types.OptionalStanza.OptionalStanzaMap a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Distribution.Solver.Types.OptionalStanza.OptionalStanzaMap a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Distribution.Solver.Types.OptionalStanza.OptionalStanzaMap a)
instance Data.Binary.Class.Binary a => Data.Binary.Class.Binary (Distribution.Solver.Types.OptionalStanza.OptionalStanzaMap a)
instance Distribution.Utils.Structured.Structured a => Distribution.Utils.Structured.Structured (Distribution.Solver.Types.OptionalStanza.OptionalStanzaMap a)
instance Data.Binary.Class.Binary Distribution.Solver.Types.OptionalStanza.OptionalStanzaSet
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.OptionalStanza.OptionalStanzaSet
instance GHC.Base.Semigroup Distribution.Solver.Types.OptionalStanza.OptionalStanzaSet
instance GHC.Base.Monoid Distribution.Solver.Types.OptionalStanza.OptionalStanzaSet
instance Data.Binary.Class.Binary Distribution.Solver.Types.OptionalStanza.OptionalStanza
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.OptionalStanza.OptionalStanza

module Distribution.Solver.Types.PackageFixedDeps

-- | Subclass of packages that have specific versioned dependencies.
--   
--   So for example a not-yet-configured package has dependencies on
--   version ranges, not specific versions. A configured or an already
--   installed package depends on exact versions. Some operations or data
--   structures (like dependency graphs) only make sense on this subclass
--   of package types.
class Package pkg => PackageFixedDeps pkg
depends :: PackageFixedDeps pkg => pkg -> ComponentDeps [UnitId]
instance Distribution.Solver.Types.PackageFixedDeps.PackageFixedDeps Distribution.Types.InstalledPackageInfo.InstalledPackageInfo


-- | An index of packages.
module Distribution.Solver.Types.PackageIndex

-- | The collection of information about packages from one or more
--   <tt>PackageDB</tt>s.
--   
--   It can be searched efficiently by package name and version.
data PackageIndex pkg

-- | Build an index out of a bunch of packages.
--   
--   If there are duplicates, later ones mask earlier ones.
fromList :: Package pkg => [pkg] -> PackageIndex pkg

-- | Merge two indexes.
--   
--   Packages from the second mask packages of the same exact name
--   (case-sensitively) from the first.
merge :: Package pkg => PackageIndex pkg -> PackageIndex pkg -> PackageIndex pkg

-- | Override-merge of two indexes.
--   
--   Packages from the second mask packages of the same exact name
--   (case-sensitively) from the first.
override :: Package pkg => PackageIndex pkg -> PackageIndex pkg -> PackageIndex pkg

-- | Inserts a single package into the index.
--   
--   This is equivalent to (but slightly quicker than) using <a>mappend</a>
--   or <a>merge</a> with a singleton index.
insert :: Package pkg => pkg -> PackageIndex pkg -> PackageIndex pkg

-- | Removes all packages with this (case-sensitive) name from the index.
deletePackageName :: Package pkg => PackageName -> PackageIndex pkg -> PackageIndex pkg

-- | Removes a single package from the index.
deletePackageId :: Package pkg => PackageIdentifier -> PackageIndex pkg -> PackageIndex pkg

-- | Removes all packages satisfying this dependency from the index.
deleteDependency :: Package pkg => PackageName -> VersionRange -> PackageIndex pkg -> PackageIndex pkg
elemByPackageId :: Package pkg => PackageIndex pkg -> PackageIdentifier -> Bool
elemByPackageName :: Package pkg => PackageIndex pkg -> PackageName -> Bool

-- | Does a case-sensitive search by package name.
lookupPackageName :: Package pkg => PackageIndex pkg -> PackageName -> [pkg]

-- | Does a lookup by package id (name &amp; version).
--   
--   Since multiple package DBs mask each other case-sensitively by package
--   name, then we get back at most one package.
lookupPackageId :: Package pkg => PackageIndex pkg -> PackageIdentifier -> Maybe pkg

-- | Does a case-sensitive search by package name and a range of versions.
--   
--   We get back any number of versions of the specified package name, all
--   satisfying the version range constraint.
lookupDependency :: Package pkg => PackageIndex pkg -> PackageName -> VersionRange -> [pkg]

-- | Does a case-insensitive search by package name.
--   
--   If there is only one package that compares case-insensitively to this
--   name then the search is unambiguous and we get back all versions of
--   that package. If several match case-insensitively but one matches
--   exactly then it is also unambiguous.
--   
--   If however several match case-insensitively and none match exactly
--   then we have an ambiguous result, and we get back all the versions of
--   all the packages. The list of ambiguous results is split by exact
--   package name. So it is a non-empty list of non-empty lists.
searchByName :: PackageIndex pkg -> String -> [(PackageName, [pkg])]
data SearchResult a
None :: SearchResult a
Unambiguous :: a -> SearchResult a
Ambiguous :: [a] -> SearchResult a

-- | Does a case-insensitive substring search by package name.
--   
--   That is, all packages that contain the given string in their name.
searchByNameSubstring :: PackageIndex pkg -> String -> [(PackageName, [pkg])]
searchWithPredicate :: PackageIndex pkg -> (String -> Bool) -> [(PackageName, [pkg])]

-- | Get all the packages from the index.
allPackages :: PackageIndex pkg -> [pkg]

-- | Get all the packages from the index.
--   
--   They are grouped by package name, case-sensitively.
allPackagesByName :: PackageIndex pkg -> [[pkg]]
instance GHC.Generics.Generic (Distribution.Solver.Types.PackageIndex.PackageIndex pkg)
instance GHC.Base.Functor Distribution.Solver.Types.PackageIndex.PackageIndex
instance GHC.Read.Read pkg => GHC.Read.Read (Distribution.Solver.Types.PackageIndex.PackageIndex pkg)
instance GHC.Show.Show pkg => GHC.Show.Show (Distribution.Solver.Types.PackageIndex.PackageIndex pkg)
instance GHC.Classes.Eq pkg => GHC.Classes.Eq (Distribution.Solver.Types.PackageIndex.PackageIndex pkg)
instance Distribution.Package.Package pkg => GHC.Base.Semigroup (Distribution.Solver.Types.PackageIndex.PackageIndex pkg)
instance Distribution.Package.Package pkg => GHC.Base.Monoid (Distribution.Solver.Types.PackageIndex.PackageIndex pkg)
instance Data.Binary.Class.Binary pkg => Data.Binary.Class.Binary (Distribution.Solver.Types.PackageIndex.PackageIndex pkg)

module Distribution.Solver.Types.PackagePath

-- | A package path consists of a namespace and a package path inside that
--   namespace.
data PackagePath
PackagePath :: Namespace -> Qualifier -> PackagePath

-- | Top-level namespace
--   
--   Package choices in different namespaces are considered completely
--   independent by the solver.
data Namespace

-- | The default namespace
DefaultNamespace :: Namespace

-- | A namespace for a specific build target
Independent :: PackageName -> Namespace

-- | Qualifier of a package within a namespace (see <a>PackagePath</a>)
data Qualifier

-- | Top-level dependency in this namespace
QualToplevel :: Qualifier

-- | Any dependency on base is considered independent
--   
--   This makes it possible to have base shims.
QualBase :: PackageName -> Qualifier

-- | Setup dependency
--   
--   By rights setup dependencies ought to be nestable; after all, the
--   setup dependencies of a package might themselves have setup
--   dependencies, which are independent from everything else. However,
--   this very quickly leads to infinite search trees in the solver.
--   Therefore we limit ourselves to a single qualifier (within a given
--   namespace).
QualSetup :: PackageName -> Qualifier

-- | If we depend on an executable from a package (via
--   <tt>build-tools</tt>), we should solve for the dependencies of that
--   package separately (since we're not going to actually try to link it.)
--   We qualify for EACH package separately; e.g., <tt><tt>Exe</tt> pn1
--   pn2</tt> qualifies the <tt>build-tools</tt> dependency on <tt>pn2</tt>
--   from package <tt>pn1</tt>. (If we tracked only <tt>pn1</tt>, that
--   would require a consistent dependency resolution for all of the
--   depended upon executables from a package; if we tracked only
--   <tt>pn2</tt>, that would require us to pick only one version of an
--   executable over the entire install plan.)
QualExe :: PackageName -> PackageName -> Qualifier

-- | Pretty-prints a qualifier. The result is either empty or ends in a
--   period, so it can be prepended onto a package name.
--   
--   NOTE: the base qualifier is for a dependency _on_ base; the qualifier
--   is there to make sure different dependencies on base are all
--   independent. So we want to print something like <tt>"A.base"</tt>,
--   where the <tt>"A."</tt> part is the qualifier and <tt>"base"</tt> is
--   the actual dependency (which, for the <tt>Base</tt> qualifier, will
--   always be <tt>base</tt>).
dispQualifier :: Qualifier -> Doc

-- | A qualified entity. Pairs a package path with the entity.
data Qualified a
Q :: PackagePath -> a -> Qualified a

-- | Qualified package name.
type QPN = Qualified PackageName

-- | Pretty-prints a qualified package name.
dispQPN :: QPN -> Doc

-- | String representation of a qualified package name.
showQPN :: QPN -> String
instance GHC.Show.Show Distribution.Solver.Types.PackagePath.Namespace
instance GHC.Classes.Ord Distribution.Solver.Types.PackagePath.Namespace
instance GHC.Classes.Eq Distribution.Solver.Types.PackagePath.Namespace
instance GHC.Show.Show Distribution.Solver.Types.PackagePath.Qualifier
instance GHC.Classes.Ord Distribution.Solver.Types.PackagePath.Qualifier
instance GHC.Classes.Eq Distribution.Solver.Types.PackagePath.Qualifier
instance GHC.Show.Show Distribution.Solver.Types.PackagePath.PackagePath
instance GHC.Classes.Ord Distribution.Solver.Types.PackagePath.PackagePath
instance GHC.Classes.Eq Distribution.Solver.Types.PackagePath.PackagePath
instance GHC.Show.Show a => GHC.Show.Show (Distribution.Solver.Types.PackagePath.Qualified a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Distribution.Solver.Types.PackagePath.Qualified a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Distribution.Solver.Types.PackagePath.Qualified a)


-- | Per-package constraints. Package constraints must be respected by the
--   solver. Multiple constraints for each package can be given, though
--   obviously it is possible to construct conflicting constraints (eg
--   impossible version range or inconsistent flag assignment).
module Distribution.Solver.Types.PackageConstraint

-- | Determines to what packages and in what contexts a constraint applies.
data ConstraintScope

-- | A scope that applies when the given package is used as a build target.
--   In other words, the scope applies iff a goal has a top-level qualifier
--   and its namespace matches the given package name. A namespace is
--   considered to match a package name when it is either the default
--   namespace (for --no-independent-goals) or it is an independent
--   namespace with the given package name (for --independent-goals).
ScopeTarget :: PackageName -> ConstraintScope

-- | The package with the specified name and qualifier.
ScopeQualified :: Qualifier -> PackageName -> ConstraintScope

-- | The package with the specified name when it has a setup qualifier.
ScopeAnySetupQualifier :: PackageName -> ConstraintScope

-- | The package with the specified name regardless of qualifier.
ScopeAnyQualifier :: PackageName -> ConstraintScope

-- | Constructor for a common use case: the constraint applies to the
--   package with the specified name when that package is a top-level
--   dependency in the default namespace.
scopeToplevel :: PackageName -> ConstraintScope

-- | Returns the package name associated with a constraint scope.
scopeToPackageName :: ConstraintScope -> PackageName
constraintScopeMatches :: ConstraintScope -> QPN -> Bool

-- | A package property is a logical predicate on packages.
data PackageProperty
PackagePropertyVersion :: VersionRange -> PackageProperty
PackagePropertyInstalled :: PackageProperty
PackagePropertySource :: PackageProperty
PackagePropertyFlags :: FlagAssignment -> PackageProperty
PackagePropertyStanzas :: [OptionalStanza] -> PackageProperty

-- | Pretty-prints a package property.
dispPackageProperty :: PackageProperty -> Doc

-- | A package constraint consists of a scope plus a property that must
--   hold for all packages within that scope.
data PackageConstraint
PackageConstraint :: ConstraintScope -> PackageProperty -> PackageConstraint

-- | Pretty-prints a package constraint.
dispPackageConstraint :: PackageConstraint -> Doc

-- | Alternative textual representation of a package constraint for
--   debugging purposes (slightly more verbose than that produced by
--   <a>dispPackageConstraint</a>).
showPackageConstraint :: PackageConstraint -> String

-- | Lossily convert a <a>PackageConstraint</a> to a <tt>Dependency</tt>.
packageConstraintToDependency :: PackageConstraint -> Maybe PackageVersionConstraint
instance GHC.Show.Show Distribution.Solver.Types.PackageConstraint.ConstraintScope
instance GHC.Classes.Eq Distribution.Solver.Types.PackageConstraint.ConstraintScope
instance GHC.Generics.Generic Distribution.Solver.Types.PackageConstraint.PackageProperty
instance GHC.Show.Show Distribution.Solver.Types.PackageConstraint.PackageProperty
instance GHC.Classes.Eq Distribution.Solver.Types.PackageConstraint.PackageProperty
instance GHC.Show.Show Distribution.Solver.Types.PackageConstraint.PackageConstraint
instance GHC.Classes.Eq Distribution.Solver.Types.PackageConstraint.PackageConstraint
instance Data.Binary.Class.Binary Distribution.Solver.Types.PackageConstraint.PackageProperty
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.PackageConstraint.PackageProperty

module Distribution.Solver.Types.LabeledPackageConstraint

-- | <a>PackageConstraint</a> labeled with its source.
data LabeledPackageConstraint
LabeledPackageConstraint :: PackageConstraint -> ConstraintSource -> LabeledPackageConstraint
unlabelPackageConstraint :: LabeledPackageConstraint -> PackageConstraint

module Distribution.Solver.Modular.Package

-- | Instance. A version number and a location.
data I
I :: Ver -> Loc -> I

-- | Location. Info about whether a package is installed or not, and where
--   exactly it is located. For installed packages, uniquely identifies the
--   package instance via its <a>PId</a>.
--   
--   TODO: More information is needed about the repo.
data Loc
Inst :: PId -> Loc
InRepo :: Loc

-- | Type alias so we can use the shorter name PackageId.
type PackageId = PackageIdentifier

-- | The name and version of a package.
data () => PackageIdentifier
PackageIdentifier :: PackageName -> Version -> PackageIdentifier

-- | The name of this package, eg. foo
[pkgName] :: PackageIdentifier -> PackageName

-- | the version of this package, eg 1.2
[pkgVersion] :: PackageIdentifier -> Version

-- | A package name.
--   
--   Use <a>mkPackageName</a> and <a>unPackageName</a> to convert from/to a
--   <a>String</a>.
--   
--   This type is opaque since <tt>Cabal-2.0</tt>
data () => PackageName

-- | Construct a <a>PackageName</a> from a <a>String</a>
--   
--   <a>mkPackageName</a> is the inverse to <a>unPackageName</a>
--   
--   Note: No validations are performed to ensure that the resulting
--   <a>PackageName</a> is valid
mkPackageName :: String -> PackageName

-- | Convert <a>PackageName</a> to <a>String</a>
unPackageName :: PackageName -> String

-- | A pkg-config library name
--   
--   This is parsed as any valid argument to the pkg-config utility.
data () => PkgconfigName

-- | Construct a <a>PkgconfigName</a> from a <a>String</a>
--   
--   <a>mkPkgconfigName</a> is the inverse to <a>unPkgconfigName</a>
--   
--   Note: No validations are performed to ensure that the resulting
--   <a>PkgconfigName</a> is valid
mkPkgconfigName :: String -> PkgconfigName

-- | Convert <a>PkgconfigName</a> to <a>String</a>
unPkgconfigName :: PkgconfigName -> String

-- | Package instance. A package name and an instance.
data PI qpn
PI :: qpn -> I -> PI qpn

-- | A package name.
type PN = PackageName

-- | Qualified package version.
type QPV = Qualified PV
instI :: I -> Bool

-- | Qualify a target package with its own name so that its dependencies
--   are not required to be consistent with other targets.
makeIndependent :: PN -> QPN

-- | Is the package in the primary group of packages. This is used to
--   determine (1) if we should try to establish stanza preferences for
--   this goal, and (2) whether or not a user specified
--   <tt>--constraint</tt> should apply to this dependency (grep
--   <a>primaryPP</a> to see the use sites). In particular this does not
--   include packages pulled in as setup deps.
primaryPP :: PackagePath -> Bool

-- | Is the package a dependency of a setup script. This is used to
--   establish whether or not certain constraints should apply to this
--   dependency (grep <a>setupPP</a> to see the use sites).
setupPP :: PackagePath -> Bool

-- | String representation of an instance.
showI :: I -> String

-- | String representation of a package instance.
showPI :: PI QPN -> String

-- | Unpacking a package name.
unPN :: PN -> String
instance GHC.Show.Show Distribution.Solver.Modular.Package.Loc
instance GHC.Classes.Ord Distribution.Solver.Modular.Package.Loc
instance GHC.Classes.Eq Distribution.Solver.Modular.Package.Loc
instance GHC.Show.Show Distribution.Solver.Modular.Package.I
instance GHC.Classes.Ord Distribution.Solver.Modular.Package.I
instance GHC.Classes.Eq Distribution.Solver.Modular.Package.I
instance GHC.Base.Functor Distribution.Solver.Modular.Package.PI
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Package.PI qpn)
instance GHC.Classes.Ord qpn => GHC.Classes.Ord (Distribution.Solver.Modular.Package.PI qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Package.PI qpn)

module Distribution.Solver.Modular.Configured

-- | A configured package is a package instance together with a flag
--   assignment and complete dependencies.
data CP qpn
CP :: PI qpn -> FlagAssignment -> OptionalStanzaSet -> ComponentDeps [PI qpn] -> CP qpn

module Distribution.Solver.Modular.Flag

-- | Flag info. Default value, whether the flag is manual, and whether the
--   flag is weak. Manual flags can only be set explicitly. Weak flags are
--   typically deferred by the solver.
data FInfo
FInfo :: Bool -> FlagType -> WeakOrTrivial -> FInfo
[fdefault] :: FInfo -> Bool
[fmanual] :: FInfo -> FlagType
[fweak] :: FInfo -> WeakOrTrivial

-- | Flag identifier. Just a string.
type Flag = FlagName

-- | Flag defaults.
type FlagInfo = Map Flag FInfo

-- | Flag name. Consists of a package instance and the flag identifier
--   itself.
data FN qpn
FN :: qpn -> Flag -> FN qpn

-- | Qualified flag name.
type QFN = FN QPN

-- | Qualified stanza name.
type QSN = SN QPN

-- | Stanza identifier.
type Stanza = OptionalStanza

-- | Stanza name. Paired with a package name, much like a flag.
data SN qpn
SN :: qpn -> Stanza -> SN qpn

-- | A property of flag and stanza choices that determines whether the
--   choice should be deferred in the solving process.
--   
--   A choice is called weak if we do want to defer it. This is the case
--   for flags that should be implied by what's currently installed on the
--   system, as opposed to flags that are used to explicitly enable or
--   disable some functionality.
--   
--   A choice is called trivial if it clearly does not matter. The special
--   case of triviality we actually consider is if there are no new
--   dependencies introduced by the choice.
newtype WeakOrTrivial
WeakOrTrivial :: Bool -> WeakOrTrivial
[unWeakOrTrivial] :: WeakOrTrivial -> Bool

-- | Value shown for a flag in a solver log message. The message can refer
--   to only the true choice, only the false choice, or both choices.
data FlagValue
FlagTrue :: FlagValue
FlagFalse :: FlagValue
FlagBoth :: FlagValue
mkFlag :: String -> Flag
showQFN :: QFN -> String
showQFNBool :: QFN -> Bool -> String

-- | String representation of a flag-value pair.
showFlagValue :: FlagName -> FlagValue -> String
showQSN :: QSN -> String
showQSNBool :: QSN -> Bool -> String
showSBool :: Stanza -> Bool -> String
instance GHC.Base.Functor Distribution.Solver.Modular.Flag.FN
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Flag.FN qpn)
instance GHC.Classes.Ord qpn => GHC.Classes.Ord (Distribution.Solver.Modular.Flag.FN qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Flag.FN qpn)
instance GHC.Base.Functor Distribution.Solver.Modular.Flag.SN
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Flag.SN qpn)
instance GHC.Classes.Ord qpn => GHC.Classes.Ord (Distribution.Solver.Modular.Flag.SN qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Flag.SN qpn)
instance GHC.Show.Show Distribution.Solver.Modular.Flag.WeakOrTrivial
instance GHC.Classes.Ord Distribution.Solver.Modular.Flag.WeakOrTrivial
instance GHC.Classes.Eq Distribution.Solver.Modular.Flag.WeakOrTrivial
instance GHC.Show.Show Distribution.Solver.Modular.Flag.FInfo
instance GHC.Classes.Eq Distribution.Solver.Modular.Flag.FInfo
instance GHC.Show.Show Distribution.Solver.Modular.Flag.FlagValue
instance GHC.Classes.Eq Distribution.Solver.Modular.Flag.FlagValue

module Distribution.Solver.Modular.Var

-- | The type of variables that play a role in the solver. Note that the
--   tree currently does not use this type directly, and rather has
--   separate tree nodes for the different types of variables. This fits
--   better with the fact that in most cases, these have to be treated
--   differently.
data Var qpn
P :: qpn -> Var qpn
F :: FN qpn -> Var qpn
S :: SN qpn -> Var qpn
showVar :: Var QPN -> String

-- | Extract the package name from a Var
varPN :: Var qpn -> qpn
instance GHC.Base.Functor Distribution.Solver.Modular.Var.Var
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Var.Var qpn)
instance GHC.Classes.Ord qpn => GHC.Classes.Ord (Distribution.Solver.Modular.Var.Var qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Var.Var qpn)


-- | Conflict sets
--   
--   Intended for double import
--   
--   <pre>
--   import Distribution.Solver.Modular.ConflictSet (ConflictSet)
--   import qualified Distribution.Solver.Modular.ConflictSet as CS
--   </pre>
module Distribution.Solver.Modular.ConflictSet

-- | The set of variables involved in a solver conflict, each paired with
--   details about the conflict.
data ConflictSet

-- | More detailed information about how a conflict set variable caused a
--   conflict. This information can be used to determine whether a second
--   value for that variable would lead to the same conflict.
--   
--   TODO: Handle dependencies under flags or stanzas.
data Conflict

-- | The conflict set variable represents a package which depends on the
--   specified problematic package. For example, the conflict set entry '(P
--   x, GoalConflict y)' means that package x introduced package y, and y
--   led to a conflict.
GoalConflict :: QPN -> Conflict

-- | The conflict set variable represents a package with a constraint that
--   excluded the specified package and version. For example, the conflict
--   set entry '(P x, VersionConstraintConflict y (mkVersion [2, 0]))'
--   means that package x's constraint on y excluded y-2.0.
VersionConstraintConflict :: QPN -> Ver -> Conflict

-- | The conflict set variable represents a package that was excluded by a
--   constraint from the specified package. For example, the conflict set
--   entry '(P x, VersionConflict y (orLaterVersion (mkVersion [2, 0])))'
--   means that package y's constraint 'x &gt;= 2.0' excluded some version
--   of x.
VersionConflict :: QPN -> OrderedVersionRange -> Conflict

-- | Any other conflict.
OtherConflict :: Conflict
type ConflictMap = Map (Var QPN) Int

-- | Version range with an <a>Ord</a> instance.
newtype OrderedVersionRange
OrderedVersionRange :: VR -> OrderedVersionRange
showConflictSet :: ConflictSet -> String
showCSSortedByFrequency :: ConflictMap -> ConflictSet -> String
showCSWithFrequency :: ConflictMap -> ConflictSet -> String
toSet :: ConflictSet -> Set (Var QPN)
toList :: ConflictSet -> [Var QPN]
union :: ConflictSet -> ConflictSet -> ConflictSet
unions :: [ConflictSet] -> ConflictSet
insert :: Var QPN -> ConflictSet -> ConflictSet
delete :: Var QPN -> ConflictSet -> ConflictSet
empty :: ConflictSet
singleton :: Var QPN -> ConflictSet
singletonWithConflict :: Var QPN -> Conflict -> ConflictSet
size :: ConflictSet -> Int
member :: Var QPN -> ConflictSet -> Bool
lookup :: Var QPN -> ConflictSet -> Maybe (Set Conflict)

-- | &lt;math&gt;. <a>filter</a>, applied to a predicate and a list,
--   returns the list of those elements that satisfy the predicate; i.e.,
--   
--   <pre>
--   filter p xs = [ x | x &lt;- xs, p x]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; filter odd [1, 2, 3]
--   [1,3]
--   </pre>
filter :: (a -> Bool) -> [a] -> [a]
fromList :: [Var QPN] -> ConflictSet
instance GHC.Show.Show Distribution.Solver.Modular.ConflictSet.OrderedVersionRange
instance GHC.Classes.Eq Distribution.Solver.Modular.ConflictSet.OrderedVersionRange
instance GHC.Show.Show Distribution.Solver.Modular.ConflictSet.Conflict
instance GHC.Classes.Ord Distribution.Solver.Modular.ConflictSet.Conflict
instance GHC.Classes.Eq Distribution.Solver.Modular.ConflictSet.Conflict
instance GHC.Show.Show Distribution.Solver.Modular.ConflictSet.ConflictSet
instance GHC.Classes.Eq Distribution.Solver.Modular.ConflictSet.ConflictSet
instance GHC.Classes.Ord Distribution.Solver.Modular.ConflictSet.ConflictSet
instance GHC.Classes.Ord Distribution.Solver.Modular.ConflictSet.OrderedVersionRange

module Distribution.Solver.Modular.Dependency

-- | The type of variables that play a role in the solver. Note that the
--   tree currently does not use this type directly, and rather has
--   separate tree nodes for the different types of variables. This fits
--   better with the fact that in most cases, these have to be treated
--   differently.
data Var qpn
P :: qpn -> Var qpn
F :: FN qpn -> Var qpn
S :: SN qpn -> Var qpn
showVar :: Var QPN -> String

-- | Extract the package name from a Var
varPN :: Var qpn -> qpn

-- | The set of variables involved in a solver conflict, each paired with
--   details about the conflict.
data ConflictSet
type ConflictMap = Map (Var QPN) Int
showConflictSet :: ConflictSet -> String

-- | Constrained instance. It represents the allowed instances for a
--   package, which can be either a fixed instance or a version range.
data CI
Fixed :: I -> CI
Constrained :: VR -> CI

-- | Flagged dependencies
--   
--   <a>FlaggedDeps</a> is the modular solver's view of a packages
--   dependencies: rather than having the dependencies indexed by
--   component, each dependency defines what component it is in.
--   
--   Note that each dependency is associated with a Component. We must know
--   what component the dependencies belong to, or else we won't be able to
--   construct fine-grained reverse dependencies.
type FlaggedDeps qpn = [FlaggedDep qpn]

-- | Flagged dependencies can either be plain dependency constraints, or
--   flag-dependent dependency trees.
data FlaggedDep qpn

-- | Dependencies which are conditional on a flag choice.
Flagged :: FN qpn -> FInfo -> TrueFlaggedDeps qpn -> FalseFlaggedDeps qpn -> FlaggedDep qpn

-- | Dependencies which are conditional on whether or not a stanza (e.g., a
--   test suite or benchmark) is enabled.
Stanza :: SN qpn -> TrueFlaggedDeps qpn -> FlaggedDep qpn

-- | Dependencies which are always enabled, for the component
--   <tt>comp</tt>.
Simple :: LDep qpn -> Component -> FlaggedDep qpn

-- | A <a>Dep</a> labeled with the reason it was introduced.
--   
--   <a>LDep</a> intentionally has no <a>Functor</a> instance because the
--   type variable is used both to record the dependencies as well as who's
--   doing the depending; having a <a>Functor</a> instance makes bugs where
--   we don't distinguish these two far too likely. (By rights <a>LDep</a>
--   ought to have two type variables.)
data LDep qpn
LDep :: DependencyReason qpn -> Dep qpn -> LDep qpn

-- | A dependency (constraint) associates a package name with a constrained
--   instance. It can also represent other types of dependencies, such as
--   dependencies on language extensions.
data Dep qpn

-- | dependency on a package component
Dep :: PkgComponent qpn -> CI -> Dep qpn

-- | dependency on a language extension
Ext :: Extension -> Dep qpn

-- | dependency on a language version
Lang :: Language -> Dep qpn

-- | dependency on a pkg-config package
Pkg :: PkgconfigName -> PkgconfigVersionRange -> Dep qpn

-- | An exposed component within a package. This type is used to represent
--   build-depends and build-tool-depends dependencies.
data PkgComponent qpn
PkgComponent :: qpn -> ExposedComponent -> PkgComponent qpn

-- | A component that can be depended upon by another package, i.e., a
--   library or an executable.
data ExposedComponent
ExposedLib :: LibraryName -> ExposedComponent
ExposedExe :: UnqualComponentName -> ExposedComponent

-- | The reason that a dependency is active. It identifies the package and
--   any flag and stanza choices that introduced the dependency. It
--   contains everything needed for creating ConflictSets or describing
--   conflicts in solver log messages.
data DependencyReason qpn
DependencyReason :: qpn -> Map Flag FlagValue -> Set Stanza -> DependencyReason qpn

-- | Print the reason that a dependency was introduced.
showDependencyReason :: DependencyReason QPN -> String

-- | Conservatively flatten out flagged dependencies
--   
--   NOTE: We do not filter out duplicates.
flattenFlaggedDeps :: FlaggedDeps qpn -> [(LDep qpn, Component)]

-- | Options for goal qualification (used in <a>qualifyDeps</a>)
--   
--   See also <tt>defaultQualifyOptions</tt>
data QualifyOptions
QO :: Bool -> Bool -> QualifyOptions

-- | Do we have a version of base relying on another version of base?
[qoBaseShim] :: QualifyOptions -> Bool
[qoSetupIndependent] :: QualifyOptions -> Bool

-- | Apply built-in rules for package qualifiers
--   
--   Although the behaviour of <a>qualifyDeps</a> depends on the
--   <a>QualifyOptions</a>, it is important that these
--   <a>QualifyOptions</a> are _static_. Qualification does NOT depend on
--   flag assignment; in other words, it behaves the same no matter which
--   choices the solver makes (modulo the global <a>QualifyOptions</a>); we
--   rely on this in <tt>linkDeps</tt> (see comment there).
--   
--   NOTE: It's the _dependencies_ of a package that may or may not be
--   independent from the package itself. Package flag choices must of
--   course be consistent.
qualifyDeps :: QualifyOptions -> QPN -> FlaggedDeps PN -> FlaggedDeps QPN

-- | Remove qualifiers from set of dependencies
--   
--   This is used during link validation: when we link package <tt>Q.A</tt>
--   to <tt>Q'.A</tt>, then all dependencies <tt>Q.B</tt> need to be linked
--   to <tt>Q'.B</tt>. In order to compute what to link these dependencies
--   to, we need to requalify <tt>Q.B</tt> to become <tt>Q'.B</tt>; we do
--   this by first removing all qualifiers and then calling
--   <a>qualifyDeps</a> again.
unqualifyDeps :: FlaggedDeps QPN -> FlaggedDeps PN

-- | A map containing reverse dependencies between qualified package names.
type RevDepMap = Map QPN [(Component, QPN)]

-- | A goal is just a solver variable paired with a reason. The reason is
--   only used for tracing.
data Goal qpn
Goal :: Var qpn -> GoalReason qpn -> Goal qpn

-- | Reason why a goal is being added to a goal set.
data GoalReason qpn
UserGoal :: GoalReason qpn
DependencyGoal :: DependencyReason qpn -> GoalReason qpn
type QGoalReason = GoalReason QPN
goalToVar :: Goal a -> Var a

-- | Compute a singleton conflict set from a <a>Var</a>
varToConflictSet :: Var QPN -> ConflictSet

-- | Convert a <a>GoalReason</a> to a <a>ConflictSet</a> that can be used
--   when the goal leads to a conflict.
goalReasonToConflictSet :: GoalReason QPN -> ConflictSet

-- | Convert a <a>GoalReason</a> to a <a>ConflictSet</a> containing the
--   reason that the conflict occurred, namely the conflict set variables
--   caused a conflict by introducing the given package goal. See the
--   documentation for <tt>GoalConflict</tt>.
--   
--   This function currently only specifies the reason for the conflict in
--   the simple case where the <a>GoalReason</a> does not involve any flags
--   or stanzas. Otherwise, it falls back to calling
--   <a>goalReasonToConflictSet</a>.
goalReasonToConflictSetWithConflict :: QPN -> GoalReason QPN -> ConflictSet

-- | This function returns the solver variables responsible for the
--   dependency. It drops the values chosen for flag and stanza variables,
--   which are only needed for log messages.
dependencyReasonToConflictSet :: DependencyReason QPN -> ConflictSet

-- | Convert a <a>DependencyReason</a> to a <a>ConflictSet</a> specifying
--   that the conflict occurred because the conflict set variables
--   introduced a problematic version constraint. See the documentation for
--   <tt>VersionConstraintConflict</tt>.
--   
--   This function currently only specifies the reason for the conflict in
--   the simple case where the <a>DependencyReason</a> does not involve any
--   flags or stanzas. Otherwise, it falls back to calling
--   <a>dependencyReasonToConflictSet</a>.
dependencyReasonToConflictSetWithVersionConstraintConflict :: QPN -> Ver -> DependencyReason QPN -> ConflictSet

-- | Convert a <a>DependencyReason</a> to a <a>ConflictSet</a> specifying
--   that the conflict occurred because the conflict set variables
--   introduced a version of a package that was excluded by a version
--   constraint. See the documentation for <tt>VersionConflict</tt>.
--   
--   This function currently only specifies the reason for the conflict in
--   the simple case where the <a>DependencyReason</a> does not involve any
--   flags or stanzas. Otherwise, it falls back to calling
--   <a>dependencyReasonToConflictSet</a>.
dependencyReasonToConflictSetWithVersionConflict :: QPN -> OrderedVersionRange -> DependencyReason QPN -> ConflictSet
instance GHC.Show.Show Distribution.Solver.Modular.Dependency.CI
instance GHC.Classes.Eq Distribution.Solver.Modular.Dependency.CI
instance GHC.Show.Show Distribution.Solver.Modular.Dependency.ExposedComponent
instance GHC.Classes.Ord Distribution.Solver.Modular.Dependency.ExposedComponent
instance GHC.Classes.Eq Distribution.Solver.Modular.Dependency.ExposedComponent
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Dependency.PkgComponent qpn)
instance GHC.Base.Functor Distribution.Solver.Modular.Dependency.PkgComponent
instance GHC.Classes.Ord qpn => GHC.Classes.Ord (Distribution.Solver.Modular.Dependency.PkgComponent qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Dependency.PkgComponent qpn)
instance GHC.Base.Functor Distribution.Solver.Modular.Dependency.Dep
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Dependency.DependencyReason qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Dependency.DependencyReason qpn)
instance GHC.Base.Functor Distribution.Solver.Modular.Dependency.DependencyReason
instance GHC.Show.Show Distribution.Solver.Modular.Dependency.QualifyOptions
instance GHC.Base.Functor Distribution.Solver.Modular.Dependency.GoalReason
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Dependency.GoalReason qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Dependency.GoalReason qpn)
instance GHC.Base.Functor Distribution.Solver.Modular.Dependency.Goal
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Modular.Dependency.Goal qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.Dependency.Goal qpn)

module Distribution.Solver.Modular.Tree

-- | A package option is a package instance with an optional linking
--   annotation
--   
--   The modular solver has a number of package goals to solve for, and can
--   only pick a single package version for a single goal. In order to
--   allow to install multiple versions of the same package as part of a
--   single solution the solver uses qualified goals. For example,
--   <tt>0.P</tt> and <tt>1.P</tt> might both be qualified goals for
--   <tt>P</tt>, allowing to pick a difference version of package
--   <tt>P</tt> for <tt>0.P</tt> and <tt>1.P</tt>.
--   
--   Linking is an essential part of this story. In addition to picking a
--   specific version for <tt>1.P</tt>, the solver can also decide to link
--   <tt>1.P</tt> to <tt>0.P</tt> (or vice versa). It means that
--   <tt>1.P</tt> and <tt>0.P</tt> really must be the very same package
--   (and hence must have the same build time configuration, and their
--   dependencies must also be the exact same).
--   
--   See <a>http://www.well-typed.com/blog/2015/03/qualified-goals/</a> for
--   details.
data POption
POption :: I -> Maybe PackagePath -> POption

-- | Type of the search tree. Inlining the choice nodes for now. Weights on
--   package, flag, and stanza choices control the traversal order.
--   
--   The tree can hold additional data on <a>Done</a> nodes (type
--   <tt>d</tt>) and choice nodes (type <tt>c</tt>). For example, during
--   the final traversal, choice nodes contain the variables that
--   introduced the choices, and <a>Done</a> nodes contain the assignments
--   for all variables.
--   
--   TODO: The weight type should be changed from [Double] to Double to
--   avoid giving too much weight to preferences that are applied later.
data Tree d c

-- | Choose a version for a package (or choose to link)
PChoice :: QPN -> RevDepMap -> c -> WeightedPSQ [Weight] POption (Tree d c) -> Tree d c

-- | Choose a value for a flag
--   
--   The Bool is the default value.
FChoice :: QFN -> RevDepMap -> c -> WeakOrTrivial -> FlagType -> Bool -> WeightedPSQ [Weight] Bool (Tree d c) -> Tree d c

-- | Choose whether or not to enable a stanza
SChoice :: QSN -> RevDepMap -> c -> WeakOrTrivial -> WeightedPSQ [Weight] Bool (Tree d c) -> Tree d c

-- | Choose which choice to make next
--   
--   Invariants:
--   
--   <ul>
--   <li>PSQ should never be empty</li>
--   <li>For each choice we additionally record the <a>QGoalReason</a> why
--   we are introducing that goal into tree. Note that most of the time we
--   are working with <tt>Tree QGoalReason</tt>; in that case, we must have
--   the invariant that the <a>QGoalReason</a> cached in the
--   <a>PChoice</a>, <a>FChoice</a> or <a>SChoice</a> directly below a
--   <a>GoalChoice</a> node must equal the reason recorded on that
--   <a>GoalChoice</a> node.</li>
--   </ul>
GoalChoice :: RevDepMap -> PSQ (Goal QPN) (Tree d c) -> Tree d c

-- | We're done -- we found a solution!
Done :: RevDepMap -> d -> Tree d c

-- | We failed to find a solution in this path through the tree
Fail :: ConflictSet -> FailReason -> Tree d c

-- | Functor for the tree type. <tt>a</tt> is the type of nodes' children.
--   <tt>d</tt> and <tt>c</tt> have the same meaning as in <a>Tree</a>.
data TreeF d c a
PChoiceF :: QPN -> RevDepMap -> c -> WeightedPSQ [Weight] POption a -> TreeF d c a
FChoiceF :: QFN -> RevDepMap -> c -> WeakOrTrivial -> FlagType -> Bool -> WeightedPSQ [Weight] Bool a -> TreeF d c a
SChoiceF :: QSN -> RevDepMap -> c -> WeakOrTrivial -> WeightedPSQ [Weight] Bool a -> TreeF d c a
GoalChoiceF :: RevDepMap -> PSQ (Goal QPN) a -> TreeF d c a
DoneF :: RevDepMap -> d -> TreeF d c a
FailF :: ConflictSet -> FailReason -> TreeF d c a
type Weight = Double
data FailReason
UnsupportedExtension :: Extension -> FailReason
UnsupportedLanguage :: Language -> FailReason
MissingPkgconfigPackage :: PkgconfigName -> PkgconfigVersionRange -> FailReason
NewPackageDoesNotMatchExistingConstraint :: ConflictingDep -> FailReason
ConflictingConstraints :: ConflictingDep -> ConflictingDep -> FailReason
NewPackageIsMissingRequiredComponent :: ExposedComponent -> DependencyReason QPN -> FailReason
NewPackageHasPrivateRequiredComponent :: ExposedComponent -> DependencyReason QPN -> FailReason
NewPackageHasUnbuildableRequiredComponent :: ExposedComponent -> DependencyReason QPN -> FailReason
PackageRequiresMissingComponent :: QPN -> ExposedComponent -> FailReason
PackageRequiresPrivateComponent :: QPN -> ExposedComponent -> FailReason
PackageRequiresUnbuildableComponent :: QPN -> ExposedComponent -> FailReason
CannotInstall :: FailReason
CannotReinstall :: FailReason
NotExplicit :: FailReason
Shadowed :: FailReason
Broken :: UnitId -> FailReason
UnknownPackage :: FailReason
GlobalConstraintVersion :: VR -> ConstraintSource -> FailReason
GlobalConstraintInstalled :: ConstraintSource -> FailReason
GlobalConstraintSource :: ConstraintSource -> FailReason
GlobalConstraintFlag :: ConstraintSource -> FailReason
ManualFlag :: FailReason
MalformedFlagChoice :: QFN -> FailReason
MalformedStanzaChoice :: QSN -> FailReason
EmptyGoalChoice :: FailReason
Backjump :: FailReason
MultipleInstances :: FailReason
DependenciesNotLinked :: String -> FailReason
CyclicDependencies :: FailReason
UnsupportedSpecVer :: Ver -> FailReason

-- | Information about a dependency involved in a conflict, for error
--   messages.
data ConflictingDep
ConflictingDep :: DependencyReason QPN -> PkgComponent QPN -> CI -> ConflictingDep

-- | Anamorphism on trees.
ana :: (a -> TreeF d c a) -> a -> Tree d c

-- | Catamorphism on trees.
cata :: (TreeF d c a -> a) -> Tree d c -> a
inn :: TreeF d c (Tree d c) -> Tree d c
innM :: Monad m => TreeF d c (m (Tree d c)) -> m (Tree d c)

-- | Paramorphism on trees.
para :: (TreeF d c (a, Tree d c) -> a) -> Tree d c -> a
trav :: TreeTrav d c a -> Tree d c -> Tree d a

-- | Approximates the number of active choices that are available in a
--   node. Note that we count goal choices as having one choice, always.
zeroOrOneChoices :: Tree d c -> Bool

-- | Determines whether a tree is active, i.e., isn't a failure node.
active :: Tree d c -> Bool
type TreeTrav d c a = TreeF d c (Tree d a) -> TreeF d a (Tree d a)
type EndoTreeTrav d c = TreeTrav d c c
instance GHC.Show.Show Distribution.Solver.Modular.Tree.POption
instance GHC.Classes.Eq Distribution.Solver.Modular.Tree.POption
instance GHC.Show.Show Distribution.Solver.Modular.Tree.ConflictingDep
instance GHC.Classes.Eq Distribution.Solver.Modular.Tree.ConflictingDep
instance GHC.Show.Show Distribution.Solver.Modular.Tree.FailReason
instance GHC.Classes.Eq Distribution.Solver.Modular.Tree.FailReason
instance Data.Traversable.Traversable (Distribution.Solver.Modular.Tree.TreeF d c)
instance Data.Foldable.Foldable (Distribution.Solver.Modular.Tree.TreeF d c)
instance GHC.Base.Functor (Distribution.Solver.Modular.Tree.TreeF d c)

module Distribution.Solver.Modular.Index

-- | An index contains information about package instances. This is a
--   nested dictionary. Package names are mapped to instances, which in
--   turn is mapped to info.
type Index = Map PN (Map I PInfo)

-- | Info associated with a package instance. Currently, dependencies,
--   component names, flags and failure reasons. The component map records
--   whether any components are unbuildable in the current environment
--   (compiler, os, arch, and global flag constraints). Packages that have
--   a failure reason recorded for them are disabled globally, for reasons
--   external to the solver. We currently use this for shadowing which
--   essentially is a GHC limitation, and for installed packages that are
--   broken.
data PInfo
PInfo :: FlaggedDeps PN -> Map ExposedComponent ComponentInfo -> FlagInfo -> Maybe FailReason -> PInfo

-- | Info associated with each library and executable in a package
--   instance.
data ComponentInfo
ComponentInfo :: IsVisible -> IsBuildable -> ComponentInfo
[compIsVisible] :: ComponentInfo -> IsVisible
[compIsBuildable] :: ComponentInfo -> IsBuildable

-- | Whether a component is visible in the current environment.
newtype IsVisible
IsVisible :: Bool -> IsVisible

-- | Whether a component is made unbuildable by a "buildable: False" field.
newtype IsBuildable
IsBuildable :: Bool -> IsBuildable
defaultQualifyOptions :: Index -> QualifyOptions
mkIndex :: [(PN, I, PInfo)] -> Index
instance GHC.Show.Show Distribution.Solver.Modular.Index.IsVisible
instance GHC.Classes.Eq Distribution.Solver.Modular.Index.IsVisible
instance GHC.Show.Show Distribution.Solver.Modular.Index.IsBuildable
instance GHC.Classes.Eq Distribution.Solver.Modular.Index.IsBuildable
instance GHC.Show.Show Distribution.Solver.Modular.Index.ComponentInfo

module Distribution.Solver.Modular.Cycles

-- | Find and reject any nodes with cyclic dependencies
detectCyclesPhase :: Tree d c -> Tree d c
instance Distribution.Compat.Graph.IsNode Distribution.Solver.Modular.Cycles.RevDepMapNode

module Distribution.Solver.Modular.Assignment

-- | A (partial) assignment of variables.
data Assignment
A :: PAssignment -> FAssignment -> SAssignment -> Assignment

-- | A (partial) package assignment. Qualified package names are associated
--   with instances.
type PAssignment = Map QPN I
type FAssignment = Map QFN Bool
type SAssignment = Map QSN Bool

-- | Delivers an ordered list of fully configured packages.
--   
--   TODO: This function is (sort of) ok. However, there's an open bug
--   w.r.t. unqualification. There might be several different instances of
--   one package version chosen by the solver, which will lead to clashes.
toCPs :: Assignment -> RevDepMap -> [CP QPN]
instance GHC.Classes.Eq Distribution.Solver.Modular.Assignment.Assignment
instance GHC.Show.Show Distribution.Solver.Modular.Assignment.Assignment

module Distribution.Solver.Modular.Linking

-- | Validate linked packages
--   
--   Verify that linked packages have
--   
--   <ul>
--   <li>Linked dependencies,</li>
--   <li>Equal flag assignments</li>
--   <li>Equal stanza assignments</li>
--   </ul>
validateLinking :: Index -> Tree d c -> Tree d c
instance GHC.Classes.Eq Distribution.Solver.Modular.Linking.LinkGroup
instance GHC.Show.Show Distribution.Solver.Modular.Linking.LinkGroup
instance GHC.Base.Monad Distribution.Solver.Modular.Linking.UpdateState
instance GHC.Base.Applicative Distribution.Solver.Modular.Linking.UpdateState
instance GHC.Base.Functor Distribution.Solver.Modular.Linking.UpdateState
instance Control.Monad.State.Class.MonadState Distribution.Solver.Modular.Linking.ValidateState Distribution.Solver.Modular.Linking.UpdateState

module Distribution.Solver.Types.PackagePreferences

-- | Per-package preferences on the version. It is a soft constraint that
--   the <tt>DependencyResolver</tt> should try to respect where possible.
--   It consists of an <a>InstalledPreference</a> which says if we prefer
--   versions of packages that are already installed. It also has (possibly
--   multiple) <tt>PackageVersionPreference</tt>s which are suggested
--   constraints on the version number. The resolver should try to use
--   package versions that satisfy the maximum number of the suggested
--   version constraints.
--   
--   It is not specified if preferences on some packages are more important
--   than others.
data PackagePreferences
PackagePreferences :: [VersionRange] -> InstalledPreference -> [OptionalStanza] -> PackagePreferences


-- | Read the list of packages available to pkg-config.
module Distribution.Solver.Types.PkgConfigDb

-- | The list of packages installed in the system visible to
--   <tt>pkg-config</tt>. This is an opaque datatype, to be constructed
--   with <a>readPkgConfigDb</a> and queried with
--   <tt>pkgConfigPkgPresent</tt>.
data PkgConfigDb

-- | If an entry is <a>Nothing</a>, this means that the package seems to be
--   present, but we don't know the exact version (because parsing of the
--   version number failed).
PkgConfigDb :: Map PkgconfigName (Maybe PkgconfigVersion) -> PkgConfigDb

-- | For when we could not run pkg-config successfully.
NoPkgConfigDb :: PkgConfigDb

-- | Query pkg-config for the list of installed packages, together with
--   their versions. Return a <a>PkgConfigDb</a> encapsulating this
--   information.
readPkgConfigDb :: Verbosity -> ProgramDb -> IO PkgConfigDb

-- | Create a <a>PkgConfigDb</a> from a list of <tt>(packageName,
--   version)</tt> pairs.
pkgConfigDbFromList :: [(String, String)] -> PkgConfigDb

-- | Check whether a given package range is satisfiable in the given
--   <tt>pkg-config</tt> database.
pkgConfigPkgIsPresent :: PkgConfigDb -> PkgconfigName -> PkgconfigVersionRange -> Bool

-- | Query the version of a package in the <tt>pkg-config</tt> database.
--   <tt>Nothing</tt> indicates the package is not in the database, while
--   <tt>Just Nothing</tt> indicates that the package is in the database,
--   but its version is not known.
pkgConfigDbPkgVersion :: PkgConfigDb -> PkgconfigName -> Maybe (Maybe PkgconfigVersion)

-- | Query pkg-config for the locations of pkg-config's package files. Use
--   this to monitor for changes in the pkg-config DB.
getPkgConfigDbDirs :: Verbosity -> ProgramDb -> IO [FilePath]
instance GHC.Generics.Generic Distribution.Solver.Types.PkgConfigDb.PkgConfigDb
instance GHC.Show.Show Distribution.Solver.Types.PkgConfigDb.PkgConfigDb
instance Data.Binary.Class.Binary Distribution.Solver.Types.PkgConfigDb.PkgConfigDb
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.PkgConfigDb.PkgConfigDb

module Distribution.Solver.Modular.Validate

-- | Interface.
validateTree :: CompilerInfo -> Index -> PkgConfigDb -> Tree d c -> Tree d c
instance Control.Monad.Reader.Class.MonadReader Distribution.Solver.Modular.Validate.ValidateState Distribution.Solver.Modular.Validate.Validate
instance GHC.Base.Monad Distribution.Solver.Modular.Validate.Validate
instance GHC.Base.Applicative Distribution.Solver.Modular.Validate.Validate
instance GHC.Base.Functor Distribution.Solver.Modular.Validate.Validate

module Distribution.Solver.Types.Progress

-- | A type to represent the unfolding of an expensive long running
--   calculation that may fail. We may get intermediate steps before the
--   final result which may be used to indicate progress and/or logging
--   messages.
data Progress step fail done
Step :: step -> Progress step fail done -> Progress step fail done
Fail :: fail -> Progress step fail done
Done :: done -> Progress step fail done

-- | Consume a <a>Progress</a> calculation. Much like <a>foldr</a> for
--   lists but with two base cases, one for a final result and one for
--   failure.
--   
--   Eg to convert into a simple <a>Either</a> result use:
--   
--   <pre>
--   foldProgress (flip const) Left Right
--   </pre>
foldProgress :: (step -> a -> a) -> (fail -> a) -> (done -> a) -> Progress step fail done -> a
instance GHC.Base.Functor (Distribution.Solver.Types.Progress.Progress step fail)
instance GHC.Base.Monad (Distribution.Solver.Types.Progress.Progress step fail)
instance GHC.Base.Applicative (Distribution.Solver.Types.Progress.Progress step fail)
instance GHC.Base.Monoid fail => GHC.Base.Alternative (Distribution.Solver.Types.Progress.Progress step fail)

module Distribution.Solver.Modular.Message
data Message

-- | increase indentation level
Enter :: Message

-- | decrease indentation level
Leave :: Message
TryP :: QPN -> POption -> Message
TryF :: QFN -> Bool -> Message
TryS :: QSN -> Bool -> Message
Next :: Goal QPN -> Message
Skip :: Set Conflict -> Message
Success :: Message
Failure :: ConflictSet -> FailReason -> Message

-- | Transforms the structured message type to actual messages (strings).
--   
--   The log contains level numbers, which are useful for any trace that
--   involves backtracking, because only the level numbers will allow to
--   keep track of backjumps.
showMessages :: Progress Message a b -> Progress String a b

module Distribution.Solver.Modular.RetryLog

-- | <a>Progress</a> as a difference list that allows efficient appends at
--   failures.
data RetryLog step fail done

-- | <i>O(1)</i>. Convert a <a>RetryLog</a> to a <a>Progress</a>.
toProgress :: RetryLog step fail done -> Progress step fail done

-- | <i>O(N)</i>. Convert a <a>Progress</a> to a <a>RetryLog</a>.
fromProgress :: Progress step fail done -> RetryLog step fail done

-- | <i>O(1)</i>. Apply a function to the failure value in a log.
mapFailure :: (fail1 -> fail2) -> RetryLog step fail1 done -> RetryLog step fail2 done

-- | <i>O(1)</i>. If the first log leads to failure, continue with the
--   second.
retry :: RetryLog step fail1 done -> (fail1 -> RetryLog step fail2 done) -> RetryLog step fail2 done

-- | <i>O(1)</i>. Create a log with one message before a failure.
failWith :: step -> fail -> RetryLog step fail done

-- | <i>O(1)</i>. Create a log with one message before a success.
succeedWith :: step -> done -> RetryLog step fail done

-- | <i>O(1)</i>. Prepend a message to a log.
continueWith :: step -> RetryLog step fail done -> RetryLog step fail done

-- | <i>O(1)</i>. Prepend the given message and <a>Enter</a> to the log,
--   and insert <a>Leave</a> before the failure if the log fails.
tryWith :: Message -> RetryLog Message fail done -> RetryLog Message fail done

module Distribution.Solver.Modular.Log

-- | Postprocesses a log file. This function discards all log messages and
--   avoids calling <a>showMessages</a> if the log isn't needed (specified
--   by <tt>keepLog</tt>), for efficiency.
displayLogMessages :: Bool -> RetryLog Message SolverFailure a -> RetryLog String SolverFailure a

-- | Information about a dependency solver failure.
data SolverFailure
ExhaustiveSearch :: ConflictSet -> ConflictMap -> SolverFailure
BackjumpLimitReached :: SolverFailure

module Distribution.Solver.Types.Settings
newtype ReorderGoals
ReorderGoals :: Bool -> ReorderGoals
newtype IndependentGoals
IndependentGoals :: Bool -> IndependentGoals
newtype PreferOldest
PreferOldest :: Bool -> PreferOldest
newtype MinimizeConflictSet
MinimizeConflictSet :: Bool -> MinimizeConflictSet
newtype AvoidReinstalls
AvoidReinstalls :: Bool -> AvoidReinstalls
newtype ShadowPkgs
ShadowPkgs :: Bool -> ShadowPkgs
newtype StrongFlags
StrongFlags :: Bool -> StrongFlags
newtype AllowBootLibInstalls
AllowBootLibInstalls :: Bool -> AllowBootLibInstalls

-- | Should we consider all packages we know about, or only those that have
--   constraints explicitly placed on them or which are goals?
data OnlyConstrained
OnlyConstrainedNone :: OnlyConstrained
OnlyConstrainedAll :: OnlyConstrained
newtype EnableBackjumping
EnableBackjumping :: Bool -> EnableBackjumping
newtype CountConflicts
CountConflicts :: Bool -> CountConflicts
newtype FineGrainedConflicts
FineGrainedConflicts :: Bool -> FineGrainedConflicts
newtype SolveExecutables
SolveExecutables :: Bool -> SolveExecutables
instance GHC.Show.Show Distribution.Solver.Types.Settings.ReorderGoals
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.ReorderGoals
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.ReorderGoals
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.ReorderGoals
instance GHC.Show.Show Distribution.Solver.Types.Settings.CountConflicts
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.CountConflicts
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.CountConflicts
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.CountConflicts
instance GHC.Show.Show Distribution.Solver.Types.Settings.FineGrainedConflicts
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.FineGrainedConflicts
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.FineGrainedConflicts
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.FineGrainedConflicts
instance GHC.Show.Show Distribution.Solver.Types.Settings.MinimizeConflictSet
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.MinimizeConflictSet
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.MinimizeConflictSet
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.MinimizeConflictSet
instance GHC.Show.Show Distribution.Solver.Types.Settings.IndependentGoals
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.IndependentGoals
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.IndependentGoals
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.IndependentGoals
instance GHC.Show.Show Distribution.Solver.Types.Settings.PreferOldest
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.PreferOldest
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.PreferOldest
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.PreferOldest
instance GHC.Show.Show Distribution.Solver.Types.Settings.AvoidReinstalls
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.AvoidReinstalls
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.AvoidReinstalls
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.AvoidReinstalls
instance GHC.Show.Show Distribution.Solver.Types.Settings.ShadowPkgs
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.ShadowPkgs
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.ShadowPkgs
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.ShadowPkgs
instance GHC.Show.Show Distribution.Solver.Types.Settings.StrongFlags
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.StrongFlags
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.StrongFlags
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.StrongFlags
instance GHC.Show.Show Distribution.Solver.Types.Settings.AllowBootLibInstalls
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.AllowBootLibInstalls
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.AllowBootLibInstalls
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.AllowBootLibInstalls
instance GHC.Show.Show Distribution.Solver.Types.Settings.OnlyConstrained
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.OnlyConstrained
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.OnlyConstrained
instance GHC.Show.Show Distribution.Solver.Types.Settings.EnableBackjumping
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.EnableBackjumping
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.EnableBackjumping
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.EnableBackjumping
instance GHC.Show.Show Distribution.Solver.Types.Settings.SolveExecutables
instance GHC.Generics.Generic Distribution.Solver.Types.Settings.SolveExecutables
instance GHC.Classes.Eq Distribution.Solver.Types.Settings.SolveExecutables
instance Distribution.Simple.Flag.BooleanFlag Distribution.Solver.Types.Settings.SolveExecutables
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.SolveExecutables
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.SolveExecutables
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.OnlyConstrained
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.OnlyConstrained
instance Distribution.Pretty.Pretty Distribution.Solver.Types.Settings.OnlyConstrained
instance Distribution.Parsec.Parsec Distribution.Solver.Types.Settings.OnlyConstrained
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.AllowBootLibInstalls
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.AllowBootLibInstalls
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.StrongFlags
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.StrongFlags
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.ShadowPkgs
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.ShadowPkgs
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.AvoidReinstalls
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.AvoidReinstalls
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.PreferOldest
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.PreferOldest
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.IndependentGoals
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.IndependentGoals
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.MinimizeConflictSet
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.MinimizeConflictSet
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.FineGrainedConflicts
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.FineGrainedConflicts
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.CountConflicts
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.CountConflicts
instance Data.Binary.Class.Binary Distribution.Solver.Types.Settings.ReorderGoals
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.Settings.ReorderGoals

module Distribution.Solver.Modular.Explore

-- | Interface.
--   
--   Takes as an argument a limit on allowed backjumps. If the limit is
--   <a>Nothing</a>, then infinitely many backjumps are allowed. If the
--   limit is 'Just 0', backtracking is completely disabled.
backjumpAndExplore :: Maybe Int -> EnableBackjumping -> FineGrainedConflicts -> CountConflicts -> Index -> Tree d QGoalReason -> RetryLog Message SolverFailure (Assignment, RevDepMap)

module Distribution.Solver.Modular.Builder

-- | Interface to the tree builder. Just takes an index and a list of
--   package names, and computes the initial state and then the tree from
--   there.
buildTree :: Index -> IndependentGoals -> [PN] -> Tree () QGoalReason

-- | Pairs each element of a list with the list resulting from removal of
--   that element from the original list.
splits :: [a] -> [(a, [a])]

module Distribution.Solver.Types.SolverId

-- | The solver can produce references to existing packages or packages we
--   plan to install. Unlike <tt>ConfiguredId</tt> we don't yet know the
--   <a>UnitId</a> for planned packages, because it's not the solver's job
--   to compute them.
data SolverId
PreExistingId :: PackageId -> UnitId -> SolverId
[solverSrcId] :: SolverId -> PackageId
[solverInstId] :: SolverId -> UnitId
PlannedId :: PackageId -> SolverId
[solverSrcId] :: SolverId -> PackageId
instance GHC.Generics.Generic Distribution.Solver.Types.SolverId.SolverId
instance GHC.Classes.Ord Distribution.Solver.Types.SolverId.SolverId
instance GHC.Classes.Eq Distribution.Solver.Types.SolverId.SolverId
instance Data.Binary.Class.Binary Distribution.Solver.Types.SolverId.SolverId
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.SolverId.SolverId
instance GHC.Show.Show Distribution.Solver.Types.SolverId.SolverId
instance Distribution.Package.Package Distribution.Solver.Types.SolverId.SolverId

module Distribution.Solver.Types.InstSolverPackage

-- | An <a>InstSolverPackage</a> is a pre-existing installed package
--   specified by the dependency solver.
data InstSolverPackage
InstSolverPackage :: InstalledPackageInfo -> ComponentDeps [SolverId] -> ComponentDeps [SolverId] -> InstSolverPackage
[instSolverPkgIPI] :: InstSolverPackage -> InstalledPackageInfo
[instSolverPkgLibDeps] :: InstSolverPackage -> ComponentDeps [SolverId]
[instSolverPkgExeDeps] :: InstSolverPackage -> ComponentDeps [SolverId]
instance GHC.Generics.Generic Distribution.Solver.Types.InstSolverPackage.InstSolverPackage
instance GHC.Show.Show Distribution.Solver.Types.InstSolverPackage.InstSolverPackage
instance GHC.Classes.Eq Distribution.Solver.Types.InstSolverPackage.InstSolverPackage
instance Data.Binary.Class.Binary Distribution.Solver.Types.InstSolverPackage.InstSolverPackage
instance Distribution.Utils.Structured.Structured Distribution.Solver.Types.InstSolverPackage.InstSolverPackage
instance Distribution.Package.Package Distribution.Solver.Types.InstSolverPackage.InstSolverPackage
instance Distribution.Package.HasMungedPackageId Distribution.Solver.Types.InstSolverPackage.InstSolverPackage
instance Distribution.Package.HasUnitId Distribution.Solver.Types.InstSolverPackage.InstSolverPackage

module Distribution.Solver.Types.SourcePackage

-- | We sometimes need to override the .cabal file in the tarball with the
--   newer one from the package index.
type PackageDescriptionOverride = Maybe ByteString

-- | A package description along with the location of the package sources.
data SourcePackage loc
SourcePackage :: PackageId -> GenericPackageDescription -> loc -> PackageDescriptionOverride -> SourcePackage loc
[srcpkgPackageId] :: SourcePackage loc -> PackageId

-- | Note, this field is lazy, e.g. when reading in hackage index we parse
--   only what we need, not whole index.
[srcpkgDescription] :: SourcePackage loc -> GenericPackageDescription
[srcpkgSource] :: SourcePackage loc -> loc
[srcpkgDescrOverride] :: SourcePackage loc -> PackageDescriptionOverride
instance GHC.Generics.Generic (Distribution.Solver.Types.SourcePackage.SourcePackage loc)
instance GHC.Show.Show loc => GHC.Show.Show (Distribution.Solver.Types.SourcePackage.SourcePackage loc)
instance GHC.Classes.Eq loc => GHC.Classes.Eq (Distribution.Solver.Types.SourcePackage.SourcePackage loc)
instance Data.Binary.Class.Binary loc => Data.Binary.Class.Binary (Distribution.Solver.Types.SourcePackage.SourcePackage loc)
instance Distribution.Utils.Structured.Structured loc => Distribution.Utils.Structured.Structured (Distribution.Solver.Types.SourcePackage.SourcePackage loc)
instance Distribution.Package.Package (Distribution.Solver.Types.SourcePackage.SourcePackage a)

module Distribution.Solver.Types.SolverPackage

-- | A <a>SolverPackage</a> is a package specified by the dependency
--   solver. It will get elaborated into a <tt>ConfiguredPackage</tt> or
--   even an <tt>ElaboratedConfiguredPackage</tt>.
--   
--   NB: <a>SolverPackage</a>s are essentially always with
--   <tt>UnresolvedPkgLoc</tt>, but for symmetry we have the parameter.
--   (Maybe it can be removed.)
data SolverPackage loc
SolverPackage :: SourcePackage loc -> FlagAssignment -> OptionalStanzaSet -> ComponentDeps [SolverId] -> ComponentDeps [SolverId] -> SolverPackage loc
[solverPkgSource] :: SolverPackage loc -> SourcePackage loc
[solverPkgFlags] :: SolverPackage loc -> FlagAssignment
[solverPkgStanzas] :: SolverPackage loc -> OptionalStanzaSet
[solverPkgLibDeps] :: SolverPackage loc -> ComponentDeps [SolverId]
[solverPkgExeDeps] :: SolverPackage loc -> ComponentDeps [SolverId]
instance GHC.Generics.Generic (Distribution.Solver.Types.SolverPackage.SolverPackage loc)
instance GHC.Show.Show loc => GHC.Show.Show (Distribution.Solver.Types.SolverPackage.SolverPackage loc)
instance GHC.Classes.Eq loc => GHC.Classes.Eq (Distribution.Solver.Types.SolverPackage.SolverPackage loc)
instance Data.Binary.Class.Binary loc => Data.Binary.Class.Binary (Distribution.Solver.Types.SolverPackage.SolverPackage loc)
instance Distribution.Utils.Structured.Structured loc => Distribution.Utils.Structured.Structured (Distribution.Solver.Types.SolverPackage.SolverPackage loc)
instance Distribution.Package.Package (Distribution.Solver.Types.SolverPackage.SolverPackage loc)

module Distribution.Solver.Types.ResolverPackage

-- | The dependency resolver picks either pre-existing installed packages
--   or it picks source packages along with package configuration.
--   
--   This is like the <a>PlanPackage</a> but with fewer cases.
data ResolverPackage loc
PreExisting :: InstSolverPackage -> ResolverPackage loc
Configured :: SolverPackage loc -> ResolverPackage loc
resolverPackageLibDeps :: ResolverPackage loc -> ComponentDeps [SolverId]
resolverPackageExeDeps :: ResolverPackage loc -> ComponentDeps [SolverId]
instance GHC.Generics.Generic (Distribution.Solver.Types.ResolverPackage.ResolverPackage loc)
instance GHC.Show.Show loc => GHC.Show.Show (Distribution.Solver.Types.ResolverPackage.ResolverPackage loc)
instance GHC.Classes.Eq loc => GHC.Classes.Eq (Distribution.Solver.Types.ResolverPackage.ResolverPackage loc)
instance Data.Binary.Class.Binary loc => Data.Binary.Class.Binary (Distribution.Solver.Types.ResolverPackage.ResolverPackage loc)
instance Distribution.Utils.Structured.Structured loc => Distribution.Utils.Structured.Structured (Distribution.Solver.Types.ResolverPackage.ResolverPackage loc)
instance Distribution.Package.Package (Distribution.Solver.Types.ResolverPackage.ResolverPackage loc)
instance Distribution.Compat.Graph.IsNode (Distribution.Solver.Types.ResolverPackage.ResolverPackage loc)

module Distribution.Solver.Types.DependencyResolver

-- | A dependency resolver is a function that works out an installation
--   plan given the set of installed and available packages and a set of
--   deps to solve for.
--   
--   The reason for this interface is because there are dozens of
--   approaches to solving the package dependency problem and we want to
--   make it easy to swap in alternatives.
type DependencyResolver loc = Platform -> CompilerInfo -> InstalledPackageIndex -> PackageIndex (SourcePackage loc) -> PkgConfigDb -> (PackageName -> PackagePreferences) -> [LabeledPackageConstraint] -> Set PackageName -> Progress String String [ResolverPackage loc]

module Distribution.Solver.Modular.IndexConversion

-- | Convert both the installed package index and the source package index
--   into one uniform solver index.
--   
--   We use <tt>allPackagesBySourcePackageId</tt> for the installed package
--   index because that returns us several instances of the same package
--   and version in order of preference. This allows us in principle to
--   "shadow" packages if there are several installed packages of the same
--   version. There are currently some shortcomings in both GHC and Cabal
--   in resolving these situations. However, the right thing to do is to
--   fix the problem there, so for now, shadowing is only activated if
--   explicitly requested.
convPIs :: OS -> Arch -> CompilerInfo -> Map PN [LabeledPackageConstraint] -> ShadowPkgs -> StrongFlags -> SolveExecutables -> InstalledPackageIndex -> PackageIndex (SourcePackage loc) -> Index
instance GHC.Classes.Ord qpn => GHC.Classes.Ord (Distribution.Solver.Modular.IndexConversion.SimpleFlaggedDepKey qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Modular.IndexConversion.SimpleFlaggedDepKey qpn)

module Distribution.Solver.Modular.ConfiguredConversion

-- | Converts from the solver specific result <tt>CP QPN</tt> into a
--   <a>ResolverPackage</a>, which can then be converted into the install
--   plan.
convCP :: InstalledPackageIndex -> PackageIndex (SourcePackage loc) -> CP QPN -> ResolverPackage loc

module Distribution.Solver.Types.Variable

-- | Variables used by the dependency solver. This type is similar to the
--   internal <tt>Var</tt> type.
data Variable qpn
PackageVar :: qpn -> Variable qpn
FlagVar :: qpn -> FlagName -> Variable qpn
StanzaVar :: qpn -> OptionalStanza -> Variable qpn
instance GHC.Show.Show qpn => GHC.Show.Show (Distribution.Solver.Types.Variable.Variable qpn)
instance GHC.Classes.Eq qpn => GHC.Classes.Eq (Distribution.Solver.Types.Variable.Variable qpn)


-- | Reordering or pruning the tree in order to prefer or make certain
--   choices.
module Distribution.Solver.Modular.Preference

-- | Avoid reinstalls.
--   
--   This is a tricky strategy. If a package version is installed already
--   and the same version is available from a repo, the repo version will
--   never be chosen. This would result in a reinstall (either
--   destructively, or potentially, shadowing). The old instance won't be
--   visible or even present anymore, but other packages might have
--   depended on it.
--   
--   TODO: It would be better to actually check the reverse dependencies of
--   installed packages. If they're not depended on, then reinstalling
--   should be fine. Even if they are, perhaps this should just result in
--   trying to reinstall those other packages as well. However, doing this
--   all neatly in one pass would require to change the builder, or at
--   least to change the goal set after building.
avoidReinstalls :: (PN -> Bool) -> EndoTreeTrav d c

-- | Deal with setup and build-tool-depends dependencies after regular
--   dependencies, so we will link setup/exe dependencies against package
--   dependencies when possible
deferSetupExeChoices :: EndoTreeTrav d c

-- | Transformation that tries to avoid making weak flag choices early.
--   Weak flags are trivial flags (not influencing dependencies) or such
--   flags that are explicitly declared to be weak in the index.
deferWeakFlagChoices :: EndoTreeTrav d c

-- | Transformation that tries to enforce the rule that manual flags can
--   only be set by the user.
--   
--   If there are no constraints on a manual flag, this function prunes all
--   but the default value. If there are constraints, then the flag is
--   allowed to have the values specified by the constraints. Note that the
--   type used for flag values doesn't need to be Bool.
--   
--   This function makes an exception for the case where there are multiple
--   goals for a single package (with different qualifiers), and flag
--   constraints for manual flag x only apply to some of those goals. In
--   that case, we allow the unconstrained goals to use the default value
--   for x OR any of the values in the constraints on x (even though the
--   constraints don't apply), in order to allow the unconstrained goals to
--   be linked to the constrained goals. See
--   <a>https://github.com/haskell/cabal/issues/4299</a>. Removing the
--   single instance restriction (SIR) would also fix #4299, so we may want
--   to remove this exception and only let the user toggle manual flags if
--   we remove the SIR.
--   
--   This function does not enforce any of the constraints, since that is
--   done by <a>enforcePackageConstraints</a>.
enforceManualFlags :: Map PN [LabeledPackageConstraint] -> EndoTreeTrav d c

-- | Traversal that tries to establish various kinds of user constraints.
--   Works by selectively disabling choices that have been ruled out by
--   global user constraints.
enforcePackageConstraints :: Map PN [LabeledPackageConstraint] -> EndoTreeTrav d c

-- | Enforce ghc's single instance restriction
--   
--   From the solver's perspective, this means that for any package
--   instance (that is, package name + package version) there can be at
--   most one qualified goal resolving to that instance (there may be other
--   goals _linking_ to that instance however).
enforceSingleInstanceRestriction :: Tree d c -> Tree d c

-- | Always choose the first goal in the list next, abandoning all other
--   choices.
--   
--   This is unnecessary for the default search strategy, because it
--   descends only into the first goal choice anyway, but may still make
--   sense to just reduce the tree size a bit.
firstGoal :: EndoTreeTrav d c

-- | Transformation that tries to make a decision on base as early as
--   possible by pruning all other goals when base is available. In nearly
--   all cases, there's a single choice for the base package. Also, fixing
--   base early should lead to better error messages.
preferBaseGoalChoice :: EndoTreeTrav d c

-- | Prefer to link packages whenever possible.
preferLinked :: EndoTreeTrav d c
preferPackagePreferences :: (PN -> PackagePreferences) -> EndoTreeTrav d c

-- | Transformation that prefers goals with lower branching degrees.
--   
--   When a goal choice node has at least one goal with zero or one
--   children, this function prunes all other goals. This transformation
--   can help the solver find a solution in fewer steps by allowing it to
--   backtrack sooner when it is exploring a subtree with no solutions.
--   However, each step is more expensive.
preferReallyEasyGoalChoices :: EndoTreeTrav d c

-- | Require installed packages.
requireInstalled :: (PN -> Bool) -> EndoTreeTrav d c

-- | Require all packages to be mentioned in a constraint or as a goal.
onlyConstrained :: (PN -> Bool) -> EndoTreeTrav d QGoalReason

-- | Sort all goals using the provided function.
sortGoals :: (Variable QPN -> Variable QPN -> Ordering) -> EndoTreeTrav d c

-- | Reduce the branching degree of the search tree by removing all choices
--   after the first successful choice at each level. The returned tree is
--   the minimal subtree containing the path to the first backjump.
pruneAfterFirstSuccess :: EndoTreeTrav d c

module Distribution.Solver.Modular.Solver

-- | Various options for the modular solver.
data SolverConfig
SolverConfig :: ReorderGoals -> CountConflicts -> FineGrainedConflicts -> MinimizeConflictSet -> IndependentGoals -> AvoidReinstalls -> ShadowPkgs -> StrongFlags -> AllowBootLibInstalls -> OnlyConstrained -> Maybe Int -> EnableBackjumping -> SolveExecutables -> Maybe (Variable QPN -> Variable QPN -> Ordering) -> Verbosity -> PruneAfterFirstSuccess -> SolverConfig
[reorderGoals] :: SolverConfig -> ReorderGoals
[countConflicts] :: SolverConfig -> CountConflicts
[fineGrainedConflicts] :: SolverConfig -> FineGrainedConflicts
[minimizeConflictSet] :: SolverConfig -> MinimizeConflictSet
[independentGoals] :: SolverConfig -> IndependentGoals
[avoidReinstalls] :: SolverConfig -> AvoidReinstalls
[shadowPkgs] :: SolverConfig -> ShadowPkgs
[strongFlags] :: SolverConfig -> StrongFlags
[allowBootLibInstalls] :: SolverConfig -> AllowBootLibInstalls
[onlyConstrained] :: SolverConfig -> OnlyConstrained
[maxBackjumps] :: SolverConfig -> Maybe Int
[enableBackjumping] :: SolverConfig -> EnableBackjumping
[solveExecutables] :: SolverConfig -> SolveExecutables
[goalOrder] :: SolverConfig -> Maybe (Variable QPN -> Variable QPN -> Ordering)
[solverVerbosity] :: SolverConfig -> Verbosity
[pruneAfterFirstSuccess] :: SolverConfig -> PruneAfterFirstSuccess

-- | Run all solver phases.
--   
--   In principle, we have a valid tree after <tt>validationPhase</tt>,
--   which means that every <a>Done</a> node should correspond to valid
--   solution.
--   
--   There is one exception, though, and that is cycle detection, which has
--   been added relatively recently. Cycles are only removed directly
--   before exploration.
solve :: SolverConfig -> CompilerInfo -> Index -> PkgConfigDb -> (PN -> PackagePreferences) -> Map PN [LabeledPackageConstraint] -> Set PN -> RetryLog Message SolverFailure (Assignment, RevDepMap)

-- | Whether to remove all choices after the first successful choice at
--   each level in the search tree.
newtype PruneAfterFirstSuccess
PruneAfterFirstSuccess :: Bool -> PruneAfterFirstSuccess

module Distribution.Solver.Modular

-- | Ties the two worlds together: classic cabal-install vs. the modular
--   solver. Performs the necessary translations before and after.
modularResolver :: SolverConfig -> DependencyResolver loc

-- | Various options for the modular solver.
data SolverConfig
SolverConfig :: ReorderGoals -> CountConflicts -> FineGrainedConflicts -> MinimizeConflictSet -> IndependentGoals -> AvoidReinstalls -> ShadowPkgs -> StrongFlags -> AllowBootLibInstalls -> OnlyConstrained -> Maybe Int -> EnableBackjumping -> SolveExecutables -> Maybe (Variable QPN -> Variable QPN -> Ordering) -> Verbosity -> PruneAfterFirstSuccess -> SolverConfig
[reorderGoals] :: SolverConfig -> ReorderGoals
[countConflicts] :: SolverConfig -> CountConflicts
[fineGrainedConflicts] :: SolverConfig -> FineGrainedConflicts
[minimizeConflictSet] :: SolverConfig -> MinimizeConflictSet
[independentGoals] :: SolverConfig -> IndependentGoals
[avoidReinstalls] :: SolverConfig -> AvoidReinstalls
[shadowPkgs] :: SolverConfig -> ShadowPkgs
[strongFlags] :: SolverConfig -> StrongFlags
[allowBootLibInstalls] :: SolverConfig -> AllowBootLibInstalls
[onlyConstrained] :: SolverConfig -> OnlyConstrained
[maxBackjumps] :: SolverConfig -> Maybe Int
[enableBackjumping] :: SolverConfig -> EnableBackjumping
[solveExecutables] :: SolverConfig -> SolveExecutables
[goalOrder] :: SolverConfig -> Maybe (Variable QPN -> Variable QPN -> Ordering)
[solverVerbosity] :: SolverConfig -> Verbosity
[pruneAfterFirstSuccess] :: SolverConfig -> PruneAfterFirstSuccess

-- | Whether to remove all choices after the first successful choice at
--   each level in the search tree.
newtype PruneAfterFirstSuccess
PruneAfterFirstSuccess :: Bool -> PruneAfterFirstSuccess
