Haskell 中使用预制数据结构进行记忆化

发布于 2024-10-29 06:02:52 字数 1846 浏览 0 评论 0原文

我找到这个答案和此 wiki 页面是对记忆化的精彩介绍哈斯克尔。然而，它们仍然给我留下了一个我希望得到解答的问题：

在我看来，所使用的技术要求您“开放”（如“访问其内部”）用于存储的数据结构你的记忆。例如， 1 实现表结构并 2 在第 3 节。是否可以使用预制的数据结构做类似的事情？例如，假设您认为 Data.Map 非常棒，并且希望将您记忆的值存储在这样的 Map 中。是否可以使用这样的预制数据结构来实现记忆化，其中不实现该结构本身，而是使用预制的数据结构？

希望有人能给我一些如何思考的提示，或者更有可能纠正我对函数式记忆的误解。

编辑：我可以想到一种方法来做到这一点，但它一点也不优雅：If f :: a -> b，那么人们可能可以轻松地制作一个记忆版本 f' :: Map ab ->一个-> (Map ab, b)，其中第一个参数是记忆存储，输出对包含可能更新的存储和计算值。这种状态传递当然不是我想要的（虽然我猜它可以包裹在一个 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))

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

原文

I find this answer and this wiki page to be excellent introductions to memoization in Haskell. They do, however, still leave me with a question that I hope to get answered:

It seems to me that the technique used requires you to "open up" (as in "access the internals of") the data structure you use to store your memoization. For example, 1 implements a table structure and 2 implements a tree in section 3. Is it possible to do something similar with a pre-made data structure? Suppose, for example, that you think that Data.Map is really awesome, and would like to store your memoized values in such a Map. Can one approach memoization with a pre-made data structure such as this, where one does not implement the structure itself, but rather use a pre-made one?

Hopefully someone will give me a hint on how to think, or, perhaps more likely, correct my misunderstanding of functional memoization in general.

Edit: I can think of one way to do it, but it's not at all elegant: If f :: a -> b, then one can probably easily make a memoized version f' :: Map a b -> a -> (Map a b, b), where the first argument is the memoization storage, and the output pair contains a potentially updated storage and the computed value. This state-passing is certainly not what I want (although I guess it could be wrapped in a monad, but it's several orders of magnitudes uglier than the approach in 1 and 2).

Edit 2: Maybe it helps to try and express my current way of (incorrect) thought. Currently, I seem to repeatedly pull myself, against my will, into the non-solution

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))

The more I stare at this, the more I realize I've misunderstood something basic. You see, it feels to me that my memo [True, False] is equivalent to the bool memoizer of 1.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

笑看君怀她人 2024-11-05 06:02:52

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

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

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

如果我没记错的话，那么第一次 (Map.!) storage 被迫评估给定的键，storage结构将被完全扭曲（尽管除了给定的键之外的任何东西都不会发生计算f）。因此第一次查找将导致额外的 O(n) 操作，n 是长度域。据我所知，后续查找不会产生此成本。

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

ps 还有比“wring out”更好的短语吗？我想到了“力量”、“脊椎”和“明显”这些词，但我不太想出正确的词/短语。