>By "incompatible" I mean that you need parallel specualative evaluation
>to implement it. So a truly polymorphic seq is out. That takes us back
>to an overloaded version, except that seq couldn't have an instance for
>(unlifted) tuples!
At the risk of repeating myself: this is exactly right. A polymorphic
function should need to know nothing about the type in which it is polymorphic.
Many implementations behave quite differently when evaluating an integer, say,
to evaluating a list. So operationally, seq does not reflect the usual intuition
about polymorphism.
Even worse (from the point of view of semantics), a "polymorphic" seq
cripples parametricity (theorems for free). Already, because fix is
polymorphic, the relations in the parametricity theorem are forced to be
strict which throws away some interesting theorems. If seq were
polymorphic, then the relations would have to be bottom-reflecting also
(only bottom related to bottom) which throws away a vast number of theorems.
(Even so it's not as bad as having equality polymorphic which forces the
relations to be one-to-one making parametricity almost entirely useless).
Using overloading solves the problem neatly.
class Str a where
seq : a -> a
instance Str [a] where
seq [] = []
seq (x:xs) = x:xs
for example. Str can be added to the collection of things which are derivable,
and everybody can sleep well at night.
John.
