Istanza di Functor per ADT polimorfici generici in Haskell?

Question

Quando si tratta di applicare la teoria delle categorie per la programmazione generica, Haskell fa un ottimo lavoro, ad esempio con librerie come recursion-schemes. Tuttavia una cosa di cui non sono sicuro è come creare un'istanza di functor generica per tipi polimorfici.

Se si dispone di un tipo polimorfico, come un elenco o un albero, è possibile creare un functor da (Hask × Hask) a Hask che li rappresenta. Per esempio:

data ListF a b = NilF | ConsF a b -- L(A,B) = 1+A×B 
data TreeF a b = EmptyF | NodeF a b b -- T(A,B) = 1+A×B×B 

Questi tipi sono polimorfici in A, ma vengono fissati i punti per quanto riguarda B, qualcosa di simile:

newtype Fix f = Fix { unFix :: f (Fix f) } 
type List a = Fix (ListF a) 
type Tree a = Fix (TreeF a) 

Ma, come molti sanno, gli elenchi e gli alberi sono anche funtori nel senso comune del termine, dove rappresentano un "contenitore" di a, che è possibile mappare una funzione f :: a -> b per ottenere un contenitore di b.

Sto cercando di capire se c'è un modo per rendere questi tipi (i punti fissi) un'istanza di Functor in un modo generico, ma non sono sicuro di come. Ho incontrato i seguenti 2 problemi finora:

---

1) In primo luogo, ci deve essere un modo per definire una generica gmap su qualsiasi punto fisso polimorfico. Sapendo che tipi come ListF e TreeF sono Bifunctors, finora ho ottenuto questo:

{-# LANGUAGE ScopedTypeVariables #-} 
import Data.Bifunctor 

newtype Fix f = Fix { unFix :: f (Fix f) } 

cata :: Functor f => (f a -> a) -> Fix f -> a 
cata f = f . fmap (cata f) . unFix 

-- To explicitly use inF as the initial algebra 
inF :: f (Fix f) -> Fix f 
inF = Fix 

gmap :: forall a b f. Bifunctor f => (a -> b) -> Fix (f a) -> Fix (f b) 
gmap f = cata alg 
    where 
     alg :: f a (Fix (f b)) -> Fix (f b) 
     alg = inF . bimap f id 

In Haskell questo mi dà il seguente errore: Could not deduce (Functor (f a)) arising from a use of cata from the context (Bifunctor f).

Sto utilizzando il pacchetto bifunctors, che ha un tipo WrappedBifunctor che definisce in modo specifico la seguente istanza che potrebbe risolvere il problema precedente: Bifunctor p => Functor (WrappedBifunctor p a). Tuttavia, non sono sicuro di come "sollevare" questo tipo all'interno Fix per essere in grado di usarlo

2) Anche se il generico gmap sopra può essere definita, non so se è possibile creare un'istanza generica di Functor che dispone di fmap = gmap e può funzionare immediatamente sia per i tipi List e Tree lassù (così come qualsiasi altro tipo definito in modo simile). È possibile?

Se sì, sarebbe possibile renderlo compatibile anche con recursion-schemes?

Answer 1

TBH io non sono sicuro di come utile questa soluzione è quella di voi perché richiede ancora un extra newtype involucro per queste a punto fisso funtori, ma qui andiamo:

È possibile continuare a utilizzare il vostro generico cata se fate qualche avvolgimento/scartare

Date le seguenti due funzioni di supporto:

unwrapFixBifunctor :: (Bifunctor f) => Fix (WrappedBifunctor f a) -> Fix (f a) 
unwrapFixBifunctor = Fix . unwrapBifunctor . fmap unwrapFixBifunctor . unFix 

wrapFixBifunctor :: (Bifunctor f) => Fix (f a) -> Fix (WrappedBifunctor f a) 
wrapFixBifunctor = Fix . fmap wrapFixBifunctor . WrapBifunctor . unFix 

è possibile definire gmap senza alcun vincolo aggiuntivo sul f:

gmap :: (Bifunctor f) => (a -> b) -> Fix (f a) -> Fix (f b) 
gmap f = unwrapFixBifunctor . cata alg . wrapFixBifunctor 
    where 
    alg = inF . bimap f id 

Si può fare Fix . f in un Functor tramite un newtype

Siamo in grado di implementare un esempio Functor per \a -> Fix (f a) mediante l'attuazione di questo "tipo- livello lambda "come newtype:

newtype FixF f a = FixF{ unFixF :: Fix (f a) } 

instance (Bifunctor f) => Functor (FixF f) where 
    fmap f = FixF . gmap f . unFixF 

Answer 2

Se siete disposti ad accettare per il momento hai a che fare con bifunctors, si può dire

cata :: Bifunctor f => (f a r -> r) -> Fix (f a) -> r 
cata f = f . bimap id (cata f) . unFix 

e poi

gmap :: forall a b f. Bifunctor f => (a -> b) -> Fix (f a) -> Fix (f b) 
gmap f = cata alg 
    where 
     alg :: f a (Fix (f b)) -> Fix (f b) 
     alg = inF . bimap f id 

(In gmap, ho appena riordinato la tua il vincolo di classe per far funzionare le variabili di tipo scoped.)

È inoltre possibile lavorare con la versione originale di cata, ma poi è necessario sia il Functor e il Bifunctor vincolo sulla gmap:

gmap :: forall a b f. (Bifunctor f, Functor (f a)) => (a -> b) -> Fix (f a) -> Fix (f b) 
gmap f = cata alg 
    where 
     alg :: f a (Fix (f b)) -> Fix (f b) 
     alg = inF . bimap f id 

Non si può fare il vostro gmap un'istanza della normale Functor di classe , perché dovrebbe essere qualcosa di simile a

instance ... => Functor (\ x -> Fix (f x)) 

e non abbiamo lambda di tipo livello. È possibile possibile eseguire questa operazione se si invertono i due argomenti di f, ma si perde l'istanza "altro" Functor e occorre definire nuovamente cata per Bifunctor.

[Potreste anche essere interessati a leggere http://www.andres-loeh.de/IndexedFunctors/ per un approccio più generale.]

Answer 3

Il pacchetto bifunctors offre anche una versione di Fix che è particolarmente appropriata:

newtype Fix p a = In {out :: p (Fix p a) a} 

Ciò è reso un'istanza Functor piuttosto facilmente:

instance Bifunctor p => Functor (Fix p) where 
    fmap f = In . bimap (fmap f) f . out