{-# 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)
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
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
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
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)