Fix FindElem while preserving error messages

This is a possible fix for #2. This reverts FindElem to have two arguments so it can be reused, and adds another typeclass to carry the contents of the error message (IfNotFound) in an isolated way. The incoherent instance makes it go away at the first sign of trouble, hopefully so that in the worst case it's as if there is no IfNotFound constraint.

TBH there doesn't seem to be a good solution for this issue. Ideally, GHC could be extended with a way to somehow annotate the Member class declaration with the custom error message in case a constraint with it cannot be resolved.

The given minimal example passes:

f :: Member (Error String) effs => Eff (Reader () : effs) ()
f = throwError "bam!"

Remove the constraint, and it fails, of course...

f :: Eff (Reader () : effs) ()
f = throwError "bam!"

... but with GHC's usual error message (it doesn't seem possible to put a custom error here).

    • No instance for (Data.OpenUnion.Internal.FindElem
                     (Error [Char]) effs)
    arising from a use of ‘throwError’

Make the effect list concrete, and it fails with the custom message.

f :: Eff '[Reader ()] ()
f = throwError "bam!"

Error:

    • ‘Error [Char]’ is not a member of the type-level list
    ‘'[Reader ()]’

This is clever, but also a little scary. I agree with your conclusion, though… I spent some time last night trying to figure out some solution to this, but it seemed impossible without some extremely naughty violations of coherence.

For future readers (including myself, after I’ve likely forgotten what the issue is), the reason this is so tricky is that there are two ways for an instance of a class to be in scope:

A top-level instance declaration can match, in which case the constraint is solved by simply inserting a reference to the relevant dictionary.
A local constraint can bring a dictionary into scope by deferring the instance selection to its caller, and an extra function argument is inserted to accept the dictionary from the calling context.

Solving a FindElem recursively walks a type-level list until it finds a matching element. If it makes its way through the entire list without finding a matching element, it fails, and freer-simple added an instance on the empty list to raise a custom type error.

Unfortunately, due to the way the FindElem instances recursively drill down through the list, by the time it reaches the empty list, it has “forgotten” the original list, so it can’t present it in its custom type error, which is less than ideal (it can only state that the effect wasn’t found). To alleviate that problem, freer-simple added an extra parameter to the FindElem class to “remember” the original list, allowing it to be used in the type error.

This works well when solving a constraint using the top-level instance declarations, since the top-level instances are defined on any list, so any list matches, and an instance is always selected. However, in the case of a local constraint, there’s a problem—the constraint solver picks a particular list to “remember” as the original one, and a dictionary is brought into scope that only works for that particular original list.

This is a sort of curious problem, since it introduces a desire for a sort of asymmetry between the selection of a top-level instance and the deference of an instance. We would like to be able to tell GHC “just completely ignore this typeclass parameter when selecting a local instance”, but my intuition is not good enough to fully anticipate what the implications of such a feature would be. It seems typeclass parameters are really the wrong way to carry this information, and what we really want is a more direct way to script the constraint solver in the case of FindElem constraints, but GHC 8’s custom type errors mechanism is relatively simple, and it does not allow us to do so.

lexi-lambda / freer-simple

Fix FindElem while preserving error messages #3