無料のモナドとファンクタの固定点の違いは？

Question

私は抽象構文木が命令セットを表すファンクタのフリーモナドとして派生したhttp://www.haskellforall.com/2013/06/from-zero-to-cooperative-threads-in-33.htmlを読んでいました。無料のモナドFreeは、ファンクタの固定小数点演算子と大きく異なるわけではないことに気づいたFix。

この資料では、これらのAST（固定点）を簡潔な方法で構築するために、モナド操作とdo構文を使用しています。それが無料のモナドインスタンスからの唯一のメリットかどうか疑問に思っていますか？他にも興味深いアプリケーションがありますか？

Answer 1

（NBこれは、両方の鉱山から、上ガブリエルのコメント@ビットを兼ね備えています。）

をFunctorのFixエド・ポイントのすべての住民が無限であるためにはそれが可能だ、つまりlet x = (Fix (Id x)) in x === (Fix (Id (Fix (Id ...))))はのだけ住人でありますFix Identity。 Freeは、少なくとも有限住人Free fが確実に存在する点で、Fixとすぐに異なります。実際、Fix fに無限の住人がある場合、Free fには無限に多くの有限の住人がいます。

この無限のもう一つの即時の副作用は、Functor f => Fix fがもうFunctorではないということです。 fmap :: Functor f => (a -> b) -> (f a -> f b)を実装する必要がありますが、Fixにはaを含むf aの「すべての穴がいっぱいです」というメッセージが含まれているため、 '関数にはaが適用されなくなりました。

我々はreturn :: a -> Free f aを実装すると言う、この法律はfmap f . return = return . fを保持する、したいのですが、それもFunctor f => Fix fに意味がありませんので、これはMonad Sを作成するために重要です。

どのようにFreeはこれらを「修正」しますか？Fixエドポイントはありますか？ Pureコンストラクタを使用して、ベースファンクタを「追加」します。従って、すべてについてFunctor f、Pure :: a -> Free f a。これは私たちが保証するタイプの有限の住人です。また、すぐに、returnのよく振る舞う定義を与えてくれます。

return = Pure 

だからFixによって作成されたネストされたFunctor秒の潜在的に無限の「木」を取り出してPureに代表される「リビング」芽、いくつかの数で混合としてこのほか考えるかもしれません。 returnを使用して新しい芽を作成します。これは、後でその芽に「戻って」計算を追加するという約束として解釈される可能性があります。実際には、これはまさにflip (>>=) :: (a -> Free f b) -> (Free f a -> Free f b)の機能です。タイプaに適用できる「継続」関数f :: a -> Free f bが与えられた場合、我々はそれぞれPure aに戻り、f aとして計算された継続と置き換えてツリーを再帰します。これは私たちの木を "成長"させます。

---

は今、Freeは明らかにFixよりも一般的です。この家を運転するには、タイプFunctor f => Fix fを対応するFree f aのサブタイプとして見ることができます。 data Void = Void Void（つまり、作成できないタイプ、空のタイプ、インスタンスがないタイプ）のa ~ Voidを選択してください。

は、私たちが break :: Fix f -> Free f aで私たちの Fix D」 Functor秒を破ると、その後 affix :: Free f Void -> Fix fでそれを反転しようとすることができ、それがより明確にします。

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

注は、まずそのaffixがあるため、この場合x :: VoidでPure xケースを処理する必要はありませんので、が本当にが存在しないので、Pure xは不合理であり、我々はそれを無視します。

もaタイプが唯一それがbreakの任意のユーザに対して完全にアクセスできないだように、戻り値の型、Free f aに表示されますので、breakの戻り値の型は少し微妙であることに注意してください。 「完全にアクセスできない」、「インスタンス化できません」は、タイプにかかわらず、affixとbreakが逆であるという最初のヒントを与えますが、われわれはそれを証明することができます。 (break . affix)が同一であることを（共誘導、または単に直感的、おそらく）を示すべき

(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) 

。他の方向は完全に同一のやり方で進む。

これは、Free fがFix fすべてがFunctor fであることを示しています。

---

だからなぜFixを使用しますか？場合によっては、fのレイヤーの副作用のために、Free f Voidのプロパティのみが必要な場合があります。この場合、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となります。しかし、これらはちょっとばかげている。

Answer 2

深い「単純な」接続があります。

これは、adjoint functor theoremの結果であり、左括弧は初期オブジェクトを保持します：L 0 ≅ 0です。

カテゴリ：Free fカテゴリからそのF-algebrasへのファンクタです（Free fは、忘却型ファンクタに迂回したままにしておきます）。Haskでの作業当初代数はVoid

Free f Void ≅ 0 

で、F-代数のカテゴリに始代数はFix fです：Free 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 <$> body) 

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

同様

、右adjoints（Cofree f、からファンクタHaskをF-co algebrasのカテゴリに分類すると、最終オブジェクト：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 <$> body) 

fixToCofree :: Functor f => Fix f -> Cofree f() 
fixToCofree (Fix body) =() :< (fixToCofree <$> 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)