如何向ADT添加只缓存内容的字段？
如何向ADT添加只缓存内容的字段？
提问于 2012-10-27 16:16:56
我经常需要在ADT中添加字段，这些字段只记录一些冗余的信息。但我还没有完全弄清楚如何做得更好、更有效。
展示问题的最好方法就是举个例子。假设我们使用的是非类型化的lambda术语：
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的函数中的模式匹配。更糟糕的是，如果我们后来决定添加一些其他的记忆字段，我们将不得不再次重写所有模式。
如何设计一个通用的解决方案，允许轻松而不引人注目地添加这样的记忆字段？我想实现以下目标：
-
data定义应该看起来尽可能接近于原始的定义，以便它易于阅读，understandable. - Pattern匹配也应该保持简单，并且稍后创建一个新的记忆字段不应该破坏现有代码，特别是：
- 不要求更改我们想要记忆的函数的使用位置(就像在这个example).
中使用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 }然后使用一个简单的函数来检索带记忆的部件：
memo :: Lambda' memo -> memo
memo (Var c _) = c
memo (App c _ _) = c
memo (Abs c _ _) = c(这可以通过使用命名字段来消除。但之后我们也会使用have to name all the other fields。)
这允许我们从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现在，我们可以高效地编写混合模式匹配和读取记忆字段的内容，如
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这似乎解决了问题：
我们添加了一个新的记忆字段，它不会中断现有的代码。
- 如果我们决定记忆一个带有签名
Lambda -> Something的函数，我们可以很容易地将它添加为一个新的记忆字段。
我仍然不喜欢这个设计的地方：
considerably.
- We
-
data定义并不是那么糟糕，但是仍然把memo放得到处乱七八糟，我们需要有智能的构造函数来构造值，但是我们使用常规的构造函数来进行模式匹配。这并不是很糟糕，我们只需添加一个_，但拥有用于构造和解构的相同签名将是很好的。我认为Views或Pattern Synonyms可以解决这个问题。 - 记忆字段(自由变量，深度)的计算与智能构造函数紧密耦合。由于假设这些记忆函数总是catamorphisms是合理的，所以我相信像the fixpoint package.
这样的工具可以在一定程度上解决这个问题
有什么想法可以改进它吗？或者有没有更好的方法来解决这样的问题？
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13098448
复制相关文章
相似问题
腾讯云开发者
