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