GHC Panic related to functional dependencies - kindFunResult

Minimal example:

{-# LANGUAGE 
  MultiParamTypeClasses, DataKinds, FunctionalDependencies, TypeOperators,
  KindSignatures, PolyKinds, FlexibleInstances, FlexibleContexts, UndecidableInstances #-}

import GHC.TypeLits 

data Proxy (a :: k) = Proxy 

class FunctorN n f a fa | n f a -> fa where 
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN 0 f a a where 
  fmapn _ _ a = a 

instance (Functor f, FunctorN (n - 1) f a fa) => FunctorN n f a (f fa) where 
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy (n-1)) pf f)

Crashes with ghc and ghci:

>ghc test
[1 of 1] Compiling Main             ( test.hs, test.o )
ghc.exe: panic! (the 'impossible' happened)
  (GHC version 7.8.20140130 for x86_64-unknown-mingw32):
        kindFunResult k{tv azb} [sk]

>ghci test
GHCi, version 7.8.20140130: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( test.hs, interpreted )
ghc.exe: panic! (the 'impossible' happened)
  (GHC version 7.8.20140130 for x86_64-unknown-mingw32):
        kindFunResult k{tv aPm} [sk]

Removing the functional dependency makes the code compile.

Trac metadata

Trac field	Value
Version	7.8.2
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tbug Trac import labels

Attached file test.hs ($981).

File containing the source which causes the crash.

Attached file verbose_output.txt (download).

Output of ghc compilation with -v3

Attached file nobug.hs ($982).

Slight modification removes the bug

The same code without GHC.TypeLits works:

{-# LANGUAGE 
  MultiParamTypeClasses, DataKinds, FunctionalDependencies, TypeOperators,
  KindSignatures, PolyKinds, FlexibleInstances, FlexibleContexts, UndecidableInstances,
  ScopedTypeVariables #-}

data Proxy (a :: k) = Proxy 

data Nat = Z | P Nat 

class FunctorN n f a fa | n f a -> fa where 
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN Z f a a where 
  fmapn _ _ a = a 

instance (Functor f, FunctorN n f a fa) => FunctorN (P n) f a (f fa) where 
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy n) pf f)

Also annotating the Z instance with a monomorphic kind, (f :: *), makes the GHC.TypeLits version work:

{-# LANGUAGE
  MultiParamTypeClasses, DataKinds, FunctionalDependencies, TypeOperators,
  KindSignatures, PolyKinds, FlexibleInstances, FlexibleContexts, UndecidableInstances, ScopedTypeVariables #-}
module FunctorN where

import GHC.TypeLits

data Proxy (a :: k) = Proxy

class FunctorN n f a fa | n f a -> fa where
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN 0 (f :: *) a a where
  fmapn _ _ a = a

instance (Functor f, FunctorN (n - 1) f a fa) => FunctorN n f a (f fa) where
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy (n-1)) pf f)

Without the annotation, f is poly-kinded in the first FunctorN instance (it is * -> * in the second instance), and the kindFunResult error seems to be related to this kind-variable. That is when I annotate the f in the first FunctorN instance as (f :: p) I get:

ghc: panic! (the 'impossible' happened)
  (GHC version 7.8.2 for x86_64-apple-darwin):
	kindFunResult p{tv a1FO} [sk]

The type family version also works:

{-# LANGUAGE DataKinds, FlexibleInstances, MultiParamTypeClasses, PolyKinds,
    ScopedTypeVariables, TypeFamilies, TypeOperators, UndecidableInstances #-}
module FunctorN where

import GHC.TypeLits

data Proxy (a :: k) = Proxy

type family F n f a
  where
    F 0 f a = a
    F n f a = f (F (n-1) f a)

class F n f a ~ fa => FunctorN n f a fa where
  fmapn :: Proxy n -> Proxy f -> (a -> a) -> fa -> fa

instance FunctorN 0 f a a where
  fmapn _ _ a  = a

instance ( Functor f, FunctorN (n-1) f a fa, F (n - 1) f a ~ fa
         , F n f a ~ f fa) => FunctorN n f a (f fa) where
  fmapn _ pf f = fmap (fmapn (Proxy :: Proxy (n-1)) pf f)

test :: Maybe (Maybe (Maybe Int))
test = fmapn (Proxy :: Proxy 3) (Proxy :: Proxy Maybe) (+1)
             (Just (Just (Just 3)))

I'm working on this... I know more or less what's happening. Thanks for the examples

mentioned in commit d8d97113

Thank you. I've fixed the crash. Now we get

T9106.hs:13:10:
    Illegal instance declaration for ‘FunctorN n f a (f fa)’
      The liberal coverage condition fails in class ‘FunctorN’
        for functional dependency: ‘n f a -> fa’
      Reason: lhs types ‘n’, ‘f’, ‘a’
        do not jointly determine rhs type ‘f fa’
    In the instance declaration for ‘FunctorN n f a (f fa)’

which looks right to me.

Simon

Trac metadata

Trac field	Value
Test case	→ polykinds/T9106

added 1 deleted label

changed milestone to %7.8.3

mentioned in issue #9210

closed

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

removed 1 deleted label

mentioned in commit d6216443

added compiler crash label

added Pnormal label