这是一个关于地图数据结构的问题，它在大量的非破坏性操作下保持内存效率。
上下文
我正在编写一个小程序，通过该程序，我根据某些逻辑在谓词iterate/2中生成"状态"(只是保存数据的术语)，这些逻辑对于本文的讨论可以忽略。
iterate/2以尾递归方式递归调用自身。在每次调用时，iterate/2都会生成更多状态，并且必须有效地检查以前是否看到过任何状态。
"以前看到"的状态数量可能相当可观(数万个)。但是，我们可以不时"忘记"(胖百分比)以前看到的条目。这是一件好事，因为我们希望将整体内存需求保持在一定范围内。
为了有效地执行"以前看到的"谓词，由适当的实现支持的"map"接口似乎是一个不错的选择(因为可以有效地在map中实现查找)。
假设我们有这样一个地图数据结构。
对于任何新生成的状态，从所述状态计算哈希值(- 通过任何方式)，并将该对(哈希，状态)作为(键，值)插入到映射中。
- 要检查某个状态之前是否已经出现过，请计算其哈希值并检查映射中是否存在与该哈希值对应的条目。(对于此练习，我们忽略了哈希冲突的可能性)
然后在iterate调用之间传递不断变化的映射数据结构。
这是一种逻辑编程语言，我们希望维持在所有可能的按定义不可变结构的永恒数学空间中工作的一般想法，在那里我们从一个结构移动到另一个结构，就像猴子从藤蔓上摆动一样，而不是像我们在命令式编程中那样不断改变时变的数据结构。我们只是希望垃圾收集器比我们更快！
我们提供的与地图相关的谓词可能是：
map_new(?Map)
。以将地图与空地图统一起来。
map_get(+Map,+Key,?Val)
。将 Val 与 map Map 中键键关联的值统一起来，或者如果 Map 不包含这样的键，则失败(通过允许键成为变量，可以通过回溯实现枚举)。
map_put(+Map,+Key,?Val,?OldVal,?NewMap)
。将地图新地图与通过将(键，Val)对插入地图地图获得的地图统一起来。如果地图映射已经包含带有键键的条目，则该条目的值与 OldVal 统一。
map_rem(+Map,+Key,?OldVal,?NewMap)
。将地图新地图与通过从地图地图中删除带有键键的条目获得的地图统一。与映射映射中的键键关联的值与 OldVal 统一。如果地图映射不包含键键，则失败。
我们将像这样使用上述内容：
iterate(Solution) :-
map_new(Map),
iterate(Map,Solution).
iterate(M,S) :-
gen_fresh_states(ListFresh),
gen_stale_states(ListStale),
add_fresh_states(M,ListFresh,MM),
del_stale_states(MM,ListStale,MMM),
( termination_check(MMM,S) -> true ; iterate(MMM,S) ).
哪里
add_fresh_states(M,ListFresh,MM),
del_stale_states(MM,ListStale,MMM),
以预期的方式迭代状态列表 ListFresh 和 ListStale ，迭代调用map_put/5或map_rem/4。
-> ;是 ->/2 谓词。
问题
此时，我们需要为地图选择一个好的实现。我们不希望在删除或添加单个项目时结构发生过度更改，以便底层实现可以通过引用映射M的子结构(例如子树)来保持复制操作，并且通常在map_put/5或map_rem/4期间从它构造MM来保持较低的堆空间。
(例如，我听说 Clojure 在其 4[不可变映射] 中的一些中使用了从这个意义上说的高效实现，但我还没有仔细研究过。
在SWI Prolog中，我们有AVL树支持的assoc实现。这非常适合快速查找。遗憾的是，每当插入或删除树节点时，AVL 树可能会发生重大变化。映射M、MM、MMM或介于两者之间的任何映射的实际堆布局之间可能没有太多共同点：堆可能会迅速填满。顺便说一下，assoc的实现是在Prolog中。(/usr/lib64/swipl-7.2.3/library/assoc.pl)，没有特殊的酱汁进入其中。
我是否误以为基于AVL树的地图无法胜任这项任务？
或者，是否有任何地图实现(不一定在SWI Prolog中)能够有效地重用子结构？
我想已经可以通过在iterate/2的子目标之间使用"！"来减轻堆的使用。这将告诉运行时不会发生回溯，从而授予它销毁任何不会再次使用的堆上结构的许可。例如，调用del_state_states/3之后的"！"可能会使MM有资格进行垃圾收集(我不知道这是否真的有效)。
我是否错误地认为基于AVL树的地图无法胜任这项任务？
很有可能：是的。
根据我的经验，library(assoc)是许多需要访问的任务的绝佳选择，如您所描述的那样。我建议你试一试 ！
在实践中，对数开销通常是可以接受的，您也可以经常从头开始重新构建地图以删除不需要的元素。
另请注意，许多其他平衡树结构(红黑树等)也承认自然和纯的Prolog实现，如果AVL 树不适合您，我建议您查看一些纯替代方案。
Chris Okasaki的博士论文《纯函数式数据结构》在这种情况下非常值得一看。