{-| Module      : Data.List.Duplicate
    Description : Group and delete duplicates from a list.
    Copyright   : (c) Preetham Gujjula, 2020
    License     : BSD3
    Maintainer  : pgujjula+list-utilities@protonmail.com
    Stability   : experimental

Group and delete duplicates from a list.
-}
module Data.List.Duplicate (
    -- * Grouping elements
      group
    , groupBy
    , groupAdj
    , groupAdjBy

    -- * Deleting duplicates
    , deleteDups
    , deleteDupsBy
    , deleteAdjDups
    , deleteAdjDupsBy
    ) where

import Control.Monad (guard)
import Data.List     (sort, sortBy, uncons)
import Data.Maybe    (fromMaybe)

{-| /O(n log(n))./ Group the equal elements of the list together, in sorted
    order.

    >>> group [1, 3, 2, 3, 2, 3]
    [[1], [2, 2], [3, 3, 3]]
    >>> group [1]
    [[1]]
    >>> group []
    []
-}
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

{-| /O(n log(n))./ Like 'group', with a custom comparison test. The grouping is
    stable, so if @x@, @y@ are in the same group, and @x@ appears before @y@ in
    the original list, then @x@ appears before @y@ in the group.

    >>> groupBy (comparing head) ["b1", "c1", "a1", "b2", "a2"]
    [["a1", "a2"], ["b1", "b2"], ["c1"]]
-}
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

{-| /O(n)./ Group adjacent elements that are equal. Works with infinite lists.
    Useful for grouping equal elements of a sorted list.

    >>> groupAdj [1, 3, 3, 3, 2, 2, 3]
    [[1], [3, 3, 3], [2, 2], [3]]
    >>> take 4 $ groupAdj $ concatMap (\x -> replicate x x) [1..]
    [[1], [2, 2], [3, 3, 3], [4, 4, 4, 4]]
    >>> groupAdj []
    []
    >>> groupAdj [1]
    [[1]]
-}
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
(==)

{-| /O(n)./ Like 'groupAdj', with a custom equality test.

    >>> groupAdjBy ((==) `on` head) ["a1", "a2", "b1", "c1", "a3", "a4"]
    [["a1", "a2"], ["b1"], ["c1"], ["a3", "a4"]]
-}
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')

{-| /O(n log(n))./ Delete duplicates from the list. Output is in sorted order.

    >>> deleteDups [3, 1, 1, 2, 1, 3]
    [1, 2, 3]
-}
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

{-| /O(n log(n))./ Like 'deleteDups', with a custom comparison test. First
    appearances are kept.

    >>> deleteDupsBy (comparing head) ["a1", "c1", "d1", "a2", "b1"]
    ["a1", "b1", "c1", "d1"]
-}
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

{-| /O(n)./ Delete adjacent duplicates from the list. Works with infinite lists.
    Useful for deleting duplicates from a sorted list. Remaining elements are in
    the same relative order.

    >>> deleteAdjDups [1, 3, 4, 4, 4, 3]
    [1, 3, 4, 3]
-}
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
(==)

{-| /O(n)./ Like 'deleteAdjDups', with a custom equality test. First appearances
    are kept.

    >>> deleteAdjDupsBy ((==) `on` head) ["a1", "a2", "b1", "b2", "a3", "a4"]
    ["a1", "b1", "a3]
-}
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)