bifunctor in Haskell, dopo il tipo meno fisso

Question

Non sono sicuro come derivare l'istanza functor dopo aver fatto un punto fisso:

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 

Se modifico Mu di accettare un parametro di tipo in più, posso progredire fino. ..:

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 

qui ho bisogno di avere undefined :: Mu (FreeF f a) a -> Mu (FreeF f b) b ma mu f è un funtore per lo stesso f e qui varia in tipo.

Qual è il modo corretto per affrontare questo?

Answer 1

mu f è un funtore per lo stesso f e qui varia tipologia.

Fortunatamente stiamo definendo Functor (Free f), e abbiamo effettivamente utilizzare questa Functor esempio per mappare nel corso degli 's a nelle PureF costruttori. Functor (Free f) abstracts su tutte le occorrenze "interne" di a.

Così, ogni volta che vogliamo mappare su entrambe le occorrenze di a, ad esempio quando vogliamo implementare FreeF f a (Mu (FreeF f a)) -> FreeF f b (Mu (FreeF f b)), possiamo farlo avvolgendo tutto in su tutto il viaggio di ritorno a Free, mappatura, quindi scartare nuovo.

i seguenti controlli fuori con le definizioni dei dati originali:

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

alcuni test:

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

Non ho mai fatto questa costruzione, ma penso di vedere qualcosa. La tua intuizione di aggiungere un argomento di Mu è buono, ma è necessario passarlo insieme in modo che Free f adatta, cioè in modo che f prende due argomenti invece di uno:

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

Mu f dovrebbe essere un Functor in condizioni adeguate , che ti darebbe l'istanza che stai cercando. Quali sono queste condizioni? Abbiamo bisogno:

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

Ci aspettiamo di essere f funtoriale nel suo secondo argomento, in modo che non è un problema. Così che cosa abbiamo davvero bisogno di un modo per ottenere

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

possiamo usare l'istanza in modo ricorsivo per ottenere Mu f a -> Mu f b, così sembra che abbiamo solo bisogno di essere f un funtore nel suo primo argomento troppo. Quindi:

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

allora si dovrebbe essere in grado di scrivere i casi adatti

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