“Illegal type synonym family application in instance” with functional dependency

Question

I have a multi-parameter typeclass with a functional dependency:

class Multi a b | a -> b

I also have a simple, non-injective type synonym family:

type family Fam a

I want to write an instance of Multi that uses Fam in the second parameter, like this:

instance Multi (Maybe a) (Fam a)

However, this instance is not accepted. GHC complains with the following error message:

error:
  • Illegal type synonym family application in instance: Fam a
  • In the instance declaration for ‘Multi (Maybe a) (Fam a)’

Fortunately, there is a workaround. I can perform a usual trick for moving a type out of the instance head and into an equality constraint:

instance (b ~ Fam a) => Multi (Maybe a) b

This instance is accepted! However, I got to thinking, and I started to wonder why this transformation could not be applied to all instances of Multi. After all, doesn’t the functional dependency imply that there can only be one b per a, anyway? In this situation, it seems like there is no reason that GHC should reject my first instance.

I found GHC Trac ticket #3485, which describes a similar situation, but that typeclass did not involve a functional dependency, so the ticket was (rightfully) closed as invalid. In my situation, however, I think the functional dependency avoids the problem described in the ticket. Is there anything I’m overlooking, or is this really an oversight/missing feature in GHC?

Judson

It'd be nice to have a self-contained example to be able to explore hypotheses when trying to answer your question. – Bekelja

@Bekelja Do you mean a self-contained practical example? The code in my question, short as it may be, should compile. – Judson

I think you've got it right. Ordinarily your second instance would be at risk of overlapping but here the fundep saves you, as you point out. I suspect the reason it hasn't been implemented in GHC is because one could argue that it's a counterintuitive/unexpected feature, which is only useful in specific situations, and which has a straightforward workaround. (To get a definitive answer you'd have to ask a GHC developer, though.) – Fanfaron

I’ve opened GHC ticket #14046 to track this issue. I’ll probably delete this question if the answer is simply “because it isn’t implemented that way”. – Judson

Please don't delete the question for such a reason. – Clinandrium

Also, some people would really like to make stuff like that actually work. The main impediments have to do with evil overlap and non-termination. – Clinandrium

@Clinandrium I’m not sure this question can be answer all that usefully if there really isn’t anything wrong with my suggestion, and this question has accumulated a downvote and a close vote. Anyway, IIUC, “evil overlap” isn’t a problem here due to the fundep, and “non-termination” is already allowed via UndecideableInstances, so I’m not sure why that would be any different here, either. – Judson

You have a functional dependency a -> b, but I don't find evidence that (Maybe a) -> (Fam a). Is that part of the culprit? – Solange

(Addressing Miao ZhiCheng, but not @'ing them because this is over a year later...) The fundep is satisfied. Maybe a -> a because Maybe is injective, and a -> Fam a because Fam is a type family. – Mccammon

Answer 1

Based on the comments I think that the problem why the first instance Multi (Maybe a) (Fam a) does not work and if the second one is due to the memory allocation why when you implement this solution it works

instance (b ~ Fam a) => Multi (Maybe a) b

because in this one you are moving (b ~ Fam a) to Multi (Maybe a) where b remains as a reserve

but that's my thinking

Wanigan

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Glissade