Факторинг из рекурсии в комплексе АСТ

Question

Для стороннего проекта, над которым я работаю, мне в настоящее время приходится иметь дело с абстрактным синтаксическим деревом и преобразовывать его в соответствии с правилами (особенности не важны).

Само AST нетривиально, то есть имеет подвыражения, которые ограничены только некоторыми типами. (например, оператор A должен принимать аргумент, который имеет тип B только не Expr, Значительно упрощенная уменьшенная версия моего типа данных выглядит следующим образом:

data Expr  = List [Expr]
           | Strange Str
           | Literal Lit
data Str   = A Expr
           | B Expr
           | C Lit
           | D String
           | E [Expr]
data Lit   = Int Int
           | String String

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

data ExprF a = List [a]
             | Strange (StrF a)
             | Literal (LitF a)
data StrF a  = A a
             | B a
             | C (LitF a)
             | D String
             | E [a]
data LitF a  = Int Int
             | String String

Если бы я не испортил, type Expr = Fix ExprF теперь должен быть изоморфен ранее определенному Expr,

Тем не менее, написание cata для этих случаев становится довольно утомительным, так как я должен соответствовать шаблону B a :: StrF a внутри Str :: ExprF a за cata быть хорошо напечатанным. Для всего оригинального AST это невозможно.

Я наткнулся на исправление GADT, которое, как мне кажется, является решением моей проблемы, однако недружественный для пользователя интерфейс дублированных классов типов высшего порядка и т. Д. Является довольно ненужным образцом.

Итак, подведем итог моим вопросам:

1. Является ли переписывание AST как GADT правильным способом?
2. Если да, как я могу преобразовать пример в хорошо работающую версию? На второй ноте, есть ли лучшая поддержка для старших Functorсейчас в GHC?

Answer 1

Если вы прошли через попытку выделить рекурсию в вашем типе данных, то вы можете просто получить Functor и вы сделали. Вам не нужны какие-то необычные функции, чтобы получить схему рекурсии. (Как примечание, нет никаких причин для параметризации Lit тип данных.)

Сгиб это:

newtype Fix f = In { out :: f (Fix f) }

gfold :: (Functor f) => (f a -> a) -> Fix f -> a
gfold alg = alg . fmap (gfold alg) . out

Чтобы указать алгебру (alg параметр), вам нужно сделать анализ случая против ExprF, но альтернативой было бы иметь сгиб с дюжиной или более параметров: по одному для каждого конструктора данных. Это на самом деле не спасет вас от большого количества печатания и будет намного труднее читать. Если вы хотите (а для этого могут потребоваться типы ранга 2 в целом), вы можете упаковать все эти параметры в запись, а затем использовать обновление записи для обновления "заранее созданных" записей, которые обеспечивают поведение "по умолчанию" в различных обстоятельствах., Есть старая газета, имеющая дело с большими бананами, которая использует такой подход. То, что я предлагаю, чтобы быть ясным, это просто завернуть gfold выше функция с функцией, которая принимает запись и передает в алгебру, которая будет делать анализ случая и вызывать соответствующее поле записи для каждого случая.

Конечно, вместо этого вы можете использовать GHC Generics или различные "универсальные / политипные" библиотеки программирования, такие как Scrap Your Boilerplate. Вы в основном воссоздаете то, что они делают.