Избегайте шаблонов при работе со многими несвязанными типами

Question

Я пишу код, который работает со значениями из Language.Exts.Annotated.Syntax , где определены различные типы, отражающие структуру модуля Haskell:

data Module l = ...
data Decl l = ...
data Exp t = ...
-- etc

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

Пока что я написал тип Tree, который охватывает каждый из этих типов, чтобы моя функция преобразования могла выполнять Tree l -> Tree l:

data Tree l = ModuleT (Module l)
            | DeclT (Decl l)
            | ExpT (Exp l)
            -- etc copy & paste

Однако теперь я пишу много кода, который принимает Module, упаковывает его ModuleT, вызывает функцию, а затем снова разворачивает результат обратно в Module. У меня есть:

class AnnotatedTree ast where
  tree :: ast l -> Tree l
  untree :: Tree l -> ast l

instance AnnotatedTree Module where
  tree = ModuleT
  untree (ModuleT x) = x
  untree _ = error "expected ModuleT"

-- etc ad nauseam

Два вопроса:

1. Учитывая, что я не могу изменить типы в Language.Exts.Annotated.Syntax, я поступаю неправильно?
2. Если нет, могу ли я как-то сократить весь этот шаблон?

Answer 1

Все эти типы являются экземплярами Typeable и Data. Вы можете определить свое дерево типов как экземпляр Typeable и Data, а затем использовать одну из доступных универсальных библиотек (SYB, uniplate, ...) для легкого обхода дерева.

Мой личный фаворит - uniplate. Например, собрать весь GuardedAlt из дерева будет так же просто, как:

import Data.Uniplate.PlateData

...

allGuardedAlts :: Tree l -> [l]
allGuardedAlts t = [ l | GuardedAlt l _ _ <- universeBi t]

Вы можете взглянуть на мой пакет graphtype , где я делал подобные вещи.