# Proposal #2717: Add nubWith, nubOrd

apfelmus apfelmus at quantentunnel.de
Thu Oct 23 03:59:26 EDT 2008

```Mitchell, Neil wrote:
> Hi
>
>> Were we to keep it, do you have a better naming suggestion?
>
> [Warning: untested code]
>
> filterAccum :: (acc -> x -> (acc,Bool)) -> acc -> [x] -> (acc, [x])
> filterAccum f a [] = (a, [])
> filterAccum f a (x:xs) = (an, [x|b]++rest)
>    where (a2,b) = f a x
>          (an,rest) = filterAccum f a2 xs
>
> This follows the type of mapAccumL, and is more general than your
> function. You could change the utility function to be (acc -> x ->
> (acc,Maybe y)) to get a variant that is more general than both mapAccum
> and filterAccum.

In other words,

mapAccumL    = mapM
filterAccumL = filterM

when used with the state monad.

Concerning the proposal, I agree with Neil, +1 for  nubOrd  and -1 for
nubWith  . Adding  filterAccum  sounds reasonable but should be a
separate proposal.

The patch introduces two documentation errors concerning the asymptotic
complexity:  m  is *not* the number of duplicate elements but the number
of *unique* elements, i.e.  n  minus the number of duplicates.
Furthermore, the proposed documentation for  nubOrd  should mention what
nubOrd  actually does. I suggest changing it to:

Like 'nub', the 'nubOrd' function removes duplicate elements
from a list.

But while 'nub' only requires that two elements
can be tested for equality ('Eq a'), 'nubOrd' requires that
the elements can be ordered ('Ord a'). This allows the 'nubOrd'
implementation to be significantly faster; it runs in
/O(n log m)/ time where /n/ is the length of the list and
/m/ is the number of unique elements in that list.

Regards,
apfelmus

```