在函数式编程语言中自动记忆
我一直认为Haskell会做某种自动智能记忆。 例如，天真的斐波那契实现
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)
因此会很快。 现在我读了这个，似乎我错了 - Haskell似乎没有做自动记忆。 或者我理解错了什么？
是否有其他语言自动执行（即隐式的，而不是显式的）记忆？
实现记忆的常用方法是什么？ 在我看到的所有示例实现中，它们都使用hashmap，但其大小没有任何限制。 显然，这在实践中不起作用，因为你需要某种限制。 考虑到这一点，它变得更加复杂，因为当你达到极限时，你必须抛弃一些数据。 在那里它变得复杂了：应该限制动态而且经常使用的函数应该比使用较少的函数具有更高的限制？ 当你达到极限时，你会扔掉什么？ 只是最新使用的一个？ 在这种情况下，您需要将您的数据另外排序。 你可以使用链表和散列图的组合来实现这一点。 这是常用的方式吗？
你可能会链接（或参考）一些常见的现实世界的实现？
谢谢，阿尔伯特
编辑：我主要对我描述的这个问题感兴趣，即如何实现这样的限制。 任何涉及这个问题的论文都会非常好。
编辑：一些自己的想法与示例实现（有限制）可以在这里找到。
编辑：我不是想解决特定应用程序中的特定问题。 我正在寻找通用的memoization解决方案，它可以全局应用于（纯函数式）程序的所有功能（因此算法没有实现内存限制不是解决方案）。 当然那里（可能）不是最佳/最好的解决方案。 但是这使得我的问题不那么有趣。
为了尝试这样的解决方案，我想把它作为一个优化添加到Haskell中。 我真的很想知道这样做会有多好。
我想知道是否有人已经做到了。
Haskell似乎没有做自动记忆。 或者我理解错了什么？
不，Haskell没有。 但是，共享表达式仅计算一次。 在Paul Johnson给出的例子中， x作为thunk存储在堆上。 y和z都可以引用x因为x在范围内，并且它们指向相同的位置。 一旦x必须被评估，它将被评估一次，只有评估的结果将被保留。 所以这不是真正的记忆，而是实施的结果。
是否有其他语言自动执行（即隐式的，而不是显式的）记忆？
我见过装饰者@memoized出现在一些python源代码中。 你当然可以完全为它创建自己的装饰器/实现。 完成您要使用的LRU和其他策略。
实现记忆的常用方法是什么？
没有实现记忆的真正common方式。 对于类似fib的模式（只有一个参数，这是一个数字），在fib-example中使用的memoisation可以设计出一个通用的解决方案（hashmaps），它可以工作，但它也可能对您的具体问题并不理想。
随着记忆，你有副作用，所以你可能希望缓存生活在国家monad。 但是，一般而言，您希望保持算法尽可能纯粹，所以如果它有递归，那么您已经陷入了一团糟。 这是因为你会递归地调用函数的memoised版本，但是需要在State monad中运行，所以现在你的整个函数必须在State monad中运行。 这也会影响懒惰，但你可以尝试懒惰状态monad。
牢记这一点： 良好的自动记忆是非常难以实现的。 但你可以轻松地走过很长的路。 自动记忆功能可能涉及程序转换，在固定点写东西可能会有很长的路要走。
编辑：我主要对我描述的这个问题感兴趣，即如何实现这样的限制。 任何涉及这个问题的论文都会非常好。
一旦你有了memoisation的基本机制，你可以调整查找和存储函数，为你记忆表来实现LRU或其他一些保持内存消耗小的机制。 也许你可以从这个C ++示例中获得LRU的想法。
我在评论中说，你的需求听起来像垃圾回收。 我认为这是因为你有兴趣管理一个有限的内存池，在一段时间内清除它，以便它不会结束。
现在我想到了，它更像是一个虚拟内存页面替换算法。 您可以阅读维基百科页面，了解用于解决此类问题的各种方法，例如“最近未使用”，“老化”，“时钟”，“第二次机会”等。
然而，记忆通常不会通过限制保留的结果来完成; 上述算法所需的变异通常是不变的。 不过，不要让这些让你灰心丧气。 你有一些有趣的想法，可能是Haskell在今后进行的探索memoization可能性的有价值的补充。
有时候，特定的记忆问题会使记忆有限。 例如，对齐两个基因序列可以通过动态编程（参见维基百科的动态编程＃序列比对）和二维记忆表完成。 但是由于给定单元格的DP解决方案仅取决于前一行的结果，因此可以从底部开始并丢弃距当前行超过1的行。 斐波那契数字是相同的：您只需要序列中前两个数字来计算下一个数字。 如果你感兴趣的只是第n个数字，你可以提前丢弃任何东西。
大多数记忆是为了加快存在共享子问题的递归算法。 许多这样的问题没有一种简单的方式来对评估进行排序，以便丢弃不再需要的结果。 那时，你只是猜测，使用启发式（如使用频率）来确定谁获得有限资源的访问权限。
不，Haskell不会自动记忆功能。 它所做的是商店价值，所以如果你有
x = somethingVeryLong
和你在同一范围内的其他地方
y = f x
z = g x
那么x只会被计算一次。
这个包显示了如何使用各种键和查找表来存储记忆值。 memoising通常在一个更大的函数的单个调用中使用，以便记忆值不会永远存在（正如您所说的那样会是一个问题）。 如果你想要一个使用LRU或其他东西忘记旧值的备忘录，那么我认为你可能需要将它放入状态monad或某物; 你不能像Haskell那样使用传统的记忆方法。
链接地址: http://www.djcxy.com/p/80541.html上一篇: Automatic memoizing in functional programming languages