Opened 4 years ago

Closed 3 years ago

Last modified 2 years ago

#10524 closed bug (fixed)

PolyKinds doesn't interact well with DeriveFunctor

Reported by: RyanGlScott Owned by:
Priority: normal Milestone: 8.0.1
Component: Compiler Version: 7.10.1
Keywords: deriving Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: GHC rejects valid program Test Case: deriving/should_compile/T10561
Blocked By: Blocking:
Related Tickets: #10561 Differential Rev(s): Phab:D2097
Wiki Page:

Description

Using PolyKinds and DeriveFunctor in tandem on GHC 7.10.2-rc1 will cause a kind incompatibility in certain cases:

GHCi, version 7.10.1.20150612: http://www.haskell.org/ghc/  :? for help
λ> :set -XPolyKinds -XDeriveFunctor -ddump-deriv
λ> newtype Compose f g a = Compose (f (g a)) deriving Functor

==================== Derived instances ====================
Derived instances:
  instance forall (k_axa :: BOX)
                  (f_axb :: k_axa -> *)
                  (g_axc :: * -> k_axa).
           (GHC.Base.Functor f_axb, GHC.Base.Functor g_axc) =>
           GHC.Base.Functor (Ghci1.Compose f_axb g_axc) where
    GHC.Base.fmap f_axd (Ghci1.Compose a1_axe)
      = Ghci1.Compose (GHC.Base.fmap (GHC.Base.fmap f_axd) a1_axe)
  

Generic representation:
  
  Generated datatypes for meta-information:
  
  Representation types:



<interactive>:3:52:
    Kind incompatibility when matching types:
      f0 :: * -> *
      f :: k -> *
    Expected type: f (g b)
      Actual type: f0 (f1 b)
    Relevant bindings include
      a1 :: f (g a) (bound at <interactive>:3:52)
      fmap :: (a -> b) -> Compose f g a -> Compose f g b
        (bound at <interactive>:3:52)
    In the first argument of ‘Compose’, namely ‘fmap (fmap f) a1’
    In the expression: Compose (fmap (fmap f) a1)
    When typechecking the code for  ‘fmap’
      in a derived instance for ‘Functor (Compose f g)’:
      To see the code I am typechecking, use -ddump-deriv

A workaround is to use StandaloneDeriving:

λ> :set -XStandaloneDeriving 
λ> newtype Compose f g a = Compose (f (g a))
λ> deriving instance (Functor f, Functor g) => Functor (Compose f g)

==================== Derived instances ====================
Derived instances:
  instance (GHC.Base.Functor f_ayO, GHC.Base.Functor g_ayP) =>
           GHC.Base.Functor (Ghci1.Compose f_ayO g_ayP) where
    GHC.Base.fmap f_ayQ (Ghci1.Compose a1_ayR)
      = Ghci1.Compose (GHC.Base.fmap (GHC.Base.fmap f_ayQ) a1_ayR)
  

Generic representation:
  
  Generated datatypes for meta-information:
  
  Representation types:

This problem does not seem to occur in GHC HEAD, however:

GHCi, version 7.11.20150608: http://www.haskell.org/ghc/  :? for help
λ> :set -XPolyKinds -XDeriveFunctor -ddump-deriv
λ> newtype Compose f g a = Compose (f (g a)) deriving Functor

==================== Derived instances ====================
Derived instances:
  instance forall (k_a148 :: BOX)
                  (f_a149 :: k_a148 -> *)
                  (g_a14a :: * -> k_a148).
           (GHC.Base.Functor f_a149, GHC.Base.Functor g_a14a) =>
           GHC.Base.Functor (Ghci3.Compose f_a149 g_a14a) where
    GHC.Base.fmap f_a14b (Ghci3.Compose a1_a14c)
      = Ghci3.Compose (GHC.Base.fmap (GHC.Base.fmap f_a14b) a1_a14c)
  

Generic representation:
  
  Generated datatypes for meta-information:
  
  Representation types:

Can this fix be backported in time for GHC 7.10.2?

Change History (20)

comment:1 Changed 4 years ago by rwbarton

FWIW this isn't a regression, 7.8 fails with the same error and 7.6 bails out even earlier. And isn't 7.10's behavior in fact the correct one? The instance produced by 7.11 is ill-kinded:

instance [safe] forall (k :: BOX) (f :: k -> *) (g :: * -> k).
                (Functor f, Functor g) =>
                Functor (Compose f g)

Functor's argument must really be of kind * -> *. (Though I don't know if this will cause any harm beyond confusing error messages down the line.)

comment:2 Changed 4 years ago by RyanGlScott

It appears that since f :: k -> * and g :: * -> k in 7.10's Functor instance, and since the kind of Compose is (k -> *) -> (k1 -> k) -> k1 -> *, it would follow that Compose f g is of kind * -> * (unless I'm reading that wrong).

I raised this issue since at the moment, 7.10 can handle certain poly-kinded derived Functor instances (e.g., newtype Alt f a = Alt (f a) deriving Functor), but throwing more than one poly-kinded type constructor into the mix causes things to go haywire.

comment:3 Changed 4 years ago by rwbarton

The instance head Functor (Compose f g) is well-kinded, but the context (Functor f, Functor g) is not unless k = *.

comment:4 Changed 4 years ago by RyanGlScott

Oh, right. So in both GHC 7.10 and 7.11, the derived kinds for the type variables in (Functor f, Functor g) => Functor (Compose f g) are incorrect, but GHC 7.11 defers the errors until later.

In that case, can this can of problem be fixed? Would deriving clauses always be able to infer the correct kinds, or would it be necessary in some cases to specify the kinds in a standalone deriving statement, e.g.,

deriving instance (Functor (f :: * -> *), Functor (g :: * -> *)) => Functor (Compose f g)

(The kind signatures wouldn't be needed here due to the explicit Functor constraint, but you get the idea.)

comment:5 Changed 4 years ago by rwbarton

Good question. In principle there are classes at other kinds Functor1, Functor2 (not part of a systematic naming scheme) for which you can write

instance (Functor1 (f :: (* -> *) -> *), Functor2 (g :: * -> (* -> *))) =>
         Functor (Compose f g)

but GHC will probably never be able to derive that instance. (Maybe if eventually get a polykinded Functor, but then the deriving clause could produce a kind-polymorphic instance and there is no problem.) So, I don't see any real issue with having ordinary deriving producing an instance for Functor (Compose * f g), to write the kind variable explicitly.

However, it's certainly more clear-cut with the standalone deriving declaration, since then the kind variable is determined by the context which you wrote explicitly.

I think GHC may have some general principles regarding ordinary deriving declarations and how they are less general than standalone deriving, but I never understood the exact details (aside from the fact that a standalone deriving declaration lets you specify the context). Maybe they don't have anything to say about this case with a kind variable anyways.

Not sure where that leaves this ticket; the behavior of HEAD is a bug that I'll file separately. Maybe a feature request dependent on the resolution of that bug.

comment:6 Changed 4 years ago by rwbarton

comment:7 Changed 4 years ago by RyanGlScott

It looks like PolyKinds also breaks deriving Data instances as well:

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE PolyKinds #-}

import Data.Data

newtype WrappedFunctor f a = WrapFunctor (f a) deriving (Data, Typeable)

This will result in the error:

    No instance for (Typeable a)
      arising from the 'deriving' clause of a data type declaration
    Possible fix:
      use a standalone 'deriving instance' declaration,
        so you can specify the instance context yourself
    When deriving the instance for (Data (WrappedFunctor f a))

(Presumably, it's trying to infer the instance context Data (f a), Typeable f, Typeable a) => Data (WrappedFunctor f a), but can't.)

I'm not sure if this is due to the same underlying issue, but it seems likely, since that code will compile without PolyKinds. I reproduced this on GHC 7.8, 7.10, and HEAD.

comment:8 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

In 8e347839be4d52b6f74cc11e18e5820f88969c80/ghc:

Make fvType ignore kinds

TcValidity.fvTypes works in partnership with sizeTypes, and
hence should ignore kinds in exactly the same way.  It wasn't
doing so, which meant that validDerivPred said "No" when it
should have said "Yes". That led to the bug reported in
Trac #10524 comment:7.

The error message is pretty terrible
  No instance for (Typeable T)
but I'll fix that next

comment:9 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

In ceb3c8448dfba23aa98a710f846304158c1c584b/ghc:

Improve error message for Typeable k (T k)

GHC can't yest build a TypeRep for a type involving kind variables.
(We await kinds = types for that.)  But the error message was terrible,
as fixing #10524 reminded me.

This improves it a lot.

comment:10 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

comment:11 Changed 4 years ago by simonpj

OK, so I fixed comment:7. But the original bug report remains

newtype Compose f g a = Compose (f (g a)) deriving Functor

should be fine, but elicits

T10524.hs:5:52: error:
    Couldn't match kind ‘k’ with ‘*’
      arising from the first field of ‘Compose’ (type ‘f (g a)’)
    When deriving the instance for (Functor (Compose f g))

After all, this explicit instance declaration typechecks fine

instance (Functor f, Functor g) => Functor (Compose f g) where
  fmap fn (Compose x) = Compose (fmap (fmap fn) x)

comment:12 Changed 4 years ago by goldfire

In my soon-to-be-merged branch, I can now accept the program in comment:7. I have not looked at the other issues at work here, though.

comment:13 Changed 4 years ago by Richard Eisenberg <eir@…>

In 67465497/ghc:

Add kind equalities to GHC.

This implements the ideas originally put forward in
"System FC with Explicit Kind Equality" (ICFP'13).

There are several noteworthy changes with this patch:
 * We now have casts in types. These change the kind
   of a type. See new constructor `CastTy`.

 * All types and all constructors can be promoted.
   This includes GADT constructors. GADT pattern matches
   take place in type family equations. In Core,
   types can now be applied to coercions via the
   `CoercionTy` constructor.

 * Coercions can now be heterogeneous, relating types
   of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2`
   proves both that `t1` and `t2` are the same and also that
   `k1` and `k2` are the same.

 * The `Coercion` type has been significantly enhanced.
   The documentation in `docs/core-spec/core-spec.pdf` reflects
   the new reality.

 * The type of `*` is now `*`. No more `BOX`.

 * Users can write explicit kind variables in their code,
   anywhere they can write type variables. For backward compatibility,
   automatic inference of kind-variable binding is still permitted.

 * The new extension `TypeInType` turns on the new user-facing
   features.

 * Type families and synonyms are now promoted to kinds. This causes
   trouble with parsing `*`, leading to the somewhat awkward new
   `HsAppsTy` constructor for `HsType`. This is dispatched with in
   the renamer, where the kind `*` can be told apart from a
   type-level multiplication operator. Without `-XTypeInType` the
   old behavior persists. With `-XTypeInType`, you need to import
   `Data.Kind` to get `*`, also known as `Type`.

 * The kind-checking algorithms in TcHsType have been significantly
   rewritten to allow for enhanced kinds.

 * The new features are still quite experimental and may be in flux.

 * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203.

 * TODO: Update user manual.

Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142.
Updates Haddock submodule.

comment:14 Changed 4 years ago by goldfire

Confirming that the example from comment:7 is accepted.

comment:15 Changed 4 years ago by simonpj

Yes, but test deriving/should_compile/T10561 still fails:

newtype Compose f g a = Compose (f (g a)) deriving Functor

(with -XPolyKinds) produces

T10561.hs:10:52: error:
    • Couldn't match kind ‘k’ with ‘*’
        arising from the first field of ‘Compose’ (type ‘f (g a)’)
    • When deriving the instance for (Functor (Compose f g))

comment:16 Changed 4 years ago by RyanGlScott

I also experienced the same error as in comment:15 when I tried to derive a Generic1 instance for Compose in Phab:D1543. A workaround is to use standalone deriving:

deriving instance Functor f => Generic1 (Compose f g)

If we fix this bug, we should remember to change that instance (located here).

comment:17 Changed 3 years ago by RyanGlScott

Differential Rev(s): Phab:D2097
Status: newpatch

comment:18 Changed 3 years ago by Ben Gamari <ben@…>

In aadde2b/ghc:

Deriving Functor-like classes should unify kind variables

While the deriving machinery always unifies the kind of the typeclass
argument with the kind of the datatype, this proves not to be sufficient
to produce well kinded instances for some poly-kinded datatypes. For
example:

```
newtype Compose (f :: k2 -> *) (g :: k1 -> k2) (a :: k1)
  = Compose (f (g a)) deriving Functor
```

would fail because only `k1` would get unified with `*`, causing the
following
ill kinded instance to be generated:

```
instance (Functor (f :: k2 -> *), Functor (g :: * -> k2)) =>
  Functor (Compose f g) where ...
```

To prevent this, we need to take the subtypes and unify their kinds with
`* -> *`.

Fixes #10524 for good.

Test Plan: ./validate

Reviewers: simonpj, hvr, austin, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2097

GHC Trac Issues: #10524, #10561

comment:19 Changed 3 years ago by RyanGlScott

Milestone: 8.0.1
Resolution: fixed
Status: patchclosed
Test Case: deriving/should_compile/T10561

comment:20 Changed 2 years ago by RyanGlScott

Keywords: deriving added
Note: See TracTickets for help on using tickets.