Using ScopedTypeVariables to constrain fmap function argument

Question

I've got the following use-case: I'm building a custom AST. As an optimization for certain operations I'm doing on the AST, I've defined a list of children for an AST node thus:

data NodeChHolder a = NNode [a] -- For "normal" operators
                    | ACNode (MultiSet a) -- For operators that can be re-ordered and parenthesized arbitrarily
                    | NCNode -- Empty, no children

Now, I want to make this type a Functor. However, there's a problem because MultiSet requires its type parameter to be Ord. So, this didn't work:

instance Functor NodeChHolder where
  fmap f (NNode l) = NNode $ map f l
  fmap f (ACNode s) = ACNode $ MultiSet.map f s
  fmap _ NCNode = NCNode

I got an error saying that there's "no instance for Ord b arising from a use of MultiSet.map", which is fair.

To resolve this problem, I tried the following approach using the ScopedTypeVariables ghc extension. I thought that this would work similarly to how it works with types, but it appears typeclasses are different:

instance Functor NodeChHolder where
  fmap f (NNode l) = NNode $ map f l
  fmap (f :: (Ord a, Ord b) => a -> b) (ACNode s) = ACNode $ MultiSet.map f s
  fmap f (ACNode s) = NNode $ map f (MultiSet.toList s)
  fmap _ NCNode = NCNode

This also failed with the same error message. Next, I tried to change it a little, because to my understanding of forall from ScopedTypeVariables, it should have made sure that the a and b type variables that I'm using are the same as for fmap.

instance Functor NodeChHolder where
  fmap f (NNode l) = NNode $ map f l
  fmap (f :: forall a b. (Ord a, Ord b) => a -> b) (ACNode s) = ACNode $ MultiSet.map f s
  fmap f (ACNode s) = NNode $ map f (MultiSet.toList s)
  fmap _ NCNode = NCNode

The above didn't work, saying it "couldn't match b with b1", because they are both "rigid type variables". I thought this was because I needed to actually declare type parameters a and b for fmap itself, so I used the InstanceSigs extension as well and ended up with

instance Functor NodeChHolder where
  fmap :: (a -> b) -> NodeChHolder a -> NodeChHolder b
  fmap f (NNode l) = NNode $ map f l
  fmap (f :: forall a b. (Ord a, Ord b) => a -> b) (ACNode s) = ACNode $ MultiSet.map f s
  fmap f (ACNode s) = NNode $ map f (MultiSet.toList s)
  fmap _ NCNode = NCNode

But I still got the same error about the rigid type variables.

At this point I don't even know if what I'm trying to do is even possible! Should I give up on trying to make this a functor altogether? With InstanceSigs, I could probably do fmap :: Ord b => (a -> b) -> NodeChHolder a -> NodeChHolder b, which would fit my usecase, but that would no longer be a true functor...

chi chi · Accepted Answer · 2018-05-11T08:55:10

You can not do this using the regular Functor class. Such class has a method

fmap :: Functor f => (a -> b) -> f a -> f b

which does not put any constraints on a and b. This requires any instance to work with any choice for a and b. Indeed, if instances were allowed to put additional requirements, then fmap could not have the type above.

You could however used another type class to represent a constrained functor. There is one in the package constrained-monads, which allows the following code.

import qualified Control.Monad.Constrained as C

data MultiSet a = Whatever -- stub

multiSet_map :: Ord b => (a -> b) -> MultiSet a -> MultiSet b
multiSet_map = undefined -- stub

data NodeChHolder a = NNode [a]
                    | ACNode (MultiSet a)
                    | NCNode

instance C.Functor NodeChHolder where
  type Suitable NodeChHolder b = Ord b
  fmap f (NNode l) = NNode $ map f l
  fmap f (ACNode s) = ACNode $ multiSet_map f s
  fmap _ NCNode = NCNode

Using ScopedTypeVariables to constrain fmap function argument

1 Answers