Karşılıklı yinelemeli sözdizimi Bound ile

Question

Bağımlı olarak yazılan bir lambda hesabı için bir sözdizimi.

data TermI a = Var a 
      | App (TermI a) (TermC a) -- when type-checking an application, infer the type of the function and then check that its argument matches the domain 
      | Star -- the type of types 
      | Pi (Type a) (Scope() Type a) -- The range of a pi-type is allowed to refer to the argument's value 
      | Ann (TermC a) (Type a) -- embed a checkable term by declaring its type 
      deriving (Functor, Foldable, Traversable) 

data TermC a = Inf (TermI a) -- embed an inferrable term 
      | Lam (Scope() TermC a) 
      deriving (Functor, Foldable, Traversable) 

type Type = TermC -- types are values in a dependent type system 

(daha çok veya daha az Simply Easy bu kaldırdı.) Tipi sistem bidirectional, türü yazarak bağlamında anlaşılabilir, bu içine bölme koşulları ve sadece bir hedef karşı kontrol edilebilir olanlar olduğu yazın. Bu, bağımlı tip sistemlerde kullanışlıdır, çünkü genel olarak lambda terimlerinde asal tip yoktur.

Neyse, bu sözdizimi için bir Monad örneğini tanımlamak için çalışırken takılıp var ettik:

instance Monad TermI where 
    return = Var 
    Var x >>= f = f x 
    App fun arg >>= f = App (fun >>= f) (arg >>= Inf . f) -- embed the substituted TermI into TermC using Inf 
    Star >>= _ = Star 
    Pi domain range >>= f = Pi (domain >>= Inf . f) (range >>>= Inf . f) 
    Ann term ty >>= f = Ann (term >>= Inf . f) (ty >>= Inf . f) 

instance Monad TermC where 
    return = Inf . return 
    Lam body >>= f = Lam (body >>>= f) 
    Inf term >>= f = Inf (term >>= _) 

TermC 'ın örneğinin son satırında boşluğu doldurmak için, ben tip a -> TermI b ama f bir şeye ihtiyacım var a -> TermC b bir türü vardır. Ann yapıcısını kullanarak TermC sonucunu TermI içine gömemiyorum çünkü TermC türünü bilmiyorum.

Bu veri türü bound modeliyle uyumlu değil mı? Yoksa Monad örneğini kullanabilmek için kullanabileceğim bir numara var mı?

Answer 1

Bunu yapmak oldukça kolay imkansız: TermC bir monad değil. İkame, terimleri değişkenlerin yerine koyar. Bunun anlaşılması için, terimlerin, sonuçta ortaya çıkan terimin hala iyi özelliklere sahip olması için yeterince benzer olması gerekmektedir. Burada, türünün, bulunamaz olması gerektiği anlamına gelir. TermC bunu yapmaz. Eğer [\ x -> x] `(var 0 (var 1)) (notasyonu kötüye) çalıştırırsanız

substI :: TermI a -> (a -> TermI b) -> TermI b 
substC :: TermC a -> (a -> TermI b) -> TermC b 

ve

instance Monad TermI where 
    return = Var 
    bind = substI