21

http://hackage.haskell.org/package/free inをControl.Monad.Free.Free使用すると、任意のの「無料モナド」にアクセスできますFunctor。ただし、MonadFixインスタンスはありません。これは、そのようなインスタンスを記述できないためですか、それとも単に省略されたためですか？

そのようなインスタンスを書き込めないのなら、どうしてですか？

4

3 に答える 3

14

何をするかの説明を検討してくださいmfix：

モナディック計算の不動点。mfix fアクションを1回だけ実行fし、最終的な出力を入力としてフィードバックします。

「実行する」という言葉は、の文脈ではFree、のレイヤーを作成することを意味しFunctorます。したがって、「1回だけ」とは、評価の結果、コンストラクターにmfix f保持される値Pureによって、作成されるファンクターのレイヤーの数を完全に決定する必要があることを意味します。

onceここで、常に単一のコンストラクターのみを作成することがわかっている特定の関数があるとします。ただし、リーフ値を保持するにFreeは多くのコンストラクターが必要です。Pureしたがって、「once」の出力は、タイプのFree f aある値と同型であるタイプの値のみになりますf a。この知識があればFree、の出力をonce安全に解除して、タイプの値を取得できますf a。

ここで、mfix「アクションを1回だけ実行する」必要がmfix onceあるため、適合インスタンスの結果にはonce、単一のアプリケーションで作成するよりも追加のモナディック構造が含まれていないことに注意してください。mfix onceしたがって、から取得した値もタイプの値と同型でなければならないと推測できますf a。

a -> f aいくつかの型を持つ関数が与えられた場合Functor f、結果を単一でラップして、上記の説明を満たすFree型の関数を取得できます。また、結果をアンラップして型の値を取得できることはすでに確立されています。a -> Free f aoncemfix oncef a

したがって、適合インスタンス(Functor f) => MonadFix (Free f)は、上記のラッピングとアンラッピングを介して、のffix :: (Functor f) => (a -> f a) -> f aすべてのインスタンスで機能する関数を記述できることを意味しますFunctor。

これは明らかに、そのようなインスタンスを作成できないことを証明するものではありません...しかし、可能であれば、直接MonadFix簡単に作成できるため、完全に不要になりますffix。（そしてmfix、Monad制約の場合と同じように、 liftM.Ughを使用して再実装すると思います。）

于 2013-02-01T05:09:38.583 に答える
5

MonadFixさて、のインスタンスに触発されてMaybe、私はこれを試しました（次の定義を使用してFree）：

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

instance (Functor f) => Monad (Free f) where
    return = Pure
    Pure x >>= f = f x
    Impure x >>= f = Impure (fmap (>>= f) x)

instance (Functor f) => MonadFix (Free f) where
    mfix f = let Pure x = f x in Pure x

法律は次のとおりです。

  • 純度：mfix (return . h) = return (fix h)
  • 左収縮：mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)
  • スライド：mfix (liftM h . f) = liftM h (mfix (f . h))、厳密にh
  • ネスト：mfix (\x -> mfix (f x)) = mfix (\x -> f x x)

純度は簡単に証明できますが、左に縮んでいることを証明しようとすると問題が発生しました。

mfix (\x -> a >>= \y -> f x y)
= let Pure x = (\x -> a >>= \y -> f x y) x in Pure x
= let Pure x = a >>= \y -> f x y in Pure x
-- case a = Pure z
  = let Pure x = Pure z >>= \y -> f x y in Pure x
  = let Pure x = f x z in Pure x
  = let Pure x = (\x -> f x z) x in Pure x
  = mfix (\x -> f x z)
  = Pure z >>= \y -> mfix (\x -> f x y)
-- case a = Impure t
  = let Pure x = Impure t >>= \y -> f x y in Pure x
  = let Pure x = Impure (fmap (>>= \y -> f x y) t) in Pure x
  = Pure _|_

しかし

  Impure t >>= \y -> mfix (\x -> f x y)
  = Impure (fmap (>>= \y -> mfix (\x -> f x y)) t)
  /= Pure _|_

したがって、少なくとも、PureとImpureコンストラクターが区別できる場合、私の実装はmfix法則を満たしていません。他の実装は考えられませんが、それが存在しないという意味ではありません。申し訳ありませんが、これ以上照らすことができませんでした。

于 2013-02-01T03:50:02.433 に答える
3

いいえ、すべてのモナドがMonadFixのインスタンスであるとは限らないため、一般的に記述することはできません。すべてのモナドは、下のFreeMonadを使用して実装できます。MonadFixを無料で実装できれば、任意のMonadからMonadFixを派生させることができますが、これは不可能です。ただし、もちろん、MonadFixクラスのFreeFixを定義することもできます。

どういうわけかこのように見えるかもしれませんが、これは3番目の推測です（まだテストされていません）：

data FreeFix m a = FreeFix { runFreeFix :: (forall r. (r -> m r) -> m r) -> m a }

instance (Monad m) => Monad (FreeFix m) where
    return a = FreeFix $ \_-> do
        return a
    f >>= g = FreeFix $ \mfx -> do
        x <- runFreeFix f mfx
        runFreeFix (g x) mfx

instance (Monad m) => MonadFix (FreeFix m) where
    mfix f = FreeFix $ \mfx -> do
        mfx (\r->runFreeFix (f r) mfx)

アイデアは、mがmfixの実装を欠いているモナドであるということです。したがって、FreeFixが削減される場合、mfixはパラメータである必要があります。

于 2013-02-07T11:29:30.383 に答える