Укомплектовать сложным типом данных в общем виде в Haskell

Question

Я использовал абстрактное синтаксическое дерево (AST) Language.C library для модификации программ на C с использованием общих преобразований SYB library. Этот АСТ имеет разные типы узлов (типы данных), каждый из которых представляет собой конструкцию С, т. Е. Выражения, утверждения, определения и т. Д. Мне нужно теперь как-то увеличить информацию, которую содержат данные, т. Е. Аннотировать их. Я должен (возможно я ошибаюсь), что я не могу изменить или переопределить исходный тип данных, поэтому я хотел бы иметь что-то вроде этого:

annotateAST anns = 
    everywhere (mkT (annotateAST_ anns)) 

annotateAST_ astnode anns 
    | isStmt astnode = AnnStmt astnode (getAnn astnode anns) 
    | otherwise = astnode 

Таким образом, я должен был бы новый AST с аннотированными заявлениями вместо первоначального. Конечно, GHC собирается жаловаться, потому что everywhere должен возвращать тот же самый тип, который он получает, и это не то, что здесь происходит.

В заключение, мне нужно в общих чертах аннотировать AST без изменения исходных типов данных и таким образом, чтобы было легко вернуться к исходной структуре данных. Я думал о разных решениях этой проблемы, но не убежден ни в одном из них, поэтому решил поделиться ею здесь.

P.S. Мне сказали, что библиотека SYB не очень эффективна. Принимая во внимание, что AST of Language.C выводит только данные, есть ли у меня более эффективная альтернатива общему обходу и модификации АСТ?

Answer 1

Я не эксперт в этой библиотеке, но, похоже, он разработан так, чтобы разрешить пользовательские декорации.

Это связано с тем, что все основные типы данных параметризованы над NodeInfo, стандартной аннотацией (только с указанием местоположения и информации о имени). Например. библиотека предоставляет

type CTranslUnit = CTranslationUnit NodeInfo 

, который позволяет определить

type MyTransUnit = CTranslationUnit MyNodeInfo 
data MyNodeInfo = MNI NodeInfo AdditionalStuffHere 

так, чтобы украсить AST, как вы хотите.

Библиотека предоставляет Functor экземпляры, которые могут повлиять на такие декорации, а также Annotated typeclass для извлечения (возможно, определяемой пользователем) аннотации из любого узла AST.

Я бы попытался продолжить этот подход.

---

Дизайн выглядит красиво. Единственный недостаток, который я вижу, заключается в том, что тип аннотации должен быть одинаковым для всех видов на узлах, что в основном заставляет его определять его как огромную сумму всех видов аннотаций, которые могут быть внутри. Например:

-- AST library for a simple lambda-calculus 
data AST n 
    = Fun n String (AST n) 
    | Var n String 
    | App n (AST n) (AST n) 

-- user code 
data Annotation 
    = AnnVar ... | AnnFun ... | AnnApp ... 
type AnnotatedAST = AST Annotation 

, и мы не предлагаем статические гарантии на функции украшаются AnnFun только.

Можно было бы желать более передовой дизайн библиотеки эксплуатации GADTs, такие как:

-- AST library for a simple lambda-calculus 
data Tag = TagFun | TagVar | TagApp 
data AST (n :: Tag -> *) 
    = Fun (n 'TagFun) String (AST n) 
    | Var (n 'TagVar) String 
    | App (n 'TagApp) (AST n) (AST n) 

-- user code 
data Annotation (n :: Tag) where 
    AnnFun :: String -> Annotation 'TagFun 
    AnnVar :: Int -> Annotation 'TagVar 
    AnnApp :: Bool -> Annotation 'TagApp 
type AnnotatedAST = AST Annotation 

, которая гарантирует правильную аннотацию в каждом узле. AST больше не будет Functor, но класс Functor-like может быть определен, по крайней мере.

Still - Буду признателен, если по крайней мере библиотека допускает определенные аннотации, определенные пользователем.