bifunctor az sabit tip

Question

sonra sabit bir noktaya yaptıktan sonra funktoru örneğini elde etmek değil nasıl eminim: Fazladan tipi parametresini kabul etmek Mu değiştirirseniz

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 

, ben gelene kadar ilerleyebilir. ..:

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 

İşte undefined :: Mu (FreeF f a) a -> Mu (FreeF f b) b ama mu f aynı f için funktoru ve burada tip değişir olması gerekir.

Bunu düzeltmenin doğru yolu nedir?

Answer 1

mu f yazmak gerekir aynı f için funktoru ve burada tip değişir.

Neyse ki Functor (Free f) tanımlarken, ve biz aslında PureF kurucularınızdaki a 's üzerinde eşleştirmek için bu Functor örneğini kullanın. Functor (Free f), a'un tüm "dahili" oluşumları üzerinde özetlemektedir. biz FreeF f a (Mu (FreeF f a)) -> FreeF f b (Mu (FreeF f b)) uygulamak istediğinizde örneğin a her iki oluşumlarını üzerinde harita istediğinizde

yani, biz Free tüm yolu geri herşeyi sararak, haritalama, sonra tekrar unwrapping yapabilir. Orijinal veri tanımları ile

aşağıdaki kontroller:

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))) 

Bazı testler:

{-# 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}]}} 

Answer 2

Bu inşaatı daha önce yapmadım, ama sanırım bir şey görüyorum. Mu bir argüman ekleme hakkında Sezginiz iyidir, ama f iki argüman bir yerine sürdüğünü Free f uyan, yani böylece böylece zevk verir gerekir:

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

Mu f gerektiğini uygun koşullar altında bir Functor olmak , size aradığınız örneği verir. Bu koşullar nedir? Biz gerekir:

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

Biz f ikinci argüman Funktor olmasını bekliyoruz, böylece sorun değil. Yani gerçekten yol gerekenler

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

Biz Mu f a -> Mu f b almak için yinelemeli örneğini kullanabilirsiniz olsun, bu yüzden sadece çok ilk argüman bir funktor olmak f ihtiyaç gibi görünüyor için. Dolayısıyla:

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

Sonra uygun örneklerini

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