Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)

[Roman Leshchinskiy]

Adrian Hey wrote:
> 
> I would ask for any correct Eq instance something like the law:
>   (x==y) = True implies x=y (and vice-versa)
> which implies f x = f y for all definable f
> which implies (f x == f y) = True (for expression types which are
> instances of Eq). This pretty much requires structural equality
> for concrete types. For abstract types you can do something different
> provided functions which can give different answers for two "equal"
> arguments are not exposed.

How do you propose something like this to be specified in the language 
definition? The report doesn't (and shouldn't) know about abstract 
types. It only talks about things which are exported and things which 
are not. The distinction between implementation modules and client 
modules is made by the programmer, not by the language. So you can 
either require your law to hold everywhere, which IMO isn't a good idea, 
or you don't require it to hold. From the language definition point of 
view, I don't see any middle ground here.

Also, when you talk about definable functions, do you include things 
like I/O? What if I want to store things (such as a Set) on a disk? If 
the same abstract value can have multiple representations, do I have to 
convert them all to some canonical representation before writing them to 
a file? This might be rather slow and is, IMO, quite unnecessary.

 From a more philosophical points of view, I'd say that the appropriate 
concept of equality depends a lot on the problem domain. Personally, I 
quite strongly disagree with restricting Eq instances in the way you 
propose. I have never found much use for strict structural equality (as 
opposed to domain-specific equality which may or may not coincide with 
the structural one).

> On the subject of ambiguity, bugs and maxima, I see we have in Data.List
> 
> [...]
> 
> So I believe I'm correct in saying that maximumBy returns the last
> of several possible maximum elements of the list. This obviously
> needs specifying in the Haddock.
> 
> Because maximumBy documentation is ambiguous in this respect, so is the
> overloaded maximum documentation. At least you can't figure it out from
> the Haddock.

Why not simply say that maximumBy returns some maximum element from the 
list but it's not specified which one? That's how I always understood 
the spec. Code which needs a particular maximum element can't use 
maximumBy but such code is rare. I don't see how this is ambiguous, it 
just leaves certain things unspecified which is perfectly ok.

Roman