2016-01-14 14 views
5

後、私は固定小数点を行った後、ファンクタのインスタンスを導出する方法がわからないです:bifunctor少なくとも固定タイプ

data FreeF f a next = PureF a | FreeF (f next) deriving (Functor) 

data Mu f = In { out :: f (Mu f) } 

newtype Free f a = Free( Mu (FreeF f a) ) 

instance Functor f => Functor (Free f) where 
    fmap h (Free (out -> PureF a)) = Free (In (PureF (h a))) 
    fmap h (Free (out -> FreeF fn)) = Free (In (fmap undefined undefined)) --stuck 

私は余分なタイプのパラメータを受け入れるようにムーを変更した場合は、私がするまで進行することができます。 ..:

ここ
data Mu f a = In { out :: f (Mu f a) } deriving (Functor) 

newtype Free f a = Free( Mu (FreeF f a) a) 

instance Functor f => Functor (Free f) where 
    fmap h (Free (out -> PureF a)) = Free . In . PureF $ h a 
    fmap h (Free (out -> FreeF fn)) = Free . In . FreeF $ fmap undefined fn 

私はundefined :: Mu (FreeF f a) a -> Mu (FreeF f b) bが、mu f同じfためのファンクタであり、ここで、それはタイプに変化を持っている必要があります。

これに取り組む正しい方法は何ですか?

答えて

4

mu f、適切なインスタンスを作成することができるはずは同じfためのファンクタであり、ここでそれは種類が変化します。

幸いにも我々はFunctor (Free f)を定義している、と私たちは実際にPureFコンストラクタでa年代の上にマッピングするために、このFunctorインスタンスを使用します。 Functor (Free f)は、すべての "内部"出現を抽象化してaです。我々はFreeF f a (Mu (FreeF f a)) -> FreeF f b (Mu (FreeF f b))を実装したい場合、たとえば、aの両方の出現を超えるマップするたび

だから、我々はFreeに戻ってすべての方法をすべてをラップすることにより、マッピング、再度アンラップことを行うことができます。元のデータ定義と

以下のチェックアウト:

newtype Free f a = Free {unFree :: Mu (FreeF f a)} -- add "unFree" 

instance Functor f => Functor (Free f) where 
    fmap h (Free (In (PureF a))) = Free (In (PureF (h a))) 
    fmap h (Free (In (FreeF fn))) = 
     Free (In (FreeF (fmap (unFree . fmap h . Free) fn))) 

いくつかのテスト:

{-# LANGUAGE UndecidableInstances, StandaloneDeriving #-} 

deriving instance Show (f (Mu f)) => Show (Mu f) 
deriving instance Show (Mu (FreeF f a)) => Show (Free f a)  

foo :: Free [] Int 
foo = Free $ In $ FreeF [ In $ PureF 100, In $ PureF 200 ] 

> fmap (+100) foo 
Free {unFree = In {out = FreeF [In {out = PureF 200},In {out = PureF 300}]}} 
+0

ではありません。冗長?(両方の出現) – chi

+0

です。私はタイプホールをちょっとやっかいに追ってきたと思う。編集されました。 –

3

私はこれまでにこの構成を行っていませんが、私は何かを見ていると思います。 Muに引数を追加することについてのあなたの直感は良いですが、あなたはFree f収まるように沿って、それを渡す必要があり、fは1つではなく、2つの引数を取りすなわちように:

newtype Mu f a = In { out :: f (Mu f a) a } 

Mu fを適切な条件下でFunctorあるべきこれはあなたが探しているインスタンスを提供します。その条件は何ですか?私たちは、必要があります。

fmap' :: (a -> b) -> f (Mu f a) a -> f (Mu f b) b 

は、我々はfが第2引数でfunctorialあることを期待し、そのためには問題ありません。だから私たちは本当に

f (Mu f a) b -> f (Mu f b) b 
     ^   ^
      +--not varying--+ 

を取得する方法を必要とするものを私たちはMu f a -> Mu f bを取得するために再帰的にインスタンスを使用することができますので、我々はあまりにもその最初の引数でファンクタするfを必要とするように見えます。したがって:

class Bifunctor f where 
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d 

次にあなたが

instance (Functor f) => Bifunctor (FreeF f) ... 
instance (Bifunctor f) => Functor (Mu f) ... 
+0

確かにそれは私がやって考えていたものです。面白い ! – nicolas

+0

私はこれが「バイフルーツスーツ」で行われた方法だと思います。 – dfeuer

関連する問題