Is there a good reason why `deleteBy` does not have its most general type?

Question

The Haskell 2010 Language Report states in section 20.10.1.1 that:

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]

In fact, the implementation in the GHC library would allow

deleteBy :: (b -> a -> Bool) -> b -> [a] -> [a]

but actually restricts the type to the former one with the annotation.

Hence, one cannot say, for instance:

foo = deleteBy fsteq 42 [(43, "foo"), (44, "bar"), (42, "baz")] where
    fsteq a (b,_) = a == b

because Int is not the same as (Int, String).

Is there any good reason for this?

The reason I am asking is that, if there is no good reason for it, I would include deleteBy with the more general type in the Frege port of Data.List I am currently doing. But maybe I am overlooking something?

EDIT: As @hammar pointed out, this applies to other xxxBy functions also.

Legibility

Answer 1

Generalising the type of deleteBy violates the standard in a very practical way: perfectly valid Haskell programs become invalid, thanks to unresolved overloading.

Here's a demonstration:

class (Num a) => Magic a where
  magic :: a -> Bool

sameMagic :: (Magic a, Magic b) => a -> b -> Bool
sameMagic a b = magic a == magic b

test :: (Magic a) => [a]
test = deleteBy sameMagic 42 [1234]

In Haskell, this program is perfectly well-typed; deleteBy's restricted type ensures that the 42 is guaranteed to have the same type as the 1234. With the generalised deleteBy, this is not the case, and so the type of 42 is ambiguous, making the program invalid. (If you want a less contrived example, consider a function which compares two Integral values with toInteger.)

So, perhaps there is no good reason for this restricted type (although if deleteBy is to be generalised, I would prefer hammar's version to your proposal), but generalising it does violate the standard, and it can break valid programs.

Starlastarlene

That's the sort of insightful comments I was looking for. Gives me something to think about. – Legibility

This is a very insightful answer! – Godric

But shouldn't 42 be resolved to Integer by type-defaulting rules? – Arlie

@Arlie Lazy Polymorphism? – Chancroid

Answer 2

I guess it's for symmetry with the other xxxBy functions. However, your type is still needlessly specific. I would prefer this.

deleteBy :: (a -> Bool) -> [a] -> [a]

You could then write your example using partial application:

foo = deleteBy (fsteq 42) [(43, "foo"), (44, "bar"), (42, "baz")] where
    fsteq a (b,_) = a == b

Exudate

Except that filter would delete all equal elements, where deleteBy must delete the first one only. – Legibility

@Ingo: Oops! You're absolutely right. filter will not do the job here. – Exudate

Sure, there are ways around it, but you see, the objective is to stick to the standard (Haskell 2010, in this case). The question being if it violates the standard if one is a bit more general. – Legibility

@Legibility "Does it violate the standard if one is a bit more general"? In technicality, yes. In practicality, no (imho). – Jacobsen

Answer 3

Ingo,

in your original question, it seems you're asking why Haskell Report specifies deleteBy like this. So if there's no strong reason, you could use a different definition in Frege (implying you don't care about Haskell Report conformance).

As Hammar says, it's like the other xxxBy functions: delete uses (==), deleteBy takes a predicate that is like (==): of type (a -> a -> Bool) and assumed to be an equivalence relation. While the type system cannot check if the predicate is really an equivalance relation, it is the function contract. So it's very easy to understand what xxxBy means if you know what xxx means. And maybe it's not the case for deleteBy, but in some cases an implementation might be optimized under the assumption the predicate has the specified properties (equivalence relation or total order, etc).

But in your comment to Hammar's answer, you ask whether the more general implementation would violate the report. Well, if the type is different then it is literally a violation, right? Since programs that shouldn't compile according to the report will be accepted by your compiler. So it gives rise to a portability problem: if your code uses the more general version, then it might not compile on another implementation that conforms to the specification. Besides, it does away with the equivalence relation requirement.

So if you want a more general function, why not simply define another function with a different name? For instance, deleteIf.

(I wanted to comment on Hammar's answer, but I can't so I wrote it here.)

Enidenigma