Yazılı ifade ayrıştırıcısı

Question

Şimdiye kadar çok iyi çalışan Haskell'de bir yazılan ifade ayrıştırıcısı oluşturmaya çalışıyorum, ancak şu anda daha yüksek sipariş işlevlerini uygulamaya çalışıyorum. Ben basit bir örnek aşağı sorunu haşlanmış ettik:

{-# LANGUAGE TypeFamilies,GADTs,FlexibleContexts,RankNTypes #-} 

-- A function has an argument type and a result type 
class Fun f where 
    type FunArg f 
    type FunRes f 

-- Expressions are either constants of function applications 
data Expr a where 
    Const :: a -> Expr a 
    App :: Fun f => f -> FunArg f -> Expr (FunRes f) 

-- A very simple function 
data Plus = Plus 

-- Which takes two integer expressions and returns an integer expression 
instance Fun Plus where 
    type FunArg Plus = (Expr Int,Expr Int) 
    type FunRes Plus = Int 

-- A more complicated function which lifts a function to lists (like in haskell) 
data Map f r = Map f 

-- For this we need the concept of lifting function arguments: 
class Liftable a where 
    type LiftRes a 

-- A singleton argument is lifted by changing the expression type from a to [a] 
instance Liftable (Expr a) where 
    type LiftRes (Expr a) = Expr [a] 

-- Two function arguments are lifted by lifting each argument 
instance (Liftable a,Liftable b) => Liftable (a,b) where 
    type LiftRes (a,b) = (LiftRes a,LiftRes b) 

-- Now we can declare a function instance for Map 
instance (Fun f,Liftable (FunArg f),r ~ LiftRes (FunArg f)) => Fun (Map f r) where 
    type FunArg (Map f r) = r 
    type FunRes (Map f r) = [FunRes f] 

-- Now a parser for functions: 
parseFun :: [String] -> (forall f. Fun f => f -> a) -> a 
-- The parser for the plus function is easy: 
parseFun ["plus"] f = f Plus 
-- But the parser for map is not possible: 
parseFun ("map":sym) f 
    = parseFun sym (\fun -> f (Map fun)) 

sorun özyinelemeli sınıf bildirimleri girişi yasak olduğu için, her LiftRes kendisi kalkar her bir tip kontrolörü ikna yolu yoktur olduğunu gibi görünüyor.

Sorum şu: Bu işi nasıl yaparım? Ipuçlarını alabildiğim başka ifade parsers örnekleri var mı?

EDIT: Görünüşe göre this discussion about type family constraints çok ilgili görünmektedir. Ancak, çözümlerini benim durumumda çözemedim, belki birisi buna yardımcı olabilir?

Answer 1

Örnek çalışmanızı yapmanın en kolay yolu, örnek beyanındaki Liftable (FunArg f) kısıtlamasını kaldırmaktır. Ama sanırım senin örneğin o kadar yoğunlaşmış ki neden ona gerçekten ihtiyacın olduğunu göstermiyor.

Böylece sonraki en iyi şey Fun sınıfa bir Liftable (FunArg f) üst sınıf kısıtlamasını eklemektir: Bu mümkün değilse

class Liftable (FunArg f) => Fun f where 
    ... 

(değil tüm fonksiyonları kaldırılabilen argüman türleri varsa yani), sonra bunu yapamazsınız Verilen türden bir parseFun yazmayı bekliyoruz.

Daha genel bir açıklama: Burada yapmaya çalıştığınız şey çok garip ve belki de çok fazla. Yapılandırılmamış dizelerden bağlamsız veri türüne ayrıştırma zaten yeterince zor. Bunu neden yapmıyorsunuz ve "türlenmemiş", ancak dilinizin yapılandırılmış sunumunu yazılana dönüştüren ayrı bir işlev yazınız.

DÜZENLEME (gözden geçirilmiş yorumlarla tepki gibi): ayrıca söz konusu bağlantılı the discussion on type family constraints işaret ettiği gibi, sen ConstraintKinds kullanarak üst sınıf döngü kısıtlama atlayabilir. İşte azaltılmış örnek çalışmanızı yapmanın bir yolu. Belki bu tam çözüm için ölçeklenecek mi?

{-# LANGUAGE RankNTypes, ScopedTypeVariables, TypeFamilies, FlexibleContexts, GADTs #-} 

import Data.Constraint -- from the constraints package 
import Data.Proxy  -- from the tagged package 

-- A function has an argument type and a result type 
class Liftable (FunArg f) => Fun f where 
    type FunArg f 
    type FunRes f 

-- Expr, Plus, and instance Fun Plus as before 

class Liftable a where 
    type LiftRes a 
    get :: p a -> Dict (Liftable (LiftRes a)) 
    -- acquire "superclass" dictionary by calling this method and 
    -- then pattern matching on the result 

instance Liftable (Expr a) where 
    type LiftRes (Expr a) = Expr [a] 
    get _ = Dict 

instance (Liftable a, Liftable b) => Liftable (a, b) where 
    type LiftRes (a, b) = (LiftRes a, LiftRes b) 
    get (_ :: p (a, b)) = 
    case get (Proxy :: Proxy a) of -- extra code required 
     Dict -> case get (Proxy :: Proxy b) of -- extra code required 
     Dict -> Dict 

data Map f r = Map f 

instance (Fun f, Liftable r, r ~ LiftRes (FunArg f)) => Fun (Map f r) where 
    type FunArg (Map f r) = r 
    type FunRes (Map f r) = [FunRes f] 

parseFun :: forall a. [String] -> (forall f. Fun f => f -> a) -> a 
parseFun ["plus"]  f = f Plus 
parseFun ("map" : sym) f = parseFun sym 
    (\ (fun :: g) -> case get (Proxy :: Proxy (FunArg g)) of -- extra code required 
        Dict -> f (Map fun))