Why is liftA2 added to Applicative as a method?

Question

I came across this discussion on the Haskell mailing list. From the discussion, there seems to be performance implications with adding liftA2 as a method of Applicative. Can you provide concrete examples why it is necessary to add liftA2 to Applicative methods?

Answer 1

The email is written in 2017. At that time the Applicative typeclass looked like:

class Functor f => Applicative f where
    -- | Lift a value.
    pure :: a -> f a

    -- | Sequential application.
    (<*>) :: f (a -> b) -> f a -> f b

    -- | Sequence actions, discarding the value of the first argument.
    (*>) :: f a -> f b -> f b
    a1 *> a2 = (id <$ a1) <*> a2
    -- This is essentially the same as liftA2 (const id), but if the
    -- Functor instance has an optimized (<$), we want to use that instead.

    -- | Sequence actions, discarding the value of the second argument.
    (<*) :: f a -> f b -> f a
    (<*) = liftA2 const

So without the liftA2 as part of the Applicative typeclass. It was defined as [src]:

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = fmap f a <*> b

so one could not make a special implementation in the typeclass. This means that sometimes liftA2 can be implemented more efficiently, but one can not define that.

For example the Maybe functor and Applicative are implemented as:

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap _ Nothing = Nothing

instance Applicative Maybe where
    pure = Just
    Just f <*> Just x = Just (f x)
    _ <*> _ = Nothing

This thus means that the liftA2 for a Maybe is implemented similar to:

liftA2Maybe :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
liftA2Maybe f x y = apMaybe (fmapMaybe f x) y
    where fmapMaybe f (Just x) = Just (f x)
          fmapMaybe _ Nothing = Nothing
          apMaybe (Just f) (Just x) = Just (f x)
          apMaybe _ _ = Nothing

But this is not optimal. It means that fmapMaybe will inspect if the parameter is a Just x, or Nothing, and then return a Just (f x) or a Nothing. But regardless, apMaybe will again inspect that, whereas we can already know that in advance. We can make a more efficient implementation with:

liftA2Maybe :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
liftA2Maybe f (Just x) (Just y) = Just (f x y)
liftA2Maybe _ _ _ = Nothing

here we avoid extra unpacking of data constructors. This is not that problematic however. For certain data structures like a ZipList the overhead will be more severe because the number of objects is larger.

On June 23, 2017, a new base library was published where the liftA2 function was added as a method to the Applicative type class.