Clarify the conventions for parameterized classes

[langston-barrett]

The classes in this library generalize those in base in several ways, but the naming convention and module structure isn't consistent. In the following, I'll focus just on Eq* and Ord*, though similar comments apply elsewhere.

• Eq, Ord, etc. classes in base
  • parameter kind: Type
  • parameter constraints: n/a
  • kind polymorphic: n/a
  • type-level evidence: n/a
  • heterogeneous: no
• Eq1, Ord1, in Data.Functor.Classes
  • parameter kind: Type -> Type
  • kind polymorphic: no
  • parameter constraints: yes, Eq, Ord, etc.
  • type-level evidence: no
  • heterogeneous: yes
• EqF
  • parameter kind: k -> Type
  • kind polymorphic: yes
  • parameter constraints: none
  • type-level evidence: n/a
  • heterogeneous: no
• OrdF
  • parameter kind: k -> Type
  • kind polymorphic: yes
  • parameter constraints: none
  • type-level evidence: yes
  • heterogeneous: yes
• TestEquality
  • parameter kind: k -> Type
  • kind polymorphic: yes
  • parameter constraints: none
  • type-level evidence: yes
  • heterogeneous: yes
• PolyEq
  • parameter kinds: * and *
  • kind polymorphic: n/a
  • parameter constraints: none
  • type-level evidence: yes
  • heterogeneous: yes

to say nothing of TestEqualityFC and OrdFC!

In summary, three roughly five axes I identify above, some of which have somewhat associated naming conventions. It would be great if we could decide on something sensible for all of them and implement it consistently.

The current state of affairs is mostly the following suffix conventions

• F denotes something with parameter kind (k -> *)
• 1 denotes something with parameter kind *
• FC denotes something with parameter kinds (k -> *) and l

Generalizing from one example, it might be the case that the prefix Poly denotes something which is heterogeneous.

[langston-barrett]

To make matters even more complex, the "type-level evidence" axis has at least four positions: no evidence (Eq1), possible positive evidence (TestEquality), possible negative evidence (no examples), and always either positive or negative evidence (DecidableEq).

[joehendrix]

I think the state space of possible equality operations is quite large, and I don't know if it's feasible to have a systematic concise naming scheme.

For example, I just looked at DecidableEq and other negative information seems only useful for classes where two values being inequal implies their types are unequal, e.g., when there is at most one inhabitant of a type for each parameter. (Technically the function associated with decEq could fail to terminate or throw an exception, but then the class name is really confusing). I didn't see that captured in the documentation above.

[Ericson2314]

I think OrdF should probably be called TestOrdering or something, as it is closer to TestEquality than EqF? C.f. the classes in https://hackage.haskell.org/package/dependent-sum-0.6.2.0/docs/Data-GADT-Compare.html. For our DMap we use (Has Eq)[hackage.haskell.org/package/constraints-extras/docs/Data-Constraint-Extras.html], which is yet another point in the design space: homogeneous but constrained parameters. This is is optimal for maps in maps and (biased) pairs where the key is heterogeneously matched first, and the values need only be compared at possible indices of the key.