Proposal #2717: Add nubWith, nubOrd
apfelmus at quantentunnel.de
Thu Oct 23 03:59:26 EDT 2008
Mitchell, Neil wrote:
>> 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
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.
More information about the Libraries