5

我发现这个答案和这个 wiki 页面是 Haskell 中记忆化的极好介绍。然而，他们确实给我留下了一个我希望得到回答的问题：

在我看来，所使用的技术要求您“打开”（如“访问内部”）用于存储记忆的数据结构。例如，1实现了一个表结构，2实现了第 3 节中的树。是否可以使用预制的数据结构做类似的事情？例如，假设您认为这Data.Map真的很棒，并且想将您的记忆值存储在这样的Map. 一种方法可以使用这样的预制数据结构进行记忆，其中一个人不实现结构本身，而是使用预制的结构？

希望有人能给我一个关于如何思考的提示，或者更有可能纠正我对功能性记忆的误解。

编辑：我可以想到一种方法，但它一点也不优雅：如果f :: a -> b，那么一个人可能很容易制作一个 memoized version f' :: Map a b -> a -> (Map a b, b)，其中第一个参数是 memoization 存储，输出对包含一个可能更新的存储和计算的值。这种状态传递当然不是我想要的（虽然我猜它可以被包裹在一个 monad 中，但它比1和2中的方法丑几个数量级）。

编辑2：也许尝试表达我目前的（不正确的）思维方式会有所帮助。目前，我似乎一再违背自己的意愿，将自己拉入无法解决的问题

import qualified Data.Map as Map
memo :: (Ord a) => [a] -> (a -> b) -> (a -> b)
memo domain f = (Map.!) storage
    where
      storage = Map.fromList (zip domain (map f domain))

我越看这个，我就越意识到我误解了一些基本的东西。你看，我觉得 mymemo [True, False]相当于1bool的memoizer 。

4

1 回答 1

3

如果您注意到，Data.Memocombinators 实际上依赖于“预制”Data.IntTrie。我相信您可以采用相同的代码并将 IntTrie 的使用替换为另一种数据结构，尽管它可能效率不高。

记忆化的一般思想是保存计算结果。在 Haskell 中，最简单的方法是将您的函数映射到一个表中，该表的每个参数都有一个维度。由于 Haskell 是惰性的（嗯，Haskell 中的大多数数据结构都是），它只会在您特别要求时评估给定单元格的值。“表”基本上意味着“地图”，因为它将您从键带到值。

[编辑] 关于示例 2 的其他想法

如果我没记错的话，那么第一次(Map.!) storage被迫评估给定的键，storage结构将被完全拧干（尽管f除了给定的键之外不会发生任何计算）。所以第一次查找将导致额外的 O(n) 操作，n 为length domain。随后的查找不会，afaik，产生这个成本。

像典型的 int 索引列表或 IntTrie 这样的惰性结构同样需要在调用查找时显示其结构，但与 Map 不同的是，它们不需要一次全部完成。在访问索引键之前，列表会被拧干。IntTries 只拧出作为所需键的“前缀”（或后缀？不确定。可以通过任何一种方式实现）的整数键。索引 11, ( 1011) 将挤出 1 ( 1)、2 ( 10)、5 ( 101) 和 11 ( 1011)。Data.Memocombinators只需将所有键转换为整数（或“位”），以便IntTrie可以使用。

ps 有没有比“拧出”更好的词组？我想到了“力”、“脊柱”和“清单”这些词，但我想不出合适的词/短语。

于 2011-04-01T14:48:42.197 回答