I parametri lambda sono parametrizzati come Monade?

Question

Ho questa rappresentazione termini del lambda calcolo parametrizzato sul tipo di nome:

{-# LANGUAGE DeriveFunctor #-} 

data Lambda a = Var a | App (Lambda a) (Lambda a) | Lam a (Lambda a) 
    deriving Functor 

Mi chiedevo se Lambda può essere fatto un'istanza di monade? Ho pensato che qualcosa di simile al seguente potrebbe funzionare per l'attuazione del join:

joinT :: Lambda (Lambda a) -> Lambda a 
joinT (Var a) = a 
joinT (fun `App` arg) = joinT fun `App` joinT arg 
joinT (Lam n body) = ? 

Per il terzo caso non ho assolutamente idea ... ma dovrebbe essere possibile - questa rappresentazione senza nome di lambda-termini, preso da De Bruijn Notation as a Nested Datatype, è un esempio di Monade (Maybe viene utilizzata per discriminare tra variabili libera e legata in questa rappresentazione):

{-# LANGUAGE RankNTypes #-} 
{-# LANGUAGE DeriveFunctor #-} 

data Expr a 
    = V a 
    | A (Expr a) (Expr a) 
    | L (Expr (Maybe a)) 
    deriving (Show, Eq, Functor) 

gfoldT :: forall m n b. 
    (forall a. m a -> n a) -> 
    (forall a. n a -> n a -> n a) -> 
    (forall a. n (Maybe a) -> n a) -> 
    (forall a. (Maybe (m a)) -> m (Maybe a)) -> 
    Expr (m b) -> n b 
gfoldT v _ _ _ (V x) = v x 
gfoldT v a l t (fun `A` arg) = a (gfoldT v a l t fun) (gfoldT v a l t arg) 
gfoldT v a l t (L body) = l (gfoldT v a l t (fmap t body)) 

joinT :: Expr (Expr a) -> Expr a 
joinT = gfoldT id (:@) Lam distT 

distT :: Maybe (Expr a) -> Expr (Maybe a) 
distT Nothing = Var Nothing 
distT (Just x) = fmap Just x 

joinT è sufficiente per instance Monad Expr:

instance Applicative Expr where 
    pure = Var 
    ef <*> ea = do 
     f <- ef 
     a <- ea 
     return $ f a 

instance Monad Expr where 
    return = Var 
    t >>= f = (joinT . fmap f) t 

supponga inoltre le seguenti due funzioni di trasformazione tra le rappresentazioni:
unname :: Lamba a -> Expr a e name :: Expr a -> Lambda a. Con quelli che possiamo implementare join per Lambda sfruttando l'isomorfismo tra i due costruttori di tipo:

joinL :: Lambda (Lambda a) -> Lambda a 
joinL = name . joinT . uname . fmap uname 

ma questo sembra molto complicato. C'è un modo più diretto, o mi manca qualcosa di importante?

---

Edit: Qui ci sono le funzioni name e uname che ho pensato che avrebbe fatto il lavoro. Come è stato sottolineato nei commenti e nella risposta, a ha davvero bisogno di un vincolo Eq che interrompa l'isomorfismo.

foldT :: forall n b. 
    (forall a. a -> n a) -> 
    (forall a. n a -> n a -> n a) -> 
    (forall a. n (Maybe a) -> n a) -> 
    Expr b -> n b 
foldT v _ _ (V x) = v x 
foldT v a l (A fun arg) = a (foldT v a l fun) (foldT v a l arg) 
foldT v a l (L body) = l (foldT v a l body) 

abstract :: Eq a => a -> Expr a -> Expr a 
abstract x = L . fmap (match x) 

match :: Eq a => a -> a -> Maybe a 
match x y = if x == y then Nothing else Just y 

apply :: Expr a -> Expr (Maybe a) -> Expr a 
apply t = joinT . fmap (subst t . fmap V) 

uname :: Eq a => Lambda a -> Expr a 
uname = foldL V A abstract 

name :: Eq a => Expr a -> Lambda a 
name e = nm [] e where 
    nm vars (V n) = Var n 
    nm vars (A fun arg) = nm vars fun `App` nm vars arg 
    nm vars (L body) = 
     Lam fresh $ nm (fresh:vars) (apply (V fresh) body) where 
     fresh = head (names \\ vars) 

names :: [String] 
names = [ [i] | i <- ['a'..'z']] ++ [i : show j | j <- [1..], i <- ['a'..'z'] ] 

Answer 1

Il tuo istinto aveva ragione: i termini che presentano nomi espliciti nei siti vincolanti non formano una monade.

La firma del >>= offre alcuni spunti di riflessione:

(>>=) :: Lambda a -> (a -> Lambda b) -> Lambda b 

Associazione di un termine lambda esegue sostituzione. La funzione che si associa è i nomi di mapping di ambiente a ai termini Lambda b; >>= trova tutte le occorrenze dei nomi a e scambia ciascuno per il valore dall'ambiente a cui fa riferimento. (Confronta a -> Lambda b con un tipo di ambiente più tradizionale, [(a, Lambda b)]).

Ma non ha senso sostituire in un sito di rilegatura. L'argomento di un termine lambda non può sintatticamente essere un lambda. (\(\x -> y) -> y non è sintatticamente valido). L'inserimento di nel proprio strumento di costruzione non può essere una monade.

La legge particolare che ti sentiresti di violazione è identità destra, in cui si afferma x >>= return = x per tutti x. (Per vedere la violazione, prova a impostare x in un termine Lam.)

---

Per vedere in un altro modo, riflettere su come si sarebbe implementare la sostituzione di cattura-evitando che >>= fornisce in carta Paterson e Bird. La sostituzione evitante alla cattura è complicata quando non si utilizzano gli indici di de Bruijn: è necessaria una fonte di nuovi nomi e la capacità di identificare i nomi coincidenti (per determinare quando è necessario utilizzarne uno nuovo). Il tipo di tale funzione sarebbe simile:

subst :: (MonadFresh a m, Eq a) => Lambda a -> (a -> Lambda a) -> m (Lambda a) 

I vincoli di classe e il contesto monadica fare questa firma molto diverso da quello di >>=! Se hai effettivamente provato a implementare name e unname vedresti che i tipi che hai ipotizzato erano errati e che joinL richiederebbe queste classi.

La rappresentazione di lambda di Bird e Paterson è una monade perché è localmente senza nome. Non c'è a nel loro costruttore L; invece, si trova il sito di rilegatura di una variabile ingrandendolo fino a quando il valore della variabile è lungo. Come spiega il documento, questo è un modo di rappresentare gli indici de Bruijn (confrontare Just (Just Nothing) con il numero naturale S (S Z)).

Per ulteriori informazioni, vedere il numero detailed article di Kmett che descrive il progetto della sua libreria bound, che utilizza l'approccio di Bird e Paterson come fonte di ispirazione.