Note [Casts and coercions in type comparision]

GHC/Core/TyCo/Compare.hs:83 compiler

As (EQTYPE) in Note [Non-trivial definitional equality] says, our
general plan, implemented by `fullEq`, is:
 (1) ignore both casts and coercions when comparing types,
 (2) instead, compare the /kinds/ of the two types,
     as well as the types themselves

If possible we want to avoid step (2), comparing the kinds; doing so involves
calling `typeKind` and doing another comparision.

When can we avoid doing so?  Answer: we can certainly avoid doing so if the
types we are comparing have no casts or coercions.  But we can do better.
Consider
    eqType (TyConApp T [s1, ..., sn]) (TyConApp T [t1, .., tn])
We are going to call (eqType s1 t1), (eqType s2 t2) etc.

The kinds of `s1` and `t1` must be equal, because these TyConApps are well-kinded,
and both TyConApps are headed by the same T. So the first recursive call to `eqType`
certainly doesn't need to check kinds. If that call returns False, we stop. Otherwise,
we know that `s1` and `t1` are themselves equal (not just their kinds). This
makes the kinds of `s2` and `t2` to be equal, because those kinds come from the
kind of T instantiated with `s1` and `t1` -- which are the same. Thus we do not
need to check the kinds of `s2` and `t2`. By induction, we don't need to check
the kinds of *any* of the types in a TyConApp, and we also do not need to check
the kinds of the TyConApps themselves.

Conclusion:

* casts and coercions under a TyConApp don't matter -- even including type synonyms

* In step (2), use `hasCasts` to tell if there are any casts to worry about. It
  does not look very deep, because TyConApps and FunTys are so common, and it
  doesn't allocate.  The only recursive cases are AppTy and ForAllTy.

Alternative implementation.  Instead of `hasCasts`, we could make the
generic_eq_type function return
  data EqResult = NotEq | EqWithNoCasts | EqWithCasts
Practically free; but stylistically I prefer useing `hasCasts`:
  * `generic_eq_type` can just uses familiar booleans
  * There is a lot more branching with the three-value variant.
  * It separates concerns.  No need to think about cast-tracking when doing the
    equality comparison.
  * Indeed sometimes we omit the kind check unconditionally, so tracking it is just wasted
    work.
I did try both; there was no perceptible perf difference so I chose `hasCasts` version.

References 1

Referenced by 1