Skip to content

Infinite recursion while deriving type

The following code:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, OverlappingInstances,
    UndecidableInstances, FunctionalDependencies #-}

class Container a b | a -> b where
    make :: b -> a

data Cont a = Cont a deriving (Show, Eq)

instance Container (Cont a) a where
    make x = Cont x

instance (Container a b, Show a, Eq a, Num b) => Num a where
    fromInteger x = make (fromInteger x)

d = fromInteger 3 :: Cont Integer

main = do
    print d

produces compilation error:

    Context reduction stack overflow; size = 21
    Use -fcontext-stack=N to increase stack size to N
      $dNum :: Num b19
      [skipped]
      $dNum :: Num b0
    In the first argument of `make', namely `(fromInteger x)'
    In the expression: make (fromInteger x)
    In an equation for `fromInteger':
        fromInteger x = make (fromInteger x)

Why I think this should work: my understanding is that in line fromInteger x = make (fromInteger x) compiler should take into account that[[BR]]

  1. the signature for make is make :: b -> a,[[BR]]
  2. type b is known at the moment of creating instance (because a == Cont Integer, which is an instance of Container (Cont Integer) Integer),[[BR]]

and cast fromInteger x to type b and pass it to make. This seems to be fixed in 7.2.2 (where this code compiles and displays Cont 3), although I did not manage to find any related entry in the changelog.

If one replaces the block instance (Container a b, ... with

class NumEquiv a where
    fromInt :: Integer -> a

instance NumEquiv Integer where
    fromInt = id

instance (Container a b, NumEquiv b) => NumEquiv a where
    fromInt x = make (fromInt x)

(which is the same as the initial code, the only difference being that the target typeclass --- NumEquiv --- is defined locally in the code), the code compiles successfully even on 7.0.4.

Edited by Simon Peyton Jones
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information