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]?
The equations for baz are in one binding group, generalisation is done after the entire group has been typed. Without a type signature, that means baz 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 of f - as long as f has a monotype. You can create the same ambiguity by giving f the same type as (==) (which requires Rank2Types),
{-# LANGUAGE Rank2Types #-}
foo :: Eq b => (forall a. Eq a => a -> a -> Bool) -> [b] -> Bool
foo f (x:y:_) = f x y
foo f[_] = foo f []
foo _ [] = False
That gives
Ambiguous type variable `b0' in the constraint:
(Eq b0) arising from a use of `foo'
Probable fix: add a type signature that fixes these type variable(s)
In the expression: foo f []
In an equation for `foo': foo f [_] = foo f []