{-# LANGUAGE ConstraintKinds          #-}


module Data.List.FastNub where


import Data.List
import Data.Function
import Data.Ord
import Control.Arrow ((&&&))


type FastNub a = (Eq a, Ord a) -- S̶h̶o̶u̶l̶d̶ ̶r̶e̶a̶l̶l̶y̶ ̶b̶e̶ ̶(̶E̶q̶ ̶a̶,̶̶ ̶H̶a̶s̶h̶a̶b̶l̶e̶ ̶a̶)̶
fastNub :: FastNub a => [a] -> [a]
fastNub :: forall a. FastNub a => [a] -> [a]
fastNub = forall a b. (a -> b) -> [a] -> [b]
map forall a. [a] -> a
head forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Eq a => [a] -> [[a]]
group forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => [a] -> [a]
sort

-- | Simply a merge sort that discards equivalent elements.
fastNubBy :: (a->a->Ordering) -> [a] -> [a]
fastNubBy :: forall a. (a -> a -> Ordering) -> [a] -> [a]
fastNubBy a -> a -> Ordering
_ [] = []
fastNubBy a -> a -> Ordering
_ [a
e] = [a
e]
fastNubBy a -> a -> Ordering
cmp [a]
es = forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
fnubMergeBy a -> a -> Ordering
cmp (forall a. (a -> a -> Ordering) -> [a] -> [a]
fastNubBy a -> a -> Ordering
cmp [a]
lhs) (forall a. (a -> a -> Ordering) -> [a] -> [a]
fastNubBy a -> a -> Ordering
cmp [a]
rhs)
 where ([a]
lhs,[a]
rhs) = forall a. Int -> [a] -> ([a], [a])
splitAt (forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
es forall a. Integral a => a -> a -> a
`quot` Int
2) [a]
es

fnubMergeBy :: (a->a->Ordering) -> [a] -> [a] -> [a]
fnubMergeBy :: forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
fnubMergeBy a -> a -> Ordering
_ [] [a]
rs = [a]
rs
fnubMergeBy a -> a -> Ordering
_ [a]
ls [] = [a]
ls
fnubMergeBy a -> a -> Ordering
cmp (a
l:[a]
ls) (a
r:[a]
rs) = case a -> a -> Ordering
cmp a
l a
r of
                              Ordering
LT -> a
l forall a. a -> [a] -> [a]
: forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
fnubMergeBy a -> a -> Ordering
cmp [a]
ls (a
rforall a. a -> [a] -> [a]
:[a]
rs)
                              Ordering
GT -> a
r forall a. a -> [a] -> [a]
: forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
fnubMergeBy a -> a -> Ordering
cmp (a
lforall a. a -> [a] -> [a]
:[a]
ls) [a]
rs
                              Ordering
EQ -> forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
fnubMergeBy a -> a -> Ordering
cmp (a
lforall a. a -> [a] -> [a]
:[a]
ls) [a]
rs

-- | Like 'fastNubBy', but doesn't just discard duplicates but \"merges\" them.
-- @'fastNubBy' cmp = cmp `'fastNubByWith'` 'const'@.
fastNubByWith :: (a->a->Ordering) -> (a->a->a) -> [a] -> [a]
fastNubByWith :: forall a. (a -> a -> Ordering) -> (a -> a -> a) -> [a] -> [a]
fastNubByWith a -> a -> Ordering
_ a -> a -> a
_ [] = []
fastNubByWith a -> a -> Ordering
_ a -> a -> a
_ [a
e] = [a
e]
fastNubByWith a -> a -> Ordering
cmp a -> a -> a
cmb [a]
es = [a] -> [a] -> [a]
merge(forall a. (a -> a -> Ordering) -> (a -> a -> a) -> [a] -> [a]
fastNubByWith a -> a -> Ordering
cmp a -> a -> a
cmb [a]
lhs)(forall a. (a -> a -> Ordering) -> (a -> a -> a) -> [a] -> [a]
fastNubByWith a -> a -> Ordering
cmp a -> a -> a
cmb [a]
rhs)
 where ([a]
lhs,[a]
rhs) = forall a. Int -> [a] -> ([a], [a])
splitAt (forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
es forall a. Integral a => a -> a -> a
`quot` Int
2) [a]
es
       merge :: [a] -> [a] -> [a]
merge [] [a]
rs = [a]
rs
       merge [a]
ls [] = [a]
ls
       merge (a
l:[a]
ls) (a
r:[a]
rs) = case a -> a -> Ordering
cmp a
l a
r of
                              Ordering
LT -> a
l forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
ls (a
rforall a. a -> [a] -> [a]
:[a]
rs)
                              Ordering
GT -> a
r forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge (a
lforall a. a -> [a] -> [a]
:[a]
ls) [a]
rs
                              Ordering
EQ -> [a] -> [a] -> [a]
merge (a -> a -> a
cmb a
l a
r forall a. a -> [a] -> [a]
: [a]
ls) [a]
rs

sfGroupBy :: (a->a->Ordering) -> [a] -> [[a]]
sfGroupBy :: forall a. (a -> a -> Ordering) -> [a] -> [[a]]
sfGroupBy a -> a -> Ordering
cmp = forall a. (a -> a -> Ordering) -> (a -> a -> a) -> [a] -> [a]
fastNubByWith (a -> a -> Ordering
cmpforall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on`forall a. [a] -> a
head) forall a. [a] -> [a] -> [a]
(++) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map(forall a. a -> [a] -> [a]
:[])




fnubConcatBy :: (a->a->Ordering) -> [[a]] -> [a]
fnubConcatBy :: forall a. (a -> a -> Ordering) -> [[a]] -> [a]
fnubConcatBy a -> a -> Ordering
cmp = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
fnubMergeBy a -> a -> Ordering
cmp) [] forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (forall a. (a -> a -> Ordering) -> [a] -> [a]
fastNubBy a -> a -> Ordering
cmp)

fnubConcat :: FastNub a => [[a]] -> [a]
fnubConcat :: forall a. FastNub a => [[a]] -> [a]
fnubConcat = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
fnubMergeBy forall a. Ord a => a -> a -> Ordering
compare) [] forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map forall a. FastNub a => [a] -> [a]
fastNub

fnubConcatMap :: FastNub b => (a -> [b]) -> [a] -> [b]
fnubConcatMap :: forall b a. FastNub b => (a -> [b]) -> [a] -> [b]
fnubConcatMap a -> [b]
f = forall a. FastNub a => [[a]] -> [a]
fnubConcat forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map a -> [b]
f

fnubIntersect :: FastNub a => [a] -> [a] -> [a]
fnubIntersect :: forall a. FastNub a => [a] -> [a] -> [a]
fnubIntersect [a]
xs [a]
ys = forall {a}. Ord a => [a] -> [a] -> [a]
fis (forall a. FastNub a => [a] -> [a]
fastNub [a]
xs) (forall a. FastNub a => [a] -> [a]
fastNub [a]
ys)
 where fis :: [a] -> [a] -> [a]
fis [] [a]
_ = []
       fis [a]
_ [] = []
       fis (a
x:[a]
xs) (a
y:[a]
ys) | a
xforall a. Ord a => a -> a -> Bool
<a
y  = [a] -> [a] -> [a]
fis [a]
xs (a
yforall a. a -> [a] -> [a]
:[a]
ys)
                         | a
xforall a. Ord a => a -> a -> Bool
>a
y  = [a] -> [a] -> [a]
fis (a
xforall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
                         | Bool
otherwise  = a
x forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
fis [a]
xs [a]
ys


-- | This function is also defined in "GHC.Exts", but only in a version that requires
--   𝓞(𝑛⋅log 𝑛) function applications, as opposed to 𝑛 here.
sortWith :: Ord b => (a -> b) -> [a] -> [a]
sortWith :: forall b a. Ord b => (a -> b) -> [a] -> [a]
sortWith a -> b
f = forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing forall a b. (a, b) -> a
fst) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (a -> b
f forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& forall a. a -> a
id)