Разница между свободными монадами и точками фиксирования функторов?

я читалhttp://www.haskellforall.com/2013/06/from-zero-to-cooperative-threads-in-33.html где абстрактное синтаксическое дерево выводится как свободная монада функтора, представляющего набор инструкций. Я заметил, что свободная монадаСвободно не сильно отличается от оператора фиксированной точки на функторахФикс.

В статье используются операции монады иdo синтаксис для создания этих AST (точек фиксации) в сжатой форме. Я'мне интересно, если этоединственная выгода от бесплатного экземпляра монады? Есть ли другие интересные приложения, которые он включает?

 J. Abrahamson04 июл. 2013 г., 20:14
Тогда еще раз с чувством!
 Gabriel Gonzalez26 июн. 2013 г., 03:06
Основное преимущество переноса морфизмов изFix вFree если вы хотите использоватьdo обозначения или комбинаторы изControl.Monad, Если вы неэти вещи не нужны, и вы можете собратьFix значения вручную, то нет необходимости проходить черезFree промежуточный. Просто подумай оFreeT f m Void как удобный монадический способ построения значений типаFix это немного больше для начинающих.
 J. Abrahamson26 июн. 2013 г., 00:31
Monad инстанс обогащаетFix с двумя вещами - определенное прекращение изreturn и натуральныйрасширение» от(>>=), Обычный(Fix f) не может быть гарантированно иметь какие-либо (конечные) значения вообще (т.е.(Fix Identity)), но(Free f) всегда заселен по крайней мереPure
 Daniel Velkov26 июн. 2013 г., 01:57
@GabrielGonzalez можете ли вы уточнить вторую часть вашего комментария? Каков пример использования?
 J. Abrahamson26 июн. 2013 г., 08:44
@DanielVelkov Также у вас естьaffix :: Functor f => Free f Void -> Fix f гдеaffix (Free f) = Free (fmap affix f), Ты нене нужноPure случай сPure (a :: Void) противоречиевы можете't имеет значения типа.Void
 Fixpoint04 июл. 2013 г., 15:28
@tel, вы должны преобразовать свой комментарий в ответ.
 Gabriel Gonzalez26 июн. 2013 г., 02:17
@DanielVelkov Вы используете трюк возврата Void всякий раз, когда хотите получить лучшее из обоих миров: то есть использовать свободную монаду для сборки типа данных, а затем использовать F-алгебру для его интерпретации. Возвращаемое значение Void гарантирует, что созданная вами свободная монада изоморфна фиксированной точке базового функтора, когда вы закончите.
 Daniel Velkov26 июн. 2013 г., 02:25
@GabrielGonzalez Есть ли библиотечная функция, которая выполняет преобразование? Имеет ли смысл переносить все морфизмы с Fix на Free?
 Gabriel Gonzalez25 июн. 2013 г., 23:05
Основным преимуществом экземпляра монады являетсяdo запись и повторное использование комбинаторов изControl.Monad (лайкreplicateM_ а такжеforM_ в примерах). Обычный трюк - создать тип, используя свободную монаду, но затем требовать, чтобы результат имел типFreeT f m Void так что он может быть преобразован в фиксированную точку функтора.
 J. Abrahamson26 июн. 2013 г., 08:38
Фикс имеет преимущество бытьnewtype что может помочь компилятору срывать слои, но яя не уверен в свете всех окончательных / CPS кодировокfree которые лгут

Ответы на вопрос(2)

Это'является следствиемтеорема о сопряженном функтореЛевые примыкающие сохраняют начальные объекты:.L 0 ≅ 0

Категорически,Free f является функтором от категории к ее F-алгебрам (Free f остается присоединенным к забывчивому функтору, идущему в другую сторону »круглый). Работает вHask наша начальная алгебраVoid

Free f Void ≅ 0

и начальная алгебра в категории F-алгебр:Fix fFree f Void ≅ Fix f

import Data.Void
import Control.Monad.Free

free2fix :: Functor f => Free f Void -> Fix f
free2fix (Pure void) = absurd void
free2fix (Free body) = Fix (free2fix <
import Data.Void
import Control.Monad.Free

free2fix :: Functor f => Free f Void -> Fix f
free2fix (Pure void) = absurd void
free2fix (Free body) = Fix (free2fix <$> body)

fixToFree :: Functor f => Fix f -> Free f Void
fixToFree (Fix body) = Free (fixToFree <$> body)
gt; body) fixToFree :: Functor f => Fix f -> Free f Void fixToFree (Fix body) = Free (fixToFree <
import Data.Void
import Control.Monad.Free

free2fix :: Functor f => Free f Void -> Fix f
free2fix (Pure void) = absurd void
free2fix (Free body) = Fix (free2fix <$> body)

fixToFree :: Functor f => Fix f -> Free f Void
fixToFree (Fix body) = Free (fixToFree <$> body)
gt; body)

Точно так же справа примыкает (Cofree fФунктор изHask в категорию F-Колорадоалгебры) сохраняет конечные объекты:R 1 ≅ 1

ВHask это блок:() и конечный объект F-Колорадоалгебры такжеFix f (они совпадают вHask) так мы получаем:Cofree f () ≅ Fix f

import Control.Comonad.Cofree

cofree2fix :: Functor f => Cofree f () -> Fix f
cofree2fix (() :< body) = Fix (cofree2fix <
import Control.Comonad.Cofree

cofree2fix :: Functor f => Cofree f () -> Fix f
cofree2fix (() :< body) = Fix (cofree2fix <$> body)

fixToCofree :: Functor f => Fix f -> Cofree f ()
fixToCofree (Fix body) = () :< (fixToCofree <$> body)
gt; body) fixToCofree :: Functor f => Fix f -> Cofree f () fixToCofree (Fix body) = () :< (fixToCofree <
import Control.Comonad.Cofree

cofree2fix :: Functor f => Cofree f () -> Fix f
cofree2fix (() :< body) = Fix (cofree2fix <$> body)

fixToCofree :: Functor f => Fix f -> Cofree f ()
fixToCofree (Fix body) = () :< (fixToCofree <$> body)
gt; body)

Просто посмотрите, насколько похожи определения!

newtype Fix f 
  = Fix (f (Fix f))

Fix f являетсяFree f без переменных.

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

Fix f являетсяCofree f с фиктивными значениями.

data Cofree f a 
  = a <: f (Cofree f a)

(N.. это объединяет немного из моих и @Gabriel 'комментарии выше.)

Это'Это возможно для каждого жителяFixред точкаFunctor быть бесконечным, т.е.let x = (Fix (Id x)) in x === (Fix (Id (Fix (Id ...)))) этотолько житель.Fix IdentityFree отличается сразу отFix в том, что он обеспечивает хотя бы одинконечный жительFree f, На самом деле, еслиFix f есть какие-то бесконечные жители тогдаFree f имеет бесконечно много конечных жителей.

Еще одним непосредственным побочным эффектом этой неограниченности является то, чтоFunctor f => Fix f ISN»тFunctor больше. Мы'нужно реализоватьfmap :: Functor f => (a -> b) -> (f a -> f b), ноFix имеет "заполнил все дыры вf a который раньше содержалaтак что у нас больше нетaчтобы применить нашиfmapд функция к.

Это важно для созданияMonadпотому что мыхотел бы реализоватьreturn :: a -> Free f a и, скажем, этот закон держатfmap f . return = return . f, но это не такдаже не имеет смысла в.Functor f => Fix f

Так как жеFree "исправить» этиFixслабые места? Это "дополняющая» наш базовый функтор сPure конструктор. Таким образом, для всех,Functor fPure :: a -> Free f a, Это наш гарантированный, чтобы быть конечным жителем типа. Это также сразу дает нам правильное определение.return

return = Pure

Так что вы можете подумать об этом дополнении как о потенциально бесконечном "дерево» вложенныхFunctorс созданныйFix и смешивая в некотором количествеживой» почки, представленныеPure, Мы создаем новые почки, используяreturn что может быть истолковано как обещаниевернуть" к этому зародышу позже и добавим больше вычислений. На самом деле этос чем именноflip (>>=) :: (a -> Free f b) -> (Free f a -> Free f b) делает. Учитывая "продолжение» функцияf :: a -> Free f b которые могут быть применены к типамaмы опускаемся на дерево, возвращаясь к каждомуPure a и заменить его продолжением, вычисленным какf a, Это позволяет намрасти» наше дерево.

Сейчас,Free явно более общий, чемFix, Чтобы ехать домой, этоможно увидеть любой типFunctor f => Fix f как подтип соответствующегоFree f a! Просто выбериa ~ Void где у нас естьdata Void = Void Void (т.е. тип, который не может быть создан, является пустым типом, не имеет экземпляров).

Чтобы было понятнее, мы можем сломатьFixFunctorсbreak :: Fix f -> Free f a а затем попытаться инвертировать его с.affix :: Free f Void -> Fix f

break (Fix f) = Free (fmap break f) 
affix (Free f) = Fix (fmap affix f)

Обратите внимание, что сначалаaffix не нужно обрабатыватьPure x случай, потому что в этом случаеx :: Void и, таким образом, не можетдействительно быть там, такPure x абсурдно и мыЯ просто проигнорирую это.

Также обратите внимание, чтоbreakтип возвращаемого значения является немного тонким, так какa тип появляется только в возвращаемом типе,Free f aтак, что этоЭто абсолютно недоступно для любого пользователя. "breakПолностью недоступный " а также "не может быть создан " дать нам первый намек на то, что, несмотря на типы,affix а такжеbreak являются обратными, но мы можем просто доказать это.

(break . affix) (Free f)
===                                     [definition of affix]
break (Fix (fmap affix f))
===                                     [definition of break]
Free (fmap break (fmap affix f))
===                                     [definition of (.)]
Free ( (fmap break . fmap affix) f )
===                                     [functor coherence laws]
Free (fmap (break . affix) f)

который должен показать (коиндуктивно, или простоинтуитивновозможно) что(break . affix) это личность. Другое направление проходит совершенно идентично.

Итак, надеюсь, это показывает, чтоFree f больше чемFix f для всех .Functor f

Так зачем вообще использоватьFix? Ну, иногда вы хотите только свойстваFree f Void из-за некоторого побочного эффекта от наслоенияfs. В этом случае, называя этоFix f делает более ясным, что мы не должныпытаться(>>=) или жеfmap над типом. Кроме того, так какFix это простоnewtype компилятору может быть легчекомпилировать слоиFix так как это играет только семантическую роль в любом случае.

Примечание: мы можем более формально говорить о том, какVoid а такжеforall a. a являются изоморфными типами, чтобы более четко увидеть, как типыaffix а такжеbreak гармоничны Например, у нас естьabsurd :: Void -> a какabsurd (Void v) = absurd v а такжеunabsurd :: (forall a. a) -> Void какunabsurd a = a, Но они становятся немного глупыми.
 Jonathan Cast18 дек. 2016 г., 21:09
Если вы правильно их определили, т.е.newtype Id a = Id a а такжеnewtype Fix f = Fix (f (Fix f)), затем после ,let x = Fix (Id x)x являетсяundefined (как и ожидалось:fix id = ⊥потому что обаFix а такжеId (конструкторы) строгие.

Ваш ответ на вопрос