如何向ADT添加仅缓存某些内容的字段？

Question

如何向ADT添加仅缓存某些内容的字段？

design-patternscachinghaskellmemoizationalgebraic-data-types

16

经常需要向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

但这使得定义变得相当丑陋。几乎所有的代码都比其他代码占用更多的空间，而且它打破了使用Lambda的所有函数中的模式匹配。更糟糕的是，如果我们稍后决定添加一些其他的记忆字段，我们将不得不重新编写所有的模式。

如何设计一个通用解决方案，可以轻松、自然地添加这样的记忆字段？我想实现以下目标：

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

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

3.后来添加新的记忆字段不应破坏现有代码，特别是：

- 不要破坏现有的模式， - 不要在使用我们想要记忆化的函数的地方（例如本例中使用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

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

这使我们能够从记忆化中选择特定的部分，同时保持与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的函数进行记忆，我们可以轻松地将其作为新的记忆字段添加。

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

数据定义并不那么糟糕，但是到处都放置“memo”会使其变得混乱。
我们需要智能构造函数来构造值，但是我们使用常规构造函数进行模式匹配。这并不太糟糕，我们只需添加一个“_”，但是具有相同签名的构造和解构将是不错的。我想Views或Pattern Synonyms可以解决这个问题。
记忆化字段（自由变量、深度）的计算与智能构造函数紧密耦合。由于可以合理地假设这些记忆化函数将始终是catamorphisms，因此我认为像the fixpoint package这样的工具可以在一定程度上解决这个问题。

有什么改进的想法吗？或者有更好的方法来解决这样的问题吗？

- Petr

1

也许 Annotations 包（可能还有其他提供类似功能的库）可以帮助你？ - kosmikus

@kosmikus，我简要地查看了这个包，恐怕如果使用这样的库，模式匹配将变得不方便。也许，如果我们将所有与“Lambda”一起工作的函数表达为ana/cata-morphisms（我完全不介意），它们中的模式可能会变得合理。也许把你的评论写成一个完整的答案会更值得。 - Petr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jake McArthur · Accepted Answer

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