A menudo necesito agregar campos a un ADT que solo memorice alguna información redundante. Pero no he descubierto completamente cómo hacerlo de manera agradable y eficiente.

La mejor manera de mostrar el problema es hacer un ejemplo. Supongamos que estamos trabajando con términos lambda no tipificados:

type VSym = String

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

Y de vez en cuando necesitamos calcular el conjunto de variables libres de un término:

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)

Pronto nos damos cuenta de que los cálculos repetidos defv Son un cuello de botella de nuestra aplicación. Nos gustaría agregarlo al tipo de datos de alguna manera. Me gusta:

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

Pero hace que la definición sea bastante fea. Casi(Set VSym) ocupa más espacio que todo el resto. Además, rompe la coincidencia de patrones en todas las funciones que utilizanLambda. Y para empeorar las cosas, si luego decidimos agregar algún otro campo de memorización, tendremos que volver a escribir todos los patrones nuevamente.

¿Cómo diseñar una solución general que permita agregar campos de memorización de manera fácil y discreta? Me gustaría alcanzar los siguientes objetivos:

losdata La definición debe ser lo más parecida posible al original, para que sea fácil de leer y entender.Las coincidencias de patrones también deben ser simples y legibles.Agregar un nuevo campo de memorización más tarde no debe romper el código existente, en particular:no romper los patrones existentes,no requerir cambios donde se usó la función que queremos memorizar (como el código que usamosfv en este ejemplo).

Voy a describir mi solución actual: Para mantener ladata La definición y el patrón coinciden lo menos posible, definamos:

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

donde los datos a memorizar se definen por separado:

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

A continuación, una función simple que recupera la parte memoized:

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

(Esto podría eliminarse mediante el uso de campos con nombre. Pero luegoDebes nombrar todos los otros campos también.)

Esto nos permite escoger partes específicas de la memoria, manteniendo la misma firma defv como antes:

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

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

Finalmente, declaramos estos constructores inteligentes:

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

Ahora podemos escribir de manera eficiente cosas que combinan la combinación de patrones con la lectura de campos memorizados como

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 t@(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

Esto parece resolver:

La coincidencia de patrones sigue siendo bastante razonable.Si agregamos un nuevo campo de memorización no interrumpirá el código existente.Si decidimos memorizar una función con firma.Lambda -> Something Podemos agregarlo fácilmente como un nuevo campo de memorización.

Lo que todavía no me gusta de este diseño:

losdata La definición no es tan mala, pero sigue colocando.memo Todo el mundo lo desordena considerablemente.Necesitamos tener constructores inteligentes para construir valores, pero usamos los constructores regulares para la comparación de patrones. Esto no es tan malo, simplemente añadimos uno._, pero tener la misma firma para construir y deconstruir sería bueno. supongoPuntos de vista oSinónimos de patrones lo solucionariaEl cálculo de los campos memorizados (variables libres, profundidad) está estrechamente relacionado con los constructores inteligentes. Como es razonable suponer que esas funciones memorizadas serán siemprecatamorfismos, Creo que esto podría ser resuelto en cierta medida por herramientas comoel paquete fixpoint.

¿Alguna idea de cómo mejorarla? ¿O hay mejores maneras de resolver tal problema?