使用`let`可以提高性能？

Question

比较以下两个片段：

expensiveFunction :: [Integer] -> [Integer -> Bool]
expensiveFunction [] = [const False]
expensiveFunction (x:xs) =
  let temp = expensiveFunction xs
  in [someOtherFunction y | y <- temp] ++ temp

和

expensiveFunction :: [Integer] -> [[Integer]]
expensiveFunction [] = [const False]
expensiveFunction (x:xs) =
  [someOtherFunction y | y <- expensiveFunction xs] ++ expensiveFunction xs

第一个代码片段似乎更高效：每次递归调用只调用

expensiveFunction

一次，将结果存储在局部变量

temp

中，然后使用该变量两次。但是，也可能

temp

仅充当

expensiveFunction xs

的简写形式，因此每次使用

temp

实际上都算作对

expensiveFunction

的调用。

我的问题：第一个片段是否只调用

expensiveFunction

一次？更一般地说：在

let

表达式中定义的局部变量的行为是否像在其他编程范例中（例如在 C++ 中）一样？也就是说，它们是否存储其定义表达式的值？或者它们只是其定义表达式的简写？

Answer 1

第一个代码片段似乎更高效：每次递归调用只调用

expensiveFunction

一次，将结果存储在局部变量 temp 中，然后使用该变量两次。但是， temp 也可能仅充当

expensiveFunction xs

的简写。

主要思想是：

只要你说出名字，就可以分享。

所以这意味着我们制作了一个工作“节点”

temp

，它本身并没有立即评估。但是，如果

temp

的某些使用需要评估节点（部分），则使用

temp

的其他部分将从已完成的工作中受益。

如果您因此调用

expensiveFunction [1,4]

，它将生成如下计算图：

+-------+
| (++)  |
+-------+
| o | o |
+-|-+-|-+
  |   '----------.
  v              |
+-------------+  |
| <list-comp> |  |
+-------------+  |
|      o      |  |
+------|------+  |
       v         v
     +-------------------+
     | expensiveFunction |<--- temp
     +-------------------+
     |         o         |
     +---------|---------+
               |
               v
           +-------+
           |  [4]  |
           +-------+

但是因此引用一个“承诺”在需要时调用

expensiveFunction

上的

[4]

的节点。例如，当我们有兴趣显示结果时，它首先需要评估列表理解，因此这将强制评估

expensiveFunction [4]

。它将替换节点，例如用

[5]

（如果这是

expensiveFunction [4]

的结果），这意味着图形将如下所示：

+-------+
| (++)  |
+-------+
| o | o |
+-|-+-|-+
  |   '----------.
  v              |
+-------------+  |
| <list-comp> |  |
+-------------+  |
|      o      |  |
+------|------+  |
       v         v
     +-------------------+
     |         [5]       |<--- temp
     +-------------------+

如果我们需要

(++)

的第二部分，它将不再执行

expensiveFunction

，而是直接使用

[5]

。

let 表达式中定义的局部变量的行为与其他编程范例（例如 C++）中的行为一样吗？

不完全不，这并不意味着首先定义

let

部分，也不意味着函数将被完全求值。事实上，我们可以相互定义两个变量，例如：

oneTwo :: [Int]
oneTwo = let { x = (1:y); y = (2:x)} in x

这将生成一个重复

1

和

2

的无限列表。该图将如下所示：

+-------+
|  (:)  |
+---+---+
| o | o |<---.
+-|-+-|-+    |
  v   |      |
  0   |      |
      v      |
  +-------+  |
  |  (:)  |  |
  +---+---+  |
  | o | o |  |
  +-|-+-|-+  |
    v   '----'
    1

因此列表本身由两个相互引用的节点组成。如果某个函数枚举它，它每次都会在第一个 (

x

) 和第二个 (

y

) 节点之间移动“光标”。

也就是说，它们是否存储定义表达式的值？或者它们只是其定义表达式的简写？

它们都不是，它们不存储值，它们本质上存储一个“承诺”，以便在必要时对其进行评估，并且由于两者都链接到相同的承诺，因此第一次评估承诺时完成的工作，然后由其他人使用与该承诺相关的项目。