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

-- | Various small helper functions for Lists, Maybes, Tuples, Functions
--   
--   Various small helper functions for Lists, Maybes, Tuples, Functions.
--   Some of these functions are improved implementations of standard
--   functions. They have the same name as their standard counterparts.
--   Others are equivalent to functions from the base package, but
--   if you import them from this utility package then you can write code
--   that runs on older GHC versions or other compilers like Hugs and JHC.
--   
--   All modules are plain Haskell 98. The package depends exclusively on
--   the base package and only that portions of base that
--   are simple to port. Thus you do not risk a dependency avalanche by
--   importing it. However, further splitting the base package might
--   invalidate this statement.
--   
--   Alternative packages: Useful, MissingH
@package utility-ht
@version 0.0.17.2

module Control.Monad.HT

-- | Also present in newer versions of the base package.
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
infixr 1 <=<

-- | Monadic repeat.
repeat :: Monad m => m a -> m [a]
nest :: Monad m => Int -> (a -> m a) -> a -> m a

-- | repeat action until result fulfills condition

-- | Deprecated: use M.until
untilM :: Monad m => (a -> Bool) -> m a -> m a

-- | repeat action until result fulfills condition
until :: Monad m => (a -> Bool) -> m a -> m a

-- | parameter order equal to that of nest

-- | Deprecated: use M.iterateLimit
iterateLimitM :: Monad m => Int -> (a -> m a) -> a -> m [a]

-- | parameter order equal to that of nest
iterateLimit :: Monad m => Int -> (a -> m a) -> a -> m [a]

-- | I think this makes only sense in a lazy monad like
--   Trans.State.Lazy or IO.Lazy.
iterate :: Monad m => (a -> m a) -> a -> m [a]

-- | Lazy monadic conjunction. That is, when the first action returns
--   False, then False is immediately returned, without
--   running the second action.
andLazy :: Monad m => m Bool -> m Bool -> m Bool

-- | Lazy monadic disjunction. That is, when the first action returns
--   True, then True is immediately returned, without
--   running the second action.
orLazy :: Monad m => m Bool -> m Bool -> m Bool
void :: Monad m => m a -> m ()
for :: Monad m => [a] -> (a -> m b) -> m [b]
map :: Monad m => (a -> m b) -> [a] -> m [b]
zipWith :: Monad m => (a -> b -> m c) -> [a] -> [b] -> m [c]
chain :: Monad m => [a -> m a] -> a -> m a
filter :: Monad m => (a -> m Bool) -> [a] -> m [a]
replicate :: Monad m => Int -> m a -> m [a]
lift :: Monad m => (a -> r) -> m a -> m r
lift2 :: Monad m => (a -> b -> r) -> m a -> m b -> m r
lift3 :: Monad m => (a -> b -> c -> r) -> m a -> m b -> m c -> m r
lift4 :: Monad m => (a -> b -> c -> d -> r) -> m a -> m b -> m c -> m d -> m r
lift5 :: Monad m => (a -> b -> c -> d -> e -> r) -> m a -> m b -> m c -> m d -> m e -> m r
liftJoin2 :: Monad m => (a -> b -> m c) -> m a -> m b -> m c
liftJoin3 :: Monad m => (a -> b -> c -> m d) -> m a -> m b -> m c -> m d
liftJoin4 :: Monad m => (a -> b -> c -> d -> m e) -> m a -> m b -> m c -> m d -> m e
liftJoin5 :: Monad m => (a -> b -> c -> d -> e -> m f) -> m a -> m b -> m c -> m d -> m e -> m f

module Data.Bits.HT

-- | Infix variant of shiftL. Precedence is chosen like
--   multiplication since a .<<. k == a * 2^k.
(.<<.) :: Bits a => a -> Int -> a
infixl 7 .<<.

-- | Infix variant of shiftR. Precedence is chosen like division
--   since a .>>. k == a / 2^k.
(.>>.) :: Bits a => a -> Int -> a
infixl 7 .>>.

module Data.Bool.HT

-- | if-then-else as function.
--   
--   Example:
--   
--   
--   if' (even n) "even" $
--   if' (isPrime n) "prime" $
--   "boring"
--   
if' :: Bool -> a -> a -> a

-- | The same as if', but the name is chosen such that it can be
--   used for GHC-7.0's rebindable if-then-else syntax.
ifThenElse :: Bool -> a -> a -> a

-- | From a list of expressions choose the one, whose condition is true.
--   
--   Example:
--   
--   
--   select "boring" $
--     (even n, "even") :
--     (isPrime n, "prime") :
--     []
--   
select :: a -> [(Bool, a)] -> a

-- | Like the ? operator of the C progamming language.
--   
--   
--   >>> True ?: ("yes", "no")
--   "yes"
--   
--   >>> False ?: ("yes", "no")
--   "no"
--   
(?:) :: Bool -> (a, a) -> a
infixr 1 ?:

-- | Logical operator for implication.
--   
--   Funnily because of the ordering of Bool it holds:
--   
--   
--   \a b -> implies a b == (a<=b)
--   
implies :: Bool -> Bool -> Bool
infixr 1 `implies`

module Data.Either.HT
mapLeft :: (a -> b) -> Either a c -> Either b c
mapRight :: (b -> c) -> Either a b -> Either a c
mapBoth :: (a -> c) -> (b -> d) -> Either a b -> Either c d
maybeLeft :: Either a b -> Maybe a
maybeRight :: Either a b -> Maybe b
swap :: Either a b -> Either b a

-- | Implementations of Ix methods in terms of Enum
--   methods.
--   
--   For a type T of class Enum you can easily define an
--   Ix instance by copying the following code into your module:
--   
--   
--   import qualified Data.Ix.Enum as IxEnum
--   
--   instance Ix T where
--      range           = IxEnum.range
--      index           = IxEnum.index
--      inRange         = IxEnum.inRange
--      rangeSize       = IxEnum.rangeSize
--      unsafeIndex     = IxEnum.unsafeIndex
--      unsafeRangeSize = IxEnum.unsafeRangeSize
--   
module Data.Ix.Enum

-- | 
--   >>> range ('x','z')
--   "xyz"
--   
--   >>> range (LT,GT)
--   [LT,EQ,GT]
--   
range :: Enum a => (a, a) -> [a]

-- | 
--   >>> index ('a','z') 'e'
--   4
--   
index :: Enum a => (a, a) -> a -> Int

-- | 
--   >>> unsafeIndex ('a','z') 'e'
--   4
--   
unsafeIndex :: Enum a => (a, a) -> a -> Int

-- | 
--   >>> inRange ('a','z') 'e'
--   True
--   
--   >>> inRange ('x','z') 'a'
--   False
--   
inRange :: Enum a => (a, a) -> a -> Bool

-- | 
--   >>> rangeSize ('x','z')
--   3
--   
rangeSize :: Enum a => (a, a) -> Int

-- | 
--   >>> unsafeRangeSize ('x','z')
--   3
--   
unsafeRangeSize :: Enum a => (a, a) -> Int

module Data.Maybe.HT

-- | Returns Just if the precondition is fulfilled. prop> b x
--   -> (guard b >> x) == (toMaybe b =<< (x::Maybe Char))
toMaybe :: Bool -> a -> Maybe a

-- | This is an infix version of fmap for writing select
--   style expressions using test functions, that produce Maybes.
--   
--   The precedence is chosen to be higher than (:), in order to
--   allow:
--   
--   
--   alternatives default $
--      checkForA ?-> (\a -> f a) :
--      checkForB ?-> (\b -> g b) :
--      []
--   
--   
--   The operation is left associative in order to allow to write
--   
--   
--   checkForA ?-> f ?-> g
--   
--   
--   which is equivalent to
--   
--   
--   checkForA ?-> g . f
--   
--   
--   due to the functor law.
(?->) :: Maybe a -> (a -> b) -> Maybe b
infixl 6 ?->
alternatives :: a -> [Maybe a] -> a

module Data.Monoid.HT

-- | Generalization of cycle to any monoid.
cycle :: Monoid m => m -> m

-- | Infix synonym for mappend.
(<>) :: Monoid m => m -> m -> m
infixr 6 <>

-- | 
--   \b m -> when b m == mfilter (const b) (m::Maybe Ordering)
--   
--   
--   
--   \b m -> when b m == mfilter (const b) (m::String)
--   
when :: Monoid m => Bool -> m -> m

-- | 
--   QC.forAll (QC.choose (0,20)) $ \k xs -> power (fromIntegral k) xs == mconcat (replicate k (xs::String))
--   
--   
--   In contrast to powerAssociative the power function
--   uses mempty only for the zeroth power.
--   
--   
--   QC.forAll (QC.choose (0,20)) $ \k xs -> power k xs == powerAssociative mappend mempty (xs::String) k
--   
power :: Monoid m => Integer -> m -> m

module Data.Strictness.HT
arguments1 :: (a -> x) -> a -> x
arguments2 :: (a -> b -> x) -> a -> b -> x
arguments3 :: (a -> b -> c -> x) -> a -> b -> c -> x
arguments4 :: (a -> b -> c -> d -> x) -> a -> b -> c -> d -> x
arguments5 :: (a -> b -> c -> d -> e -> x) -> a -> b -> c -> d -> e -> x

module Data.Tuple.Lazy

-- | Cf. (***).
--   
--   Apply two functions on corresponding values in a pair, where the
--   pattern match on the pair constructor is lazy. This is crucial in
--   recursions such as the one of partition. One the other hand
--   there are applications where strict application is crucial, e.g.
--   mapSnd f ab where the left pair member is a large lazy list.
--   With the lazy mapSnd we make the application of f
--   depend on the whole pair ab. See Data.Tuple.Example
--   for two examples where one variant is definitely better than the other
--   one.
mapPair :: (a -> c, b -> d) -> (a, b) -> (c, d)

-- | first
mapFst :: (a -> c) -> (a, b) -> (c, b)

-- | second
mapSnd :: (b -> c) -> (a, b) -> (a, c)
zipPair :: (a, b) -> (c, d) -> ((a, c), (b, d))
zipWithPair :: (a -> c -> e, b -> d -> f) -> (a, b) -> (c, d) -> (e, f)
swap :: (a, b) -> (b, a)
forcePair :: (a, b) -> (a, b)
mapTriple :: (a -> d, b -> e, c -> f) -> (a, b, c) -> (d, e, f)
mapFst3 :: (a -> d) -> (a, b, c) -> (d, b, c)
mapSnd3 :: (b -> d) -> (a, b, c) -> (a, d, c)
mapThd3 :: (c -> d) -> (a, b, c) -> (a, b, d)
zipWithTriple :: (a -> d -> g, b -> e -> h, c -> f -> i) -> (a, b, c) -> (d, e, f) -> (g, h, i)
uncurry3 :: (a -> b -> c -> d) -> (a, b, c) -> d

module Data.Tuple.HT

-- | Cf. (***).
--   
--   Apply two functions on corresponding values in a pair, where the
--   pattern match on the pair constructor is lazy. This is crucial in
--   recursions such as the one of partition. One the other hand
--   there are applications where strict application is crucial, e.g.
--   mapSnd f ab where the left pair member is a large lazy list.
--   With the lazy mapSnd we make the application of f
--   depend on the whole pair ab. See Data.Tuple.Example
--   for two examples where one variant is definitely better than the other
--   one.
mapPair :: (a -> c, b -> d) -> (a, b) -> (c, d)

-- | first
mapFst :: (a -> c) -> (a, b) -> (c, b)

-- | second
mapSnd :: (b -> c) -> (a, b) -> (a, c)
swap :: (a, b) -> (b, a)

-- | This is convenient for quick hacks but I suggest that you better
--   define a type for an ordered pair for your application at hand. This
--   way, you can clearly see from the type that a pair is ordered.
sortPair :: Ord a => (a, a) -> (a, a)
forcePair :: (a, b) -> (a, b)

-- | Known as dup in the Arrow literature.
double :: a -> (a, a)
fst3 :: (a, b, c) -> a
snd3 :: (a, b, c) -> b
thd3 :: (a, b, c) -> c
mapTriple :: (a -> d, b -> e, c -> f) -> (a, b, c) -> (d, e, f)
mapFst3 :: (a -> d) -> (a, b, c) -> (d, b, c)
mapSnd3 :: (b -> d) -> (a, b, c) -> (a, d, c)
mapThd3 :: (c -> d) -> (a, b, c) -> (a, b, d)
curry3 :: ((a, b, c) -> d) -> a -> b -> c -> d
uncurry3 :: (a -> b -> c -> d) -> (a, b, c) -> d
triple :: a -> (a, a, a)

-- | The functions in this module process the list from the end. They do
--   not access elements at the beginning if not necessary. You can apply
--   the function only to finite lists. Use these functions if the list is
--   short and the test is expensive.
module Data.List.Reverse.StrictSpine

-- | 
--   forAllPredicates $ \p xs -> Rev.dropWhile p xs == reverse (List.dropWhile p (reverse xs))
--   
--   
--   
--   \x xs pad -> defined $ length $ Rev.dropWhile ((x::Char)/=) $ Match.replicate (pad::[()]) undefined ++ x:xs
--   
dropWhile :: (a -> Bool) -> [a] -> [a]

-- | 
--   forAllPredicates $ \p xs -> Rev.takeWhile p xs == reverse (List.takeWhile p (reverse xs))
--   
--   
--   
--   \x xs pad -> defined $ Rev.takeWhile ((x::Char)/=) $ Match.replicate (pad::[()]) undefined ++ x:xs
--   
takeWhile :: (a -> Bool) -> [a] -> [a]

-- | 
--   forAllPredicates $ \p xs -> Rev.span p xs == swap (mapPair (reverse, reverse) (List.span p (reverse xs)))
--   
--   
--   
--   forAllPredicates $ \p xs -> Rev.span p xs == (Rev.dropWhile p xs, Rev.takeWhile p xs)
--   
--   
--   
--   \x xs pad -> defined $ mapFst length $ Rev.span ((x::Char)/=) $ Match.replicate (pad::[()]) undefined ++ x:xs
--   
span :: (a -> Bool) -> [a] -> ([a], [a])

module Data.String.HT

-- | Remove leading and trailing spaces.
--   
--   We use spine strict dropWhile instead of the element strict
--   version. This is more efficient for finite Strings because
--   isSpace is expensive. The downside is that trim does not
--   work for infinite Strings.
trim :: String -> String

-- | The functions in this module process the list formally from the end.
--   Actually they traverse the list from the start and check every
--   element. This way they are strict in the elements and lazy in the list
--   spline. Thus you can apply them to infinite lists. Use these functions
--   if the list is long or the test is cheap.
module Data.List.Reverse.StrictElement

-- | Remove the longest suffix of elements satisfying p. In contrast to
--   reverse . dropWhile p . reverse this works for infinite
--   lists, too.
--   
--   
--   forAllPredicates $ \p xs -> Rev.dropWhile p xs == reverse (List.dropWhile p (reverse xs))
--   
--   
--   
--   \x xs pad -> defined $ Match.take (pad::[()]) $ Rev.dropWhile ((x::Char)/=) $ cycle $ x:xs
--   
dropWhile :: (a -> Bool) -> [a] -> [a]

-- | Alternative version of reverse . takeWhile p . reverse.
--   
--   
--   forAllPredicates $ \p xs -> Rev.takeWhile p xs == reverse (List.takeWhile p (reverse xs))
--   
takeWhile :: (a -> Bool) -> [a] -> [a]

-- | 
--   forAllPredicates $ \p xs -> Rev.span p xs == swap (mapPair (reverse, reverse) (List.span p (reverse xs)))
--   
--   
--   
--   forAllPredicates $ \p xs -> Rev.span p xs == (Rev.dropWhile p xs, Rev.takeWhile p xs)
--   
--   
--   
--   \x xs pad -> defined $ Match.take (pad::[()]) $ fst $ Rev.span ((x::Char)/=) $ cycle $ x:xs
--   
span :: (a -> Bool) -> [a] -> ([a], [a])

module Data.Function.HT

-- | Useful for adding type annotations like in
--   
--   
--   f . (id :: Id Char) . g
--   
type Id a = a -> a

-- | Compositional power of a function, i.e. apply the function n
--   times to a value. It is rather the same as iter in Simon
--   Thompson: "The Craft of Functional Programming", page 172
nest :: Int -> (a -> a) -> a -> a

-- | powerAssociative is an auxiliary function that, for an
--   associative operation op, computes the same value as
--   
--   
--   powerAssociative op a0 a n = foldr op a0 (genericReplicate n a)
--   
--   
--   but applies "op" O(log n) times and works for large n.
powerAssociative :: (a -> a -> a) -> a -> a -> Integer -> a

-- | Known as on in newer versions of the base package.
compose2 :: (b -> b -> c) -> (a -> b) -> a -> a -> c

module Data.Ord.HT
comparing :: Ord b => (a -> b) -> a -> a -> Ordering

-- | limit (lower,upper) x restricts x to the range from
--   lower to upper. Don't expect a sensible result for
--   lower>upper.
--   
--   Called clamp elsewhere.
limit :: Ord a => (a, a) -> a -> a

-- | limit (lower,upper) x checks whether x is in the
--   range from lower to upper. Don't expect a sensible
--   result for lower>upper.
inRange :: Ord a => (a, a) -> a -> Bool

-- | Variant of Data.List functions like group, sort
--   where the comparison is performed on a key computed from the list
--   elements. In principle these functions could be replaced by e.g.
--   sortBy (compare on f), but f will be
--   re-computed for every comparison. If the evaluation of f is
--   expensive, our functions are better, since they buffer the results of
--   f.
module Data.List.Key
nub :: Eq b => (a -> b) -> [a] -> [a]
sort :: Ord b => (a -> b) -> [a] -> [a]

-- | argmin
minimum :: Ord b => (a -> b) -> [a] -> a

-- | argmax
maximum :: Ord b => (a -> b) -> [a] -> a

-- | Divides a list into sublists such that the members in a sublist share
--   the same key. It uses semantics of groupBy, not that of
--   groupBy.
group :: Eq b => (a -> b) -> [a] -> [[a]]
merge :: Ord b => (a -> b) -> [a] -> [a] -> [a]

module Data.Eq.HT
equating :: Eq b => (a -> b) -> a -> a -> Bool

module Control.Functor.HT
void :: Functor f => f a -> f ()
map :: Functor f => (a -> b) -> f a -> f b
for :: Functor f => f a -> (a -> b) -> f b

-- | Caution: Every pair member has a reference to the argument of
--   unzip. Depending on the consumption pattern this may cause a
--   memory leak. For lists, I think, you should generally prefer
--   unzip.
unzip :: Functor f => f (a, b) -> (f a, f b)

-- | Caution: See unzip.
unzip3 :: Functor f => f (a, b, c) -> (f a, f b, f c)

-- | Caution: See unzip.
uncurry :: Functor f => (f a -> f b -> g) -> f (a, b) -> g

-- | Caution: See unzip.
uncurry3 :: Functor f => (f a -> f b -> f c -> g) -> f (a, b, c) -> g
mapFst :: Functor f => (a -> f c) -> (a, b) -> f (c, b)
mapSnd :: Functor f => (b -> f c) -> (a, b) -> f (a, c)
mapFst3 :: Functor f => (a -> f d) -> (a, b, c) -> f (d, b, c)
mapSnd3 :: Functor f => (b -> f d) -> (a, b, c) -> f (a, d, c)
mapThd3 :: Functor f => (c -> f d) -> (a, b, c) -> f (a, b, d)

-- | Generalization of outerProduct.
outerProduct :: (Functor f, Functor g) => (a -> b -> c) -> f a -> g b -> f (g c)

module Data.List.Match

-- | Make a list as long as another one
--   
--   
--   \(Shape xs) (List ys) -> Match.take xs ys == List.take (length xs) ys
--   
take :: [b] -> [a] -> [a]

-- | Drop as many elements as the first list is long
--   
--   
--   \(Shape xs) (List ys) -> Match.drop xs ys == List.drop (length xs) ys
--   
--   
--   
--   \(Shape xs) (List ys) -> Match.take xs ys ++ Match.drop xs ys == ys
--   
drop :: [b] -> [a] -> [a]

-- | 
--   \(Shape xs) (List ys) -> Match.splitAt xs ys == (Match.take xs ys, Match.drop xs ys)
--   
--   
--   
--   \(Shape xs) (List ys) -> Match.splitAt xs ys == List.splitAt (length xs) ys
--   
splitAt :: [b] -> [a] -> ([a], [a])

-- | 
--   \(Shape xs) (List ys) -> Match.takeRev xs ys == reverse (Match.take xs (reverse ys))
--   
takeRev :: [b] -> [a] -> [a]

-- | 
--   \(Shape xs) (List ys) -> Match.dropRev xs ys == reverse (Match.drop xs (reverse ys))
--   
dropRev :: [b] -> [a] -> [a]

-- | Specialisation of $>.
replicate :: [a] -> b -> [b]

-- | Check whether two lists with different element types have equal
--   length. It holds
--   
--   
--   \(Shape xs) (List ys) -> equalLength xs ys == (length xs == length ys)
--   
--   
--   but equalLength is more efficient.
equalLength :: [a] -> [b] -> Bool

-- | Compare the length of two lists over different types. It holds
--   
--   
--   \(Shape xs) (List ys) -> compareLength xs ys == compare (length xs) (length ys)
--   
--   
--   but compareLength is more efficient.
compareLength :: [a] -> [b] -> Ordering

-- | lessOrEqualLength x y is almost the same as compareLength
--   x y <= EQ, but
--   
--   
--   >>> lessOrEqualLength "" undefined
--   True
--   
--   
--   whereas compareLength [] undefined <= EQ = undefined.
lessOrEqualLength :: [a] -> [b] -> Bool

-- | Returns the shorter one of two lists. It works also for infinite lists
--   as much as possible. E.g.
--   
--   
--   >>> shorterList (shorterList (repeat 'a') (repeat 'b')) "abc"
--   "abc"
--   
--   
--   The trick is, that the skeleton of the resulting list is constructed
--   using zipWith without touching the elements. The contents is
--   then computed (only) if requested.
shorterList :: [a] -> [a] -> [a]

module Data.List.HT

-- | This function is lazier than the one suggested in the Haskell 98
--   report. It is inits undefined = [] : undefined, in contrast
--   to Data.List.inits undefined = undefined.
inits :: [a] -> [[a]]

-- | This function is lazier than the one suggested in the Haskell 98
--   report. It is tails undefined = ([] : undefined) : undefined,
--   in contrast to Data.List.tails undefined = undefined.
tails :: [a] -> [[a]]

-- | This function compares adjacent elements of a list. If two adjacent
--   elements satisfy a relation then they are put into the same sublist.
--   Example:
--   
--   
--   >>> groupBy (<) "abcdebcdef"
--   ["abcde","bcdef"]
--   
--   
--   In contrast to that groupBy compares the head of each sublist
--   with each candidate for this sublist. This yields
--   
--   
--   >>> List.groupBy (<) "abcdebcdef"
--   ["abcdebcdef"]
--   
--   
--   The second b is compared with the leading
--   a. Thus it is put into the same sublist as
--   a.
--   
--   The sublists are never empty. Thus the more precise result type would
--   be [(a,[a])].
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
group :: Eq a => [a] -> [[a]]

-- | Like standard unzip but more lazy. It is Data.List.unzip
--   undefined == undefined, but unzip undefined == (undefined,
--   undefined).
unzip :: [(a, b)] -> ([a], [b])

-- | partition of GHC 6.2.1 fails on infinite lists. But this one
--   does not.
partition :: (a -> Bool) -> [a] -> ([a], [a])

-- | It is Data.List.span f undefined = undefined, whereas
--   span f undefined = (undefined, undefined).
span :: (a -> Bool) -> [a] -> ([a], [a])

-- | It is Data.List.span f undefined = undefined, whereas
--   span f undefined = (undefined, undefined).
break :: (a -> Bool) -> [a] -> ([a], [a])

-- | Split the list at the occurrences of a separator into sub-lists.
--   Remove the separators. This is somehow a generalization of
--   lines and words. But note the differences:
--   
--   
--   >>> words "a  a"
--   ["a","a"]
--   
--   >>> chop (' '==) "a  a"
--   ["a","","a"]
--   
--   
--   
--   >>> lines "a\n\na"
--   ["a","","a"]
--   
--   >>> chop ('\n'==) "a\n\na"
--   ["a","","a"]
--   
--   
--   
--   >>> lines "a\n"
--   ["a"]
--   
--   >>> chop ('\n'==) "a\n"
--   ["a",""]
--   
chop :: (a -> Bool) -> [a] -> [[a]]

-- | Like break, but splits after the matching element.
--   
--   
--   forAllPredicates $ \p xs -> uncurry (++) (breakAfter p xs) == xs
--   
breakAfter :: (a -> Bool) -> [a] -> ([a], [a])

-- | Take all elements until one matches. The matching element is returned,
--   too. This is the key difference to takeWhile (not . p). It
--   holds:
--   
--   
--   forAllPredicates $ \p xs -> takeUntil p xs == fst (breakAfter p xs)
--   
takeUntil :: (a -> Bool) -> [a] -> [a]

-- | Split the list after each occurence of a terminator. Keep the
--   terminator. There is always a list for the part after the last
--   terminator. It may be empty. See package non-empty for more
--   precise result type.
--   
--   
--   forAllPredicates $ \p xs -> concat (segmentAfter p xs) == xs
--   
--   
--   
--   forAllPredicates $ \p xs -> length (filter p xs) == length (tail (segmentAfter p xs))
--   
--   
--   
--   forAllPredicates $ \p -> all (p . last) . init . segmentAfter p
--   
--   
--   
--   forAllPredicates $ \p -> all (all (not . p) . init) . init . segmentAfter p
--   
--   
--   This test captures both infinitely many groups and infinitely big
--   groups:
--   
--   
--   forAllPredicates $ \p x -> flip seq True . (!!100) . concat . segmentAfter p . cycle . (x:)
--   
segmentAfter :: (a -> Bool) -> [a] -> [[a]]

-- | Split the list before each occurence of a leading character. Keep
--   these characters. There is always a list for the part before the first
--   leading character. It may be empty. See package non-empty for
--   more precise result type.
--   
--   
--   >>> segmentBefore isUpper "AbcdXyz"
--   ["","Abcd","Xyz"]
--   
--   >>> segmentBefore isUpper "kAbcdXYZ"
--   ["k","Abcd","X","Y","Z"]
--   
--   
--   
--   forAllPredicates $ \p xs -> concat (segmentBefore p xs) == xs
--   
--   
--   
--   forAllPredicates $ \p xs -> length (filter p xs) == length (tail (segmentBefore p xs))
--   
--   
--   
--   forAllPredicates $ \p -> all (p . head) . tail . segmentBefore p
--   
--   
--   
--   forAllPredicates $ \p -> all (all (not . p) . tail) . tail . segmentBefore p
--   
--   
--   
--   forAllPredicates $ \p x -> flip seq True . (!!100) . concat . segmentBefore p . cycle . (x:)
--   
segmentBefore :: (a -> Bool) -> [a] -> [[a]]

-- | 
--   >>> segmentAfterJust (\c -> toMaybe (isLetter c) (toUpper c)) "123a5345b---"
--   ([("123",'A'),("5345",'B')],"---")
--   
segmentAfterJust :: (a -> Maybe b) -> [a] -> ([([a], b)], [a])

-- | Deprecated: use segmentAfterJust instead
segmentAfterMaybe :: (a -> Maybe b) -> [a] -> ([([a], b)], [a])

-- | 
--   >>> segmentBeforeJust (\c -> toMaybe (isLetter c) (toUpper c)) "123a5345b---"
--   ("123",[('A',"5345"),('B',"---")])
--   
segmentBeforeJust :: (a -> Maybe b) -> [a] -> ([a], [(b, [a])])

-- | Deprecated: use segmentBeforeJust instead
segmentBeforeMaybe :: (a -> Maybe b) -> [a] -> ([a], [(b, [a])])

-- | 
--   >>> segmentAfterRight [Left 'a', Right LT, Right GT, Left 'b']
--   ([("a",LT),("",GT)],"b")
--   
--   
--   
--   forAllMaybeFn $ \f xs -> segmentAfterJust f xs == segmentAfterRight (map (\x -> maybe (Left x) Right (f x)) xs)
--   
segmentAfterRight :: [Either a b] -> ([([a], b)], [a])

-- | 
--   >>> segmentBeforeRight [Left 'a', Right LT, Right GT, Left 'b']
--   ("a",[(LT,""),(GT,"b")])
--   
--   
--   
--   forAllMaybeFn $ \f xs -> segmentBeforeJust f xs == segmentBeforeRight (map (\x -> maybe (Left x) Right (f x)) xs)
--   
segmentBeforeRight :: [Either a b] -> ([a], [(b, [a])])

-- | removeEach xs represents a list of sublists of xs,
--   where each element of xs is removed and the removed element
--   is separated. It seems to be much simpler to achieve with zip xs
--   (map (flip List.delete xs) xs), but the implementation of
--   removeEach does not need the Eq instance and thus can
--   also be used for lists of functions.
--   
--   See also the proposal
--   http://www.haskell.org/pipermail/libraries/2008-February/009270.html
--   
--   
--   >>> removeEach "abc"
--   [('a',"bc"),('b',"ac"),('c',"ab")]
--   
--   >>> removeEach "a"
--   [('a',"")]
--   
--   >>> removeEach ""
--   []
--   
removeEach :: [a] -> [(a, [a])]

-- | 
--   >>> splitEverywhere "abc"
--   [("",'a',"bc"),("a",'b',"c"),("ab",'c',"")]
--   
--   >>> splitEverywhere "a"
--   [("",'a',"")]
--   
--   >>> splitEverywhere ""
--   []
--   
splitEverywhere :: [a] -> [([a], a, [a])]

-- | It holds splitLast xs == (init xs, last xs), but
--   splitLast is more efficient if the last element is accessed
--   after the initial ones, because it avoids memoizing list.
--   
--   
--   \(NonEmpty xs) -> splitLast (xs::String)  ==  (init xs, last xs)
--   

-- | Deprecated: use viewR instead
splitLast :: [a] -> ([a], a)

-- | Should be prefered to head and tail.
viewL :: [a] -> Maybe (a, [a])

-- | Should be prefered to init and last.
--   
--   
--   \xs -> maybe True ((init xs, last xs) == ) (viewR (xs::String))
--   
viewR :: [a] -> Maybe ([a], a)

-- | Should be prefered to head and tail.
switchL :: b -> (a -> [a] -> b) -> [a] -> b

-- | Should be prefered to init and last.
--   
--   
--   \xs -> switchR True (\ixs lxs -> ixs == init xs && lxs == last xs) (xs::String)
--   
switchR :: b -> ([a] -> a -> b) -> [a] -> b

-- | dropRev n is like reverse . drop n . reverse but it
--   is lazy enough to work for infinite lists, too.
--   
--   
--   \n xs -> dropRev n (xs::String) == reverse (drop n (reverse xs))
--   
dropRev :: Int -> [a] -> [a]

-- | takeRev n is like reverse . take n . reverse but it
--   is lazy enough to work for infinite lists, too.
--   
--   
--   \n xs -> takeRev n (xs::String) == reverse (take n (reverse xs))
--   
takeRev :: Int -> [a] -> [a]

-- | splitAtRev n xs == (dropRev n xs, takeRev n xs).
--   
--   
--   \n xs -> splitAtRev n (xs::String) == (dropRev n xs, takeRev n xs)
--   
--   
--   
--   \n xs -> (xs::String) == uncurry (++) (splitAtRev n xs)
--   
splitAtRev :: Int -> [a] -> ([a], [a])

-- | Deprecated: Use dropWhile from Data.List.Reverse.StrictElement or
--   Data.List.Reverse.StrictSpine instead
dropWhileRev :: (a -> Bool) -> [a] -> [a]

-- | Deprecated: Use takeWhile from Data.List.Reverse.StrictElement or
--   Data.List.Reverse.StrictSpine instead
takeWhileRev :: (a -> Bool) -> [a] -> [a]

-- | maybePrefixOf xs ys is Just zs if xs is a
--   prefix of ys, where zs is ys without the
--   prefix xs. Otherwise it is Nothing. It is the same
--   as stripPrefix.
--   
--   
--   >>> maybePrefixOf "abc" "abcdef"
--   Just "def"
--   
--   >>> maybePrefixOf "def" "abcdef"
--   Nothing
--   
maybePrefixOf :: Eq a => [a] -> [a] -> Maybe [a]

-- | 
--   >>> maybeSuffixOf "abc" "abcdef"
--   Nothing
--   
--   >>> maybeSuffixOf "def" "abcdef"
--   Just "abc"
--   
maybeSuffixOf :: Eq a => [a] -> [a] -> Maybe [a]

-- | Partition a list into elements which evaluate to Just or
--   Nothing by f.
--   
--   
--   forAllMaybeFn $ \f xs -> partitionMaybe f xs == (mapMaybe f xs, filter (isNothing . f) xs)
--   
--   
--   
--   forAllPredicates $ \p xs -> partition p xs == partitionMaybe (\x -> toMaybe (p x) x) xs
--   
partitionMaybe :: (a -> Maybe b) -> [a] -> ([b], [a])

-- | This is the cousin of takeWhile analogously to catMaybes
--   being the cousin of filter.
--   
--   
--   >>> takeWhileJust [Just 'a', Just 'b', Nothing, Just 'c']
--   "ab"
--   
--   
--   Example: Keep the heads of sublists until an empty list occurs.
--   
--   
--   >>> takeWhileJust $ map (fmap fst . viewL) ["abc","def","","xyz"]
--   "ad"
--   
--   
--   For consistency with takeWhile, partitionMaybe and
--   dropWhileNothing it should have been:
--   
--   
--   takeWhileJust_ :: (a -> Maybe b) -> a -> [b]
--   
--   
--   However, both variants are interchangeable:
--   
--   
--   takeWhileJust_ f == takeWhileJust . map f
--   takeWhileJust == takeWhileJust_ id
--   
takeWhileJust :: [Maybe a] -> [a]
dropWhileNothing :: (a -> Maybe b) -> [a] -> Maybe (b, [a])

-- | 
--   forAllMaybeFn $ \f xs -> snd (breakJust f xs) == dropWhileNothing f xs
--   
breakJust :: (a -> Maybe b) -> [a] -> ([a], Maybe (b, [a]))
spanJust :: (a -> Maybe b) -> [a] -> ([b], [a])
unzipEithers :: [Either a b] -> ([a], [b])

-- | keep every k-th value from the list
--   
--   
--   >>> sieve 6 ['a'..'z']
--   "agmsy"
--   
sieve :: Int -> [a] -> [a]

-- | 
--   >>> sliceHorizontal 6 ['a'..'z']
--   ["agmsy","bhntz","ciou","djpv","ekqw","flrx"]
--   
--   
--   
--   \(NonEmpty xs) -> QC.forAll (QC.choose (1, length xs)) $ \n -> sliceHorizontal n xs == transpose (sliceVertical n (xs::String))
--   
--   
--   
--   \(NonEmpty xs) -> QC.forAll (QC.choose (1, length xs)) $ \n -> sliceVertical  n xs == transpose (sliceHorizontal n (xs::String))
--   
--   
--   The properties do not hold for empty lists because of:
--   
--   
--   >>> sliceHorizontal 4 ([]::[Int])
--   [[],[],[],[]]
--   
sliceHorizontal :: Int -> [a] -> [[a]]

-- | 
--   >>> sliceVertical 6 ['a'..'z']
--   ["abcdef","ghijkl","mnopqr","stuvwx","yz"]
--   
sliceVertical :: Int -> [a] -> [[a]]
search :: Eq a => [a] -> [a] -> [Int]

-- | 
--   \(NonEmpty xs) ys -> replace xs xs ys == (ys::String)
--   
--   
--   
--   \(NonEmpty xs) (NonEmpty ys) -> equating (take 1000) (replace xs ys (cycle xs)) (cycle (ys::String))
--   
replace :: Eq a => [a] -> [a] -> [a] -> [a]

-- | prop src dst xs -> replace src dst xs == multiReplace
--   (src,dst)
multiReplace :: Eq a => [([a], [a])] -> [a] -> [a]

-- | Transform
--   
--   
--   [[00,01,02,...],          [[00],
--    [10,11,12,...],   -->     [10,01],
--    [20,21,22,...],           [20,11,02],
--    ...]                      ...]
--   
--   
--   With concat . shear you can perform a Cantor diagonalization,
--   that is an enumeration of all elements of the sub-lists where each
--   element is reachable within a finite number of steps. It is also
--   useful for polynomial multiplication (convolution).
shear :: [[a]] -> [[a]]

-- | Transform
--   
--   
--   [[00,01,02,...],          [[00],
--    [10,11,12,...],   -->     [01,10],
--    [20,21,22,...],           [02,11,20],
--    ...]                      ...]
--   
--   
--   It's like shear but the order of elements in the sub list is
--   reversed. Its implementation seems to be more efficient than that of
--   shear. If the order does not matter, better choose
--   shearTranspose.
--   
--   
--   \xs -> shearTranspose xs  ==  map reverse (shear (xs::[String]))
--   
shearTranspose :: [[a]] -> [[a]]

-- | Operate on each combination of elements of the first and the second
--   list. In contrast to the list instance of liftM2 it holds the
--   results in a list of lists.
--   
--   
--   \xs ys -> let f x y = (x::Char,y::Int) in concat (outerProduct f xs ys)  ==  liftM2 f xs ys
--   
outerProduct :: (a -> b -> c) -> [a] -> [b] -> [[c]]

-- | Take while first predicate holds, then continue taking while second
--   predicate holds, and so on.
takeWhileMulti :: [a -> Bool] -> [a] -> [a]

-- | rotate left
rotate :: Int -> [a] -> [a]

-- | Given two lists that are ordered (i.e. p x y holds for
--   subsequent x and y) mergeBy them into a list
--   that is ordered, again.
--   
--   
--   >>> mergeBy (<=) "agh" "begz"
--   "abegghz"
--   
mergeBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]

-- | 
--   >>> allEqual "aab"
--   False
--   
--   >>> allEqual "aaa"
--   True
--   
--   >>> allEqual "aa"
--   True
--   
--   >>> allEqual "a"
--   True
--   
--   >>> allEqual ""
--   True
--   
allEqual :: Eq a => [a] -> Bool

-- | 
--   >>> isAscending "abc"
--   True
--   
--   >>> isAscending "abb"
--   True
--   
--   >>> isAscending "aba"
--   False
--   
--   >>> isAscending "cba"
--   False
--   
--   >>> isAscending "a"
--   True
--   
--   >>> isAscending ""
--   True
--   
isAscending :: Ord a => [a] -> Bool
isAscendingLazy :: Ord a => [a] -> [Bool]

-- | This function combines every pair of neighbour elements in a list with
--   a certain function.
--   
--   
--   >>> mapAdjacent (<=) ""
--   []
--   
--   >>> mapAdjacent (<=) "a"
--   []
--   
--   >>> mapAdjacent (<=) "aba"
--   [True,False]
--   
--   >>> mapAdjacent (,) "abc"
--   [('a','b'),('b','c')]
--   
--   
--   
--   \x xs -> mapAdjacent subtract (scanl (+) x xs) == (xs::[Integer])
--   
mapAdjacent :: (a -> a -> b) -> [a] -> [b]

-- | 
--   >>> let f x y z = [x,y]++show(z::Int) in mapAdjacent1 f 'a' [('b',1), ('c',2), ('d',3)]
--   ["ab1","bc2","cd3"]
--   
mapAdjacent1 :: (a -> a -> b -> c) -> a -> [(a, b)] -> [c]

-- | 
--   >>> equalWith (<=) "ab" "bb"
--   True
--   
--   >>> equalWith (<=) "aa" "bbb"
--   False
--   
--   >>> equalWith (==) "aa" "aaa"
--   False
--   
--   
--   
--   \as bs -> let f a b = abs (a-b) <= (10::Int) in equalWith f as bs ==  equalWithRec f as bs
--   
--   
--   
--   \as bs -> let f a b = abs (a-b) <= (10::Int) in equalWith f as bs ==  equalWithLiftM f as bs
--   
equalWith :: (a -> b -> Bool) -> [a] -> [b] -> Bool

-- | Enumerate without Enum context. For Enum equivalent to enumFrom.
--   
--   
--   >>> range 0 :: [Integer]
--   []
--   
--   >>> range 1 :: [Integer]
--   [0]
--   
--   >>> range 8 :: [Integer]
--   [0,1,2,3,4,5,6,7]
--   
--   
--   
--   \(NonNegative n) -> length (range n :: [Integer]) == n
--   
range :: Num a => Int -> [a]
padLeft :: a -> Int -> [a] -> [a]
padRight :: a -> Int -> [a] -> [a]

-- | For an associative operation op this computes
--   iterateAssociative op a = iterate (op a) a but it is even
--   faster than map (powerAssociative op a a) [0..] since it
--   shares temporary results.
--   
--   The idea is: From the list map (powerAssociative op a a)
--   [0,(2*n)..] we compute the list map (powerAssociative op a a)
--   [0,n..], and iterate that until n==1.
--   
--   
--   \x -> equating (take 1000) (List.iterate (x+) x) (iterateAssociative (+) (x::Integer))
--   
iterateAssociative :: (a -> a -> a) -> a -> [a]

-- | This is equal to iterateAssociative. The idea is the following:
--   The list we search is the fixpoint of the function: "Square all
--   elements of the list, then spread it and fill the holes with
--   successive numbers of their left neighbour." This also preserves log n
--   applications per value. However it has a space leak, because for the
--   value with index n all elements starting at div n 2
--   must be kept.
--   
--   
--   \x -> equating (take 1000) (List.iterate (x+) x) (iterateLeaky (+) (x::Integer))
--   
iterateLeaky :: (a -> a -> a) -> a -> [a]

-- | 
--   >>> lengthAtLeast 0 ""
--   True
--   
--   >>> lengthAtLeast 3 "ab"
--   False
--   
--   >>> lengthAtLeast 3 "abc"
--   True
--   
--   >>> lengthAtLeast 3 $ repeat 'a'
--   True
--   
--   >>> lengthAtLeast 3 $ "abc" ++ undefined
--   True
--   
--   
--   
--   \n xs -> lengthAtLeast n (xs::String)  ==  (length xs >= n)
--   
lengthAtLeast :: Int -> [a] -> Bool

-- | 
--   >>> lengthAtMost 0 ""
--   True
--   
--   >>> lengthAtMost 3 "ab"
--   True
--   
--   >>> lengthAtMost 3 "abc"
--   True
--   
--   >>> lengthAtMost 3 "abcd"
--   False
--   
--   >>> lengthAtMost 3 $ repeat 'a'
--   False
--   
--   >>> lengthAtMost 3 $ "abcd" ++ undefined
--   False
--   
--   
--   
--   \n xs -> lengthAtMost n (xs::String)  ==  (length xs <= n)
--   
lengthAtMost :: Int -> [a] -> Bool

module Data.Record.HT

-- | Lexicographically compare a list of attributes of two records.
--   
--   Example:
--   
--   
--   compare [comparing fst, comparing snd]
--   
compare :: [a -> a -> Ordering] -> a -> a -> Ordering

-- | Check whether a selected set of fields of two records is equal.
--   
--   Example:
--   
--   
--   equal [equating fst, equating snd]
--   
equal :: [a -> a -> Bool] -> a -> a -> Bool

module Control.Applicative.HT
mapPair :: Applicative f => (a -> f c, b -> f d) -> (a, b) -> f (c, d)
mapTriple :: Applicative m => (a -> m d, b -> m e, c -> m f) -> (a, b, c) -> m (d, e, f)
curry :: Applicative f => (f (a, b) -> g) -> f a -> f b -> g
curry3 :: Applicative f => (f (a, b, c) -> g) -> f a -> f b -> f c -> g
lift :: Applicative m => (a -> r) -> m a -> m r
lift2 :: Applicative m => (a -> b -> r) -> m a -> m b -> m r
lift3 :: Applicative m => (a -> b -> c -> r) -> m a -> m b -> m c -> m r
lift4 :: Applicative m => (a -> b -> c -> d -> r) -> m a -> m b -> m c -> m d -> m r
lift5 :: Applicative m => (a -> b -> c -> d -> e -> r) -> m a -> m b -> m c -> m d -> m e -> m r
lift6 :: Applicative m => (a -> b -> c -> d -> e -> f -> r) -> m a -> m b -> m c -> m d -> m e -> m f -> m r

-- | Deprecated: use App.lift4
liftA4 :: Applicative f => (a -> b -> c -> d -> e) -> f a -> f b -> f c -> f d -> f e

-- | Deprecated: use App.lift5
liftA5 :: Applicative f => (a -> b -> c -> d -> e -> g) -> f a -> f b -> f c -> f d -> f e -> f g

-- | Deprecated: use App.lift6
liftA6 :: Applicative f => (a -> b -> c -> d -> e -> g -> h) -> f a -> f b -> f c -> f d -> f e -> f g -> f h

module Data.Tuple.Strict
mapPair :: (a -> c, b -> d) -> (a, b) -> (c, d)
mapFst :: (a -> c) -> (a, b) -> (c, b)
mapSnd :: (b -> c) -> (a, b) -> (a, c)
zipPair :: (a, b) -> (c, d) -> ((a, c), (b, d))
zipWithPair :: (a -> c -> e, b -> d -> f) -> (a, b) -> (c, d) -> (e, f)
swap :: (a, b) -> (b, a)
mapTriple :: (a -> d, b -> e, c -> f) -> (a, b, c) -> (d, e, f)
mapFst3 :: (a -> d) -> (a, b, c) -> (d, b, c)
mapSnd3 :: (b -> d) -> (a, b, c) -> (a, d, c)
mapThd3 :: (c -> d) -> (a, b, c) -> (a, b, d)
zipWithTriple :: (a -> d -> g, b -> e -> h, c -> f -> i) -> (a, b, c) -> (d, e, f) -> (g, h, i)
uncurry3 :: (a -> b -> c -> d) -> (a, b, c) -> d

module Text.Read.HT

-- | Parse a string containing an infix operator.
readsInfixPrec :: (Read a, Read b) => String -> Int -> Int -> (a -> b -> c) -> ReadS c

-- | Compose two parsers sequentially.
(.>) :: ReadS (b -> c) -> ReadS b -> ReadS c
infixl 9 .>
readMany :: Read a => String -> [a]
maybeRead :: Read a => String -> Maybe a

module Text.Show.HT

-- | Show a value using an infix operator.
showsInfixPrec :: (Show a, Show b) => String -> Int -> Int -> a -> b -> ShowS
concatS :: [ShowS] -> ShowS
