// In particular, it would be nice to be able to specialise based on the instances, as we do for [a] --> [Int], e.g.

RULES sum = sumInt :: [Int] -> Int

is fine in the current system. So I could imagine some nice specialisations based on say, the good old Ord:

RULES nub = nubOrd :: (Eq a, Ord a) => [a] -> [a]

which might use a Map, say.

I don't know how costly this instance matching would be. -- Don In principle I think you should be able to get constraint-specialized implementations right now, using Oleg's type-class overloaded (aka 2-polymorphic) functions (http://okmij.org/ftp/Haskell/poly2.txt). Some prototyping, not tested:

import Poly2 {- -- from Poly2: (these can also be expressed as `TypeCls'-Membership-instance -> feasable with deriving machinery?) type Fractionals = Float :*: Double :*: HNil type Nums = Int :*: Integer :*: AllOf Fractionals :*: HNil type Ords = Bool :*: Char :*: AllOf Nums :*: HNil type Eqs = AllOf (TypeCl OpenEqs) :*: AllOfBut Ords Fractionals :*: HNil -} data NubLabel -- Ord-specialized instance, guarded by Membership-Predicate instance GFN Z NubLabel (Member Ords) instance (Ord a) => Apply (GFnA Z NubLabel) [a] [a] where -- we get here if Guard succeded apply _ = Map.tolist . Map.fromListWith const -- default instance instance TypeCast pred Otherwise => GFN n NubLabel pred instance (Eq a) => Apply (GFnA n NubLabel) [a] [a] where apply _ = List.nub nub_opt xs = apply (GFn NubLabel) xs But it probably needs some deriving-infrastructure for the `TypeCls' member-predicate to make it feasible. BTW: rewriting rules being turing-complete, I'm wondering if theres some "freaky hackery" to be discovered, or yet going on? :>