Opened 4 years ago

Closed 4 years ago

Last modified 2 years ago

#11174 closed bug (fixed)

Traversable can't be derived for datatypes with unboxed arguments

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

Description (last modified by RyanGlScott)

Unlike Functor and Foldable, Traversable cannot be derived for datatypes that contain arguments with unboxed types. A simple example:

{-# LANGUAGE DeriveTraversable, MagicHash #-}

import GHC.Prim (Int#)

data IntHash a = IntHash Int# deriving (Functor, Foldable, Traversable)

The generated Traversable instance reveals the issue:

instance Traversable IntHash where
  traverse f (IntHash a1) = fmap IntHash (pure a1)
    Couldn't match kind `*' with `#'
    When matching types
      a0 :: *
      Int# :: #
    Expected type: a0 -> IntHash b
      Actual type: Int# -> IntHash b
    In the first argument of `fmap', namely `IntHash'
    In the expression: fmap IntHash (pure a1)
    When typechecking the code for  `traverse'
      in a derived instance for `Traversable IntHash':
      To see the code I am typechecking, use -ddump-deriv

We have to avoid calling pure on a1, since pure expects an argument with a *-kinded type, not a #-kinded one.

One way to fix this would be restructuring the derived traverse implementation such that arguments which do not mention the last type parameter are moved to the function initially lifted with pure, and doing nothing with them later. To better articulate what I mean, envision something like this:

data IntHash2 a = IntHash2 Int# a (IntHash2 a) Int deriving (Functor, Foldable)

Then a derived Traversable instance that would type-check (and kind-check) would be:

instance Traversable IntHash2 where
  traverse f (IntHash2 a1 a2 a3 a4) =
    pure (\x2 x3 -> IntHash2 a1 x2 x3 a4) <*> f a2 <*> traverse f a3

Conceptually, this doesn't sound hard to implement. The tricky part is figuring out how much of the existing Functor/Foldable/Traversable deriving machinery would need to be tweaked to make this work.

Change History (7)

comment:1 Changed 4 years ago by RyanGlScott

Description: modified (diff)

comment:2 Changed 4 years ago by simonpj

Keywords: Generics added

comment:3 Changed 4 years ago by RyanGlScott

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

I've uploaded a Phab:D1908, based on the design philosophy outlined in this wiki page.

comment:4 Changed 4 years ago by bgamari

Milestone: 8.2.1
Resolution: fixed
Status: patchclosed

Thanks RyanGlScott!

comment:5 Changed 4 years ago by Ben Gamari <ben@…>

In a82956d/ghc:

Remove superfluous code when deriving Foldable/Traversable

Currently, `-XDeriveFoldable` and `-XDeriveTraversable` generate
unnecessary `mempty` and `pure` expressions when it traverses of an
argument of a constructor whose type does not mention the last type
parameter. Not only is this inefficient, but it prevents `Traversable`
from being derivable for datatypes with unlifted arguments (see
Trac #11174).

The solution to this problem is to adopt a slight change to the
algorithms for `-XDeriveFoldable` and `-XDeriveTraversable`, which is
described in [this wiki
page](https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFu
nctor#Proposal:alternativestrategyforderivingFoldableandTraversable).
The wiki page also describes why we don't apply the same changes to the
algorithm for `-XDeriveFunctor`.

This is techincally a breaking change for users of `-XDeriveFoldable`
and `-XDeriveTraversable`, since if someone was using a law-breaking
`Monoid` instance with a derived `Foldable` instance (i.e., one where `x
<> mempty` does not equal `x`) or a law-breaking `Applicative` instance
with a derived `Traversable` instance, then the new generated code could
result in different behavior. I suspect the number of scenarios like
this is very small, and the onus really should be on those users to fix
up their `Monoid`/`Applicative` instances.

Fixes #11174.

Test Plan: ./validate

Reviewers: hvr, simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: thomie

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

GHC Trac Issues: #11174

comment:6 Changed 4 years ago by bgamari

Milestone: 8.2.18.0.1

I went ahead and merged this to ghc-8.0.

comment:7 Changed 2 years ago by RyanGlScott

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