如何向ADT添加只缓存内容的字段？
我经常需要在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.
这样的工具可以在一定程度上解决这个问题
有什么想法可以改进它吗？或者有没有更好的方法来解决这样的问题？
回答 1
Stack Overflow用户
发布于 2012-11-10 00:20:38
我认为你的所有目标都可以通过在函数中使用普通的旧式记忆来实现，而不是通过在ADT本身中缓存结果。就在几周前，我发布了stable-memo包，它在这里应该会有所帮助。检查你的标准，我认为我们不能做得比这更好：
- 你的数据定义根本不会改变，
- 模式匹配也不会改变，
代码也不会仅仅因为你写了更多的记忆函数而改变。
- 不会破坏现有的模式。
- 不会获取现有的内存函数get patterns
使用它非常简单。只需将memo应用于您想要记忆的任何函数，确保您在任何地方都使用该函数的记忆版本，即使在递归调用中也是如此。以下是如何编写您在问题中使用的示例：
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 thttps://stackoverflow.com/questions/13098448
复制相似问题