Аппликативный экземпляр для бесплатной монады

Пытаясь найти монаду haskell, которая может выполняться поэтапно / разрешает многопоточность, я обнаружил бесплатную монаду

data Free f a = Return a | Roll (f (Free f a))

со своим экземпляром монады

instance (Functor f) => Monad (Free f) where
  return = Return
  Return x    >>= f = f x
  Roll action >>= f = Roll $ fmap (>>= f) action

и его экземпляр функтора

instance (Functor f) => Functor (Free f) where
  fmap f (Return x) = Return (f x)
  fmap f (Roll   x) = Roll $ fmap (fmap f) x

Я знаю, что каждая монада - это аппликативный функтор с pure = return и (<*>) = ap. Для меня аппликативные функторы концептуально сложнее монад. Для лучшего понимания аппликативных функторов мне нравится иметь аппликативный экземпляр, не прибегая к ap.

Первая строка для <*> проста:

instance (Applicative f) => Applicative (Free f) where
  pure = Return
  Return f <*> x = fmap f x -- follows immediately from pure f <*> x = f <$> x
--Roll   f <*> x = Roll $ (fmap ((fmap f) <*>)) x -- wrong, does not type-check

Как определить Roll f <*> x в общих чертах с fmap и <*>?


haskell applicative free-monad
person Franky    schedule 01.03.2014    source источник

Ответы (1)


arrow_upward
19
arrow_downward

Подойдет ли это?

instance (Functor f) => Applicative (Free f) where
  pure = Return
  Return f  <*> as  = fmap f as
  Roll faf  <*> as  = Roll (fmap (<*> as) faf)

План состоит в том, чтобы действовать только на листьях дерева, которое производит функцию, поэтому для Return мы действуем, применяя функцию ко всем значениям аргументов, созданным действием аргумента. Что касается Roll, мы просто делаем со всеми под-действиями то же, что намереваемся сделать с общим действием.

Важно отметить, что то, что мы делаем, когда мы достигаем Return, уже установлено до того, как мы начнем. Мы не меняем свои планы в зависимости от того, где мы находимся на дереве. Это отличительная черта Applicative: структура вычислений фиксирована, поэтому значения зависят от значений, а действия - нет.

person pigworker    schedule 02.03.2014