什么时候GHC Haskell自动记忆？ [英] When is memoization automatic in GHC Haskell?

问题描述

我无法弄清为什么m1显然被记忆，而m2不在下面：
$ b

  m1 =（（过滤奇数[1 ..]）!!）
 
 m2 n =（（filter odd [1 ..]）!! n）
  
解决方案
 GHC不记忆函数。 
 
 
但是，每次输入其周围的lambda表达式时，最多只能计算一次代码中的任何给定表达式，或者如果它处于最高级别，则最多只能计算一次。确定lambda表达式的位置可能会有点棘手，因为在你的例子中使用语法糖时，让我们将它们转换为等价的desugared语法： 
 
 
  m1'=（!!）（过滤奇数[1 ..]） - 注意：见下文！ 
 m2'= \\\
  - > （!!）（filter odd [1 ..]）n 
  
 
 
 <注意：Haskell 98报告实际上描述了左操作符部分，如（a％）等价于 \ b  - >（％）ab  ，但GHC将它解析为（％）a 。这些在技术上是不同的，因为它们可以通过 seq 来区分。 ）
 
 
 
鉴于此，您可以看到在 m1'，表达式 filter odd [1 ..] 不包含在任何lambda表达式中，所以它只会在程序的每次运行中计算一次，而在<$每输入一次lambda表达式，即在每一个表达式上都会计算c $ c> m2'，过滤器odd [1 ..] 调用 m2'。这解释了你看到的时间上的差异。
实际上，某些版本的GHC会与某些优化选项共享比以上描述更多的值表示。在某些情况下，这可能会有问题。例如，考虑函数 
 
 
  f = \ x  - >让y = [1..30000000] in foldl'（+）0（y ++ [x]）
  
 GHC可能会注意到 y 不依赖于 x 并将函数重写为
  f = let y = [1..30000000] in \x  - > foldl'（+）0（y ++ [x]）
  
在这种情况下，效率要低得多，因为它必须从存储 y 的内存中读取大约1 GB的内存，而原始版本将在恒定空间中运行并适合处理器的缓存。事实上，在GHC 6.12.1下，编译没有使用优化时，函数 f 几乎是使用<$ c $编译时的两倍c> -O2 。
 
I can't figure out why m1 is apparently memoized while m2 is not in the following:
m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)
m1 10000000 takes about 1.5 seconds on the first call, and a fraction of that on subsequent calls (presumably it caches the list), whereas m2 10000000 always takes the same amount of time (rebuilding the list with each call). Any idea what's going on? Are there any rules of thumb as to if and when GHC will memoize a function? Thanks.
解决方案
GHC does not memoize functions.

It does, however, compute any given expression in the code at most once per time that its surrounding lambda-expression is entered, or at most once ever if it is at top level.  Determining where the lambda-expressions are can be a little tricky when you use syntactic sugar like in your example, so let's convert these to equivalent desugared syntax:
m1' = (!!) (filter odd [1..])              -- NB: See below!
m2' = \n -> (!!) (filter odd [1..]) n
(Note: The Haskell 98 report actually describes a left operator section like (a %) as equivalent to \b -> (%) a b, but GHC desugars it to (%) a.  These are technically different because they can be distinguished by seq.  I think I might have submitted a GHC Trac ticket about this.)

Given this, you can see that in m1', the expression filter odd [1..] is not contained in any lambda-expression, so it will only be computed once per run of your program, while in m2', filter odd [1..] will be computed each time the lambda-expression is entered, i.e., on each call of m2'.  That explains the difference in timing you are seeing.



Actually, some versions of GHC, with certain optimization options, will share more values than the above description indicates.  This can be problematic in some situations.  For example, consider the function
f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x])
GHC might notice that y does not depend on x and rewrite the function to
f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x])
In this case, the new version is much less efficient because it will have to read about 1 GB from memory where y is stored, while the original version would run in constant space and fit in the processor's cache.  In fact, under GHC 6.12.1, the function f is almost twice as fast when compiled without optimizations than it is compiled with -O2.

                        
这篇关于什么时候GHC Haskell自动记忆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！