design-patterns - gof - design patterns types

¿Cómo agregar campos que solo cachean algo a ADT?

Question

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 de fv 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 el resto. Además, rompe la coincidencia de patrones en todas las funciones que usan Lambda . 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:

1. La definición de los data debe verse lo más cerca posible del original, para que sea fácil de leer y entender.
2. Las coincidencias de patrones también deben ser simples y legibles.
3. 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 usó fv en este ejemplo).

Describiré mi solución actual: para mantener la definición de data y las coincidencias de patrones lo más poco 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 también tendríamos que nombrar todos los demás campos ).

Esto nos permite escoger partes específicas de la memoria, manteniendo la misma firma de fv que 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 la firma Lambda -> Something , podemos agregarla fácilmente como un nuevo campo de memorización.

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

• La definición de los data no es tan mala, pero aun así, colocar la memo todas partes 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 agregamos un _ , pero tener la misma firma para construir y deconstruir sería bueno. Supongo que Views o Pattern Sinónimos lo resolverían.
• El cálculo de los campos memorizados (variables libres, profundidad) está estrechamente relacionado con los constructores inteligentes. Como es razonable suponer que esas funciones memorizadas siempre serán catamorphisms , creo que esto podría resolverse en cierta medida con herramientas como el paquete de punto de referencia .

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

Answer 1

Creo que todos sus objetivos se pueden cumplir utilizando una memoria simple en la función en lugar de almacenar los resultados en caché en el propio ADT. Hace solo un par de semanas, stable-memo paquete stable-memo , que debería ayudar aquí. Comprobando sus criterios, no creo que podamos hacer nada mejor que esto:

1. Su definición de datos no cambia en absoluto.
2. La coincidencia de patrones tampoco cambia.
3. El código existente no tiene que cambiar simplemente porque escribe más funciones memoizadas.
   • No se rompen los patrones existentes.
   • Ninguna función memoized existente se rompe.

Usarlo es muy simple. Simplemente aplique memo a cualquier función que desee memorizar, asegurándose de que utiliza la versión memorizada de la función en todas partes, incluso en llamadas recursivas. Aquí le mostramos cómo escribir el ejemplo que utilizó en su pregunta:

import Data.StableMemo
type VSym = String
data Lambda = Var VSym
| App Lambda Lambda
| Abs VSym Lambda
fv :: Lambda -> Set VSym
fv = memo go
where
go (Var v) = Set.singleton v
go (App s t) = fv s `Set.union` fv t
go (Abs v t) = v `Set.delete` fv t