エドKmettの<code>recursion-scheme</code>パッケージにはエドKmettの再帰スキームパッケージ

Question

で修正、ムーとニューの違いは何ですか、3つの宣言があります。

newtype Fix f = Fix (f (Fix f)) 

newtype Mu f = Mu (forall a. (f a -> a) -> a) 

data Nu f where 
    Nu :: (a -> f a) -> a -> Nu f 

は、これらの3つのデータ・タイプの違いは何ですか？

Answer 1

Muは、折り返しとして再帰型を表し、Nuは展開されたものとして表します。ハスケルでは、これらは同形であり、同じ型を表す異なる方法です。 Haskellに任意の再帰がないと思われる場合、これらの型の区別はより面白くなります。Mu fは、最小（初期）の固定小数点がfであり、Nu fが最大固定小数点です。

はfの固定点、すなわち逆関数in :: f T -> T、out :: T -> f T一対の種類TTとf Tの間に同型です。タイプFixは、Haskellの組込み型再帰を使用して、同形を直接宣言します。しかし、MuとNuの両方でイン/アウトを実装できます。

具体的な例として、再帰的な値を書くことができないようなふりをする。 Mu Maybeの住民、すなわち値:: forall r. (Maybe r -> r) -> rは、自然人、{0,1,2、...}である。 Nu Maybeの住人、すなわち値:: exists x. (x, x -> Maybe x)は、共生体{0,1,2、...、∞}である。これらのタイプの可能な値を考えて、なぜNu Maybeに余分な住人がいるのかを確認してください。

あなたはこれらのタイプのいくつかの直感を取得したい場合は、（大体難易度の増加順に）再帰せずに次のことを実現するための楽しいエクササイズになります

• zeroMu :: Mu Maybe、succMu :: Mu Maybe -> Mu Maybe
• zeroNu :: Nu Maybe、 succNu :: Nu Maybe -> Nu Maybe、inftyNu :: Nu Maybe
• muTofix :: Mu f -> Fix f、fixToNu :: Fix f -> Nu f
• inMu :: f (Mu f) -> Mu f、outMu :: Mu f -> f (Mu f)
• inNu :: f (Nu f) -> Nu f、outNu :: Nu f -> f (Nu f)

またこれらを実装しようとすることができますが、彼らは再帰が必要です。

• nuToFix :: Nu f -> Fix f、fixToMu :: Fix f -> Mu f

Mu fは最小不動点である、とNu fです最大のので、関数を書くこと:: Mu f -> Nu fは非常に簡単ですが、関数を書くこと:: Nu f -> Mu fは難しいです。それは現在と泳ぐようなものです。 （私はこれらのタイプのより詳細な説明を記述することを意味した1点で、それは、この形式のために少し長すぎるかもしれません。）