402

Free Monadという用語が時々出てくるの見てきました もがそれらが何であるかを説明せずにそれらを使用/議論しているようです。だから:無料のモナドとは何ですか?(私はモナドとHaskellの基本に精通していると思いますが、圏論については非常に大まかな知識しか持っていません。)

4

7 に答える 7

464

さらに簡単な答えは次のとおりです。モナドは、モナドコンテキストが(として定義できることjoin :: m (m a) -> m aを思い出して)折りたたまれたときに「計算」するものです。これは、モナドが計算のシーケンシャルチェーンを介してコンテキストを運ぶ方法です。シリーズの各ポイントで、前の呼び出しからのコンテキストが次の呼び出しで折りたたまれているためです。>>=x >>= y = join (fmap y x)

無料のモナドはすべてのモナドの法則を満たしますが、折りたたみ(つまり、計算)は行いません。ネストされた一連のコンテキストを構築するだけです。そのような無料のモナディック値を作成するユーザーは、それらのネストされたコンテキストで何かを行う責任があるため、そのような構成の意味は、モナディック値が作成されるまで延期できます。

于 2012-11-14T23:08:32.857 に答える
316

エドワード・クメットの答えは明らかに素晴らしいです。しかし、それは少し技術的です。これはおそらくもっとわかりやすい説明です。

無料のモナドは、ファンクターをモナドに変える一般的な方法です。つまり、任意のファンクターf Free fがモナドであると仮定します。これは、関数のペアを取得することを除いて、あまり役に立ちません。

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r

これらの最初のものはあなたがあなたのモナドに「入る」ことを可能にし、そして2番目のものはあなたにそれから「出る」方法を与える。

より一般的には、XがYであり、余分なものがPである場合、「無料のX」は、余分なものを何も取得せずにYからXに移動する方法です。

例:モノイド(X)は、追加の構造(P)を持つ集合(Y)であり、基本的に、演算(加算と考えることができます)といくつかのアイデンティティ(ゼロなど)があることを示します。

それで

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

今、私たちは皆リストを知っています

data [a] = [] | a : [a]

まあ、t私たちが知っているタイプを考えると、それ[t]はモノイドです

instance Monoid [t] where
  mempty   = []
  mappend = (++)

したがって、リストはセット(またはHaskellタイプ)に対する「自由モノイド」です。

さて、無料のモナドは同じ考えです。ファンクターを取り、モナドを返します。実際、モナドはエンドファンクターのカテゴリーではモノイドと見なすことができるため、リストの定義

data [a] = [] | a : [a]

無料のモナドの定義によく似ています

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

インスタンスはリストのインスタンスと類似MonadしていますMonoid

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)

instance Functor f => Monad (Free f) where
  return = Pure -- just like []
  x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind

今、私たちは2つの操作を取得します

-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)
于 2012-11-13T08:11:33.717 に答える
152

無料のfooは、たまたますべての「foo」の法則を満たす最も単純なものです。つまり、それはfooであるために必要な法則を正確に満たし、余分なものは何もありません。

忘却関手とは、あるカテゴリーから別のカテゴリーに移るときに、構造の一部を「忘れる」ファンクターです。

与えられた関手F : D -> C、およびG : C -> D、は、と言いますがF -| G、すべてのa、b:がと同型であるときはいつでも、に隣接したままであるか、または右に隣接しています。ここで、矢印は適切なカテゴリから来ています。FGGFF a -> ba -> G b

正式には、無料の関手は忘却関手に隣接して残されます。

自由モノイド

もっと簡単な例、自由モノイドから始めましょう。

いくつかのキャリアセットによって定義されるモノイド、T要素のペアを一緒にマッシュアップするためのバイナリ関数f :: T → T → T、および、を取りunit :: Tます。これにより、結合法則と同一性法則が得られますf(unit,x) = x = f(x,unit)

Uモノイドのカテゴリ(矢印はモノイドの準同型です。つまり、他のモノイドにマッピングされ、意味を変えずに他のモノイドにマッピングする前または後に作成できます)unitからカテゴリにファンクターを作成できます。unitのセット(矢印は単なる関数の矢印です)は、操作とを「忘れて」unit、キャリアセットを提供します。

F次に、セットのカテゴリから、このファンクターに隣接したままのモノイドのカテゴリにファンクターを定義できます。そのファンクターは、セットaをモノイド[a]、ここで、、unit = []およびにマップするファンクターですmappend = (++)

したがって、これまでの例を疑似ハスケルで確認するには、次のようにします。

U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a

F : Set → Mon -- is our free functor
F a = ([a],(++),[])

次に、F無料で表示するUには、忘却関手に隣接していることを示す必要があります。つまり、前述のように、それを表示する必要があります。

F a → b同型であるa → U b

ここで、のターゲットがモノイドFのカテゴリMonにあることを思い出してください。矢印はモノイド準同型であるため、からのモノイド準同型がから[a] → bの関数によって正確に記述できることを示す必要がありa → bます。

Haskellでは、この側面をSet(ええと、Hask私たちがふりをするHaskellタイプのカテゴリはSetです)にある側と呼びます。これは、からListsfoldMapに特化したときにタイプがあります。Data.FoldableMonoid m => (a → m) → [a] → m

これが随伴関手であることに続く結果があります。特に、忘れた場合は無料で構築し、もう一度忘れてください。これは、一度忘れたのと同じです。これを使用して、モナディック結合を構築できます。UFUF〜〜でU(FUF)あり、随伴関手を定義する同型写像を介しUFてアイデンティティモノイド準同型を渡すことができるので、からのリスト同型写像は型の関数であり、これは単にリストの戻り値です。[a][a][a] → [a]a -> [a]

次の用語でリストを説明することにより、これらすべてをより直接的に構成できます。

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

無料のモナド

では、無料のモナドとは何ですか?

さて、以前と同じことをします。矢印がモナド準同型であるモナドのカテゴリーから、矢印が自然変換であるエンドファンクターのカテゴリーまで、忘却関手Uから始め、随伴関手が残っている関手を探します。それに。

それで、これは通常使用されるフリーモナドの概念とどのように関連していますか?

何かが自由なモナドであることを知っていると、Free fからモナド準同型を与えることFree f -> mは、から自然変換(関手準同型)を与えることと同じこと(同型)であることがわかりf -> mます。F a -> bFがUに隣接したままになるには、同型でなければならないことを覚えておいてくださいa -> U b。ここでUは、モナドをファンクターにマップしました。

Fは、少なくともハッキングのパッケージでFree使用するタイプと同型です。free

また、次のように定義することで、フリーリストの上記のコードとより厳密に類似して構築することもできます。

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

Cofree Comonads

忘却関手が存在すると仮定して、その随伴関手を見ることで、似たようなものを構築することができます。余自由関手は忘却関手に単純に/右随伴/であり、対称的に、何かが余自由余代数であることを知ることは、から余自由余代数準同型を与えることw -> Cofree fはから自然変換を与えることと同じことを知ることと同じですw -> f

于 2012-11-12T22:25:07.490 に答える
84

Free Monad(データ構造)は、List(データ構造)からMonoid(クラス)のようにMonad(クラス)になります。これは簡単な実装であり、後でコンテンツをどのように組み合わせるかを決定できます。


あなたはおそらくモナドが何であるか、そして各モナドが++または+のいずれかの特定の(モナド法を順守する)実装を必要とすることを知ってfmapいます。joinreturnbindreturn

ファンクター(の実装fmap)があると仮定しますが、残りは実行時に行われた値と選択に依存します。つまり、モナドプロパティを使用できるようにしたいが、後でモナド関数を選択したいということです。

joinこれは、Free Monad(データ構造)を使用して実行できます。FreeMonad(データ構造)は、Functor(タイプ)を縮小ではなくスタックするようにラップします。

実際returnjoin使用したいものを、リダクション関数のパラメーターとして指定できるようになりましたfoldFree

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

タイプを説明するために、次のように置き換えることがFunctor fできます。Monad mb(m a)

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)
于 2012-11-22T14:34:42.600 に答える
67

Haskellの無料モナドはファンクターのリストです。比較:

data List a   = Nil    | Cons  a (List a  )

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

Pureに類似してNilおり、Freeに類似していConsます。無料のモナドは、値のリストではなくファンクターのリストを格納します。技術的には、別のデータ型を使用して無料のモナドを実装できますが、実装は上記のものと同型である必要があります。

抽象構文木が必要なときはいつでも、無料のモナドを使用します。フリーモナドの基本ファンクターは、構文木の各ステップの形状です。

誰かがすでにリンクしている私の投稿は、無料のモナドで抽象構文木を構築する方法のいくつかの例を示しています

于 2012-11-13T16:09:54.797 に答える
27

簡単な具体例が役立つと思います。ファンクターがあるとします

data F a = One a | Two a a | Two' a a | Three Int a a a

明らかなfmap。次にFree F a、葉がタイプaを持ち、ノードが、、、およびでタグ付けされOneているTwo木のタイプです。 -nodesには1つの子があり、-および-nodesには2つの子があり、-nodesには3つの子があり、。でタグ付けされています。Two'ThreeOneTwoTwo'ThreeInt

Free Fモナドです。 値を持つ単なる葉であるツリーにreturnマップします。 それぞれの葉を見て、それらを木に置き換えます。葉に値がある場合、その葉を木に置き換えます。xxt >>= fyf y

ダイアグラムはこれをより明確にしますが、私にはそれを簡単に描くための設備がありません!

于 2012-11-17T17:10:22.193 に答える
4

ここでの単純な答えと完全な答えの間に「架け橋」の答えを提供しようとしています。

つまり、「無料のモナド」は、任意の「ファンクター」から「モナド」を構築するので、これらを順番に見ていきましょう。

ファンクターの詳細

いくつかのものは型レベルの形容詞です。つまり、「整数」のような型名詞を取り、「整数のリスト」や「整数の文字列のペア」、さらには「から文字列を作成する関数」のような別の型名詞を返します。整数。」任意の形容詞を表すために、代用の単語「青」を使用します。

しかし、次に、これらの形容詞のいくつかが、それらが変更する名詞で入力っぽいまたは出力っぽいというパターンに気づきます。たとえば、「__から文字列を作成する関数」は入力っぽく、「文字列を__に変換する関数」は出力っぽいです。ここでのルールは、関数XYを持っていることを含みます。そのような関数を使用して、青いXを青いYに変換できる場合は、形容詞「青」が出力れます。「消防ホースがXsをスプレーする」と考えてから、このX→Y関数をねじ込むと消防ホースがYsをスプレーます。またはそれは入力的または反変です逆の場合は、掃除機がY sを吸い上げ、これをねじ込むと掃除機がXsを吸い上げます。いくつかのものは、出力的でも入力的でもありません。両方ともファントムであることがわかります。青いXを取り、青いYを作る関数「強制」を定義できるという意味で、それらが説明する名詞とはまったく関係ありませんが、*知らないうちにタイプXまたはYの詳細」、それらの間の関数さえ必要としません。

したがって、「lists of __」は出力されます。XYをXのリストにマップして、 Yのリストを取得できます。同様に、「文字列と__のペア」が出力されます。一方、「__からそれ自体への関数」はoutputtishでもinputtishでもありませんが、「文字列と正確にゼロの__sのリスト」はおそらく「ファントム」の場合です。

しかし、ええ、プログラミングのファンクターにはこれですべてです。それらはマッピング可能なものにすぎません。何かがファンクターである場合、それは一意のファンクターです。データ構造に関数を一般的にマップする方法は、せいぜい1つだけです。

モナド

モナドは、さらに両方であるファンクターです

  1. 普遍的に適用可能で、任意のXが与えられる、青いXを作成できます。
  2. 意味をあまり変えずに繰り返すことができます。したがって、-青のXは、ある意味で青のXと同じです。

つまり、これが意味するのは、任意の青-青__を青__だけに折りたたむ正規関数があるということ です。(もちろん、すべてを正気にするための法則を追加します。青のレイヤーの1つがユニバーサルアプリケーションからのものである場合は、そのユニバーサルアプリケーションを消去したいだけです。さらに、青-青-青のXを平らにして青X、最初の2つのを最初に折りたたむか、次の2つを最初に折りたたむかは違いはありません。)

最初の例は「null許容__」です。したがって、null許容のnull許容整数を提供する場合、ある意味では、null許容整数以上のものは提供していません。または、「intのリスト」の場合、ポイントが0個以上である場合、「intのリスト」は問題なく機能し、適切に折りたたむと、すべてのリストが1つのスーパーリストに連結されます。

ハスケルは、実際には何も起こらない数学的に純粋な世界に違反することなく、現実の世界で物事を行うためのアプローチを必要としていたため、モナドはハスケルで大きくなりました。解決策は、「__を生成するプログラム」の形容詞を導入するメタプログラミングの一種の骨抜き形式を追加することでした。では、現在の日付を取得するにはどうすればよいですか?ええと、Haskellはそれなしでは直接それを行うことはできませんunsafePerformIOが、それはあなたが現在の日付を生成するプログラムを記述して構成することを可能にします。このビジョンでは、「Main.main」と呼ばれるものを生成しないプログラムを記述し、コンパイラーがその記述を受け取り、このプログラムをいつでも実行できるバイナリ実行可能ファイルとして渡すことになっています。

とにかく、「intを生成するプログラム」は「intを生成するプログラム」よりも多くを購入することはないので、これはモナドであることがわかります。

無料のモナド

ファンクターとは異なり、モナドは一意のモナドではありません。特定のファンクターのモナドインスタンスは1つだけではありません。たとえば、「intと__のペア」の場合、そのintで何をしているのでしょうか。あなたはそれを加えることができます、あなたはそれを掛けることができます。これをnull許容整数にすると、最小の非null値または最大の非null値、あるいは左端の非null値または右端の非null値を保持できます。

特定のファンクターのフリーモナドは「退屈な」構造であり、「フリーブルーXは任意のn = 0、1、2、...のブルーnXです」です

blue⁰Xは単なるXであるため、これは普遍的です。そして、フリーブルーフリーブルーXはブルーmブルーn Xであり、これは単なるブルーm + nX です。「折りたたみ」を実装しているため、折りたたみをまったく実装しないことで、内部的にブルーが任意にネストされます。

これはまた、選択しているモナドを後日まで正確に延期できることを意味します。後で、青-青Xを青Xに縮小し、これらすべてを青0,1 X折りたたむ関数定義から、別の関数をXから青Xは、全体に青1Xを与えます。

于 2020-10-11T12:43:21.920 に答える