Muitas vezes, estou precisando adicionar campos a um ADT que apenas armazena algumas informações redundantes. Mas eu não descobri completamente como fazê-lo de forma agradável e eficiente.

A melhor maneira de mostrar o problema é dar um exemplo. Suponha que estamos trabalhando com termos lambda não tipificados:

type VSym = String

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

E, de tempos em tempos, precisamos calcular o conjunto de variáveis ​​livres de um termo:

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)

Logo percebemos que cálculos repetidos defv são um gargalo da nossa aplicação. Gostaríamos de adicioná-lo ao tipo de dados de alguma forma. Gostar:

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

Mas isso torna a definição bastante feia. Quase(Set VSym) ocupa mais espaço do que todo o resto. Além disso, quebra a correspondência de padrões em todas as funções que usamLambda. E para piorar as coisas, se mais tarde decidirmos adicionar algum outro campo de memorando, teremos que reescrever todos os padrões novamente.

Como projetar uma solução geral que permita adicionar esses campos de memorização de maneira fácil e discreta? Eu gostaria de alcançar os seguintes objetivos:

odata A definição deve parecer o mais próximo possível do original, para que seja facilmente legível e compreensível.Correspondências de padrões também devem permanecer simples e legíveis.Adicionando um novo campo memoizing mais tarde não deve quebrar o código existente, em particular:não quebrar padrões existentes,para não exigir mudanças onde a função que queremos para memoize foi usada (como o código quefv neste exemplo).

Vou descrever minha solução atual: para manter odata definição e padrão correspondem tão pouco confuso quanto possível, vamos definir:

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

onde os dados a serem memoizados são definidos separadamente:

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

Então uma função simples que recupera a parte memoizada:

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

(Isso pode ser eliminado usando campos nomeados. Mas então nóstem que nomear todos os outros campos também.)

Isso nos permite escolher partes específicas do memoize, mantendo a mesma assinatura defv como antes:

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

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

Finalmente, nós declaramos estes construtores 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

Agora podemos escrever eficientemente coisas que combinam padrões de correspondência com a leitura 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

Isso parece resolver:

A correspondência de padrões ainda é bastante razoável.Se adicionarmos um novo campo de memoizing, ele não interromperá o código existente.Se decidirmos memorizar uma função com assinaturaLambda -> Something Podemos facilmente adicioná-lo como um novo campo de memorando.

O que eu ainda não gosto neste design:

odata definição não é tão ruim, mas ainda colocandomemo em toda parte desordena consideravelmente.Precisamos ter construtores inteligentes para construir valores, mas usamos os construtores regulares para correspondência de padrões. Isso não é tão ruim, nós simplesmente adicionamos um_, mas ter a mesma assinatura para construir e desconstruir seria bom. Eu suponhoViews ouPadrão Sinônimo resolveria isso.O cálculo dos campos memoizados (variáveis ​​livres, profundidade) é fortemente acoplado aos construtores inteligentes. Como é razoável supor que essas funções memoizadas serão semprecatamorfismos, Acredito que isso poderia ser resolvido até certo ponto por ferramentas comoo pacote do ponto de fixação.

Alguma idéia de como melhorá-lo? Ou existem maneiras melhores de resolver esse problema?