How can I track down GHC "Couldn't match expected type" errors?

Question

This Haskell code contains a type error, a dumb mistake on my part that will be obvious once you see it.

I figured it out, but it was hard. My question is: How should I have gone about diagnosing this?

class Cell c where
  start :: c
  moves :: c -> [c]

score :: Cell c => (c -> Float) -> Int -> c -> Float
score estimate limit x =
  foldr (scoreRed (limit - 1)) (-1) (moves x)
  where
    scoreRed limit x best =
      max best $ foldr (scoreBlue limit best x) 1 (moves x)
    scoreBlue limit best x worst =
      if limit <= 0
      then estimate x
      else min worst $ foldr (scoreRed (limit - 1)) best (moves x)

main = return ()

Notes:

• Everything named limit is of type Int.
• Everything named x is of type c, an instance of Cell.
• best and worst are Float.
• score, estimate, scoreRed, and scoreBlue all return Float.
• I deleted a bunch of code to simplify it enough for this question. Focus on the types and not runtime behavior.

The error message from GHC 7.6.3 is:

[1 of 1] Compiling Main             ( Game.hs, Game.o )

Game.hs:13:12:
    Couldn't match expected type `c -> c' with actual type `Float'
    In the return type of a call of `estimate'
    Probable cause: `estimate' is applied to too many arguments
    In the expression: estimate x
    In the expression:
      if limit <= 0 then
          estimate x
      else
          min worst $ foldr (scoreRed (limit - 1)) best (moves x)

Why I found this hard:

• The actual error is not on line 13 and has nothing to do with estimate.

• It seemed like the error could be caused by almost any identifier in the program.

• Sometimes adding explicit type declarations to everything helps, but not here: I don't know how to write type declarations for scoreRed and scoreBlue. If I write

  scoreRed :: Int -> Float -> c -> Float
  

  then GHC thinks I'm introducing a fresh type variable c, not referring to the type variable c in score's type. I get different error messages, but not better ones.

It looks like the "please please give me a fish" version of this question has been asked dozens of times. How about we teach me to fish instead. I'm ready.

Answer 1

For what it's worth, here's how I mentally process the error.

I start from c -> c vs Float, and realize there's a problem with the number of arguments somewhere: some non-function is being applied, or a function is being passed too many arguments (which is the same thing, because of currying).

Then I consider where the error points to: estimate x. I check the type for estimate to discover that estimate takes exactly one parameter. (Eyebrow-raising step here.) I infer that that code is fine, but that it's used in a context which passes too many arguments, something like

(if ... then estimate x else ...) unexpectedArg

Fortunately, estimate is used inside the definition of a function:

scoreBlue limit best x worst = ...

Here's where I add a type signature to that definition before investigating further. As you noticed, doing that is not trivial in this case, since you cope with one of the plain Haskell's shortcomings :-/ Also fortunately, as @bheklilr points out in a comment, you can write the signature anyway if you turn on the ScopedTypeVariables extension. (Personally, I hope that the next Haskell standard includes this (and a few others very common extensions).)

In this case, since I have no editor open with the code at hand, I check where scoreBlue is used, noting that foldr above is passing one argument too much. (... but this is not what the question is about.)

To be honest, in my own code I tend to frequently add type annotations in let/where definitions, perhaps a bit too defensively. While I sometimes omit these when the code is simple, when writing a many-arguments function like scoreBlue I would surely write the type before starting with the actual definition, since I'd consider the type as a fundamental guideline and documentation to the actual code.

Answer 2

For a problem like this, you could easily use the ScopedTypeVariables extension and change score's type signature to begin with forall c. Cell c => ..., but I would prefer extracting those functions out to the top level instead. In order to do this you'll need to add estimate as an argument to both scoreRed and scoreBlue:

score :: Cell c => (c -> Float) -> Int -> c -> Float
score estimate limit x =
    foldr (scoreRed estimate (limit - 1)) (-1) (moves x)

scoreRed estimate limit x best =
    max best $ foldr (scoreBlue estimate limit best x) 1 (moves x)

scoreBlue estimate limit best x worst =
    if limit <= 0
        then estimate x
        else min worst $ foldr (scoreRed estimate (limit - 1)) best (moves x)

And now you'll get the errors

jason_orendorff.hs:9:25:
    Couldn't match type ‘Float’ with ‘Float -> Float’
    Expected type: Float -> Float -> Float
      Actual type: c -> Float
    In the first argument of ‘scoreRed’, namely ‘estimate’
    In the first argument of ‘foldr’, namely
      ‘(scoreRed estimate (limit - 1))’

jason_orendorff.hs:17:18:
    Occurs check: cannot construct the infinite type: r ~ r -> r
    Relevant bindings include
      worst :: r (bound at jason_orendorff.hs:14:37)
      x :: r (bound at jason_orendorff.hs:14:35)
      best :: r (bound at jason_orendorff.hs:14:30)
      estimate :: r -> r -> r (bound at jason_orendorff.hs:14:15)
      scoreBlue :: (r -> r -> r) -> a -> r -> r -> r -> r -> r
        (bound at jason_orendorff.hs:14:5)
    In the expression:
      min worst $ foldr (scoreRed estimate (limit - 1)) best (moves x)
    In the expression:
      if limit <= 0 then
          estimate x
      else
          min worst $ foldr (scoreRed estimate (limit - 1)) best (moves x)
    In an equation for ‘scoreBlue’:
        scoreBlue estimate limit best x worst
          = if limit <= 0 then
                estimate x
            else
                min worst $ foldr (scoreRed estimate (limit - 1)) best (moves x)

Which tells us there's still a problem with the use of estimate. At this point, I would comment out scoreRed and scoreBlue, then put an underscore in front of the call to scoreRed in score, making it a named hole:

score :: Cell c => (c -> Float) -> Int -> c -> Float
score estimate limit x =
    foldr (_scoreRed estimate (limit - 1)) (-1) (moves x)

Which tells us that _scoreRed should have the type (c -> Float) -> Int -> c -> Float -> Float. So now we can put this as a type signature and a function declaration with a hole for scoreBlue:

score :: Cell c => (c -> Float) -> Int -> c -> Float
score estimate limit x =
    foldr (scoreRed estimate (limit - 1)) (-1) (moves x)

scoreRed :: Cell c => (c -> Float) -> Int -> c -> Float -> Float
scoreRed estimate limit x best =
    max best $ foldr (_scoreBlue estimate limit best x) 1 (moves x)

Compiling tells us that _scoreBlue :: (c -> Float) -> Int -> Float -> c -> c -> Float -> Float, and this is where I see the problem, scoreBlue is expecting two c arguments, when in reality I bet you want it to only take one. You want to fold across scoreBlue when it only needs x and worst as arguments, but you've already provided it with x. If we remove that from the fold and uncomment scoreBlue:

score :: Cell c => (c -> Float) -> Int -> c -> Float
score estimate limit x =
    foldr (scoreRed estimate (limit - 1)) (-1) (moves x)

scoreRed :: Cell c => (c -> Float) -> Int -> c -> Float -> Float
scoreRed estimate limit x best =
    max best $ foldr (scoreBlue estimate limit best) 1 (moves x)

scoreBlue :: Cell c => (c -> Float) -> Int -> Float -> c -> Float -> Float
scoreBlue estimate limit best x worst =
    if limit <= 0
        then estimate x
        else min worst $ foldr (scoreRed estimate (limit - 1)) best (moves x)

And now everything type-checks. I don't know if this is the correct behavior, the type system can help only to a certain point, but this code will run. Then you can refactor this back to use the local functions instead of top-level:

score :: Cell c => (c -> Float) -> Int -> c -> Float
score estimate limit x =
    foldr (scoreRed (limit - 1)) (-1) (moves x)
    where
        scoreRed limit x best =
            max best $ foldr (scoreBlue limit best) 1 (moves x)
        scoreBlue limit best x worst =
            if limit <= 0
                then estimate x
                else min worst $ foldr (scoreRed (limit - 1)) best (moves x)

And everything still type-checks.