module Data.List.Duplicate (
group
, groupBy
, groupAdj
, groupAdjBy
, deleteDups
, deleteDupsBy
, deleteAdjDups
, deleteAdjDupsBy
) where
import Control.Monad (guard)
import Data.List (sort, sortBy, uncons)
import Data.Maybe (fromMaybe)
group :: (Ord a) => [a] -> [[a]]
group :: [a] -> [[a]]
group = [a] -> [[a]]
forall a. Eq a => [a] -> [[a]]
groupAdj ([a] -> [[a]]) -> ([a] -> [a]) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Ord a => [a] -> [a]
sort
groupBy :: (a -> a -> Ordering) -> [a] -> [[a]]
groupBy :: (a -> a -> Ordering) -> [a] -> [[a]]
groupBy cmp :: a -> a -> Ordering
cmp = (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupAdjBy a -> a -> Bool
eq ([a] -> [[a]]) -> ([a] -> [a]) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy a -> a -> Ordering
cmp
where
eq :: a -> a -> Bool
eq a :: a
a b :: a
b = a -> a -> Ordering
cmp a
a a
b Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
EQ
groupAdj :: (Eq a) => [a] -> [[a]]
groupAdj :: [a] -> [[a]]
groupAdj = (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupAdjBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
groupAdjBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupAdjBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupAdjBy eq :: a -> a -> Bool
eq = (a -> [[a]] -> [[a]]) -> [[a]] -> [a] -> [[a]]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [[a]] -> [[a]]
f []
where
f :: a -> [[a]] -> [[a]]
f x :: a
x yss :: [[a]]
yss = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
zs)[a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
:[[a]]
zss
where
(zs :: [a]
zs, zss :: [[a]]
zss) = ([a], [[a]]) -> Maybe ([a], [[a]]) -> ([a], [[a]])
forall a. a -> Maybe a -> a
fromMaybe ([], [[a]]
yss) (Maybe ([a], [[a]]) -> ([a], [[a]]))
-> Maybe ([a], [[a]]) -> ([a], [[a]])
forall a b. (a -> b) -> a -> b
$ do
(ys :: [a]
ys, yss' :: [[a]]
yss') <- [[a]] -> Maybe ([a], [[a]])
forall a. [a] -> Maybe (a, [a])
uncons [[a]]
yss
Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (a
x a -> a -> Bool
`eq` [a] -> a
forall a. [a] -> a
head [a]
ys)
([a], [[a]]) -> Maybe ([a], [[a]])
forall (m :: * -> *) a. Monad m => a -> m a
return ([a]
ys, [[a]]
yss')
deleteDups :: (Ord a) => [a] -> [a]
deleteDups :: [a] -> [a]
deleteDups = [a] -> [a]
forall a. Eq a => [a] -> [a]
deleteAdjDups ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Ord a => [a] -> [a]
sort
deleteDupsBy :: (a -> a -> Ordering) -> [a] -> [a]
deleteDupsBy :: (a -> a -> Ordering) -> [a] -> [a]
deleteDupsBy cmp :: a -> a -> Ordering
cmp = (a -> a -> Bool) -> [a] -> [a]
forall a. (a -> a -> Bool) -> [a] -> [a]
deleteAdjDupsBy a -> a -> Bool
eq ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy a -> a -> Ordering
cmp
where
eq :: a -> a -> Bool
eq a :: a
a b :: a
b = a -> a -> Ordering
cmp a
a a
b Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
EQ
deleteAdjDups :: (Eq a) => [a] -> [a]
deleteAdjDups :: [a] -> [a]
deleteAdjDups = (a -> a -> Bool) -> [a] -> [a]
forall a. (a -> a -> Bool) -> [a] -> [a]
deleteAdjDupsBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
deleteAdjDupsBy :: (a -> a -> Bool) -> [a] -> [a]
deleteAdjDupsBy :: (a -> a -> Bool) -> [a] -> [a]
deleteAdjDupsBy _ [] = []
deleteAdjDupsBy eq :: a -> a -> Bool
eq xs :: [a]
xs@(x :: a
x:_) =
a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ((a, a) -> a) -> [(a, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a, a) -> a
forall a b. (a, b) -> a
fst (((a, a) -> Bool) -> [(a, a)] -> [(a, a)]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> ((a, a) -> Bool) -> (a, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Bool) -> (a, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> Bool
eq) ([(a, a)] -> [(a, a)]) -> [(a, a)] -> [(a, a)]
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [(a, a)]
forall a b. [a] -> [b] -> [(a, b)]
zip ([a] -> [a]
forall a. [a] -> [a]
tail [a]
xs) [a]
xs)