如何添加仅缓存ADT的内容？ [英] How to add fields that only cache something to ADT?

问题描述

通常，我需要向只能记录一些冗余信息的ADT添加字段。但是我并没有完全弄清楚如何做到这一点非常有效率。

显示问题的最好办法就是举个例子。假设我们正在使用无类型的lambda术语：

 键入VSym = String 
 
 data Lambda = Var VSym 
 | App Lambda Lambda 
 | Abs VSym Lambda 
  

不时，我们需要计算一个术语的自由变量集：

  fv :: Lambda  - >设置VSym 
 fv（Var v）= Set.singleton v 
 fv（App st）=（fv s）`Set.union`（fv t）
 fv（Abs vt）= v `Set.delete`（fv t）
  

很快，我们意识到重复计算 fv 是我们应用程序的瓶颈。我们想以某种方式将其添加到数据类型。像：

  data Lambda1 = Var（Set VSym）VSym 
 | App（Set VSym）Lambda Lambda 
 | Abs（Set VSym）VSym Lambda 
  

但是它的定义很丑陋。几乎（设置VSym）占用的空间比其余的多。此外，它会破坏使用 Lambda 的所有函数中的模式匹配。为了使事情变得更糟，如果我们以后决定添加一些其他的记忆领域，我们将不得不重新编写所有模式。

如何设计一般的解决方案可以轻松，不引人注目地添加这样的记忆领域？我想达成以下目标：

1. 数据定义应该尽可能靠近原始，以便它易于阅读和理解。


2. 模式匹配也应该保持简单易读。


3. 稍后添加新的记忆字段不应该破坏现有的代码，特别是：
   
   
   
   
   • 不要破坏现有的模式，
   
   
   • 不需要更改我们想要记忆的功能（例如在本例中使用 fv 的代码） / li>
     

---

我会描述我的当前的解决方案：要保持数据定义和模式匹配为一个小clutte我们可以定义：

  data Lambda'memo = Var备注VSym 
 |应用笔记（Lambda'备忘录）（Lambda'备注）
 | Abs备忘录VSym（Lambda'memo）
 type Lambda = Lambda'LambdaMemo 
  

其中数据要记录的是单独定义的：

 数据LambdaMemo = LambdaMemo {_fv :: Set VSym，_depth :: Int} 
  

然后一个简单的函数来检索记忆部分：

  memo :: Lambda'备注 - >备忘录
备忘录（var c _）= c 
备忘录（App c _ _）= c 
备忘录（Abs c _ _）= c 
  

（这可以通过使用命名字段来消除，但是我们会必须命名所有其他字段）。

这允许我们从回忆中选择具体的部分，保持与以前一样的 fv 的相同签名：

  fv :: Lambda  - >设置VSym 
 fv = _fv。备注
 
 depth :: Lambda  - > Int 
 depth = _depth。 memo 
  

最后，我们声明这些智能构造函数：

  var :: VSym  - > Lambda 
 var v = Var（LambdaMemo（Set.singleton v）0）v 
 
 app :: Lambda  - > λ - Lambda 
 app s t = App（LambdaMemo（fv s`Set.union` fv t）（max（depth t）（depth s）））s t 
 
 abs :: VSym  - > λ - Lambda 
 abs vt = Abs（LambdaMemo（v`Set.delete` fv t）（1 + depth t））vt 
  

现在我们可以有效地写出混合模式匹配的东西，比如读取记住的字段，如

  canSubstitute： ：VSym  - > λ - λ - Bool 
 canSubstitute x s t 
 |不是（x`Set.member`（fv t））
 = True  - 变量不会出现在`t`全部
 canSubstitute xst @（Abs _ u t'）
 | u`Set.member`（fv s）
 = False 
 |否则
 = canSubstitute xs t'
 canSubstitute xs（Var _ _）
 = True 
 canSubstitute xs（App _ t1 t2）
 = canSubstitute xs t1&& ; canSubstitute xs t2 
  

这似乎解决了：

<

如果我们添加一个新的记忆字段，它不会中断现有的代码。

如果我们决定使用签名 Lambda - >某些东西我们可以轻松地添加它作为一个新的记忆领域。

我还不喜欢这个设计：

• 数据定义不是那么糟糕，
  
• 我们需要有聪明的构造函数来构造值，但是我们使用常规构造函数进行模式匹配。这不是很糟糕，我们只需添加一个 _ ，但是具有相同的构造和解构签名将是很好的。我想视图或模式同义词将解决它。


• 记忆区域的计算（自由变量，深度）紧密耦合到智能构造器。因为假设这些记忆功能将始终是变形，这是合理的，我相信这可以解决在某种程度上可以通过 fixpoint软件包等工具。

任何想法如何改进？还是有更好的方法来解决这个问题？

解决方案

我认为所有的目标都可以通过使用普通的老回忆来满足在函数中，而不是通过缓存ADT本身的结果。就在几周前，我发布了 stable-memo 软件包，这应该在这里有所帮助。检查您的标准，我不认为我们可以做得比以前更好：

1. 您的数据定义根本没有改变。


2. 模式匹配也不会改变。


3. 现有代码不必仅仅因为写入更多的备忘功能而改变。
   
   
   
   • 没有现有的模式被破坏。
   
   
   • 没有现有的记忆功能被破坏。
   
   

使用它非常简单。只需将 memo 应用于您想要记住的任何功能，确保即使在递归调用中也可以使用函数的记忆版本。以下是如何编写您在问题中使用的示例：

  import Data.StableMemo 
 
 type VSym = String 
 
 data Lambda = Var VSym 
 | App Lambda Lambda 
 | Abs VSym Lambda 
 
 fv :: Lambda  - >设置VSym 
 fv = memo go 
其中
 go（Var v）= Set.singleton v 
 go（App st）= fv s`Set.union` fv t 
 go（Abs vt）= v`Set.delete` fv t 
  

Often I'm in the need of adding fields to an ADT that only memoize some redundant information. But I haven't figured out completely how to do it nicely and efficiently.

The best way to show the problem is to make an example. Suppose we're working with untyped lambda terms:

type VSym = String

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

And from time to time we need to compute the set of free variables of a term:

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)

Soon we realize that repeated computations of fv are a bottleneck of our application. We would like to add it to the data type somehow. Like:

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

But it makes the definition quite ugly. Almost (Set VSym) takes more space than all the rest. Moreover, it breaks pattern matching in all functions that use Lambda. And to make things worse, if we later decide to add some other memoizing field, we'll have to rewrite all patterns again.

How to design a general solution that allows adding such memoizing fields easily and unobtrusively? I'd like to reach the following goals:

1. The data definition should look as close as possible to the original, so that it's easily readable and understandable.
2. Pattern matches too should remain simple and readable.
3. Adding a new memoizing field later should not break existing code, in particular:
   • not to break existing patterns,
   • not to require changes where the function we want to memoize was used (like code that used fv in this example).

---

I'll describe my current solution: To keep the data definition and pattern matches as little cluttered as possible, let's define:

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

where the data to be memoized is defined separately:

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

Then a simple function that retrieves the memoized part:

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

(This could be eliminated by using named fields. But then we'd have to name all the other fields as well.)

This allows us to pick specific parts from the memoize, keeping the same signature of fv as before:

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

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

Finally, we declare these smart constructors:

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

Now we can efficiently write things that mix pattern matching with reading the memoized fields like

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

This seems to solve:

• Pattern matching is still quite reasonable.
• If we add a new memoizing field it won't disrupt existing code.
• If we decide to memoize a function with signature Lambda -> Something we can easily add it as a new memoizing field.

What I still don't like about this design:

• The data definition isn't so bad, but still placing memo everywhere clutters it considerably.
• We need to have smart constructors for constructing values but we use the regular constructors for pattern matching. This is not so bad, we simply add one _, but having the same signature for constructing and deconstructing would be nice. I suppose Views or Pattern Synonyms would solve it.
• The computation of the memoized fields (free variables, depth) is tightly coupled to the smart constructors. As it's reasonable to assume that those memoized functions will be always catamorphisms, I believe this could be solved to some extent by tools like the fixpoint package.

Any ideas how to improve it? Or are there better ways to solve such a problem?

解决方案

I think all of your goals can be met by using plain old memoization in the function instead of by caching results in the ADT itself. Just a couple weeks ago, I released the stable-memo package, which should help here. Checking over your criteria, I don't think we could do any better than this:

1. Your data definition doesn't change at all.
2. Pattern matching doesn't change, either.
3. Existing code doesn't have to change merely because you write more memoized functions.
   • No existing patterns get broken.
   • No existing memoized functions get broken.

Using it is very simple. Just apply memo to any function you want to memoize, making sure that you use the memoized version of the function everywhere, even in recursive calls. Here's how to write the example you used in your question:

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

这篇关于如何添加仅缓存ADT的内容？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！