Как добавить поля, которые только кэшируют что-то в ADT?

Часто мне нужно добавлять поля в ADT, которые только запоминают некоторую избыточную информацию. Но я не понял полностью, как сделать это красиво и эффективно.

Лучшим способом показать проблему является пример. Предположим, что мы работаем с нетипизированными лямбда-терминами:

type VSym = String

data Lambda = Var VSym 
            | App Lambda Lambda
            | Abs VSym Lambda

И время от времени нам нужно вычислить множество свободных переменных члена:

fv :: Lambda -> Set VSym
fv (Var v)    = Set.singleton v
fv (App s t)  = (fv s) `Set.union` (fv t)
fv (Abs v t)  = v `Set.delete` (fv t)

Вскоре мы понимаем, что повторные вычисления fv являются узким местом нашего приложения. Мы хотели бы как-то добавить его к типу данных. Как:

data Lambda1 = Var (Set VSym) VSym
             | App (Set VSym) Lambda Lambda
             | Abs (Set VSym) VSym Lambda

Но это делает определение довольно уродливым. Почти (Set VSym) занимает больше места, чем все остальные. Более того, он разбивает соответствие шаблонов во всех функциях, которые используют Lambda. И чтобы ухудшить ситуацию, если позже мы примем еще какое-то другое поле memoizing, нам придется снова переписать все шаблоны.

Как создать общее решение, позволяющее легко и ненавязчиво добавлять такие memoizing поля? Я хотел бы достичь следующих целей:

Определение data должно выглядеть как можно ближе к оригиналу, чтобы оно было легко читаемым и понятным.
Соответствие шаблону также должно оставаться простым и читаемым.
Добавление нового поля memoizing позже не должно нарушать существующий код, в частности:
- не нарушать существующие шаблоны,
- не требует изменений, в которых использовалась функция, которую мы хотим использовать memoize (например, код, который использовал fv в этом примере).

Я опишу свое текущее решение: для того, чтобы определение data и шаблон совпадали как можно меньше, пусть определите:

data Lambda' memo = Var memo VSym 
                  | App memo (Lambda' memo) (Lambda' memo)
                  | Abs memo VSym (Lambda' memo)
type Lambda = Lambda' LambdaMemo

где данные, подлежащие замещению, определяются отдельно:

data LambdaMemo = LambdaMemo { _fv :: Set VSym, _depth :: Int }

Затем простая функция, которая извлекает memoized часть:

memo :: Lambda' memo -> memo
memo (Var c _)   = c
memo (App c _ _) = c
memo (Abs c _ _) = c

(Это можно устранить, используя именованные поля. Но тогда мы также должны указать все остальные поля)

Это позволяет нам выбирать определенные части из memoize, сохраняя ту же подпись fv, как и раньше:

fv :: Lambda -> Set VSym
fv = _fv . memo

depth :: Lambda -> Int
depth = _depth . memo

Наконец, мы объявляем эти интеллектуальные конструкторы:

var :: VSym -> Lambda
var v = Var (LambdaMemo (Set.singleton v) 0) v

app :: Lambda -> Lambda -> Lambda
app s t = App (LambdaMemo (fv s `Set.union` fv t) (max (depth t) (depth s))) s t

abs :: VSym -> Lambda -> Lambda
abs v t = Abs (LambdaMemo (v `Set.delete` fv t) (1 + depth t)) v t

Теперь мы можем эффективно писать вещи, которые смешивают шаблон с чтением memoized полей, таких как

canSubstitute :: VSym -> Lambda -> Lambda -> Bool
canSubstitute x s t
  | not (x `Set.member` (fv t))
      = True -- the variable doesn't occur in `t` at all
canSubstitute x s [email protected](Abs _ u t')
  | u `Set.member` (fv s)
      = False
  | otherwise
      = canSubstitute x s t'
canSubstitute x s (Var _ _)
      = True
canSubstitute x s (App _ t1 t2)
      = canSubstitute x s t1 && canSubstitute x s t2

Это, кажется, решает:

Совпадение шаблонов по-прежнему вполне разумно.
Если мы добавим новое поле memoizing, оно не нарушит существующий код.
Если мы решаем memoize функцию с сигнатурой Lambda -> Something, мы можем легко добавить ее в новое поле memoizing.

Что мне еще не нравится в этом проекте:

Определение data не так уж плохо, но размещение memo повсеместно сильно мешает ему.
Нам нужны интеллектуальные конструкторы для построения значений, но мы используем регулярные конструкторы для сопоставления шаблонов. Это не так уж плохо, мы просто добавляем один _, но иметь такую же подпись для построения и деконструкции было бы неплохо. Я полагаю, что Views или Синонимы шаблонов разрешат его.
Вычисление memoized полей (свободных переменных, глубина) тесно связано с интеллектуальными конструкторами. Поскольку разумно предположить, что эти memoized функции будут всегда catamorphisms, я считаю, что это может быть в какой-то мере разрешено такими инструментами, как пакет исправлений.

Есть идеи, как его улучшить? Или есть ли лучшие способы решения такой проблемы?

Ответ 1