Changes between Initial Version and Version 1 of Commentary/Compiler/DeriveFunctor


Ignore:
Timestamp:
Jun 5, 2015 9:50:13 PM (5 years ago)
Author:
RyanGlScott
Comment:

Create article about DeriveFunctor, DeriveFoldable, and DeriveTraversable

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/DeriveFunctor

    v1 v1  
     1= Support for deriving {{{Functor}}}, {{{Foldable}}}, and {{{Traversable}}} instances =
     2[[PageOutline]]
     3
     4GHC 6.12.1 introduces an extension to the {{{deriving}}} mechanism allowing for automatic derivation of {{{Functor}}}, {{{Foldable}}}, and {{{Traversable}}} instances using the {{{DeriveFunctor}}}, {{{DeriveFoldable}}}, and {{{DeriveTraversable}}} extensions, respectively. Twan van Laarhoven [https://mail.haskell.org/pipermail/haskell-prime/2007-March/002137.html first proposed this feature] in 2007, and [https://ghc.haskell.org/trac/ghc/ticket/2953 opened a related GHC Trac ticket] in 2009.
     5
     6== Example ==
     7
     8{{{#!hs
     9{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
     10
     11data Example a = Ex a Char (Example a) (Example Char)
     12  deriving (Functor, Foldable, Traversable)
     13}}}
     14
     15The derived code would look something like this:
     16
     17{{{#!hs
     18instance Functor Example where
     19    fmap f (Ex a1 a2 a3 a4) = Ex (f a1) a2 (fmap f a3) a4
     20
     21instance Foldable Example where
     22    foldr f z (Ex a1 a2 a3 a4) = f a1 (foldr f z a3)
     23    foldMap f (Ex a1 a2 a3 a4) = mappend (f a1) (mappend mempty (mappend (foldMap f a3) mempty))
     24
     25instance Traversable Example where
     26    traverse f (Ex a1 a2 a3 a4) = Ex <$> (f a) <*> pure a2 <*> traverse f a3 <*> pure a4
     27}}}
     28
     29== Algorithm description ==
     30
     31{{{DeriveFunctor}}}, {{{DeriveFoldable}}}, and {{{DeriveTraversable}}} all operate using the same underlying mechanism. GHC inspects the arguments of each constructor and derives some operation to perform on each argument, which depends of the type of the argument itself. In a {{{Functor}}} instance, for example {{{fmap}}} would be applied to occurrences of the last type parameter, but {{{id}}} would be applied to other type parameters. Typically, there are five cases to consider. (Suppose we have a data type {{{data A a = ...}}}.)
     32
     331. Terms whose type does not mention {{{a}}}
     342. Terms whose type mentions {{{a}}}
     353. Occurrences of {{{a}}}
     364. Tuple values
     375. Function values
     38
     39After this is done, the new terms are combined in some way. For instance, {{{Functor}}} instances combine terms in a derived {{{fmap}}} definition by applying the appropriate constructor to all terms, whereas in {{{Foldable}}} instances, a derived {{{foldMap}}} definition would {{{mappend}}} the terms together.
     40
     41=== {{{DeriveFunctor}}} ===
     42
     43A comment in [http://git.haskell.org/ghc.git/blob/9f968e97a0de9c2509da00f6337b612dd72a0389:/compiler/typecheck/TcGenDeriv.hs#l1476 TcGenDeriv.hs] lays out the basic structure of {{{DeriveFunctor}}}, which derives an implementation for {{{fmap}}}.
     44
     45{{{
     46For the data type:
     47
     48  data T a = T1 Int a | T2 (T a)
     49
     50We generate the instance:
     51
     52  instance Functor T where
     53      fmap f (T1 b1 a) = T1 b1 (f a)
     54      fmap f (T2 ta)   = T2 (fmap f ta)
     55
     56Notice that we don't simply apply 'fmap' to the constructor arguments.
     57Rather
     58  - Do nothing to an argument whose type doesn't mention 'a'
     59  - Apply 'f' to an argument of type 'a'
     60  - Apply 'fmap f' to other arguments
     61That's why we have to recurse deeply into the constructor argument types,
     62rather than just one level, as we typically do.
     63
     64What about types with more than one type parameter?  In general, we only
     65derive Functor for the last position:
     66
     67  data S a b = S1 [b] | S2 (a, T a b)
     68  instance Functor (S a) where
     69    fmap f (S1 bs)    = S1 (fmap f bs)
     70    fmap f (S2 (p,q)) = S2 (a, fmap f q)
     71
     72However, we have special cases for
     73         - tuples
     74         - functions
     75
     76More formally, we write the derivation of fmap code over type variable
     77'a for type 'b as ($fmap 'a 'b).  In this general notation the derived
     78instance for T is:
     79
     80  instance Functor T where
     81      fmap f (T1 x1 x2) = T1 ($(fmap 'a 'b1) x1) ($(fmap 'a 'a) x2)
     82      fmap f (T2 x1)    = T2 ($(fmap 'a '(T a)) x1)
     83
     84  $(fmap 'a 'b)          =  \x -> x     -- when b does not contain a
     85  $(fmap 'a 'a)          =  f
     86  $(fmap 'a '(b1,b2))    =  \x -> case x of (x1,x2) -> ($(fmap 'a 'b1) x1, $(fmap 'a 'b2) x2)
     87  $(fmap 'a '(T b1 b2))  =  fmap $(fmap 'a 'b2)   -- when a only occurs in the last parameter, b2
     88  $(fmap 'a '(b -> c))   =  \x b -> $(fmap 'a' 'c) (x ($(cofmap 'a 'b) b))
     89
     90For functions, the type parameter 'a can occur in a contravariant position,
     91which means we need to derive a function like:
     92
     93  cofmap :: (a -> b) -> (f b -> f a)
     94
     95This is pretty much the same as $fmap, only without the $(cofmap 'a 'a) case:
     96
     97  $(cofmap 'a 'b)          =  \x -> x     -- when b does not contain a
     98  $(cofmap 'a 'a)          =  error "type variable in contravariant position"
     99  $(cofmap 'a '(b1,b2))    =  \x -> case x of (x1,x2) -> ($(cofmap 'a 'b1) x1, $(cofmap 'a 'b2) x2)
     100  $(cofmap 'a '[b])        =  map $(cofmap 'a 'b)
     101  $(cofmap 'a '(T b1 b2))  =  fmap $(cofmap 'a 'b2)   -- when a only occurs in the last parameter, b2
     102  $(cofmap 'a '(b -> c))   =  \x b -> $(cofmap 'a' 'c) (x ($(fmap 'a 'c) b))
     103}}}
     104
     105{{{DeriveFunctor}}} is special in that it can recurse into function types, whereas {{{DeriveFoldable}}} and {{{DeriveTraversable}}} cannot (see the section on covariant and contravariant positions).
     106
     107=== {{{DeriveFoldable}}} ===
     108
     109Another comment in [http://git.haskell.org/ghc.git/blob/9f968e97a0de9c2509da00f6337b612dd72a0389:/compiler/typecheck/TcGenDeriv.hs#l1725 TcGenDeriv.hs] reveals the underlying mechanism behind {{{DeriveFoldable}}}:
     110
     111{{{
     112Deriving Foldable instances works the same way as Functor instances,
     113only Foldable instances are not possible for function types at all.
     114Here the derived instance for the type T above is:
     115
     116  instance Foldable T where
     117      foldr f z (T1 x1 x2 x3) = $(foldr 'a 'b1) x1 ( $(foldr 'a 'a) x2 ( $(foldr 'a 'b2) x3 z ) )
     118
     119The cases are:
     120
     121  $(foldr 'a 'b)         =  \x z -> z     -- when b does not contain a
     122  $(foldr 'a 'a)         =  f
     123  $(foldr 'a '(b1,b2))   =  \x z -> case x of (x1,x2) -> $(foldr 'a 'b1) x1 ( $(foldr 'a 'b2) x2 z )
     124  $(foldr 'a '(T b1 b2)) =  \x z -> foldr $(foldr 'a 'b2) z x  -- when a only occurs in the last parameter, b2
     125
     126Note that the arguments to the real foldr function are the wrong way around,
     127since (f :: a -> b -> b), while (foldr f :: b -> t a -> b).
     128}}}
     129
     130In addition to {{{foldr}}}, {{{DeriveFoldable}}} also generates a definition for {{{foldMap}}} as of GHC 7.8.1 (addressing [https://ghc.haskell.org/trac/ghc/ticket/7436 #7436]). The pseudo-definition for {{{$(foldMap)}}} would look something like this:
     131
     132{{{
     133  $(foldMap 'a 'b)         = \x -> mempty     -- when b does not contain a
     134  $(foldMap 'a 'a)         = f
     135  $(foldMap 'a '(b1,b2))   = \x -> case x of (x1, x2) -> mappend ($(foldMap 'a 'b1) x1) ($(foldMap 'a 'b2) x2)
     136  $(foldMap 'a '(T b1 b2)) = \x -> foldMap $(foldMap 'a 'b2) x -- when a only occurs in the last parameter, b2
     137}}}
     138
     139=== {{{DeriveTraversable}}} ===
     140
     141From [http://git.haskell.org/ghc.git/blob/9f968e97a0de9c2509da00f6337b612dd72a0389:/compiler/typecheck/TcGenDeriv.hs#l1800 TcGenDeriv.hs]:
     142
     143{{{
     144Again, Traversable is much like Functor and Foldable.
     145
     146The cases are:
     147
     148  $(traverse 'a 'b)          =  pure     -- when b does not contain a
     149  $(traverse 'a 'a)          =  f
     150  $(traverse 'a '(b1,b2))    =  \x -> case x of (x1,x2) -> (,) <$> $(traverse 'a 'b1) x1 <*> $(traverse 'a 'b2) x2
     151  $(traverse 'a '(T b1 b2))  =  traverse $(traverse 'a 'b2)  -- when a only occurs in the last parameter, b2
     152
     153Note that the generated code is not as efficient as it could be. For instance:
     154
     155  data T a = T Int a  deriving Traversable
     156
     157gives the function: traverse f (T x y) = T <$> pure x <*> f y
     158instead of:         traverse f (T x y) = T x <$> f y
     159}}}
     160
     161=== Covariant and contravariant positions ===
     162
     163One challenge of deriving {{{Functor}}} instances for arbitrary data types is handling function types. To illustrate this, note that these all can have derived {{{Functor}}} instances:
     164
     165{{{#!hs
     166data CovFun1 a = CovFun1 (Int -> a)
     167data CovFun2 a = CovFun2 ((a -> Int) -> a)
     168data CovFun3 a = CovFun3 (((Int -> a) -> Int) -> a)
     169}}}
     170
     171but none of these can:
     172
     173{{{#!hs
     174data ContraFun1 a = ContraFun1 (a -> Int)
     175data ContraFun2 a = ContraFun2 ((Int -> a) -> Int)
     176data ContraFun3 a = ContraFun3 (((a -> Int) -> a) -> Int)
     177}}}
     178
     179In {{{CovFun1}}}, {{{CovFun2}}}, and {{{CovFun3}}}, all occurrences of the type variable {{{a}}} are in ''covariant'' positions (i.e., the {{{a}}} values are produced), whereas in {{{ContraFun1}}}, {{{ContraFun2}}}, and {{{ContraFun3}}}, all occurrences of {{{a}}} are in ''contravariant'' positions (i.e., the {{{a}}} values are consumed). If we have a function {{{f :: a -> b}}}, we can't apply {{{f}}} to an {{{a}}} value in a contravariant position, which precludes a {{{Functor}}} instance.
     180
     181Most type variables appear in covariant positions. Functions are special in that the lefthand side of a function arrow reverses variance. If a function type {{{a -> b}}} appears in a covariant position (e.g., {{{CovFun1}}} above), then {{{a}}} is in a contravariant position and {{{b}}} is in a covariant position. Similarly, if {{{a -> b}}} appears in a contravariant position (e.g., {{{CovFun2}}} above), then {{{a}}} is in a covariant position and {{{b}}} is in a contravariant position.
     182
     183If we annotate covariant positions with {{{p}}} (for positive) and contravariant positions with {{{n}}} (for negative), then we can examine the above examples with the following pseudo-type signatures:
     184
     185{{{
     186CovFun1/ContraFun1 :: n -> p
     187CovFun2/ContraFun2 :: (p -> n) -> p
     188CovFun3/ContraFun3 :: ((n -> p) -> n) -> p
     189}}}
     190
     191Since {{{ContraFun1}}}, {{{ContraFun2}}}, and {{{ContraFun3}}} all use the last type parameter in at least one {{{n}}} position, GHC would reject a derived {{{Functor}}} instance for each of them.
     192
     193== Requirements for legal instances ==
     194
     195This mechanism cannot derive {{{Functor}}}, {{{Foldable}}}, or {{{Traversable}}} instances for all data types. Currently, GHC checks if a data type meets the following criteria:
     196
     1971. The data type has at least one type parameter. (For example, {{{data NoArg = NoArg}}} cannot have a {{{Functor}}} instance.)
     1982. The data type's last type parameter cannot be used contravariantly. (see the section on covariant and contravariant positions.)
     1993. The data type's last type parameter cannot be used in the "wrong place" in any constructor's data arguments. For example, in {{{data Right a = Right [a] (Either Int a)}}}, the type parameter {{{a}}} is only ever used as the last type argument in {{{[]}}} and {{{Either}}}, so both {{{[a]}}} and {{{Either Int a}}} values can be {{{fmap}}}ped. However, in {{{data Wrong a = Wrong (Either a a)}}}, the type variable {{{a}}} appears in a position other than the last, so trying to {{{fmap}}} an {{{Either a a}}} value would not typecheck.
     200
     201   Note that there are two exceptions to this rule: tuple and function types.
     2024. The data type cannot use {{{-XDatatypeContexts}}}. For example, {{{data Ord a => O a = O a deriving Functor}}} would be rejected.
     2035. The data type's last type variable must be truly universally quantified, i.e., it must not have any class or equality constraints. This means that the following is legal:
     204
     205{{{#!hs
     206data T a b where
     207    T1 :: a -> b -> T a b      -- Fine! Vanilla H-98
     208    T2 :: b -> c -> T a b      -- Fine! Existential c, but we can still map over 'b'
     209    T3 :: b -> T Int b         -- Fine! Constraint 'a', but 'b' is still polymorphic
     210
     211deriving instance Functor (T a)
     212
     213{-
     214instance Functor (T a) where
     215    fmap f (T1 a b) = T1 a (f b)
     216    fmap f (T2 b c) = T2 (f b) c
     217    fmap f (T3 x)   = T3 (f x)
     218-}
     219}}}
     220
     221   but the following is not legal:
     222
     223{{{#!hs
     224data T a b where
     225    T4 :: Ord b => b -> T a b  -- No!  'b' is constrained
     226    T5 :: b -> T b b           -- No!  'b' is constrained
     227    T6 :: T a (b,b)            -- No!  'b' is constrained
     228}}}
     229
     230For derived {{{Foldable}}} and {{{Traversable}}} instances, a data type cannot use function types. This restriction does not apply to derived {{{Functor}}} instances, however.
     231
     232=== Proposal: relax universality check for {{{DeriveFoldable}}} ===
     233
     234In the Requirements for legal instances section, restriction 5 applies to {{{DeriveFunctor}}}, {{{DeriveFoldable}}}, and {{{DeriveTraversable}}} alike. However, {{{Foldable}}} instances are unique in that they do not produce constraints, but only consume them. Therefore, it is permissible to derive {{{Foldable}}} instances for constrained data types (e.g., GADTs), so restriction 5 should be lifted for {{{DeriveFoldable}}}.
     235
     236For example, consider the following GADT:
     237
     238{{{#!hs
     239data T a where
     240    T1 :: Ord a => a -> T a
     241}}}
     242
     243In the type signatures for {{{fmap :: Functor t => (a -> b) -> t a -> t b}}} and {{{traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)}}}, the {{{t}}} parameter appears both in an argument and the result type, so pattern-matching on a value of {{{t}}} must not impose any constraints, as neither {{{fmap}}} nor {{{traverse}}} would typecheck.
     244
     245{{{Foldable}}}, however, only mentions {{{t}}} in argument types:
     246
     247{{{#!hs
     248class Foldable t where
     249    fold :: Monoid m => t m -> m
     250    foldMap :: Monoid m => (a -> m) -> t a -> m
     251    foldr :: (a -> b -> b) -> b -> t a -> b
     252    foldr' :: (a -> b -> b) -> b -> t a -> b
     253    foldl :: (b -> a -> b) -> b -> t a -> b
     254    foldl' :: (b -> a -> b) -> b -> t a -> b
     255    foldr1 :: (a -> a -> a) -> t a -> a
     256    foldl1 :: (a -> a -> a) -> t a -> a
     257    toList :: t a -> [a]
     258    null :: t a -> Bool
     259    length :: t a -> Int
     260    elem :: Eq a => a -> t a -> Bool
     261    maximum :: forall a. Ord a => t a -> a
     262    minimum :: forall a. Ord a => t a -> a
     263    sum :: Num a => t a -> a
     264    product :: Num a => t a -> a
     265}}}
     266
     267Therefore, a derived {{{Foldable}}} instance for {{{T}}} would typecheck:
     268
     269{{{#!hs
     270instance Foldable T where
     271    foldr f z (T1 a) = f a z -- foldr :: Ord a => (a -> b -> b) -> b -> T a -> b
     272    foldMap f (T1 a) = f a   -- foldMap :: (Monoid m, Ord a) => (a -> m) -> T a -> m
     273}}}
     274
     275Deriving {{{Foldable}}} instances for GADTs with equality constraints can become murky, however. Consider this GADT:
     276
     277{{{#!hs
     278data E a where
     279    E1 :: (a ~ Int) => a   -> E1 a
     280    E2 ::              Int -> E1 Int
     281    E3 :: (b ~ Int) => b   -> E1 Int
     282    E4 :: (a ~ Int) => Int -> E1 a
     283}}}
     284
     285All four {{{E}}} constructors have the same "shape" in that they all take an argument of type {{{a}}} (or {{{Int}}}, to which {{{a}}} is constrained to be equal). Does that mean all four constructors would have their arguments folded over? While it is possible to derive perfectly valid code which would do so:
     286
     287{{{#!hs
     288instance Foldable E where
     289    foldr f z (E1 e) = f e z
     290    foldr f z (E2 e) = f e z
     291    foldr f z (E3 e) = f e z
     292    foldr f z (E4 e) = f e z
     293
     294    foldMap f (E1 e) = f e
     295    foldMap f (E2 e) = f e
     296    foldMap f (E3 e) = f e
     297    foldMap f (E4 e) = f e
     298}}}
     299
     300it is much harder to determine which arguments are equivalent to {{{a}}}. Also consider this case:
     301
     302{{{#!hs
     303data UnknownConstraints a where
     304    UC :: Mystery a => Int -> UnknownConstraints a
     305}}}
     306
     307For all we know, it may be that {{{a ~ Int => Mystery a}}}. Does this mean that the {{{Int}}} argument in {{{UC}}} should be folded over?
     308
     309To avoid these thorny edge cases, we only consider constructor arguments whose types are ''syntactically'' equivalent to the last type parameter. In the above {{{E}}} example, only {{{E1}}} fits the bill, so the derived {{{Foldable}}} instance should actually be:
     310
     311{{{#!hs
     312instance Foldable E where
     313    foldr f z (E1 e) = f e z
     314    foldr f z (E2 e) = z
     315    foldr f z (E3 e) = z
     316    foldr f z (E4 e) = z
     317
     318    foldMap f (E1 e) = f e
     319    foldMap f (E2 e) = mempty
     320    foldMap f (E3 e) = mempty
     321    foldMap f (E4 e) = mempty
     322}}}
     323
     324For the original discussion on this proposal, see [https://ghc.haskell.org/trac/ghc/ticket/10447 #10447].