Haskell/GHC UndecidableInstances - example for non-terminating type check?

decidable, ghc, haskell, typechecking

Solution

For example:

{-# LANGUAGE UndecidableInstances #-}

class C a where
    f :: a -> a

instance C [[a]] => C [a] where
    f = id

g x = x + f [x]

What is happening: When typing `f [x]` the compiler needs to ensure that `x :: C [a]` for some `a`. The instance declaration says that `x` can be of type `C [a]` only if it is also of type `C [[a]]`. So the compiler needs to ensure that `x :: C [[a]]`, etc. and gets caught in an infinite loop.

See also Can using UndecidableInstances pragma locally have global consequences on compilation termination?

Problem

I've written some Haskell code which needs -XUndecidableInstances to compile. I do understand why that happens, that there is a certain condition which is violated and therefore GHC yells. However, I've never come across a situation where the type checker would actually hang or wind up in an endless loop. What does a non-terminating instance definition look like - can you give an example?

Original source

Related problems