gsp*_*spr 5 haskell memoization
我发现这个答案和这个wiki页面是对Haskell中的memoization的精彩介绍.但是,他们确实给我留下了一个我希望得到回答的问题:
在我看来,所使用的技术要求您"打开"(如"访问内部")用于存储备忘录的数据结构.例如,1实现了表结构,2实现了第3节中的树.是否可以使用预先制作的数据结构进行类似的操作？例如,假设您认为这Data.Map非常棒,并希望将您的memoized值存储在这样的Map.一种方法记忆化与预制的数据结构,如这一点,其中一个就可以不执行结构本身,而是使用预先制作的吗？
希望有人能给我一个关于如何思考的提示,或者更可能的是,纠正我对功能性记忆的误解.
编辑:我可以想到一种方法,但它并不优雅:如果f :: a -> b,那么可以轻松制作一个memoized版本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))
我越是盯着这个,我越发现我误解了一些基本的东西.你看,我觉得我memo [True, False]相当于1的bool记忆.
如果您注意到，Data.Memocombinators 实际上依赖于“预制”Data.IntTrie。我确信您可以采用相同的代码并用另一个数据结构替换 IntTrie 的使用，尽管它可能不那么高效。
记忆化的总体思想是保存计算结果。在 Haskell 中，最简单的方法是将函数映射到一个表上，该表的每个参数只有一个维度。由于 Haskell 是惰性的（Haskell 中的大多数数据结构都是惰性的），因此它只会在您明确要求时评估给定单元格的值。“表”基本上意味着“地图”，因为它将您从键带到值。
[编辑] 关于示例 2 的其他想法
如果我没有记错的话，那么第一次(Map.!) storage被迫评估给定的键，storage结构将完全被扭曲（尽管f除了给定的键之外的任何东西都不会发生计算）。因此第一次查找将导致额外的 O(n) 操作，n 为length domain。据我所知，后续查找不会产生此成本。
惰性结构（如典型的 int 索引列表或 IntTrie）同样需要在调用查找时显示其结构，但与 Map 不同，它们不需要一次全部显示出来。列表会被耗尽，直到访问索引键为止。IntTries 仅输出作为所需键的“前缀”（或后缀？不确定。可以以任何一种方式实现）的整数键。索引 11 ( 1011) 将输出 1 ( 1)、2 ( 10)、5 ( 101) 和 11 ( 1011)。Data.Memocombinators只需将所有键转换为整数（或“位”），以便IntTrie可以使用 an 。
ps 还有比“wring out”更好的短语吗？我想到了“力量”、“脊椎”和“明显”这些词，但我不太想出正确的词/短语。