のドキュメントにFreeは次のように書かれています：
多くの一般的なモナドが自由モナドとして発生し、
- 与えられ
data Empty aたは、モナドFree Emptyに同型です。Identity- Free
Maybeを使用して、各層が計算をしばらく実行することを表す部分モナドをモデル化できます。
を使用して表現できる他のモナドは何Freeですか?
もう 1 つしか考えられませんでしFree (Const e)たEither e。
編集:使用して表現できないモナドFreeとその理由は?
それらのほとんどすべて (ループおよび に関連する問題までmfix) ではありませんCont。
Stateモナドを考える
newtype State s a = State (s -> (a,s))
フリーモナドのようには見えません...しかし、それをどのように使用するかStateという観点から考えてください
get :: m s --or equivalently (s -> m a) -> m a
set :: s -> m () --or (s,m a) -> m a
runState :: m a -> s -> (a,s)
操作をコンストラクターとしてリストすることにより、このインターフェースで自由なモナドを設計できます。
data StateF s a
= Get (s -> a) | Set s a deriving Functor
それから私たちは持っています
type State s a = Free (StateF s) a
と
get = Impure (Get Pure)
set x = Impure (Set x (Pure ())
そして、それを使用する方法が必要です
runState (Pure a) s = (a,s)
runState (Impure (Get f)) s = runState (f s) s
runState (Impure (Set s next)) _ = runState next s
ほとんどのモナドでこの構築を行うことができます。Maybe/partiality モナドが定義されているように
stop :: m a
maybe :: b -> (a -> b) -> m a -> b
ルールは、m x一部で終わる関数のそれぞれをxファンクターのコンストラクターとして扱い、他の関数は結果のフリーモナドを実行する方法です。この場合
data StopF a = StopF deriving Functor
maybe _ f (Pure a) = f a
maybe b _ (Impure Stop) = b
なぜこれはクールなのですか？さて、いくつかのこと
f a -> aに一部の関数にすぎません) が与えられた場合、構成もその代数を持ちます。 af関手合成はただのことです いくつかの方法で関手を組み合わせることができますが、そのほとんどはその代数を維持します。この場合、ファンクターの合成では (f (g (x)))なく、ファンクターの共積が必要です。ファンクタ追加
data f :+: g a = Inl (f a) | Inr (g a)
instance (Functor f, Functor g) => Functor (f :+: g) where
fmap f (Inl x) = Inl (fmap f x)
fmap f (Inr x) = Inr (fmap f x)
compAlg :: (f a -> a) -> (g a -> a) -> f :+: g a -> a
compAlg f _ (Inl x) = f x
compAlf _ g (Inr x) = g x
フリーモナドも代数を保存する
freeAlg :: (f a -> a) -> Free f a -> a
freeAlg _ (Pure a) = a
freeAlg f (Impure x) = f $ fmap (freeAlg f) x
Wouter Swierstra の有名な論文Data Types A La Carteでは、これが非常に効果的に使用されています。その論文の簡単な例は電卓です。この投稿の新しいモナドを取り上げます。与えられた代数
class Calculator f where
eval :: f Integer -> Integer
様々な事例が考えられます
data Mult a = Mult a a deriving Functor
instance Calculator Mult where
eval (Mult a b) = a*b
data Add a = Add a a deriving Functor
instance Calculator Add where
eval (Add a b) = a+b
data Neg a = Neg a deriving Functor
instance Calculator Neg where
eval (Neg a) = negate a
instance Calculator (Const Integer) where
eval (Const a) = a
data Signum a = Signum a deriving Functor
instance Calculator Signum where
eval (Signum a) = signum a
data Abs a = Abs a deriving Functor
instance Calculator Abs where
eval (Abs a) = abs a
そして最も重要な
instance (Calculator f, Calculator g) => Calculator (f :+: g) where
eval = compAlg eval
数値モナドを定義できます
newtype Numerical a = Numerical (
Free (Mult
:+: Add
:+: Neg
:+: Const Integer
:+: Signum
:+: Abs) a deriving (Functor, Monad)
そして、あなたは定義することができます
instance Num (Numerical a)
まったく役に立たないかもしれませんが、とてもクールだと思います。次のような他のものを定義できます
class Pretty f where
pretty :: f String -> String
instance Pretty Mult where
pretty (Mult a b) = a ++ "*" ++ b
残りのすべてについても同様です。
これは有用な設計戦略です: モナドに実行させたいことをリストします ==> 各操作のファンクターを定義します ==> その代数のいくつかがどうあるべきかを理解します ==> 各操作のファンクターを定義します ==> 作成します速い。
高速化は難しいですが、いくつかのトリックがあります。トリック 1 は、フリー モナドを (「高速化ボタン」で) ラップするCodensityことですが、それがうまくいかない場合は、フリー モナドを取り除きたいと考えます。私たちが持っていたときを思い出してください
runState (Pure a) s = (a,s)
runState (Impure (Get f)) s = runState (f s) s
runState (Impure (Set s next)) _ = runState next s
Free StateF aこれは、状態の定義が合理的であるように見えるため、結果の型を使用するための関数s -> (a,s)です...しかし、操作をどのように定義するのでしょうか? この場合、あなたは答えを知っていますが、それを導き出す 1 つの方法は、Conal Elliott が型クラス射と呼ぶものの観点から考えることです。あなたがしたい
runState (return a) = return a
runState (x >>= f) = (runState x) >>= (runState f)
runState (set x) = set x
runState get = get
それはそれをかなり簡単にします
runState (return a) = (Pure a) = \s -> (a,s)
runState (set x)
= runState (Impure (Set x (Pure ())))
= \_ -> runState (Pure ()) x
= \_ -> (\s -> (a,s)) x
= \_ -> (a,x)
runState get
= runState (Impure (Get Pure))
= \s -> runState (Pure s) s
= \s -> (s,s)
これはかなり役に立ちます。この方法で導出>>=するのは難しい場合があるため、ここには含めませんが、これらの他の定義はまさにあなたが期待する定義です。
述べられているように質問に答えるために、質問で言及しなかったおなじみのモナドのほとんどは、それ自体が無料のモナドではありません。Philip JF の答えは、与えられたモナドを新しい自由なモナドに関連付ける方法をほのめかしていますが、新しいモナドは「より大きく」なります。元のモナドよりも明確な値を持っています。たとえば、実State sモナドは を満たしますget >>= put = return ()が、自由モナドは満たしStateFません。自由なモナドとして、定義上余分な方程式を満たさない。それがまさに自由の概念です。
//の特別な条件下を除いてReader r、Writer wとモナドはフリーではないことを示します。State srws
いくつかの用語を紹介しましょう。mがモナドの場合、型m aの任意の値を ( m-) アクションと呼びます。-action がfor some ;mと等しい場合、それを自明と呼びます。それ以外の場合は、非自明と呼びます。return xx
m = Free fがファンクター上の任意の自由モナドである場合f、へmのモナド準同型を認めMaybeます。これは、Freeがその引数でファンクトリアルでfありMaybe = Free (Const ())、Const ()がファンクターのカテゴリの終端オブジェクトであるからです。具体的には、この準同型写像は次のように書ける。
toMaybe :: Free f a -> Maybe a
toMaybe (Pure a) = Just a
toMaybe (Impure _) = Nothing
toMaybeはモナド準同型であるため、特に任意toMaybe (v >> w) = toMaybe v >> toMaybe wのm-actionvおよび を満たしwます。ここで、自明なアクションを自明なアクションにtoMaybe送信し、非自明なアクションを非自明なアクションに送信することを確認します。自明でないアクションを任意のアクションで処理すると、いずれの順序でも、自明でないアクションが生成されるというプロパティが追加されました ( )。は (非) 自明性を維持するモナド準同型であるため、同じことが にも当てはまります。mMaybemMaybeNothingMaybe>>Nothing >> w = v >> Nothing = NothingmtoMaybe
>>(必要に応じて、自由モナドの式から直接これを確認することもできます。)
特定のモナドmが任意の自由モナドと同型でないことを示すには、少なくとも と の 1 つが自明ではないが自明であるm-actionvなどを見つければ十分です。wvwv >> w
Reader rを満たすため、少なくとも 2 つの値を持つ限り存在する非自明なアクションv >> w = wを選択する必要があります (その場合、非定数、つまり非自明です)。w = return ()vrask
について、恒等性以外にWriter w可逆要素があるとします。をその逆にしますk :: w。kinv :: w次にtell k >> tell kinv = return ()、しかしtell kとtell kinvは自明ではありません。任意の非自明なグループ (たとえば、足し算の整数) は、そのような要素 を持ちますk。形式の自由モナドはWriter w、モノイドw自体が自由であるもの、つまり 、w = [a]のみであると推測しWriter w ~ Free ((,) a)ます。
に対してState s、同様に、逆 を伴うs自明ではない自己同形を認める場合、. 少なくとも 2 つの要素と決定可能な等価性を持つ型には、このような自己同型があります。f :: s -> sfinv :: s -> smodify f >> modify finv = return ()s
すべてのモナドはフリーモナドとして表現できます。FreeMonadはFreeMonadFixまたはFreeContではないため、それらの追加のプロパティ（MonadFixやContなど）をそのように取り除くことができます。
一般的な方法は、liftMの観点からFunctorのfmapを定義してから、そのFunctorをFreeでラップすることです。return結果のモナドは、関数とjoin（純粋および不純）を実際のモナドにマップする方法を指定することにより、前の/実際のモナドに減らすことができます。