Proposal #2717: Add nubWith, nubOrd

[apfelmus]

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