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

Question

Пытаясь найти монаду 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 а также <*>?

Answer 1

Будет ли это делать?

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: структура вычисления фиксирована, поэтому значения зависят от значений, а действия - нет.