[Haskell-cafe] Re: (flawed?) benchmark : sort

[John Meacham]

Note that even if you wanted Eq to mean observational equality, you
still can't perform that kind of reordering or 'sort' optimizations
without running into trouble. for a not contrived at all example:

data Id = Id { idIdent :: Int, idFreeVarCache :: [Id] }

instance Eq Id where
        x == y = idIdent x == idIdent y

now, this type represents an identifier in a language that is annotated
with the free variables it contains. Note that the Eq instance really
does declare observational equality here, the free var cache is only a
copy of what is in the definition of the Id. now consider the id for the
simple 

v1 = v1

all of the following are observationally the same

x = Id 1 [x]
x = Id 1 [Id 1 [x]]
x = Id 1 [Id 1 [Id 1 [Id 1 ... 

now, this is just fine, there is no way for a program to tell the
difference between them, but the difference is very important! the
second wastes space and the third is an honest to goodness space leak.
One has to rely on the fact Set.insert really replaces its element, max
x y where x == y is always y and other such things to reasonably reason
about the space usage of haskell programs, something that is hard enough
as it is without basics like 'sort' trying to be clever.


So, even if a == b always meant observational equality, specifying bias
is still very important. Even if you document it as 'unspecified' that
is fine (though it limits the use of said library), but it is part of
the API.

For the record I also always thought of 'Eq' as an arbitrary equality
relationship and 'Ord' as a compatible total ordering. It is not even
clear whether structural equality is meaningful for a lot of types, even
though they might have a 'natural' equality relationship.


        John


-- 
John Meacham - ⑆repetae.net⑆john⑈