Why Haskell's Data.List.deleteBy takes in input a comparison function (a -> a -> Bool) and a value instead of a predicate (a -> Bool)?

Question

I have a question related to Data.List and the signature of deleteBy. Ideally this function should take in input a predicate and delete the first element for which the predicate is true. Something like:

deleteBy :: (a -> Bool) -> [a] -> [a]
deleteBy p = go
    where go []                   = []
          go (x:xs) | p x         = xs
                    | otherwise   = x:go xs

Instead the function defined in the library takes both a predicate and a value:

deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy _  _ []        = []
deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys

It's easy to see that eq is always used with x as first argument and x is fixed in deleteBy, so there is no reason to get both eq and x instead of eq x. On contrary, by taking a predicate working on a single element you can pass predicates that don't compare two values, such as a function that works on a part of the type a or a trivial function like cons true. My question is: why deleteBy has been implemented in this way?

Relevant answers: http://stackoverflow.com/questions/9004937/is-there-a-good-reason-why-deleteby-does-not-have-its-most-general-type . Consistency with the type of `(==)` sounds like a plausible explanation. — duplode, Apr 10 '14 at 23:29

score 11 · Accepted Answer · answered Apr 10 '14 at 23:49

The deleteBy function is a generalization of delete, so it's helpful to take a look at delete first.

delete :: Eq a => a -> [a] -> [a]

delete takes a value Eq a => a, then deletes the first occurance of that value from the [a] using the (==) from the Eq instance.

As with all the *By functions in Data.List, the Eq constraint is removed and the programmer is required to provide their own replacement (==) function.

So removing the Eq constraint from delete and replacing it with the type of (==), namely a -> a -> Bool, gives you the type of deleteBy.

In other words, it's for consistency with the rest of the *By operations in Data.List.

Which all suggests `deleteBy` should be given in terms of the more general function. — dfeuer, Apr 10 '14 at 23:52

score 0 · Answer 2 · answered Apr 17 '14 at 13:49

As cdk and others point out. It is to generalize over the equality predicate.

The function you are asking for is 'delete elements in the list which match this predicate'. This is more akin to single element filter.

The deleteBy function is 'delete element x, but use this comparison operator instead of (==)'.

Why Haskell's Data.List.deleteBy takes in input a comparison function (a -> a -> Bool) and a value instead of a predicate (a -> Bool)?

2 Answers2