design-patterns - 如何将仅缓存某些内容的字段添加到 ADT？

Question

我经常需要向 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定义应尽可能接近原始定义，以便易于阅读和理解。

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

稍后添加新的内存字段不应破坏现有代码，特别是:

不要打破现有模式，

不需要更改使用我们想要内存的函数的位置(如本例中使用 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 内存一个函数我们可以轻松地将其添加为新的内存字段。

我仍然不喜欢这个设计的地方:

data定义还不错，但仍然放置memo到处都把它弄得乱七八糟。

我们需要智能构造函数来构造值，但我们使用常规构造函数进行模式匹配。这还不错，我们简单地添加一个 _ ，但是对于构造和解构具有相同的签名会很好。我想Views或 Pattern Synonyms会解决它。

内存字段(自由变量、深度)的计算与智能构造函数紧密耦合。因为可以合理地假设这些内存函数将始终为 catamorphisms , 我相信这可以通过 the fixpoint package 等工具在一定程度上解决.

任何想法如何改进它？或者有没有更好的方法来解决这样的问题？

Answer 1

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

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

模式匹配也不会改变。

现有代码不必仅仅因为您编写了更多的内存函数而改变。

现有模式不会被破坏。

没有现有的内存功能被破坏。

使用它非常简单。只需申请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 t