11

Control.Monad.Freeフリーモナドを次のように実装します。

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

instance Functor f => Functor (Free f) where
  fmap f = go where
    go (Pure a)  = Pure (f a)
    go (Free fa) = Free (go <$> fa)

特にフリーモナドとは何かgoの説明の文脈では、2行目を理解するのに非常に苦労しています。これがどのように機能し、なぜそれがフリーモナドを作るのかを誰か説明してもらえますか?Free f a

4

3 に答える 3

14

この時点でFreeは、モナドではなくファンクターを作成しているだけです。もちろん、モナドであるためには、ファンクターでもある必要があります!

Free混乱を避けるためにコンストラクターの名前を変更すると、少し考えやすくなると思います。

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

では、構築するものの構造を見てみましょう。このPure場合、 type の値しかありませんa。このWrap場合、ファンクタにラップされた別の値があります。 Free f af

コンストラクタを少し無視しましょう。つまり、Wrap (f (Pure a))と考えてみましょうf a。これは、私たちが構築している構造が単なるfファンクタであり、何度か繰り返し適用されることを意味します。このタイプの値は次のようになりますf (f (f (f (f a))))。より具体的にするために、 get:にしましょfう。コンストラクターを繰り返し使用することで、必要な数のレベルを持つことができます。を使用するとすべてが終了します。[][[[[[a]]]]]WrapPure

コンストラクターを元に戻すと、次の[[a]]ようになりますWrap [Wrap [Pure a]]。

つまり、Pure値を取得してファンクターを繰り返し適用するだけです。

繰り返し適用されるファンクターのこの構造を考えると、どのように関数をその上にマッピングしますか? ラップする前のPure場合、fこれは非常に簡単です: 関数を適用するだけです。しかし、値fを少なくとも 1 回ラップしたことがある場合は、外側のレベルをマップしてから、すべての内側のレイヤーを再帰的にマップする必要があります。別の言い方をすればFree、 functor 上の monad 上のmapping をマッピングする必要がありfます。

これはまさに の 2 番目のケースgoが行っていることです。go本体はあくまでfmap為Free f aです。<$>です。fmap_ fこれにより、全体が再帰的になりますfmap go。f

このマッピング関数は再帰的であるため、任意の数のレベルを処理できます。したがって、関数を[[a]]or[[[[a]]]]または何でもマップできます。これがfmap go、 go がfmapそれ自体である場合に必要な理由です。重要な違いは、最初のfmapものが単一のレイヤーに対して機能fし、構造全体goに対して再帰的に機能することです。 Free f a

これで問題が少し解決したことを願っています。

于 2013-04-13T17:36:44.770 に答える
7

実を言うと、私は通常、これらの単純な関数のコードを読むのではなく、型を読んで関数を自分で書く方が簡単だと思っています。パズルだと思ってください。あなたはこれを構築しようとしています:

mapFree :: Functor f => (a -> b) -> Free f a -> Free f b

では、どうすればよいのでしょうか。Pureさて、最初にコンストラクターを取りましょう：

mapFree f (Pure a) = ...
-- I like to write comments like these while using Haskell, then usually delete 
-- them by the end:
--
-- f :: a -> b
-- a :: a

そこに 2 つの型のコメントがあり、 の型がわかれPureば、すぐに解決策がわかるはずです。

mapFree f (Pure a) = Pure (f a)

2番目のケース：

mapFree f (Free fa) = ...
-- f  :: a -> b
-- fa :: Functor f => f (Free f a)

fは であるため、Functor実際に を使用して の内部コンポーネントにmapFree適用できます。したがって、次のようになります。mapFree ff (Free f a)

mapFree f (Free fa) = Free (fmap (mapFree f) fa)

この定義をFunctor f => Functor (Free f)インスタンスとして使用すると、次のようになります。

instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Free fa) = Free (fmap (fmap f) fa)

ちょっとした作業で、ここでたどり着いた定義が、あなたが困惑しているものと同じものであることを確認できます。(他の人が述べたように、(<$>)(defined in Control.Applicative) は の同義語にすぎfmapません。) まだ理解していないかもしれませんが、なんとか記述できました。これは、これらのような抽象的な型の場合、非常に多くの場合十分です。

しかし、それを理解するのに役立つのは、次のことです。モナドを、 asとasFreeを使用した一種のリストのような構造と考えてください。型の定義から、これがわかるはずです:は基本ケースであり、再帰ケースです。インスタンスが行っているのは、マップされた関数をこの構造の一番下、つまり が存在する場所に「プッシュ」することです。 Pure[]Free(:)PureFreefmapPure

于 2013-04-13T21:45:54.290 に答える
1

私は自分自身が混乱しているので、質問に答えます...これは正しい置換でしょうか(Tikhon's Wrapの説明に依存しています)? 

...
fmap g = go where
  go (Pure a)  = Pure (g a)
  go (Wrap fa) = Wrap (go <$> fa)

Substituting "fmap g" for "go", and "fmap" for "<$>" (since "<$>" is infix, 
 we flip "go" and "<$>"):

fmap g (Pure a)  = Pure (g a)
fmap g (Wrap fa) = Wrap (fmap (fmap g) fa)

Substituting "f (Free f a)" for "fa" in the last line (from the first data 
 declaration):

fmap g (Wrap fa) = Wrap ( fmap (fmap g) (f (Free f a)) )

                 = Wrap ( f ( fmap g (Free f a) ) )

                 = wrap ( f (Pure (g a) ) ) --if Free f a is Pure
                 or
                 = Wrap ( f ( fmap g (Wrap fa') ) ) --if Free f a is Wrap

The last line includes the recursion "fmap g (Wrap fa')", which would continue 
 unless Pure is encountered.
于 2013-04-13T19:56:52.430 に答える