Можно ли реализовать `(Аппликативный m) => Аппликативный (StateT s m)`?

В настоящее время я работаю над Data.Fresh и Control.Monad.Trans.Fresh, которые соответственно. определить интерфейс для генерации свежих переменных и трансформатор монады, который реализует этот интерфейс.

Первоначально я думал, что возможно реализовать экземпляр Applicative для моего FreshT v m с единственным требованием, что Applicative m существует. Тем не менее, я застрял, и мне показалось, что мне нужно Monad m. Не доверяя моему Haskell-fu, я затем повернулся к пакету трансформаторов и был удивлен тем, что нашел в Control.Monad.Trans.State.Lazy и .Strict:

instance (Functor m, Monad m) => Applicative (StateT s m) where
    pure = return
    (<*>) = ap

Итак, вот мой вопрос: возможно ли создать экземпляр с эквивалентной семантикой со следующей головой экземпляра?

instance (Applicative m) => Applicative (StateT s m) where

Ответы

Ответ 1

Учтите, что у вас есть две функции:

 f :: s -> m (s, a -> b)
 g :: s -> m (s, a)

И вы хотите создать функцию h = StateT f <*> StateF g

 h :: s -> m (s, b)

Из вышесказанного вы можете s перейти на f, чтобы у вас было:

 f' :: m (s, a -> b)
 g :: s -> m (s, a)

Однако чтобы получить s из f', вам понадобится Monad (что бы вы ни делали с аппликативным, оно все равно будет в форме m s, поэтому вы не сможете применить значение к g).

Вы можете играть с определениями и использовать бесплатную монаду, но для краха состояния вам нужно join.

Ответ 2

Хотя, как отмечено в предыдущем ответе, этот экземпляр не может быть определен вообще, стоит отметить, что, когда f является Applicative и s является Monoid, StateT s f также Applicative, так как его можно рассматривать как композицию аппликативных функторов:

StateT s f = Reader s `Compose` f `Compose` Writer s

Ответ 3

Более слабый вариант трансформатора `Applicative`

Хотя для StateT невозможно определить аппликативный трансформатор, возможно определить более слабый вариант, который работает. Вместо того, чтобы иметь s -> m (a, s), где состояние решает следующий эффект (поэтому m должна быть монадой), мы можем использовать m (s -> (a, s)) или эквивалентно m (State s a).

import Control.Applicative
import Control.Monad
import Control.Monad.State
import Control.Monad.Trans

newtype StateTA s m a = StateTA (m (State s a))

Это строго слабее, чем StateT. Каждый StateTA можно сделать в StateT (но не наоборот):

toStateTA :: Applicative m => StateTA s m a -> StateT s m a
toStateTA (StateTA k) = StateT $ \s -> flip runState s <$> k

Определение Functor и Applicative - это только вопрос о выполнении операций State в базовом m:

instance (Functor m) => Functor (StateTA s m) where
    fmap f (StateTA k) = StateTA $ liftM f <$> k
instance (Applicative m) => Applicative (StateTA s m) where
    pure = StateTA . pure . return
    (StateTA f) <*> (StateTA k) = StateTA $ ap <$> f <*> k

И мы можем определить аппликативный вариант lift:

lift :: (Applicative m) => m a -> StateTA s m a
lift = StateTA . fmap return

Обновление: На самом деле это не нужно, так как состав двух аппликативных функторов всегда является аппликативным функтором (в отличие от монад). Наш StateTA изоморфен Compose m (State s), который автоматически Applicative:

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
    pure x = Compose (pure (pure x))
    Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

Поэтому мы могли бы написать просто