Wed, 28 Jun 2000 04:36:01 -0700, Simon Peyton-Jones <[EMAIL PROTECTED]> pisze:
> Why can't you have
>
> class Eq a => Member c a | c -> a where member :: Eq a => c -> a -> Bool
>
> OK, so then sequences require Eq on elements, but since Member is a
> superclass of sequence, every sequence has a member method,
> and so a must be in Eq anyway.
Only the member method requires Eq, others do not.
My example was unnecessarily complicated:
class Sequence s a where
single :: a -> s a
member :: Eq a => s a -> a -> Bool
instance Sequence [] a where
single x = [x]
member xs x = x `elem` xs
Everything is well defined and as generic as it should, only GHC does
not like it.
Why the element type is in the class head? Because not all sequences
are fully polymorphic:
newtype PS a = PS PackedString
instance Sequence PS Char where
single x = packString [x]
member xs x = x `elemPS` xs
------------------------------------------------------------------------
An issue independent of this problem. Another possibility is:
class Sequence s a | s -> a where
single :: a -> s
member :: Eq a => s -> a -> Bool
instance Sequence [a] a where ...
instance Sequence PackedString Char ...
It has the advantage that PackedString does not require an artificial
argument, but a disadvantage is that Sequence cannot contain map that
changes the type of the element. With the previous approach it can,
although not as naturally as a class of fully polymorphic sequences:
class Sequence s a where
...
map :: Sequence s b => (a -> b) -> s a -> s b
Although this type is not symmetric wrt. a and b as seen from inside
(when we define instances) and could be written in the opposite way,
it is symmetric outside.
A definition for polymorphic sequences is not problematic and
can depend on particular implementation of both input and output
value. Unfortunately it's not that easy for PackedString:
instance Sequence PS char where
...
map = ... -- We must provide a function of the type
-- Sequence PS b => (Char -> b) -> PS Char -> PS b
Even if we know that it will be used only for b = Char, because
otherwise the result is not a Sequence and cannot be used in any
interesting way, the definition must be polymorphic wrt. b and we
can only use generic methods to construct the result.
The only way to use mapPS :: (Char -> Char) -> PackedString -> PackedString
through the common map interface is by {-# RULES #-} or unsafeCoerce#.
The overall situation looks a bit ugly. Any ideas?
------------------------------------------------------------------------
If we could live without PackedString being a Sequence, we could make
it nice and symmetric by having only fully polymorphic sequences.
It would lead to simpler contexts needed for particular pieces of code.
If only we had local universal quantification in contexts...
class Sequence s where
single :: a -> s a
member :: Eq a => s a -> a -> Bool
I want to reuse member for collections. Collections are not fully
polymorphic, so even if we define a class of collections over type
constructors instead of over applied types:
class Coll c a where
insert :: a -> c a -> c a
member :: c a -> a -> Bool
and want to move member to a common superclass, it must be constrained
by the type of elements, because individual collection instances can
require arbitrary restrictions on it (e.g. Ord a):
class Member c a where
member :: Eq a => c a -> a -> Bool
class Member c a => Coll c a where
insert :: a -> c a -> c a
For sequences it cannot have any restrictions other than Eq, because
being a sequence cannot depend on the element type:
class (forall a. Member s a) => Sequence s where
single :: a -> s a
Ah, is that possible?
------------------------------------------------------------------------
In fact most classes will constrain applied types instead of type
constructors, because the type is not always the last argument of the
collection type. Classes will constrain type constructors only when
needed for cases like map, i.e. sequence elements and association
map values.
class Lookup c k a | c -> k a where
(!) :: c -> k -> a
lookupMaybe :: c -> k -> Maybe a
-- Or maybe: (!?) :: c -> k -> Maybe a -- :-)
-- Variant with constrained element types:
class Lookup (s a) Int a => Sequence s a where ...
class Lookup c a a => Coll c a where ...
class Lookup (m v) k v => AssocMap m k v where ...
-- Variant with fully polymorphic classes:
class (forall a. Lookup (s a) Int a) => Sequence s where ...
class Lookup c a a => Coll c a where ...
class (forall v. Lookup (m v) k v) => AssocMap m k where ...
Functional dependencies are really important in this case.
--
__("< Marcin Kowalczyk * [EMAIL PROTECTED] http://qrczak.ids.net.pl/
\__/ GCS/M d- s+:-- a23 C+++$ UL++>++++$ P+++ L++>++++$ E-
^^ W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP+ t
QRCZAK 5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-
