Jak powinienem reprezentować AST opatrzony dodatkowymi informacjami?

Question

Powiedzmy mam prosty typ danych reprezentujący AST w jakimś języku: (. W rzeczywistości byłoby oczywiście mieć więcej konstruktorów niż to)

data Term = Var String 
      | Num Integer 
      | Expr [Term] 

mogę to wykorzystać, aby napisać prostą ocenę funkcja pasująca do struktury AST:

eval :: Term -> Result 
eval (Var name) = lookup name 
eval (Num n)  = return n 
eval (Expr exprs) = ... 

Czy mogę opatrzyć przypisami AST informacje takie jak numery linii bez zmiany sposobu dopasowywania wzorców?

(Jeśli nie przeszkadza zmianę wzorców, mogę używać rekordowe składniowe lub zobacz wzory, oczywiście.)

Answer 1

Dlaczego nie reprezentują AST polimorficznie

data Term term = Var String 
     | Num Integer 
     | Expr [term] 

wówczas typ orignal Term jest

newtype SimplTerm = SimplTerm (Term (SimplTerm)) 

i można łatwo zrobić, co chcesz z widokiem wzorców

data AtLine = AtLine (Term AtLine) Integer 

view :: AtLine -> Term AtLine 
view (AtLine x _) = x 

eval (view -> Var name) = lookup name 
eval (view -> Num n) = numResult n 
eval (view -> Expr expr) = listResult (map eval expr) 

lub dokonywania widok polimorficzny

class AST t where 
    term :: t -> Term t 
instance AST SimplTemr where 
    term (SimplTemr x) = x 
instance AST AtLine where 
    term (AtLine x _) = x 

eval :: AST t => t -> Result 
eval (view -> Var name) = lookup name 
eval (view -> Num n) = numResult n 
eval (view -> Expr expr) = listResult (map eval expr) 

dla obsługi błędów Szkoda, że ​​nie było sposobu, aby zobaczyć wzory pojawić się w monady, ale takie jest życie (co można zrobić, jeśli funkcja view przeprowadzono w cps i potraktował kontynuację jako argument zamiast zwracania wartości).