{-# LANGUAGE CPP #-}{-# LANGUAGE BangPatterns #-}
#ifdef __GLASGOW_HASKELL__
{-# LANGUAGE Trustworthy #-}
#endif
------------------------------------------------------------------------------- |-- Module : Data.Containers.ListUtils-- Copyright : (c) Gershom Bazerman 2018-- License : BSD-style-- Maintainer : libraries@haskell.org-- Portability : portable---- This module provides efficient containers-based functions on the list type.---- In the documentation, \(n\) is the number of elements in the list while-- \(d\) is the number of distinct elements in the list. \(W\) is the number-- of bits in an 'Int'.---- @since 0.6.0.1-----------------------------------------------------------------------------moduleData.Containers.ListUtils(nubOrd ,nubOrdOn ,nubInt ,nubIntOn )whereimportData.Set (Set )importqualifiedData.Set asSetimportqualifiedData.IntSet asIntSetimportData.IntSet (IntSet )
#ifdef __GLASGOW_HASKELL__
importGHC.Exts(build)
#endif
-- *** Ord-based nubbing ***-- | \( O(n \log d) \). The @nubOrd@ function removes duplicate elements from a-- list. In particular, it keeps only the first occurrence of each element. By-- using a 'Set' internally it has better asymptotics than the standard-- 'Data.List.nub' function.---- ==== Strictness---- @nubOrd@ is strict in the elements of the list.---- ==== Efficiency note---- When applicable, it is almost always better to use 'nubInt' or 'nubIntOn'-- instead of this function, although it can be a little worse in certain-- pathological cases. For example, to nub a list of characters, use---- @ nubIntOn fromEnum xs @---- @since 0.6.0.1nubOrd ::Orda =>[a ]->[a ]nubOrd :: forall a. Ord a => [a] -> [a]
nubOrd =(a -> a) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
nubOrdOn a -> a
forall a. a -> a
id{-# INLINEnubOrd #-}-- | The @nubOrdOn@ function behaves just like 'nubOrd' except it performs-- comparisons not on the original datatype, but a user-specified projection-- from that datatype.---- ==== Strictness---- @nubOrdOn@ is strict in the values of the function applied to the-- elements of the list.---- @since 0.6.0.1nubOrdOn ::Ordb =>(a ->b )->[a ]->[a ]-- For some reason we need to write an explicit lambda here to allow this-- to inline when only applied to a function.nubOrdOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
nubOrdOn a -> b
f =\[a]
xs ->(a -> b) -> Set b -> [a] -> [a]
forall b a. Ord b => (a -> b) -> Set b -> [a] -> [a]
nubOrdOnExcluding a -> b
f Set b
forall a. Set a
Set.empty [a]
xs {-# INLINEnubOrdOn #-}-- Splitting nubOrdOn like this means that we don't have to worry about-- matching specifically on Set.empty in the rewrite-back rule.nubOrdOnExcluding ::Ordb =>(a ->b )->Set b ->[a ]->[a ]nubOrdOnExcluding :: forall b a. Ord b => (a -> b) -> Set b -> [a] -> [a]
nubOrdOnExcluding a -> b
f =Set b -> [a] -> [a]
go wherego :: Set b -> [a] -> [a]
go Set b
_[]=[]go Set b
s (a
x :[a]
xs )|b
fx b -> Set b -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set b
s =Set b -> [a] -> [a]
go Set b
s [a]
xs |Bool
otherwise=a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:Set b -> [a] -> [a]
go (b -> Set b -> Set b
forall a. Ord a => a -> Set a -> Set a
Set.insert b
fx Set b
s )[a]
xs where!fx :: b
fx =a -> b
f a
x 
#ifdef __GLASGOW_HASKELL__
-- We want this inlinable to specialize to the necessary Ord instance.{-# INLINABLE[1]nubOrdOnExcluding #-}{-# RULES-- Rewrite to a fusible form."nubOrdOn"[~1]forallf as s .nubOrdOnExcluding f s as =build(\c n ->foldr(nubOrdOnFB f c )(constNubOn n )as s )-- Rewrite back to a plain form"nubOrdOnList"[1]forallf as s .foldr(nubOrdOnFB f (:))(constNubOn [])as s =nubOrdOnExcluding f s as #-}nubOrdOnFB ::Ordb =>(a ->b )->(a ->r ->r )->a ->(Set b ->r )->Set b ->r nubOrdOnFB :: forall b a r.
Ord b =>
(a -> b) -> (a -> r -> r) -> a -> (Set b -> r) -> Set b -> r
nubOrdOnFB a -> b
f a -> r -> r
c a
x Set b -> r
r Set b
s |b
fx b -> Set b -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set b
s =Set b -> r
r Set b
s |Bool
otherwise=a
x a -> r -> r
`c` Set b -> r
r (b -> Set b -> Set b
forall a. Ord a => a -> Set a -> Set a
Set.insert b
fx Set b
s )where!fx :: b
fx =a -> b
f a
x {-# INLINABLE[0]nubOrdOnFB #-}constNubOn ::a ->b ->a constNubOn :: forall a b. a -> b -> a
constNubOn a
x b
_=a
x {-# INLINE[0]constNubOn #-}
#endif
-- *** Int-based nubbing ***-- | \( O(n \min(d,W)) \). The @nubInt@ function removes duplicate 'Int'-- values from a list. In particular, it keeps only the first occurrence-- of each element. By using an 'IntSet' internally, it attains better-- asymptotics than the standard 'Data.List.nub' function.---- See also 'nubIntOn', a more widely applicable generalization.---- ==== Strictness---- @nubInt@ is strict in the elements of the list.---- @since 0.6.0.1nubInt ::[Int]->[Int]nubInt :: [Int] -> [Int]
nubInt =(Int -> Int) -> [Int] -> [Int]
forall a. (a -> Int) -> [a] -> [a]
nubIntOn Int -> Int
forall a. a -> a
id{-# INLINEnubInt #-}-- | The @nubIntOn@ function behaves just like 'nubInt' except it performs-- comparisons not on the original datatype, but a user-specified projection-- from that datatype. For example, @nubIntOn 'fromEnum'@ can be used to-- nub characters and typical fixed-with numerical types efficiently.---- ==== Strictness---- @nubIntOn@ is strict in the values of the function applied to the-- elements of the list.---- @since 0.6.0.1nubIntOn ::(a ->Int)->[a ]->[a ]-- For some reason we need to write an explicit lambda here to allow this-- to inline when only applied to a function.nubIntOn :: forall a. (a -> Int) -> [a] -> [a]
nubIntOn a -> Int
f =\[a]
xs ->(a -> Int) -> IntSet -> [a] -> [a]
forall a. (a -> Int) -> IntSet -> [a] -> [a]
nubIntOnExcluding a -> Int
f IntSet
IntSet.empty [a]
xs {-# INLINEnubIntOn #-}-- Splitting nubIntOn like this means that we don't have to worry about-- matching specifically on IntSet.empty in the rewrite-back rule.nubIntOnExcluding ::(a ->Int)->IntSet ->[a ]->[a ]nubIntOnExcluding :: forall a. (a -> Int) -> IntSet -> [a] -> [a]
nubIntOnExcluding a -> Int
f =IntSet -> [a] -> [a]
go wherego :: IntSet -> [a] -> [a]
go IntSet
_[]=[]go IntSet
s (a
x :[a]
xs )|Int
fx Int -> IntSet -> Bool
`IntSet.member` IntSet
s =IntSet -> [a] -> [a]
go IntSet
s [a]
xs |Bool
otherwise=a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:IntSet -> [a] -> [a]
go (Int -> IntSet -> IntSet
IntSet.insert Int
fx IntSet
s )[a]
xs where!fx :: Int
fx =a -> Int
f a
x 
#ifdef __GLASGOW_HASKELL__
-- We don't mark this INLINABLE because it doesn't seem obviously useful-- to inline it anywhere; the elements the function operates on are actually-- pulled from a list and installed in a list; the situation is very different-- when fusion occurs. In this case, we let GHC make the call.{-# NOINLINE[1]nubIntOnExcluding #-}{-# RULES"nubIntOn"[~1]forallf as s .nubIntOnExcluding f s as =build(\c n ->foldr(nubIntOnFB f c )(constNubOn n )as s )"nubIntOnList"[1]forallf as s .foldr(nubIntOnFB f (:))(constNubOn [])as s =nubIntOnExcluding f s as #-}nubIntOnFB ::(a ->Int)->(a ->r ->r )->a ->(IntSet ->r )->IntSet ->r nubIntOnFB :: forall a r.
(a -> Int) -> (a -> r -> r) -> a -> (IntSet -> r) -> IntSet -> r
nubIntOnFB a -> Int
f a -> r -> r
c a
x IntSet -> r
r IntSet
s |Int
fx Int -> IntSet -> Bool
`IntSet.member` IntSet
s =IntSet -> r
r IntSet
s |Bool
otherwise=a
x a -> r -> r
`c` IntSet -> r
r (Int -> IntSet -> IntSet
IntSet.insert Int
fx IntSet
s )where!fx :: Int
fx =a -> Int
f a
x {-# INLINABLE[0]nubIntOnFB #-}
#endif