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


-- | Fast generic linear-time sorting, joins and container construction.
--   
--   This package provides fast, generic, linear-time discrimination and
--   sorting.
--   
--   The techniques applied are based on <a>multiple</a> <a>papers</a> and
--   <a>talks</a> by <a>Fritz Henglein</a>.
@package discrimination
@version 0.3


-- | Small primitive boxed arrays
module Data.Discrimination.Internal.SmallArray

-- | Boxed arrays
data SmallArray a
SmallArray :: (SmallArray# a) -> SmallArray a

-- | Mutable boxed arrays associated with a primitive state token.
data SmallMutableArray s a
SmallMutableArray :: (SmallMutableArray# s a) -> SmallMutableArray s a

-- | Create a new mutable array of the specified size and initialise all
--   elements with the given value.
newSmallArray :: PrimMonad m => Int -> a -> m (SmallMutableArray (PrimState m) a)

-- | Read a value from the array at the given index.
readSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> m a

-- | Write a value to the array at the given index.
writeSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> a -> m ()

-- | Read a value from the immutable array at the given index.
indexSmallArray :: SmallArray a -> Int -> a

-- | Monadically read a value from the immutable array at the given index.
--   This allows us to be strict in the array while remaining lazy in the
--   read element which is very useful for collective operations. Suppose
--   we want to copy an array. We could do something like this:
--   
--   <pre>
--   copy marr arr ... = do ...
--                          writeSmallArray marr i (indexSmallArray arr i) ...
--                          ...
--   </pre>
--   
--   But since primitive arrays are lazy, the calls to
--   <a>indexSmallArray</a> will not be evaluated. Rather, <tt>marr</tt>
--   will be filled with thunks each of which would retain a reference to
--   <tt>arr</tt>. This is definitely not what we want!
--   
--   With <a>indexSmallArrayM</a>, we can instead write
--   
--   <pre>
--   copy marr arr ... = do ...
--                          x &lt;- indexSmallArrayM arr i
--                          writeSmallArray marr i x
--                          ...
--   </pre>
--   
--   Now, indexing is executed immediately although the returned element is
--   still not evaluated.
indexSmallArrayM :: Monad m => SmallArray a -> Int -> m a

-- | Convert a mutable array to an immutable one without copying. The array
--   should not be modified after the conversion.
unsafeFreezeSmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> m (SmallArray a)

-- | Convert an immutable array to an mutable one without copying. The
--   immutable array should not be used after the conversion.
unsafeThawSmallArray :: PrimMonad m => SmallArray a -> m (SmallMutableArray (PrimState m) a)

-- | Check whether the two arrays refer to the same memory block.
sameSmallMutableArray :: SmallMutableArray s a -> SmallMutableArray s a -> Bool

-- | Copy a slice of an immutable array to a mutable array.
copySmallArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> SmallArray a -> Int -> Int -> m ()

-- | Copy a slice of a mutable array to another array. The two arrays may
--   not be the same.
copySmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> SmallMutableArray (PrimState m) a -> Int -> Int -> m ()

-- | Return a newly allocated SmallArray with the specified subrange of the
--   provided SmallArray. The provided SmallArray should contain the full
--   subrange specified by the two Ints, but this is not checked.
cloneSmallArray :: SmallArray a -> Int -> Int -> SmallArray a

-- | Return a newly allocated SmallMutableArray. with the specified
--   subrange of the provided SmallMutableArray. The provided
--   SmallMutableArray should contain the full subrange specified by the
--   two Ints, but this is not checked.
cloneSmallMutableArray :: PrimMonad m => SmallMutableArray (PrimState m) a -> Int -> Int -> m (SmallMutableArray (PrimState m) a)
instance GHC.Exts.IsList (Data.Discrimination.Internal.SmallArray.SmallArray a)
instance GHC.Base.Functor Data.Discrimination.Internal.SmallArray.SmallArray
instance Data.Foldable.Foldable Data.Discrimination.Internal.SmallArray.SmallArray
instance Data.Traversable.Traversable Data.Discrimination.Internal.SmallArray.SmallArray
instance GHC.Show.Show a => GHC.Show.Show (Data.Discrimination.Internal.SmallArray.SmallArray a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Discrimination.Internal.SmallArray.SmallArray a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Discrimination.Internal.SmallArray.SmallArray a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Discrimination.Internal.SmallArray.SmallArray a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Discrimination.Internal.SmallArray.SmallArray a)


-- | This module suppose a Word64-based array-mapped PATRICIA Trie.
--   
--   The most significant nybble is isolated by using techniques based on
--   <a>https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-4</a>
--   but modified to work nybble-by-nybble rather than bit-by-bit.
module Data.Discrimination.Internal.WordMap
data WordMap v

-- | Build a singleton WordMap
singleton :: Key -> v -> WordMap v
empty :: WordMap a
insert :: Key -> v -> WordMap v -> WordMap v
lookup :: Key -> WordMap v -> Maybe v
member :: Key -> WordMap v -> Bool
fromList :: [(Word64, v)] -> WordMap v
instance GHC.Show.Show v => GHC.Show.Show (Data.Discrimination.Internal.WordMap.WordMap v)
instance Control.DeepSeq.NFData v => Control.DeepSeq.NFData (Data.Discrimination.Internal.WordMap.WordMap v)
instance GHC.Base.Functor Data.Discrimination.Internal.WordMap.WordMap
instance Data.Foldable.Foldable Data.Discrimination.Internal.WordMap.WordMap
instance Data.Traversable.Traversable Data.Discrimination.Internal.WordMap.WordMap

module Data.Discrimination.Internal
runs :: Eq a => [(a, b)] -> [[b]]
groupNum :: [[k]] -> [(k, Int)]
bdiscNat :: Int -> ([v] -> v -> [v]) -> [(Int, v)] -> [[v]]
updateBag :: [Int] -> Int -> [Int]
updateSet :: [Int] -> Int -> [Int]

-- | Optimized and CPS'd version of <a>partitionEithers</a>, where all
--   lefts are known to come before all rights
spanEither :: ([a] -> [b] -> c) -> [Either a b] -> c

module Data.Discrimination.Grouping

-- | Productive Stable Unordered Discriminator
newtype Group a
Group :: (forall m b. PrimMonad m => (b -> m (b -> m ())) -> m (a -> b -> m ())) -> Group a
[getGroup] :: Group a -> forall m b. PrimMonad m => (b -> m (b -> m ())) -> m (a -> b -> m ())

-- | <a>Eq</a> equipped with a compatible stable unordered discriminator.
class Grouping a where grouping = deciding (Proxy :: Proxy Grouping) grouping

-- | For every surjection <tt>f</tt>,
--   
--   <pre>
--   <a>contramap</a> f <a>grouping</a> ≡ <a>grouping</a>
--   </pre>
grouping :: Grouping a => Group a

-- | For every surjection <tt>f</tt>,
--   
--   <pre>
--   <a>contramap</a> f <a>grouping</a> ≡ <a>grouping</a>
--   </pre>
grouping :: (Grouping a, Deciding Grouping a) => Group a
class Grouping1 f where grouping1 = deciding1 (Proxy :: Proxy Grouping) grouping
grouping1 :: Grouping1 f => Group a -> Group (f a)
grouping1 :: (Grouping1 f, Deciding1 Grouping f) => Group a -> Group (f a)

-- | <i>O(n)</i>. This upgrades <a>nub</a> from <tt>Data.List</tt> from
--   <i>O(n^2)</i> to <i>O(n)</i> by using productive unordered
--   discrimination.
--   
--   <pre>
--   <a>nub</a> = <a>nubWith</a> <a>id</a>
--   <a>nub</a> as = <a>head</a> <a>&lt;$&gt;</a> <a>group</a> as
--   </pre>
nub :: Grouping a => [a] -> [a]

-- | <i>O(n)</i>. Online <a>nub</a> with a Schwartzian transform.
--   
--   <pre>
--   <a>nubWith</a> f as = <a>head</a> <a>&lt;$&gt;</a> <a>groupWith</a> f as
--   </pre>
nubWith :: Grouping b => (a -> b) -> [a] -> [a]

-- | <i>O(n)</i>. Similar to <a>group</a>, except we do not require groups
--   to be clustered.
--   
--   This combinator still operates in linear time, at the expense of
--   storing history.
--   
--   The result equivalence classes are <b>not</b> sorted, but the grouping
--   is stable.
--   
--   <pre>
--   <a>group</a> = <a>groupWith</a> <a>id</a>
--   </pre>
group :: Grouping a => [a] -> [[a]]

-- | <i>O(n)</i>. This is a replacement for <a>groupWith</a> using
--   discrimination.
--   
--   The result equivalence classes are <b>not</b> sorted, but the grouping
--   is stable.
groupWith :: Grouping b => (a -> b) -> [a] -> [[a]]

-- | Valid definition for <tt>(<a>==</a>)</tt> in terms of <a>Grouping</a>.
groupingEq :: Grouping a => a -> a -> Bool
runGroup :: Group a -> [(a, b)] -> [[b]]

-- | This may be useful for pragmatically accelerating a grouping structure
--   by preclassifying by a hash function
--   
--   Semantically,
--   
--   <pre>
--   grouping = hashing &lt;&gt; grouping
--   </pre>
hashing :: Hashable a => Group a
instance Data.Functor.Contravariant.Contravariant Data.Discrimination.Grouping.Group
instance Data.Functor.Contravariant.Divisible.Divisible Data.Discrimination.Grouping.Group
instance Data.Functor.Contravariant.Divisible.Decidable Data.Discrimination.Grouping.Group
instance Data.Semigroup.Semigroup (Data.Discrimination.Grouping.Group a)
instance GHC.Base.Monoid (Data.Discrimination.Grouping.Group a)
instance Data.Discrimination.Grouping.Grouping Data.Void.Void
instance Data.Discrimination.Grouping.Grouping GHC.Word.Word8
instance Data.Discrimination.Grouping.Grouping GHC.Word.Word16
instance Data.Discrimination.Grouping.Grouping GHC.Word.Word32
instance Data.Discrimination.Grouping.Grouping GHC.Word.Word64
instance Data.Discrimination.Grouping.Grouping GHC.Types.Word
instance Data.Discrimination.Grouping.Grouping GHC.Int.Int8
instance Data.Discrimination.Grouping.Grouping GHC.Int.Int16
instance Data.Discrimination.Grouping.Grouping GHC.Int.Int32
instance Data.Discrimination.Grouping.Grouping GHC.Int.Int64
instance Data.Discrimination.Grouping.Grouping GHC.Types.Int
instance Data.Discrimination.Grouping.Grouping GHC.Types.Char
instance Data.Discrimination.Grouping.Grouping GHC.Types.Bool
instance (Data.Discrimination.Grouping.Grouping a, Data.Discrimination.Grouping.Grouping b) => Data.Discrimination.Grouping.Grouping (a, b)
instance (Data.Discrimination.Grouping.Grouping a, Data.Discrimination.Grouping.Grouping b, Data.Discrimination.Grouping.Grouping c) => Data.Discrimination.Grouping.Grouping (a, b, c)
instance (Data.Discrimination.Grouping.Grouping a, Data.Discrimination.Grouping.Grouping b, Data.Discrimination.Grouping.Grouping c, Data.Discrimination.Grouping.Grouping d) => Data.Discrimination.Grouping.Grouping (a, b, c, d)
instance Data.Discrimination.Grouping.Grouping a => Data.Discrimination.Grouping.Grouping [a]
instance Data.Discrimination.Grouping.Grouping a => Data.Discrimination.Grouping.Grouping (GHC.Base.Maybe a)
instance (Data.Discrimination.Grouping.Grouping a, Data.Discrimination.Grouping.Grouping b) => Data.Discrimination.Grouping.Grouping (Data.Either.Either a b)
instance Data.Discrimination.Grouping.Grouping a => Data.Discrimination.Grouping.Grouping (Data.Complex.Complex a)
instance Data.Discrimination.Grouping.Grouping a => Data.Discrimination.Grouping.Grouping (GHC.Real.Ratio a)
instance (Data.Discrimination.Grouping.Grouping1 f, Data.Discrimination.Grouping.Grouping1 g, Data.Discrimination.Grouping.Grouping a) => Data.Discrimination.Grouping.Grouping (Data.Functor.Compose.Compose f g a)
instance Data.Discrimination.Grouping.Grouping1 []
instance Data.Discrimination.Grouping.Grouping1 GHC.Base.Maybe
instance Data.Discrimination.Grouping.Grouping a => Data.Discrimination.Grouping.Grouping1 (Data.Either.Either a)
instance Data.Discrimination.Grouping.Grouping a => Data.Discrimination.Grouping.Grouping1 ((,) a)
instance (Data.Discrimination.Grouping.Grouping a, Data.Discrimination.Grouping.Grouping b) => Data.Discrimination.Grouping.Grouping1 ((,,) a b)
instance (Data.Discrimination.Grouping.Grouping a, Data.Discrimination.Grouping.Grouping b, Data.Discrimination.Grouping.Grouping c) => Data.Discrimination.Grouping.Grouping1 ((,,,) a b c)
instance (Data.Discrimination.Grouping.Grouping1 f, Data.Discrimination.Grouping.Grouping1 g) => Data.Discrimination.Grouping.Grouping1 (Data.Functor.Compose.Compose f g)
instance Data.Discrimination.Grouping.Grouping1 Data.Complex.Complex

module Data.Discrimination.Sorting

-- | Stable Ordered Discriminator
newtype Sort a
Sort :: (forall b. [(a, b)] -> [[b]]) -> Sort a
[runSort] :: Sort a -> forall b. [(a, b)] -> [[b]]

-- | <a>Ord</a> equipped with a compatible stable, ordered discriminator.
class Grouping a => Sorting a where sorting = deciding (Proxy :: Proxy Sorting) sorting

-- | For every strictly monotone-increasing function <tt>f</tt>:
--   
--   <pre>
--   <a>contramap</a> f <a>sorting</a> ≡ <a>sorting</a>
--   </pre>
sorting :: Sorting a => Sort a

-- | For every strictly monotone-increasing function <tt>f</tt>:
--   
--   <pre>
--   <a>contramap</a> f <a>sorting</a> ≡ <a>sorting</a>
--   </pre>
sorting :: (Sorting a, Deciding Sorting a) => Sort a
class Grouping1 f => Sorting1 f where sorting1 = deciding1 (Proxy :: Proxy Sorting) sorting
sorting1 :: Sorting1 f => Sort a -> Sort (f a)
sorting1 :: (Sorting1 f, Deciding1 Sorting f) => Sort a -> Sort (f a)

-- | <i> O(n)</i>. Sort a list using discrimination.
--   
--   <pre>
--   <a>sort</a> = <a>sortWith</a> <a>id</a>
--   </pre>
sort :: Sorting a => [a] -> [a]

-- | <i>O(n)</i>. Sort a list with a Schwartzian transformation by using
--   discrimination.
--   
--   This linear time replacement for <a>sortWith</a> and <a>sortOn</a>
--   uses discrimination.
sortWith :: Sorting b => (a -> b) -> [a] -> [a]
desc :: Sort a -> Sort a

-- | Valid definition for <a>compare</a> in terms of <a>Sorting</a>.
sortingCompare :: Sorting a => a -> a -> Ordering

-- | <i>O(n)</i>. Construct a <a>Map</a>.
--   
--   This is an asymptotically faster version of <a>fromList</a>, which
--   exploits ordered discrimination.
--   
--   <pre>
--   &gt;&gt;&gt; toMap [] == empty
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMap [(5,"a"), (3 :: Int,"b"), (5, "c")]
--   fromList [(5,"c"), (3,"b")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMap [(5,"c"), (3,"b"), (5 :: Int, "a")]
--   fromList [(5,"a"), (3,"b")]
--   </pre>
toMap :: Sorting k => [(k, v)] -> Map k v

-- | <i>O(n)</i>. Construct a <a>Map</a>, combining values.
--   
--   This is an asymptotically faster version of <a>fromListWith</a>, which
--   exploits ordered discrimination.
--   
--   (Note: values combine in anti-stable order for compatibility with
--   <a>fromListWith</a>)
--   
--   <pre>
--   &gt;&gt;&gt; toMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
--   fromList [(3, "ab"), (5, "cba")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMapWith (++) [] == empty
--   True
--   </pre>
toMapWith :: Sorting k => (v -> v -> v) -> [(k, v)] -> Map k v

-- | <i>O(n)</i>. Construct a <a>Map</a>, combining values with access to
--   the key.
--   
--   This is an asymptotically faster version of <a>fromListWithKey</a>,
--   which exploits ordered discrimination.
--   
--   (Note: the values combine in anti-stable order for compatibility with
--   <a>fromListWithKey</a>)
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; toMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
--   fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMapWithKey f [] == empty
--   True
--   </pre>
toMapWithKey :: Sorting k => (k -> v -> v -> v) -> [(k, v)] -> Map k v

-- | <i>O(n)</i>. Construct an <a>IntMap</a>.
--   
--   <pre>
--   &gt;&gt;&gt; toIntMap [] == empty
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMap [(5,"a"), (3,"b"), (5, "c")]
--   fromList [(5,"c"), (3,"b")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMap [(5,"c"), (3,"b"), (5, "a")]
--   fromList [(5,"a"), (3,"b")]
--   </pre>
toIntMap :: [(Int, v)] -> IntMap v

-- | <i>O(n)</i>. Construct an <a>IntMap</a>, combining values.
--   
--   This is an asymptotically faster version of <a>fromListWith</a>, which
--   exploits ordered discrimination.
--   
--   (Note: values combine in anti-stable order for compatibility with
--   <a>fromListWith</a>)
--   
--   <pre>
--   &gt;&gt;&gt; toIntMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
--   fromList [(3, "ab"), (5, "cba")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMapWith (++) [] == empty
--   True
--   </pre>
toIntMapWith :: (v -> v -> v) -> [(Int, v)] -> IntMap v

-- | <i>O(n)</i>. Construct a <a>Map</a>, combining values with access to
--   the key.
--   
--   This is an asymptotically faster version of <a>fromListWithKey</a>,
--   which exploits ordered discrimination.
--   
--   (Note: the values combine in anti-stable order for compatibility with
--   <a>fromListWithKey</a>)
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; toIntMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
--   fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMapWithKey f [] == empty
--   True
--   </pre>
toIntMapWithKey :: (Int -> v -> v -> v) -> [(Int, v)] -> IntMap v

-- | <i>O(n)</i>. Construct a <a>Set</a> in linear time.
--   
--   This is an asymptotically faster version of <a>fromList</a>, which
--   exploits ordered discrimination.
toSet :: Sorting k => [k] -> Set k

-- | <i>O(n)</i>. Construct an <a>IntSet</a> in linear time.
--   
--   This is an asymptotically faster version of <a>fromList</a>, which
--   exploits ordered discrimination.
toIntSet :: [Int] -> IntSet
sortingNat :: Int -> Sort Int

-- | Construct a stable ordered discriminator that sorts a list as
--   multisets of elements from another stable ordered discriminator.
--   
--   The resulting discriminator only cares about the set of keys and their
--   multiplicity, and is sorted as if we'd sorted each key in turn before
--   comparing.
sortingBag :: Foldable f => Sort k -> Sort (f k)

-- | Construct a stable ordered discriminator that sorts a list as sets of
--   elements from another stable ordered discriminator.
--   
--   The resulting discriminator only cares about the set of keys, and is
--   sorted as if we'd sorted each key in turn before comparing.
sortingSet :: Foldable f => Sort k -> Sort (f k)
instance Data.Functor.Contravariant.Contravariant Data.Discrimination.Sorting.Sort
instance Data.Functor.Contravariant.Divisible.Divisible Data.Discrimination.Sorting.Sort
instance Data.Functor.Contravariant.Divisible.Decidable Data.Discrimination.Sorting.Sort
instance Data.Semigroup.Semigroup (Data.Discrimination.Sorting.Sort a)
instance GHC.Base.Monoid (Data.Discrimination.Sorting.Sort a)
instance Data.Discrimination.Sorting.Sorting GHC.Word.Word8
instance Data.Discrimination.Sorting.Sorting GHC.Word.Word16
instance Data.Discrimination.Sorting.Sorting GHC.Word.Word32
instance Data.Discrimination.Sorting.Sorting GHC.Word.Word64
instance Data.Discrimination.Sorting.Sorting GHC.Types.Word
instance Data.Discrimination.Sorting.Sorting GHC.Int.Int8
instance Data.Discrimination.Sorting.Sorting GHC.Int.Int16
instance Data.Discrimination.Sorting.Sorting GHC.Int.Int32
instance Data.Discrimination.Sorting.Sorting GHC.Int.Int64
instance Data.Discrimination.Sorting.Sorting GHC.Types.Int
instance Data.Discrimination.Sorting.Sorting GHC.Types.Char
instance Data.Discrimination.Sorting.Sorting Data.Void.Void
instance Data.Discrimination.Sorting.Sorting GHC.Types.Bool
instance Data.Discrimination.Sorting.Sorting a => Data.Discrimination.Sorting.Sorting [a]
instance Data.Discrimination.Sorting.Sorting a => Data.Discrimination.Sorting.Sorting (GHC.Base.Maybe a)
instance (Data.Discrimination.Sorting.Sorting a, Data.Discrimination.Sorting.Sorting b) => Data.Discrimination.Sorting.Sorting (Data.Either.Either a b)
instance (Data.Discrimination.Sorting.Sorting a, Data.Discrimination.Sorting.Sorting b) => Data.Discrimination.Sorting.Sorting (a, b)
instance (Data.Discrimination.Sorting.Sorting a, Data.Discrimination.Sorting.Sorting b, Data.Discrimination.Sorting.Sorting c) => Data.Discrimination.Sorting.Sorting (a, b, c)
instance (Data.Discrimination.Sorting.Sorting a, Data.Discrimination.Sorting.Sorting b, Data.Discrimination.Sorting.Sorting c, Data.Discrimination.Sorting.Sorting d) => Data.Discrimination.Sorting.Sorting (a, b, c, d)
instance (Data.Discrimination.Sorting.Sorting1 f, Data.Discrimination.Sorting.Sorting1 g, Data.Discrimination.Sorting.Sorting a) => Data.Discrimination.Sorting.Sorting (Data.Functor.Compose.Compose f g a)
instance (Data.Discrimination.Sorting.Sorting1 f, Data.Discrimination.Sorting.Sorting1 g) => Data.Discrimination.Sorting.Sorting1 (Data.Functor.Compose.Compose f g)
instance Data.Discrimination.Sorting.Sorting1 []
instance Data.Discrimination.Sorting.Sorting1 GHC.Base.Maybe
instance Data.Discrimination.Sorting.Sorting a => Data.Discrimination.Sorting.Sorting1 (Data.Either.Either a)

module Data.Discrimination.Class
class Decidable f => Discriminating f
disc :: Discriminating f => f a -> [(a, b)] -> [[b]]

-- | <i>O(n)</i>. Perform a full outer join while explicit merging of the
--   two result tables a table at a time.
--   
--   The results are grouped by the discriminator.
joining :: Discriminating f => f d -> ([a] -> [b] -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [c]

-- | <i>O(n)</i>. Perform an inner join, with operations defined one row at
--   a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
inner :: Discriminating f => f d -> (a -> b -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]

-- | <i>O(n)</i>. Perform a full outer join with operations defined one row
--   at a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
outer :: Discriminating f => f d -> (a -> b -> c) -> (a -> c) -> (b -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]

-- | <i>O(n)</i>. Perform a left outer join with operations defined one row
--   at a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
leftOuter :: Discriminating f => f d -> (a -> b -> c) -> (a -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]

-- | <i>O(n)</i>. Perform a right outer join with operations defined one
--   row at a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
rightOuter :: Discriminating f => f d -> (a -> b -> c) -> (b -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]
instance Data.Discrimination.Class.Discriminating Data.Discrimination.Sorting.Sort
instance Data.Discrimination.Class.Discriminating Data.Discrimination.Grouping.Group

module Data.Discrimination
class Decidable f => Discriminating f
disc :: Discriminating f => f a -> [(a, b)] -> [[b]]

-- | Productive Stable Unordered Discriminator
newtype Group a
Group :: (forall m b. PrimMonad m => (b -> m (b -> m ())) -> m (a -> b -> m ())) -> Group a
[getGroup] :: Group a -> forall m b. PrimMonad m => (b -> m (b -> m ())) -> m (a -> b -> m ())

-- | <a>Eq</a> equipped with a compatible stable unordered discriminator.
class Grouping a where grouping = deciding (Proxy :: Proxy Grouping) grouping

-- | For every surjection <tt>f</tt>,
--   
--   <pre>
--   <a>contramap</a> f <a>grouping</a> ≡ <a>grouping</a>
--   </pre>
grouping :: Grouping a => Group a

-- | For every surjection <tt>f</tt>,
--   
--   <pre>
--   <a>contramap</a> f <a>grouping</a> ≡ <a>grouping</a>
--   </pre>
grouping :: (Grouping a, Deciding Grouping a) => Group a
class Grouping1 f where grouping1 = deciding1 (Proxy :: Proxy Grouping) grouping
grouping1 :: Grouping1 f => Group a -> Group (f a)
grouping1 :: (Grouping1 f, Deciding1 Grouping f) => Group a -> Group (f a)

-- | <i>O(n)</i>. This upgrades <a>nub</a> from <tt>Data.List</tt> from
--   <i>O(n^2)</i> to <i>O(n)</i> by using productive unordered
--   discrimination.
--   
--   <pre>
--   <a>nub</a> = <a>nubWith</a> <a>id</a>
--   <a>nub</a> as = <a>head</a> <a>&lt;$&gt;</a> <a>group</a> as
--   </pre>
nub :: Grouping a => [a] -> [a]

-- | <i>O(n)</i>. Online <a>nub</a> with a Schwartzian transform.
--   
--   <pre>
--   <a>nubWith</a> f as = <a>head</a> <a>&lt;$&gt;</a> <a>groupWith</a> f as
--   </pre>
nubWith :: Grouping b => (a -> b) -> [a] -> [a]

-- | <i>O(n)</i>. Similar to <a>group</a>, except we do not require groups
--   to be clustered.
--   
--   This combinator still operates in linear time, at the expense of
--   storing history.
--   
--   The result equivalence classes are <b>not</b> sorted, but the grouping
--   is stable.
--   
--   <pre>
--   <a>group</a> = <a>groupWith</a> <a>id</a>
--   </pre>
group :: Grouping a => [a] -> [[a]]

-- | <i>O(n)</i>. This is a replacement for <a>groupWith</a> using
--   discrimination.
--   
--   The result equivalence classes are <b>not</b> sorted, but the grouping
--   is stable.
groupWith :: Grouping b => (a -> b) -> [a] -> [[a]]
runGroup :: Group a -> [(a, b)] -> [[b]]

-- | Valid definition for <tt>(<a>==</a>)</tt> in terms of <a>Grouping</a>.
groupingEq :: Grouping a => a -> a -> Bool

-- | Stable Ordered Discriminator
newtype Sort a
Sort :: (forall b. [(a, b)] -> [[b]]) -> Sort a
[runSort] :: Sort a -> forall b. [(a, b)] -> [[b]]

-- | <a>Ord</a> equipped with a compatible stable, ordered discriminator.
class Grouping a => Sorting a where sorting = deciding (Proxy :: Proxy Sorting) sorting

-- | For every strictly monotone-increasing function <tt>f</tt>:
--   
--   <pre>
--   <a>contramap</a> f <a>sorting</a> ≡ <a>sorting</a>
--   </pre>
sorting :: Sorting a => Sort a

-- | For every strictly monotone-increasing function <tt>f</tt>:
--   
--   <pre>
--   <a>contramap</a> f <a>sorting</a> ≡ <a>sorting</a>
--   </pre>
sorting :: (Sorting a, Deciding Sorting a) => Sort a
class Grouping1 f => Sorting1 f where sorting1 = deciding1 (Proxy :: Proxy Sorting) sorting
sorting1 :: Sorting1 f => Sort a -> Sort (f a)
sorting1 :: (Sorting1 f, Deciding1 Sorting f) => Sort a -> Sort (f a)
desc :: Sort a -> Sort a

-- | <i> O(n)</i>. Sort a list using discrimination.
--   
--   <pre>
--   <a>sort</a> = <a>sortWith</a> <a>id</a>
--   </pre>
sort :: Sorting a => [a] -> [a]

-- | <i>O(n)</i>. Sort a list with a Schwartzian transformation by using
--   discrimination.
--   
--   This linear time replacement for <a>sortWith</a> and <a>sortOn</a>
--   uses discrimination.
sortWith :: Sorting b => (a -> b) -> [a] -> [a]

-- | Construct a stable ordered discriminator that sorts a list as
--   multisets of elements from another stable ordered discriminator.
--   
--   The resulting discriminator only cares about the set of keys and their
--   multiplicity, and is sorted as if we'd sorted each key in turn before
--   comparing.
sortingBag :: Foldable f => Sort k -> Sort (f k)

-- | Construct a stable ordered discriminator that sorts a list as sets of
--   elements from another stable ordered discriminator.
--   
--   The resulting discriminator only cares about the set of keys, and is
--   sorted as if we'd sorted each key in turn before comparing.
sortingSet :: Foldable f => Sort k -> Sort (f k)

-- | Valid definition for <a>compare</a> in terms of <a>Sorting</a>.
sortingCompare :: Sorting a => a -> a -> Ordering

-- | <i>O(n)</i>. Construct a <a>Map</a>.
--   
--   This is an asymptotically faster version of <a>fromList</a>, which
--   exploits ordered discrimination.
--   
--   <pre>
--   &gt;&gt;&gt; toMap [] == empty
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMap [(5,"a"), (3 :: Int,"b"), (5, "c")]
--   fromList [(5,"c"), (3,"b")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMap [(5,"c"), (3,"b"), (5 :: Int, "a")]
--   fromList [(5,"a"), (3,"b")]
--   </pre>
toMap :: Sorting k => [(k, v)] -> Map k v

-- | <i>O(n)</i>. Construct a <a>Map</a>, combining values.
--   
--   This is an asymptotically faster version of <a>fromListWith</a>, which
--   exploits ordered discrimination.
--   
--   (Note: values combine in anti-stable order for compatibility with
--   <a>fromListWith</a>)
--   
--   <pre>
--   &gt;&gt;&gt; toMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
--   fromList [(3, "ab"), (5, "cba")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMapWith (++) [] == empty
--   True
--   </pre>
toMapWith :: Sorting k => (v -> v -> v) -> [(k, v)] -> Map k v

-- | <i>O(n)</i>. Construct a <a>Map</a>, combining values with access to
--   the key.
--   
--   This is an asymptotically faster version of <a>fromListWithKey</a>,
--   which exploits ordered discrimination.
--   
--   (Note: the values combine in anti-stable order for compatibility with
--   <a>fromListWithKey</a>)
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; toMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
--   fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toMapWithKey f [] == empty
--   True
--   </pre>
toMapWithKey :: Sorting k => (k -> v -> v -> v) -> [(k, v)] -> Map k v

-- | <i>O(n)</i>. Construct an <a>IntMap</a>.
--   
--   <pre>
--   &gt;&gt;&gt; toIntMap [] == empty
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMap [(5,"a"), (3,"b"), (5, "c")]
--   fromList [(5,"c"), (3,"b")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMap [(5,"c"), (3,"b"), (5, "a")]
--   fromList [(5,"a"), (3,"b")]
--   </pre>
toIntMap :: [(Int, v)] -> IntMap v

-- | <i>O(n)</i>. Construct an <a>IntMap</a>, combining values.
--   
--   This is an asymptotically faster version of <a>fromListWith</a>, which
--   exploits ordered discrimination.
--   
--   (Note: values combine in anti-stable order for compatibility with
--   <a>fromListWith</a>)
--   
--   <pre>
--   &gt;&gt;&gt; toIntMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
--   fromList [(3, "ab"), (5, "cba")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMapWith (++) [] == empty
--   True
--   </pre>
toIntMapWith :: (v -> v -> v) -> [(Int, v)] -> IntMap v

-- | <i>O(n)</i>. Construct a <a>Map</a>, combining values with access to
--   the key.
--   
--   This is an asymptotically faster version of <a>fromListWithKey</a>,
--   which exploits ordered discrimination.
--   
--   (Note: the values combine in anti-stable order for compatibility with
--   <a>fromListWithKey</a>)
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; toIntMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
--   fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; toIntMapWithKey f [] == empty
--   True
--   </pre>
toIntMapWithKey :: (Int -> v -> v -> v) -> [(Int, v)] -> IntMap v

-- | <i>O(n)</i>. Construct a <a>Set</a> in linear time.
--   
--   This is an asymptotically faster version of <a>fromList</a>, which
--   exploits ordered discrimination.
toSet :: Sorting k => [k] -> Set k

-- | <i>O(n)</i>. Construct an <a>IntSet</a> in linear time.
--   
--   This is an asymptotically faster version of <a>fromList</a>, which
--   exploits ordered discrimination.
toIntSet :: [Int] -> IntSet

-- | <i>O(n)</i>. Perform a full outer join while explicit merging of the
--   two result tables a table at a time.
--   
--   The results are grouped by the discriminator.
joining :: Discriminating f => f d -> ([a] -> [b] -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [c]

-- | <i>O(n)</i>. Perform an inner join, with operations defined one row at
--   a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
inner :: Discriminating f => f d -> (a -> b -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]

-- | <i>O(n)</i>. Perform a full outer join with operations defined one row
--   at a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
outer :: Discriminating f => f d -> (a -> b -> c) -> (a -> c) -> (b -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]

-- | <i>O(n)</i>. Perform a left outer join with operations defined one row
--   at a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
leftOuter :: Discriminating f => f d -> (a -> b -> c) -> (a -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]

-- | <i>O(n)</i>. Perform a right outer join with operations defined one
--   row at a time.
--   
--   The results are grouped by the discriminator.
--   
--   This takes operation time linear in both the input and result sets.
rightOuter :: Discriminating f => f d -> (a -> b -> c) -> (b -> c) -> (a -> d) -> (b -> d) -> [a] -> [b] -> [[c]]