Understanding the Replace class in GADTs for dummies

Learn
#1

I’m working through the GADTs for dummies tutorial and I’m having trouble understanding the Replace type class:

Another example is a class that replaces all occurrences of ‘a’ with ‘b’ in type ‘t’ and return the result as ‘res’:

class Replace t a b res
instance Replace t a a t
instance (Replace t a b res) => Replace [t] a b [res]
instance Replace t a b t

(Omitted a couple of instances for brevity.) I’m reading this as: A Replace [t] a b [t] matches the third line, for which the constraint matches the fourth line, resulting in Replace [t] a b [t]. A Replace [t] a a [t] also matches the third line, but for which the constraint matches the second line, resulting in Replace [t] a a [t]. Either I am not understanding how instances are selected, and/or that there is something about how the type replacement is encoded that I don’t get. Can someone break this down for me?

There’s also a paragraph about instance selection order:

In many other cases this automatic selection is not powerful enough and we are forced to use some artificial tricks or complain to the language developers. The two most well-known language extensions proposed to solve such problems are instance priorities, which allow us to explicitly specify instance selection order, and ‘/=’ constraints, which can be used to explicitly prohibit unwanted matches:

instance Replace t a a t
instance (a /= b) => Replace [t] a b [Replace t a b]
instance (a /= b, t /= [_]) => Replace t a b t

What extensions are being referred to here? There doesn’t seem to be any InstancePriorities.

#2

Unfortunately I think that article is confusing at best, dangerously misleading at worst.

The problems range from basic pedagogical weaknesses (one shouldn’t have to wade through type class contortions to learn about GADTs) to fundamental inaccuracies (see below). All I can suggest is trying to learn from a better resource but I don’t really have one to suggest. Perhaps the paper linked at the top of the Wiki page is a good idea?

One of the problems with the Haskell Wiki is that no one has the mandate to keep it up-to-date and accurate, nor does anyone have the authority to override the implicit wishes of the original author to keep the content available.
I have an issue tracking the quality of this page at https://github.com/tomjaguarpaw/tilapia/issues/96

Inaccuracies:

  • type class instances … are not checked in order. Instead, the most specific instance is automatically selected

    Normally you will get an overlapping instance error when you try to do this, and with good reason – it’s likely to lead to a great deal of confusing and possibly broken code (for example, an overlapping Ord instance can break a Data.Map.Map).

  • The two most well-known language extensions proposed to solve such problems are instance priorities, which allow us to explicitly specify instance selection order, and ‘/=’ constraints

    Unless I’ve slipped into some alternate timeline, GHC does not have /= constraints. Perhaps it used to have them, or Hugs has or had them. In any case, they sound like they will lead to a world of pain.

    GHC does have some facilities for disambiguating overlapping instances but unless you’re an expert who is willing to use her or his utmost ingenuity to avoid a world of pain, don’t use those.

1 Like
#3

Thanks, that’s very helpful. To be fair, I do think the “hypothetical extensions” add a useful perspective for getting into thinking at the type level, at least for the examples where it correctly translates to real Haskell.

To anyone looking for a GADT tutorial, I think this is a good one: https://en.m.wikibooks.org/wiki/Haskell/GADT

#4

Can you make that example more concrete? I don’t think this can happen without orphan instances (which can also lead to problems without overlapping instances). Edit: I guess there is a concrete example here: https://reddit.com/r/haskell/comments/7nre75/fixing_overlapping_instances/

GHC also does not have a mechanism for specifying selection order. So, I think both of those are still in the “suggestion” stage and not actually implemented yet. I agree that the language (e.g. “can” instead of “could”) and the code example are confusing, but I think a small change there could fix it.

#5

for example, an overlapping Ord instance can break a Data.Map.Map

Can you make that example more concrete? I don’t think this can happen without orphan instances

Maybe it was a poor example. The operative point is that GHC errors if you try to use an orphan overlapping instance. The example in the article just won’t work.

I think both of those are still in the “suggestion” stage and not actually implemented yet. I agree that the language (e.g. “can” instead of “could”) and the code example are confusing, but I think a small change there could fix it.

I’m not sure what you mean. The article says

The two most well-known language extensions proposed to solve such problems are instance priorities, which allow us to explicitly specify instance selection order, and ‘/=’ constraints, which can be used to explicitly prohibit unwanted matches

under the heading “Back to real Haskell - type classes” so it seems to me that it is clearly implying those extensions exist.