Haskell中函数调用的优化 [英] Optimization of Function Calls in Haskell

问题描述

不确定这个问题到底是什么，所以我会直接把它发布到SO：

1. Haskell中的变量是不可变的


2. 纯函数对于相同的参数应该得到相同的值
   




从这两点来看，推断如果你在你的代码中调用 somePureFunc somevar1 somevar2 两次，在第一次调用期间计算该值才有意义。结果值可以存储在某种巨大的哈希表（或类似的东西）中，并在以后对该函数的调用中查找。我有两个问题：





1. GHC是否真的实现了这种优化？
   
2. ，在重复计算比查找结果更便宜的情况下，行为是什么？



谢谢。 GHC不会自动执行 nofollow noreferrer>记事本。请参阅常见子表达式排除中的GHC常见问题（不完全相同的事情，但我的猜测是，推理是一样的）和答案这个问题。





如果你想自己做记忆，那么看看 Data.MemoCombinators 。





查看记忆的另一种方式是使用懒惰来利用记忆。例如，您可以根据自身定义一个列表。下面的定义是所有斐波那契数字的无限列表（摘自 Haskell Wiki ）

  fibs = 0：1：zipWith（+）fibs（尾纤）
  

由于列表是懒惰地实现的，它与预先计算（记忆）的先前值相似。例如 fibs !! 10 将创建前10个元素，使得 fibs 11 快得多。




Not sure what exactly to google for this question, so I'll post it directly to SO:

1. Variables in Haskell are immutable
2. Pure functions should result in same values for same arguments

From these two points it's possible to deduce that if you call somePureFunc somevar1 somevar2 in your code twice, it only makes sense to compute the value during the first call. The resulting value can be stored in some sort of a giant hash table (or something like that) and looked up during subsequent calls to the function. I have two questions:

1. Does GHC actually do this kind of optimization?
2. If it does, what is the behaviour in the case when it's actually cheaper to repeat the computation than to look up the results?

Thanks.

解决方案

GHC doesn't do automatic memoization. See the GHC FAQ on Common Subexpression Elimination (not exactly the same thing, but my guess is that the reasoning is the same) and the answer to this question.

If you want to do memoization yourself, then have a look at Data.MemoCombinators.

Another way of looking at memoization is to use laziness to take advantage of memoization. For example, you can define a list in terms of itself. The definition below is an infinite list of all the Fibonacci numbers (taken from the Haskell Wiki)

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Because the list is realized lazily it's similar to having precomputed (memoized) previous values. e.g. fibs !! 10 will create the first ten elements such that fibs 11 is much faster.

这篇关于Haskell中函数调用的优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！