Why is there no `-XDeriveApplicative` extension?

Question

GHC has several useful language extensions for mechanically deriving various common Haskell typeclasses (-XDeriveFunctor, -XDeriveFoldable, -XDeriveTraversable). It seems that Applicative is another class which is often needed and frequently easily derived. For a simple record containing slots of type a, e.g.,

data SimpleRecord a = Simple a a a

the Applicative instance is trivially derived,

instance Applicative SimpleRecord where
    pure x = Simple x x x
    Simple a1 b1 c1 <*> Simple a2 b2 c2 = Simple (a1 a2) (b1 b2) (c1 c2)

Even in the slightly harder case where some a values are buried in other applicative functors, e.g.,

data MyRecord f a = MyRecord (f a) a

a reasonable instance is easily written,

instance (Applicative f) => Applicative (MyRecord f) where
    pure x = MyRecord (pure x) x
    MyRecord a1 b1 <*> MyRecord a2 b2 = MyRecord (a1 <*> a2) (b1 b1)

Why is it that a -XDeriveApplicative extension implementing these sorts of mechanical instances does not exist? Even the derive and generic-derive packages apparently lack Applicative support. Is there a theoretical issue precluding these instances from being usually valid (beyond those reasons that might also threaten the Functor, Foldable, or Traversable extensions)?

Jacobin

Answer 1

There is at most one instance of Functor for a given data type that follows the functor laws. For example, map is the only lawful implementation of fmap for lists:

fmap id      == id
fmap (f . g) == fmap f . fmap g

But there can be more than one law-abiding instance of Applicative, which isn’t necessarily obvious.

pure id <*> v              == v
pure (.) <*> u <*> v <*> w == u <*> (v <*> w)
pure f <*> pure x          == pure (f x)
u <*> pure y               == pure ($ y) <*> u

For lists, <*> can behave like \fs xs -> concatMap (\f -> map f xs) fs or like zipWith ($), and it isn’t clear which one the compiler should choose.

Touchstone

In the case of pure things seem quite unambiguous (you only have one a and can unambiguously insert it into the structure assuming each constituent functor is applicative. In the case of <*> there is the problem of ordering, but it seems perfectly reasonable (and often the user's intention) to simply apply corresponding fields for single constructor types. For anything more complicated (including ADTs) the compiler could simply refuse to derive the instance. – Jacobin

This same objection could be used against -XDeriveTraversable, could it not? The Traversable definition states that the actions should be sequenced "from left to right" although it still strikes me that it isn't always clear what this means. – Jacobin

@bgamari: Yes, the compiler could simply fail when the data type doesn’t have a particular structure, but that seems too arbitrary. If there is at least one possible instance, there may always be multiple—I don’t know. – Touchstone

There are many ways to derive Ord as well, that's not a problem as long as it's well specified what deriving does. – Carousel

@Jacobin Actually even pure isn't unambiguous. For the standard applicative functor for lists pure gives you a singleton list, but to make the applicative laws work the ZipList pure has to give you the infinite list of repetitions of the injected value! hackage.haskell.org/packages/archive/base/latest/doc/html/src/… – Ascogonium

@augustss: one difference is that for many cases it doesn't matter what ordering is used so long as it's used consistently. Contrast that with Applicative, which is useful mainly for the actual properties of the instance. – Designing

Even if it's possible to pick a particular implementation of (<*>) by default, is it possible to always guarantee that the default pure/fmap/(<*>) uphold the Applicative laws? – Nonnah

Answer 2

To echo others, there's no good reason I know of why we can't have -XDeriveApplicative, we simply happen not to. There are typically more than one lawful instance of Foldable and Traversable, and we have a flag to derive those. For a while we had no real good story for traversable laws, but now we have some. Similarly we still have no Foldable laws (but I think we can, see here).

Among the different 'obvious' applicatives, such as forwards and backwards ones (vis a vis <*> itself, and even permuted vis a vis the multiple a in an f a if there are such), then building applicatives as suggested here, with traversal in syntactic order, seems legitimate. However, for recursive types such as lists, or even types with multiple constructors, our choice of valid applicatives blossoms in interesting ways. For listlike regular recursive types, the obvious applicative choice is naturally the "zipLike" once, since it generalizes the nonrecursive case in the natural way, matching structure with structure. For sum types with multiple constructors, the "obvious" choice is much harder to define.

It seems to me that an entirely reasonable derivation of applicative would work as suggested here, in syntactic order on types (including recursive ones) with only one constructor. In cases of multiple constructors, failure seems legitimate.

On the other hand, while Foldable and Traversable seem to come up frequently in their "obvious" forms, its not too clear to me how many times we wish to define "obvious" applicatives, as compared to interesting ones. My intuition tells me this feature would be seldom-exercised, and perhaps simply not frequently useful.

Kopaz

Answer 3

Next release of GHC's base will include

• newtype Generically a = Generically a
• newtype Generically1 f a = Generically1 (f a)

in GHC.Generics.

This allows exactly those instances to be derived out of the box

{-# Language DeriveGeneric #-}
{-# Language DerivingVia #-}
{-# Language DerivingStrategies #-}
..

import GHC.Generics

data SimpleRecord a = Simple a a a
 deriving
 stock Generic1

 deriving (Functor, Applicative)
 via Generically1 SimpleRecord

data MyRecord f a = MyRecord (f a) a
 deriving
 stock Generic1

 deriving (Functor, Applicative)
 via Generically1 (MyRecord f)

This only works for product types, Applicative for sum types is a lot more diverse since we need a coherent way to mediate between the constructors. This requires a function that preserves the Applicative structure (Applicative morphism) called Idiom in this package I wrote:

https://hackage.haskell.org/package/idiomatic

This package allows deriving Applicative for sum types with a type level configuration of Applicative morphisms.

Kulun

Other commentor mentioned order. To derive Applicative with "backwards" effects you simply derive via Backwards (Generically1 SimpleRecord). – Kulun