Возможно ли реализовать MonadFix для `Free`?

Question

http://hackage.haskell.org/package/free in Control.Monad.Free.Free позволяет получить доступ к "свободной монаде" для любого данного Functor, Это, однако, не имеет MonadFix пример. Это потому, что такой экземпляр не может быть записан, или он был просто опущен?

Если такой экземпляр не может быть написан, почему бы и нет?

Answer 1

Рассмотрим описание того, что mfix делает:

Неподвижная точка монадического вычисления. mfix f выполняет действие f только один раз, с возможным выводом, возвращаемым в качестве входа.

Слово "выполняет" в контексте Free, значит создание слоев Functor, Таким образом, "только один раз" означает, что в результате оценки mfix fзначения хранятся в Pure Конструкторы должны полностью определить, сколько слоев функтора создано.

Теперь, скажем, у нас есть конкретная функция once что мы знаем, всегда будет создавать только один Free конструктор, а также многие другие Pure Конструкторы необходимы для хранения значений листа. Выходные данные "единожды" будут только значениями типа Free f a которые изоморфны некоторому значению типа f a, С этим знанием мы можемFree выход once безопасно, чтобы получить значение типа f a,

Теперь обратите внимание, что потому что mfix требуется "выполнить действие только один раз", результат mfix once должен, для соответствующего случая, не содержать никакой дополнительной монадической структуры, чем once создает в одном приложении. Таким образом, мы можем сделать вывод, что значение, полученное из mfix once также должен быть изоморфным значению типа f a,

Дана любая функция с типом a -> f a для некоторых Functorfмы можем обернуть результат одним Free и получить функцию типа a -> Free f a который удовлетворяет описанию once выше, и мы уже установили, что мы можем развернуть результат mfix once чтобы получить значение типа f a назад.

Таким образом, соответствующий экземпляр (Functor f) => MonadFix (Free f) подразумевает возможность написать через описанную выше упаковку и функцию ffix :: (Functor f) => (a -> f a) -> f a это будет работать для всех случаев Functor,

Это, очевидно, не доказательство того, что вы не можете написать такой экземпляр... но если бы это было возможно, MonadFix было бы совершенно лишним, потому что вы могли бы так же легко написать ffix непосредственно. (И я полагаю, переопределить это как mfix с Monad ограничение, используя liftM, Тьфу.)

Answer 2

Ну, вдохновленный MonadFix экземпляр для MaybeЯ попробовал это (используя следующие определения Free):

data Free f a
    = Pure a
    | Impure (f (Free f a))

instance (Functor f) => Monad (Free f) where
    return = Pure
    Pure x >>= f = f x
    Impure x >>= f = Impure (fmap (>>= f) x)

instance (Functor f) => MonadFix (Free f) where
    mfix f = let Pure x = f x in Pure x

Законы таковы:

• Чистота: mfix (return . h) = return (fix h)
• Левый сжимается: mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)
• Раздвижная: mfix (liftM h . f) = liftM h (mfix (f . h))для строгого h
• Вложение: mfix (\x -> mfix (f x)) = mfix (\x -> f x x)

Чистоту легко доказать, но я столкнулся с проблемой, когда пытался доказать, что сжимается влево:

mfix (\x -> a >>= \y -> f x y)
= let Pure x = (\x -> a >>= \y -> f x y) x in Pure x
= let Pure x = a >>= \y -> f x y in Pure x
-- case a = Pure z
  = let Pure x = Pure z >>= \y -> f x y in Pure x
  = let Pure x = f x z in Pure x
  = let Pure x = (\x -> f x z) x in Pure x
  = mfix (\x -> f x z)
  = Pure z >>= \y -> mfix (\x -> f x y)
-- case a = Impure t
  = let Pure x = Impure t >>= \y -> f x y in Pure x
  = let Pure x = Impure (fmap (>>= \y -> f x y) t) in Pure x
  = Pure _|_

но

  Impure t >>= \y -> mfix (\x -> f x y)
  = Impure (fmap (>>= \y -> mfix (\x -> f x y)) t)
  /= Pure _|_

Так что, по крайней мере, если Pure а также Impure конструкторы различимы, то моя реализация mfix не удовлетворяет законам. Я не могу думать ни о какой другой реализации, но это не значит, что она не существует. Извините, я не мог осветить дальше.

Answer 3

Нет, его нельзя написать вообще, потому что не каждая Monad является экземпляром MonadFix. Каждая монада может быть реализована с помощью FreeMonad внизу. Если бы вы могли реализовать MonadFix бесплатно, то вы могли бы получить MonadFix из любой монады, что невозможно. Но, конечно, вы можете определить FreeFix для класса MonadFix.

Я думаю, это может выглядеть как-то так, но это всего лишь третье предположение (все еще не проверено):

data FreeFix m a = FreeFix { runFreeFix :: (forall r. (r -> m r) -> m r) -> m a }

instance (Monad m) => Monad (FreeFix m) where
    return a = FreeFix $ \_-> do
        return a
    f >>= g = FreeFix $ \mfx -> do
        x <- runFreeFix f mfx
        runFreeFix (g x) mfx

instance (Monad m) => MonadFix (FreeFix m) where
    mfix f = FreeFix $ \mfx -> do
        mfx (\r->runFreeFix (f r) mfx)

Идея состоит в том, что m является монадой, в которой отсутствует реализация для mfix; поэтому mfix должен быть параметром, когда FreeFix будет уменьшен.