Constructor Class/Functor for a constrained element type?

This is a FAQ -- for example this answer; or Section 3.2 'A Constraint for Well-Formed Applications' in 'Partial Type Constructors' [Jones, Morris, Eisenberg 2020]. And the frequent answer is you can't do it. I think I kinda have done it. (But it ain't pretty.)

data Set a = NilSet | ConsSet a (Set a)    deriving (Eq, Show, Read)
mySet = ConsSet 'a' $ ConsSet 'b' $ ConsSet 'A' NilSet

My Set type should not have duplicate elements. So if I fmap toUpper mySet, I want to avoid two 'A's. Then consider

Addit: in response to comments. (Original code retained below, for reference.)

@Carl [the restriction in the Language Report] applies only to constraints on exactly the type u.

Yes I didn't even try "exactly type u", because I assumed it would be banned. But ... I can now dispose of @Fyodor's line of questions about whether there might be some residual restrictions:

The minimal language extensions I need are MultiParamTypeClasses, FlexibleInstances -- which I'm relaxed about; they're long-standing/stable/well-tried. I don't even need FunctionalDependencies. And this also works in Hugsmode.

class Functorish2 f  where
  fmapish2 :: (FConstr2 f a b) => (a -> b) -> f a -> f b    -- huh? compiles ok
instance Functorish2 f  where                               -- needs FlexibleInstances
  fmapish2 = fmapish3

class FConstr2 f a b  where fmapish3 :: (a -> b) -> f a -> f b

-- IOW same signature as fmap. This gives me a free hand.

instance (Eq b) => FConstr2 Set a b  where                  -- needs FlexibleInstances
  fmapish3 f NilSet = NilSet
  fmapish3 f (ConsSet x xs) = uqCons (f x) (fmapish3 f xs)
    where uqCons fx xss | fElem fx xss = xss
                        | otherwise    = ConsSet fx xss
          fElem fx (ConsSet y ys) = fx == y || fElem fx ys
          fElem fx NilSet         = False

And indeed fmapish2 toUpper mySet squishes out the duplicates. More realistically, a Set implementation would use a BST or hashmap or some such, so the constraint on elements would be more complex than Eq b. Never the less, seems I can add any constraints on the elements of the Set.

Or is there a catch? Is this a fault I could abuse to cause type-unsafety? Presumably the Language Report restriction (next para) doesn't want to allow fmapish2 to be less polymorphic than the class head would indicate.

The surprise is the line I've marked "huh?". According to the 2010 Language Report Section 4.3.1 'Class Declarations' constraints on method signatures "The cxi may constrain only w-bar; in particular, the cxi may not constrain u." -- the u being the tyvar(s) from the class head. (BTW the deriving (Eq) on Set isn't essential.)

The second surprise is that not only does this work in GHC (8.10.2, 7.10), it also works in Hugs (2006).

(Code from original q.)

{-# LANGUAGE  MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, 
          UndecidableInstances   #-}

import Data.Char                                          -- toUpper

class Functorish f  where
  fmapish :: (FConstr (f b)) => (a -> b) -> f a -> f b    -- huh? compiles ok

class FConstr fb  where fMerge :: fb -> fb -> fb

instance Functorish Set  where
  fmapish f NilSet         = NilSet
  fmapish f (ConsSet x xs) = fMerge (ConsSet (f x) NilSet) (fmapish f xs)

instance (Eq a) => FConstr (Set a)  where            
  fMerge (ConsSet x NilSet) yss | fElem x yss = yss
                                | otherwise   = ConsSet x yss
        where fElem x (ConsSet y ys) = x == y || fElem x ys
              fElem x NilSet         = False

Solution

The surprise is the line I've marked "huh?". According to the 2010 Language Report Section 4.3.1 'Class Declarations' constraints on method signatures "The cxi may constrain only w-bar; in particular, the cxi may not constrain u." -- the u being the tyvar(s) from the class head. (BTW the deriving (Eq) on Set isn't essential.)

Turning my comment into an answer, I think the relevant GHC extension is called ConstrainedClassMethods which is implied by MultiParamTypeClasses.

For example, this code doesn't compile:

class Test a where
  test :: Eq a => a -> a -> Bool

You'll get the error:

Test.hs:2:3: error:
    • Constraint ‘Eq a’ in the type of ‘test’
        constrains only the class type variables
      Enable ConstrainedClassMethods to allow it
    • When checking the class method:
        test :: forall a. (Test a, Eq a) => a -> a -> Bool
      In the class declaration for ‘Test’
  |
2 |   test :: Eq a => a -> a -> Bool
  |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

If you enable ConstraintClassMethods then it does compile.

In your case ConstraintedClassMethods is implied by MultiParamTypeClasses, which also fixes the error in this test example.

But even without that, it would compile, because the FConstr2 f a b constraint constrains more than just the variables mentioned in the instance head. See this example from the linked GHC guide, in particular op5:

class C a where
  op3 :: Eq a => a -> a    -- Rejected: constrains class variable only
  op4 :: D b => a -> b     -- Accepted: constrains a locally-quantified variable `b`
  op5 :: D (a,b) => a -> b -- Accepted: constrains a locally-quantified variable `b`

So the constraint FConstr2 f a b would also be accepted, because it constrains locally-quantified variables a and b.