-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Fast generic linear-time sorting, joins and container construction.
--
@package discrimination
@version 0
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 partitionEithers, where all
-- lefts are known to come before all rights
spanEither :: ([a] -> [b] -> c) -> [Either a b] -> c
module Data.Discrimination.Grouping
-- | Discriminator
newtype Group a
Group :: (forall b. [(a, b)] -> [[b]]) -> Group a
runGroup :: Group a -> forall b. [(a, b)] -> [[b]]
-- | Eq equipped with a compatible stable unordered discriminator.
class Grouping a where grouping = deciding (Proxy :: Proxy Grouping) grouping
grouping :: Grouping a => Group a
class Grouping1 f where grouping1 = deciding1 (Proxy :: Proxy Grouping) grouping
grouping1 :: Grouping1 f => Group a -> Group (f a)
-- | O(n). This upgrades nub from Data.List from
-- O(n^2) to O(n) by using unordered discrimination.
--
--
-- nub = nubWith id
-- nub as = head <$> group as
--
nub :: Grouping a => [a] -> [a]
-- | O(n). nub with a Schwartzian transform.
--
--
-- nubWith f as = head <$> groupWith f as
--
nubWith :: Grouping b => (a -> b) -> [a] -> [a]
-- | O(n). Similar to group, except we do not require groups
-- to be clustered.
--
-- This combinator still operates in linear time, at the expense of
-- productivity.
--
-- The result equivalence classes are _not_ sorted, but the grouping is
-- stable.
--
--
-- group = groupWith id
--
group :: Grouping a => [a] -> [[a]]
-- | O(n). This is a replacement for groupWith using
-- discrimination.
--
-- The result equivalence classes are _not_ sorted, but the grouping is
-- stable.
groupWith :: Grouping b => (a -> b) -> [a] -> [[a]]
-- | Valid definition for (==) in terms of Grouping.
groupingEq :: Grouping a => a -> a -> Bool
-- | Construct an stable unordered discriminator that partitions into
-- equivalence classes based on the equivalence of keys as a multiset.
groupingBag :: Foldable f => Group k -> Group (f k)
-- | Construct an stable unordered discriminator that partitions into
-- equivalence classes based on the equivalence of keys as a set.
groupingSet :: Foldable f => Group k -> Group (f k)
-- | Shared bucket set for small integers
groupingShort :: Group Int
-- | Perform stable unordered discrimination by bucket.
--
-- This reuses arrays unlike the more obvious ST implementation, so it
-- wins by a huge margin in a race, especially when we have a large
-- keyspace, sparsely used, with low contention. This will leak a number
-- of arrays equal to the maximum concurrent contention for this
-- resource. If this becomes a bottleneck we can make multiple stacks of
-- working pads and index the stack with the hash of the current thread
-- id to reduce contention at the expense of taking more memory.
--
-- You should create a thunk that holds the discriminator from
-- groupingNat n for a known n and then reuse it.
groupingNat :: Int -> Group Int
instance Typeable Group
instance Grouping1 Complex
instance (Grouping1 f, Grouping1 g) => Grouping1 (Compose f g)
instance (Grouping a, Grouping b, Grouping c) => Grouping1 ((,,,) a b c)
instance (Grouping a, Grouping b) => Grouping1 ((,,) a b)
instance Grouping a => Grouping1 ((,) a)
instance Grouping a => Grouping1 (Either a)
instance Grouping1 Maybe
instance Grouping1 []
instance (Grouping1 f, Grouping1 g, Grouping a) => Grouping (Compose f g a)
instance (Grouping a, Integral a) => Grouping (Ratio a)
instance Grouping a => Grouping (Complex a)
instance (Grouping a, Grouping b) => Grouping (Either a b)
instance Grouping a => Grouping (Maybe a)
instance Grouping a => Grouping [a]
instance (Grouping a, Grouping b, Grouping c, Grouping d) => Grouping (a, b, c, d)
instance (Grouping a, Grouping b, Grouping c) => Grouping (a, b, c)
instance (Grouping a, Grouping b) => Grouping (a, b)
instance Grouping Bool
instance Grouping Int
instance Grouping Int64
instance Grouping Int32
instance Grouping Int16
instance Grouping Int8
instance Grouping Word
instance Grouping Word64
instance Grouping Word32
instance Grouping Word16
instance Grouping Word8
instance Grouping Void
instance Monoid (Group a)
instance Decidable Group
instance Divisible Group
instance Contravariant Group
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]]
-- | Ord equipped with a compatible stable, ordered discriminator.
class Grouping a => Sorting a where sorting = deciding (Proxy :: Proxy Sorting) sorting
sorting :: Sorting a => Sort a
class Grouping1 f => Sorting1 f where sorting1 = deciding1 (Proxy :: Proxy Sorting) sorting
sorting1 :: Sorting1 f => Sort a -> Sort (f a)
-- | O(n). Sort a list using discrimination.
--
--
-- sort = sortWith id
--
sort :: Sorting a => [a] -> [a]
-- | O(n). Sort a list with a Schwartzian transformation by using
-- discrimination.
--
-- This linear time replacement for sortWith and sortOn
-- uses discrimination.
sortWith :: Sorting b => (a -> b) -> [a] -> [a]
desc :: Sort a -> Sort a
-- | Valid definition for compare in terms of Sorting.
sortingCompare :: Sorting a => a -> a -> Ordering
-- | O(n). Construct a Map.
--
-- This is an asymptotically faster version of fromList, which
-- exploits ordered discrimination.
--
--
-- >>> toMap [] == empty
-- True
--
--
--
-- >>> toMap [(5,"a"), (3 :: Int,"b"), (5, "c")]
-- fromList [(5,"c"), (3,"b")]
--
--
--
-- >>> toMap [(5,"c"), (3,"b"), (5 :: Int, "a")]
-- fromList [(5,"a"), (3,"b")]
--
toMap :: Sorting k => [(k, v)] -> Map k v
-- | O(n). Construct a Map, combining values.
--
-- This is an asymptotically faster version of fromListWith, which
-- exploits ordered discrimination.
--
-- (Note: values combine in anti-stable order for compatibility with
-- fromListWith)
--
--
-- >>> toMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
-- fromList [(3, "ab"), (5, "cba")]
--
--
--
-- >>> toMapWith (++) [] == empty
-- True
--
toMapWith :: Sorting k => (v -> v -> v) -> [(k, v)] -> Map k v
-- | O(n). Construct a Map, combining values with access to
-- the key.
--
-- This is an asymptotically faster version of fromListWithKey,
-- which exploits ordered discrimination.
--
-- (Note: the values combine in anti-stable order for compatibility with
-- fromListWithKey)
--
--
-- >>> let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--
-- >>> toMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
-- fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--
--
--
-- >>> toMapWithKey f [] == empty
-- True
--
toMapWithKey :: Sorting k => (k -> v -> v -> v) -> [(k, v)] -> Map k v
-- | O(n). Construct an IntMap.
--
--
-- >>> toIntMap [] == empty
-- True
--
--
--
-- >>> toIntMap [(5,"a"), (3,"b"), (5, "c")]
-- fromList [(5,"c"), (3,"b")]
--
--
--
-- >>> toIntMap [(5,"c"), (3,"b"), (5, "a")]
-- fromList [(5,"a"), (3,"b")]
--
toIntMap :: [(Int, v)] -> IntMap v
-- | O(n). Construct an IntMap, combining values.
--
-- This is an asymptotically faster version of fromListWith, which
-- exploits ordered discrimination.
--
-- (Note: values combine in anti-stable order for compatibility with
-- fromListWith)
--
--
-- >>> toIntMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
-- fromList [(3, "ab"), (5, "cba")]
--
--
--
-- >>> toIntMapWith (++) [] == empty
-- True
--
toIntMapWith :: (v -> v -> v) -> [(Int, v)] -> IntMap v
-- | O(n). Construct a Map, combining values with access to
-- the key.
--
-- This is an asymptotically faster version of fromListWithKey,
-- which exploits ordered discrimination.
--
-- (Note: the values combine in anti-stable order for compatibility with
-- fromListWithKey)
--
--
-- >>> let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--
-- >>> toIntMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
-- fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--
--
--
-- >>> toIntMapWithKey f [] == empty
-- True
--
toIntMapWithKey :: (Int -> v -> v -> v) -> [(Int, v)] -> IntMap v
-- | O(n). Construct a Set in linear time.
--
-- This is an asymptotically faster version of fromList, which
-- exploits ordered discrimination.
toSet :: Sorting k => [k] -> Set k
-- | O(n). Construct an IntSet in linear time.
--
-- This is an asymptotically faster version of fromList, 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 Typeable Sort
instance Sorting a => Sorting1 (Either a)
instance Sorting1 Maybe
instance Sorting1 []
instance (Sorting1 f, Sorting1 g) => Sorting1 (Compose f g)
instance (Sorting1 f, Sorting1 g, Sorting a) => Sorting (Compose f g a)
instance (Sorting a, Sorting b, Sorting c, Sorting d) => Sorting (a, b, c, d)
instance (Sorting a, Sorting b, Sorting c) => Sorting (a, b, c)
instance (Sorting a, Sorting b) => Sorting (a, b)
instance (Sorting a, Sorting b) => Sorting (Either a b)
instance Sorting a => Sorting (Maybe a)
instance Sorting a => Sorting [a]
instance Sorting Bool
instance Sorting Void
instance Sorting Int
instance Sorting Int64
instance Sorting Int32
instance Sorting Int16
instance Sorting Int8
instance Sorting Word
instance Sorting Word64
instance Sorting Word32
instance Sorting Word16
instance Sorting Word8
instance Monoid (Sort a)
instance Decidable Sort
instance Divisible Sort
instance Contravariant Sort
module Data.Discrimination.Class
class Decidable f => Discriminating f
disc :: Discriminating f => f a -> [(a, b)] -> [[b]]
-- | O(n). 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]
-- | O(n). 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]]
-- | O(n). 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]]
-- | O(n). 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]]
-- | O(n). 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 Discriminating Group
instance Discriminating Sort
module Data.Discrimination
class Decidable f => Discriminating f
disc :: Discriminating f => f a -> [(a, b)] -> [[b]]
-- | Discriminator
newtype Group a
Group :: (forall b. [(a, b)] -> [[b]]) -> Group a
runGroup :: Group a -> forall b. [(a, b)] -> [[b]]
-- | Eq equipped with a compatible stable unordered discriminator.
class Grouping a where grouping = deciding (Proxy :: Proxy Grouping) grouping
grouping :: Grouping a => Group a
class Grouping1 f where grouping1 = deciding1 (Proxy :: Proxy Grouping) grouping
grouping1 :: Grouping1 f => Group a -> Group (f a)
-- | O(n). This upgrades nub from Data.List from
-- O(n^2) to O(n) by using unordered discrimination.
--
--
-- nub = nubWith id
-- nub as = head <$> group as
--
nub :: Grouping a => [a] -> [a]
-- | O(n). nub with a Schwartzian transform.
--
--
-- nubWith f as = head <$> groupWith f as
--
nubWith :: Grouping b => (a -> b) -> [a] -> [a]
-- | O(n). Similar to group, except we do not require groups
-- to be clustered.
--
-- This combinator still operates in linear time, at the expense of
-- productivity.
--
-- The result equivalence classes are _not_ sorted, but the grouping is
-- stable.
--
--
-- group = groupWith id
--
group :: Grouping a => [a] -> [[a]]
-- | O(n). This is a replacement for groupWith using
-- discrimination.
--
-- The result equivalence classes are _not_ sorted, but the grouping is
-- stable.
groupWith :: Grouping b => (a -> b) -> [a] -> [[a]]
-- | Construct an stable unordered discriminator that partitions into
-- equivalence classes based on the equivalence of keys as a multiset.
groupingBag :: Foldable f => Group k -> Group (f k)
-- | Construct an stable unordered discriminator that partitions into
-- equivalence classes based on the equivalence of keys as a set.
groupingSet :: Foldable f => Group k -> Group (f k)
-- | Valid definition for (==) in terms of Grouping.
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]]
-- | Ord equipped with a compatible stable, ordered discriminator.
class Grouping a => Sorting a where sorting = deciding (Proxy :: Proxy Sorting) sorting
sorting :: Sorting a => Sort a
class Grouping1 f => Sorting1 f where sorting1 = deciding1 (Proxy :: Proxy Sorting) sorting
sorting1 :: Sorting1 f => Sort a -> Sort (f a)
desc :: Sort a -> Sort a
-- | O(n). Sort a list using discrimination.
--
--
-- sort = sortWith id
--
sort :: Sorting a => [a] -> [a]
-- | O(n). Sort a list with a Schwartzian transformation by using
-- discrimination.
--
-- This linear time replacement for sortWith and sortOn
-- 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 compare in terms of Sorting.
sortingCompare :: Sorting a => a -> a -> Ordering
-- | O(n). Construct a Map.
--
-- This is an asymptotically faster version of fromList, which
-- exploits ordered discrimination.
--
--
-- >>> toMap [] == empty
-- True
--
--
--
-- >>> toMap [(5,"a"), (3 :: Int,"b"), (5, "c")]
-- fromList [(5,"c"), (3,"b")]
--
--
--
-- >>> toMap [(5,"c"), (3,"b"), (5 :: Int, "a")]
-- fromList [(5,"a"), (3,"b")]
--
toMap :: Sorting k => [(k, v)] -> Map k v
-- | O(n). Construct a Map, combining values.
--
-- This is an asymptotically faster version of fromListWith, which
-- exploits ordered discrimination.
--
-- (Note: values combine in anti-stable order for compatibility with
-- fromListWith)
--
--
-- >>> toMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
-- fromList [(3, "ab"), (5, "cba")]
--
--
--
-- >>> toMapWith (++) [] == empty
-- True
--
toMapWith :: Sorting k => (v -> v -> v) -> [(k, v)] -> Map k v
-- | O(n). Construct a Map, combining values with access to
-- the key.
--
-- This is an asymptotically faster version of fromListWithKey,
-- which exploits ordered discrimination.
--
-- (Note: the values combine in anti-stable order for compatibility with
-- fromListWithKey)
--
--
-- >>> let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--
-- >>> toMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
-- fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--
--
--
-- >>> toMapWithKey f [] == empty
-- True
--
toMapWithKey :: Sorting k => (k -> v -> v -> v) -> [(k, v)] -> Map k v
-- | O(n). Construct an IntMap.
--
--
-- >>> toIntMap [] == empty
-- True
--
--
--
-- >>> toIntMap [(5,"a"), (3,"b"), (5, "c")]
-- fromList [(5,"c"), (3,"b")]
--
--
--
-- >>> toIntMap [(5,"c"), (3,"b"), (5, "a")]
-- fromList [(5,"a"), (3,"b")]
--
toIntMap :: [(Int, v)] -> IntMap v
-- | O(n). Construct an IntMap, combining values.
--
-- This is an asymptotically faster version of fromListWith, which
-- exploits ordered discrimination.
--
-- (Note: values combine in anti-stable order for compatibility with
-- fromListWith)
--
--
-- >>> toIntMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
-- fromList [(3, "ab"), (5, "cba")]
--
--
--
-- >>> toIntMapWith (++) [] == empty
-- True
--
toIntMapWith :: (v -> v -> v) -> [(Int, v)] -> IntMap v
-- | O(n). Construct a Map, combining values with access to
-- the key.
--
-- This is an asymptotically faster version of fromListWithKey,
-- which exploits ordered discrimination.
--
-- (Note: the values combine in anti-stable order for compatibility with
-- fromListWithKey)
--
--
-- >>> let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
--
-- >>> toIntMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
-- fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
--
--
--
-- >>> toIntMapWithKey f [] == empty
-- True
--
toIntMapWithKey :: (Int -> v -> v -> v) -> [(Int, v)] -> IntMap v
-- | O(n). Construct a Set in linear time.
--
-- This is an asymptotically faster version of fromList, which
-- exploits ordered discrimination.
toSet :: Sorting k => [k] -> Set k
-- | O(n). Construct an IntSet in linear time.
--
-- This is an asymptotically faster version of fromList, which
-- exploits ordered discrimination.
toIntSet :: [Int] -> IntSet
-- | O(n). 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]
-- | O(n). 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]]
-- | O(n). 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]]
-- | O(n). 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]]
-- | O(n). 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]]