Why can't I declare the inferred type?

6
votes

I have the following:

runcount :: (Eq a, Num b) => [a] -> b
runcount = runcountacc 0

runcountacc :: (Eq a, Num b) => b -> [a] -> b
runcountacc n (_:[]) = runcountacc (n+1) []
runcountacc n (x:xs) = runcountacc (n+(if head xs==x then 0 else 1)) xs 
runcountacc n _ = n

Which generates this error when I try to load it into Hugs:

:6 - Cannot justify constraints in explicitly typed binding
*** Expression    : runcountacc
*** Type          : (Eq a, Num b) => b -> [a] -> b
*** Given context : (Eq a, Num b)
*** Constraints   : Eq c

And the following error when loaded into ghci:

:6:23: Ambiguous type variable `a0' in the constraint:
  (Eq a0) arising from a use of `runcountacc'
Probable fix: add a type signature that fixes these type variable(s)
In the expression: runcountacc (n + 1) []
In an equation for `runcountacc':
   runcountacc n ([x]) = runcountacc (n + 1) []

However when the type declaration of runcountacc is removed:

runcount :: (Eq a, Num b) => [a] -> b
runcount = runcountacc 0

runcountacc n (_:[]) = runcountacc (n+1) []
runcountacc n (x:xs) = runcountacc (n+(if head xs==x then 0 else 1)) xs 
runcountacc n _ = n

The code loads fine and when ghci is asked what the type of runcountacc is, we get the following:

λ> :t runcountacc 
runcountacc :: (Num a, Eq a1) => a -> [a1] -> a

Why can't I declare the inferred type of runcountacc?

2
haskelltypes
First of all, hugs is ancient, you should use GHc. Secondly this is not a hugs specific problem, you get a similar error with ghc. – HaskellElephant
@HaskellElephant hugs being "ancient" is not a good reason to avoid it. The implementation still works. – singpolyma
@singpolyma , yes, it being old is not good enough reason on its own, but since the latest build is from 2006 it is not supported by new libraries and it does not support the haskell 2010 standard. Furthermore many of the reasons to use hugs (such as the interpreter) has since been implemented in GHC. – HaskellElephant
@HaskellElephant Haskell2010 is very new. I wouldn't expect support to be widespread for quite some time. (Think of how long C99 took to become mostly accepted!) – singpolyma

2 Answers

8
votes

My guess is that when you leave out the type signature, Haskell assumes you're not intending to use polymorphic recursion (for which type inference is not so effective). Correspondingly, when you make that recursive call to runcountacc (n + 1) [], the list element type is taken to be the same as in the original function call. The usual Hindley-Milner process works fine, computing a uniform monomorphic type for runcountacc, then forming a type scheme by generalizing over the free type variables and unsolved constraints.

However, as soon as you write a type signature, you allow for the possibility of polymorphic recursion, and when you call runcountacc (n + 1) [], there is no reason to assume that the undetermined element type for [] should be anything in particular. However, this undetermined type still needs an Eq instance to satisfy the constraints on runcountacc, and there's no way to figure out which Eq instance to use. It's genuinely ambiguous.

There are plenty of ways you can rewrite this code to sort out this ambiguity.

8
votes

Why can't I write the inferred type of runcountacc in the code?

The short answer is that because you created polymorphic recursion by mistake and type inference is not supposed to work at all if polymorphic recursion is present.

GHC gives a better error message:

orig.hs:5:24:
    Ambiguous type variable `a0' in the constraint:
      (Eq a0) arising from a use of `runcountacc'
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: runcountacc (n + 1) []
    In an equation for `runcountacc':
        runcountacc n (_ : []) = runcountacc (n + 1) []

There it can't infer the type for the right-side []. The following signature fixes the problem, because without it it's not clear empty list of what should be used:

runcountacc n (_:[]) = runcountacc (n+1) ([] :: [a])

We have a kind of (infinite) polymorphic recursion here. The type of right side empty list can be anything, and GHC cannot understand which one. For example, the following is still valid:

runcountacc n (_:[]) = runcountacc (n+1) ([] :: [String])

The question why the problem disappears without type signatures remain open though.

The idea of @pigworker is that if you omit the signatures, Haskell disallows polymorphic recursion, and with monomorphic recrusion there's no ambiguity.

NB: You got the base case of recursion wrong - an infinite loop must not appear there in first place.