Почему liftA2 добавлен в Applicative как метод?

Question

Я натолкнулся на это обсуждение в списке рассылки Haskell. Из обсуждения, кажется, влияют на производительность с добавлением liftA2 в качестве метода Applicative. Можете ли вы привести конкретные примеры, почему необходимо добавить liftA2 к методам Applicative?

Answer 1

Письмо написано в 2017 году. В то время класс Applicative класса выглядел так:

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

Так что без liftA2 как часть класса типов Applicative. Он был определен как [src] :

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

, поэтому нельзя было сделать специальную реализацию в классе типов. Это означает, что иногда liftA2 может быть реализовано более эффективно, но это невозможно определить.

Например, функтор Maybe и Applicative реализованы как:

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

Таким образом, это означает, что liftA2 для Maybe реализован аналогично:

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

Но это не оптимально. Это означает, что fmapMaybe проверит, является ли параметр Just x или Nothing, а затем вернет Just (f x) или Nothing. Но независимо от того, apMaybe будет снова проверять это, тогда как мы уже можем это знать заранее. Мы можем сделать более эффективную реализацию с помощью:

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

здесь мы избегаем дополнительной распаковки конструкторов данных. Однако это не так проблематично c. Для некоторых структур данных, таких как ZipList, накладные расходы будут более серьезными, поскольку число объектов больше.

23 июня 2017 года новый * Была опубликована библиотека 1051 *, в которой функция liftA2 была добавлена ​​как метод к классу типов Applicative .