[GHC] #5759: Infinite recursion while deriving type

[GHC]

#5759: Infinite recursion while deriving type
---------------------------------+------------------------------------------
    Reporter:  Bogdan            |       Owner:                           
        Type:  bug               |      Status:  new                      
    Priority:  normal            |   Milestone:                           
   Component:  Compiler          |     Version:  7.0.4                    
    Keywords:                    |          Os:  Unknown/Multiple         
Architecture:  Unknown/Multiple  |     Failure:  GHC rejects valid program
  Difficulty:  Unknown           |    Testcase:                           
   Blockedby:                    |    Blocking:                           
     Related:                    |  
---------------------------------+------------------------------------------
Changes (by simonpj):

  * difficulty:  => Unknown


Old description:

> 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.

New description:

 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.

--

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5759#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler