This code breaks when a type declaration for baz
is added:
baz (x:y:_) = x == y
baz [_] = baz []
baz [] = False
A common explanation (see Why can't I declare the inferred type? for an example) is that it's because of polymorphic recursion.
But that explanation doesn't explain why the effect disappears with another polymorphically recursive example:
foo f (x:y:_) = f x y
foo f [_] = foo f []
foo f [] = False
It also doesn't explain why GHC thinks the recursion is monomorphic without type declaration.
Can the explanation of the example with reads
in http://www.haskell.org/onlinereport/decls.html#sect4.5.5 be applied to my baz
case?
I.e. adding a signature removes monomorphism restriction, and without the restriction an ambiguity of right-side [] appears, with an 'inherently ambigous' type of forall a . Eq a => [a]
?
Your second example isn't polymorphically recursive. This is because the function
f
appears on both the LHS and RHS of the recursive definition. Also consider the type offoo
,(a -> a -> Bool) -> [a] -> Bool
. This fixes the list element type to be identical to the type off
's arguments. As a result, GHC can determine that the empty list on the RHS must have the same type as the input list.I don't think that the
reads
example is applicable to thebaz
case, because GHC is able to compilebaz
with no type signature and the monomorphism restriction disabled. Therefore I expect that GHC's type algorithm has some other mechanism by which it removes the ambiguity.The equations for
baz
are in one binding group, generalisation is done after the entire group has been typed. Without a type signature, that meansbaz
is assumed to have a monotype, so the type of[]
in the recursive call is given by that (look at ghc's -ddump-simpl output). With a type signature, the compiler is explicitly told that the function is polymorphic, so it can't assume the type of[]
in the recursive call to be the same, hence it's ambiguous.As John L said, in
foo
, the type is fixed by the occurrence off
- as long asf
has a monotype. You can create the same ambiguity by givingf
the same type as(==)
(which requiresRank2Types
),That gives