Error about wrong missing instance

[tomjaguarpaw]

Here's a puzzling one. I've made a mistake in the second clause of leftSkewed. The second argument should be Leaf n, not n. Therefore I really want the error "No instance for Num Tree", pointing to that mistake. Instead I get the error "No instance for Eq Tree" pointing to the 0 match in the first clause!

I think what has happened here is that the type checker has deduced that n :: Tree, and given that we're passing n - 1 to leftSkewed the argument to leftSkewed must be :: Tree. Then the 0 pattern requires an Eq Tree constraint. But I wish it would just bail out earlier and say that it can't find a Num instance for Tree!

data Tree = Branch Tree Tree | Leaf Int

leftSkewed 0 = Leaf 0
leftSkewed n = Branch (leftSkewed (n - 1)) n

[noughtmare]

I think what is happening is that like this:

-- due to the 0 pattern match
leftSkewed :: (Eq a, Num a) => a -> b
-- due to the Leaf 0 return
leftSkewed :: (Eq a, Num a) => a -> Tree
-- due to the Branch ... n return
leftSkewed :: (Eq Tree, Num Tree) => Tree -> Tree

Note that when the n - 1 was encountered we already had the Num a constraint due to the pattern match on the first line.

GHC doesn't use abductive reasoning (it doesn't take into account multiple sources of errors), so it does not use the n - 1 information as extra evidence.

Helium does use multiple sources of information like that (see these slides) and could perhaps give better error messages, but it would be difficult to retrofit that onto GHC.

[goldfirere]

I agree that the n - 1 isn't part of the problem, but I'm sympathetic to what you report.

After figuring out what's wrong with a program (that is, what constraints it cannot solve), GHC must then figure out which to report. Currently, if there are multiple errors of the same nature(*) with the same location, GHC reports only one of them, arbitrarily. In this particular case, the failure of Eq Tree and Num Tree both get reported on 0. The errors are of the same nature, and so GHC reports the Eq Tree failure. Interestingly, if you reverse the order of equations, GHC reports both errors, because the Num Tree error arises first on n - 1 and the Eq Tree error arises later, on the 0.

(*) GHC categorizes errors en route to reporting them. These categories are internal, and would be hard to predict as a user. But Eq Tree and Num Tree fall into the same category (unsurprisingly).

One easy-to-implement solution here would be to report all failed constraints that arise at the same point, when there are multiple. We could even likely do so in one error message. To wit:

Scratch.hs:65:12: error:
    • No instances for (Eq Tree, Num Tree) arising from the literal ‘0’
    • In the pattern: 0
      In an equation for ‘leftSkewed’: leftSkewed 0 = Leaf 0

Would that be an improvement? And what do you think of the two errors you get when the equations are reordered?

[tomjaguarpaw]

Ah, you're right, it's not to do with n - 1. It's because n is an argument to leftSkewed and also the second argument to Branch. Therefore the first argument to leftSkewed must be :: Tree.

I don't actually think my confusion is as much to do with seeing Num Tree as it is to do with not seeing the type that GHC has deduced for leftSkewed. If GHC said

I deduced the type of leftSkewed to be Tree -> Tree
There is no Num instance for Tree

then I think that would go a long way to solving my confusing. GHC new a lot more than it was telling me! Some trail of breadcrumbs leading back to the mistake would be helpful, although I appreciate this is not always easy (or maybe indeed possible) to provide.

[goldfirere]

If you were writing in an editor with HLS humming in the background, you would learn leftSkewed :: Tree -> Tree:

When I point at the error, I see this:

This begs a question: with respect to what environment should we be optimizing? That is, we here are trying to improve the user experience of programming in Haskell. Is our archetypical user in an IDE or on the command line? This choice has real consequences in what information we try to squeeze into error messages! I vote: in an IDE. Specifically, in VSCode with HLS, as that is, I believe, the most likely configuration for our newer users, who need our work here the most. Of course, improvements for other situations are welcome, too, but this ticket here is a case where a user of VSCode would plausibly not have had the problem our OP did.

[tomjaguarpaw]

Interesting! I do use an IDE of sorts (dante mode for emacs) but it doesn't have this feature. I also agree that optimising for IDE use makes sense. I don't think that showing that type signature on the command line would be a waste of space though.