19

フリーモナドが何であるかについては大まかな考えがあると思いますが、それを視覚化するためのより良い方法が欲しいです。

自由なマグマが単なる二分木であることは理にかなっています。なぜなら、それは情報を失うことなく可能な限り「一般的」だからです。

同様に、操作の順序は重要ではないため、自由モノイドが単なるリストであることは理にかなっています。「二分木」には冗長性があるため、それが理にかなっている場合は、単純に平坦化できます。

同様の理由で、フリー グループがフラクタルのように見えることは理にかなっています: https://en.wikipedia.org/wiki/Cayley_graph#/media/File:Cayley_graph_of_F2.svg 他のグループを取得するには、さまざまな要素を識別するだけです。グループを「同じ」と見なし、他のグループを取得します。

フリーモナドをどのように視覚化すればよいですか? 現時点では、想像できる最も一般的な抽象構文ツリーと考えています。それは本質的にそれですか？それとも私はそれを単純化しすぎていますか？

また、同様に、自由なモナドからリストや他のモナドに移行する際に、何を失うのでしょうか? 私たちは何を「同じ」と認識していますか?

これに光を当てるすべてのコメントに感謝します。ありがとう！

4

2 に答える 2

15

今のところ、私は [自由なモナド] を想像できる最も一般的な抽象構文木と考えています。それは本質的にそれですか？それとも私はそれを単純化しすぎていますか？

あなたはそれを単純化しすぎています：

  1. 「フリー モナド」は「特定のファンクター上のフリー モナド」またはデータ型の略でFree f a、実際には の選択ごとに異なるフリー モナドですf。
  2. すべての自由モナドが持つ一般的な構造はありません。それらの構造は次のように分類されます。
    • Free自ら貢献するもの
    • さまざまな選択によってもたらされるものf

しかし、別のアプローチを取りましょう。フリーモナドについては、代わりに、より均一で視覚化しやすい構造を持つ、密接に関連するオペレーショナルモナドを最初に研究することで学びました。リンク自体からそれを学ぶことを強くお勧めします。

操作モナドを定義する最も簡単な方法は次のようになります。

{-# LANGUAGE GADTs #-}

data Program instr a where
  Return :: a -> Program instr a
  Bind :: instr x                  -- an "instruction" with result type `x`
       -> (x -> Program instr a)   -- function that computes rest of program
       -> Program instr a          -- a program with result type `a`

...ここで、instr型パラメーターはモナドの「命令」型を表し、通常は GADT です。例（リンクから取得）：

data StackInstruction a where
    Pop  :: StackInstruction Int
    Push :: Int -> StackInstruction ()

したがってProgram、オペレーショナルモナドでは、非公式に、命令の「動的リスト」として視覚化します。ここでは、命令の実行によって生成された結果が、「命令表」です。コンストラクターはBind、命令と「テール チューザー」関数を組み合わせます。

多くの自由モナドも同様の用語で視覚化できます。与えられた自由モナドに対して選択された関手は、その「命令セット」として機能すると言えます。しかし、自由なモナドでは、「命令」の「テール」または「子」はFunctorそれ自体によって管理されます。簡単な例 (トピックに関する Gabriel González の人気ブログ エントリから引用):

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

-- The `next` parameter represents the "tails" of the computation.
data Toy b next =
    Output b next
  | Bell next
  | Done

instance Functor (Toy b) where
  fmap f (Output b next) = Output b (f next)
  fmap f (Bell next) = Bell (f next)
  fmap _ Done = Done

操作モナドでは、「テール」を生成するために使用される関数はProgram(コンストラクター内の) 型に属しますがBind、フリー モナドでは、テールは「命令」/Functor型に属します。これにより、フリー モナドの「命令」(現在分解中のアナロジー) が単一の「テール」(OutputまたはのようなBell)、ゼロのテール ( のようなDone)、または選択した場合は複数のテールを持つことができます。または、別の一般的なパターンでは、nextパラメーターは埋め込み関数の結果の型にすることができます。

data Terminal a next = 
    PutStrLn String next
  | GetLine (String -> next)  -- can't access the next "instruction" unless
                              -- you supply a `String`.

instance Functor Terminal where
    fmap f (PutStrLn str next) = PutStrLn str (f next)
    fmap f (GetLine g) = GetLine (fmap f g)

ついでに言うと、自由モナドや操作モナドを「構文木」と呼んでいる人々に対して、私は長い間反論してきました。それらを実際に使用するには、ノードの「子」が関数内に不透明に隠されている必要があります。通常、この「ツリー」を完全に検査することはできません。

つまり、フリーモナドを視覚化する方法は、Functorそれをパラメータ化するために使用する の構造に完全に依存します。リストのように見えるものもあれば、ツリーのように見えるものもあれば、関数をノードとして持つ「不透明なツリー」のように見えるものもあります。(誰かが、上記の私の反論に対して、「関数は可能な引数と同じ数の子を持つツリー ノードです」のような行で答えたことがあります。)

于 2015-12-02T23:02:29.297 に答える
2

聞いたことがあるかもしれません

モナドは、エンドファンクターのカテゴリーのモノイドです

そして、モノイドは単なるリストであるとすでに述べました。それで、あなたはそこにいます。

それを少し拡張します：

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

通常の のリストでaはなく、 の中で末尾が折り返されたリストfです。複数のネストされたバインドの値の構造を記述すると、それが表示されます。

pure x >>= f >>= g >>= h :: Free m a

につながる可能性があります

Free $ m1 $ Free $ m2 $ Free $ m3 $ Pure x
  where m1, m2, m3 :: a -> m a -- Some underlying functor "constructors"

上記mの例で sum タイプの場合:

data Sum a = Inl a | Inr a
  deriving Functor

次に、各コンストラクターで左または右に分岐できるため、リストは実際にはツリーです。

聞いたことがあるかもしれません

Applicative は、エンドファンクタのカテゴリのモノイドです。

...カテゴリが違うだけです。Roman Cheplyaka のブログ投稿には、さまざまな無料のアプリカティブ エンコーディングの優れた視覚化があります。

だから無料Applicativeもリストです。f a私はそれを異種の値のリストと単一の関数として想像します:

 x :: FreeA f a
 x = FreeA g [ s, t, u, v]
    where g :: b -> c -> d -> e -> a
          s :: f b
          t :: f c
          u :: f d
          v :: f e

この場合、テール自体は でラップされませんfが、各要素は個別にラップされます。これは、 と の違いを理解するのに役立つ場合と、そうでない場合がApplicativeありMonadます。

上記のモナドに反して、makeでfある必要はないことに注意してください。FunctorApplicative (FreeA f a)Free

無料もありますFunctor

data Coyoneda f a = Coyoneda :: (b -> a) -> f b -> Coyoneda f a

これにより、任意の* -> *タイプが作成されますFunctor。上記のフリーと比較してくださいApplicative。適用可能なケースでは、値の長さnの異種リストf aと、それらを組み合わせた n 項関数がありました。コヨネダは上記の 1 項の特殊なケースです。

Coyonedaとを組み合わせて自由なモナドFreeを作ることができます。Operationalそして、他の回答が言及しているように、関係する機能があるため、それはツリーとして想像できるものではありません。OTOH、あなたはそれらの継続をあなたの写真の異なる魔法の矢として想像することができます:)

于 2015-12-03T00:23:35.170 に答える