如何添加仅缓存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.更糟糕的是,如果我们后来决定添加一些其他的memoizing字段,我们将不得不再次重写所有模式.

如何设计一个通用的解决方案,允许轻松,不引人注意地添加这些记忆字段？我想达到以下目标:

1. 该data定义应该尽可能接近原来的,所以它很容易阅读和理解.
2. 模式匹配也应该保持简单和可读.
3. 稍后添加新的memoizing字段不应该破坏现有代码,特别是:
   • 不要打破现有的模式,
   • 不要求使用我们想要记忆的函数的更改(比如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 }

然后是一个检索memoized部分的简单函数:

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

(这可以通过使用命名字段来消除.但是我们也必须为所有其他字段命名.)

这允许我们从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

这似乎解决了:

• 模式匹配仍然很合理.
• 如果我们添加一个新的memoizing字段,它将不会破坏现有代码.
• 如果我们决定使用签名来记忆函数,Lambda -> Something我们可以轻松地将其添加为新的记忆字段.

我仍然不喜欢这个设计:

• 该data定义并没有那么糟糕,但仍然将memo无处不在杂波它增色不少.
• 我们需要有智能构造函数来构造值,但我们使用常规构造函数进行模式匹配.这并不是很糟糕,我们只需添加一个_,但具有相同的签名用于构造和解构将是很好的.我认为视图或模式同义词会解决它.
• 记忆字段(自由变量,深度)的计算与智能构造函数紧密耦合.由于可以合理地假设那些记忆功能将始终是catamorphisms,我相信这可以通过像fixpoint包这样的工具在某种程度上解决.

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

Answer 1

我认为您的所有目标都可以通过在函数中使用普通的旧记忆来实现，而不是通过在 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 -> 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