评估策略

Question

在Haskell中的以下示例中，应该如何解释函数求值：

let f x = ...
    x = ...
in map (g (f x)) xs

在GHC中，有时(f x)只评估一次，有时对xs中的每个元素评估一次。这取决于f和g究竟是什么。当CCD_ 5是一个昂贵的计算时，这可能是重要的。它刚刚绊倒了我正在帮助的一个Haskell初学者，除了这取决于编译器之外，我不知道该告诉他什么。还有更好的故事吗？

更新

在以下示例中，(f x)将被评估4次：

let f x = trace "!" $ zip x x
    x = "abc"
in map (i -> lookup i (f x)) "abcd" 

Answer 1

使用语言扩展，我们可以创建f x必须重复评估的情况：

{-# LANGUAGE GADTs, Rank2Types #-}
module MultiEvG where
data BI where
    B :: (Bounded b, Integral b) => b -> BI
foo :: [BI] -> [Integer]
foo xs = let f :: (Integral c, Bounded c) => c -> c
             f x = maxBound - x
             g :: (forall a. (Integral a, Bounded a) => a) -> BI -> Integer
             g m (B y) = toInteger (m + y)
             x :: (Integral i) => i
             x = 3
         in map (g (f x)) xs

关键是要使f x多态，即使作为g的自变量，我们也必须创造一种无法预测所需类型的情况（我的第一次尝试使用了Either a b而不是BI，但在优化时，当然最多只能对f x进行两次评估）。

多态性表达式的每种类型都必须至少评估一次。这就是单态性限制的原因之一。然而，当需要它的类型范围受到限制时，可以记住每个类型的值，在某些情况下，GHC会这样做（需要优化，我希望涉及的类型数量不能太多）。在这里，我们面对的基本上是一个非均匀列表，因此在每次调用g (f x)时，它可能是满足约束的任意类型所需要的，因此，计算不能在map之外进行（从技术上讲，编译器仍然可以在每个使用的类型上建立一个值的缓存，因此每个类型只对其进行一次评估，但GHC没有，很可能不值得麻烦）。

• 同态表达式只需要计算一次，就可以共享。它们是否由实施决定；就纯粹性而言，它不会改变程序的语义。如果表达式绑定到一个名称，那么在实践中，您可以依赖于它的共享，因为这很容易，而且显然是程序员想要的。如果它没有绑定到一个名称，那就是一个优化问题。有了字节码生成器或没有优化，表达式通常会被重复求值，但有了优化，重复求值将表明存在编译器错误
• 对于每个使用的类型，必须至少对多态表达式求值一次，但通过优化，当GHC可以看到它可以在同一类型中多次使用时，在更大的计算过程中，它（通常）仍然会为该类型共享

一句话：始终使用优化进行编译，通过将您想要共享的表达式绑定到一个名称来帮助编译器，并在可能的情况下提供单态类型签名。

Answer 2

您的示例确实大不相同。

在第一个示例中，要映射的参数是g (f x)，并且很可能作为部分应用的函数传递给map一次。如果g (f x)在应用于map中的一个参数时评估其第一个参数，则只执行一次，然后使用结果更新thunk（f x）。

因此，在您的第一个示例中，f x将被评估最多1次。

第二个例子需要进行更深入的分析，然后编译器才能得出（f x）在lambda表达式中始终是常量的结论。也许它永远不会优化它，因为它可能知道trace不太符合kosher。因此，在跟踪时，这可能会评估4次，在不跟踪时评估4次或1次。

Answer 3

正如您所知，这实际上取决于GHC的优化。

最好的事情是研究优化程序后得到的GHC核心。我将查看生成的Core，并检查f x是否在map之外有自己的let语句。

如果你想确定，那么你应该将f x因子分解到let中分配的自己的变量中，但除了阅读Core之外，没有真正有保证的方法来计算它。

尽管如此，除了像trace这样使用unsafePerformIO的东西之外，这永远不会改变程序的语义：它的实际行为。

Answer 4

在没有优化的GHC中，每次调用函数时都会评估函数体。（"调用"表示将函数应用于参数并计算结果。）在以下示例中，f x位于函数内部，因此每次调用函数时都会执行。（GHC可以优化这个表达式，如FAQ[1]中所讨论的。）

let f x = trace "!" $ zip x x
    x = "abc"
in map (i -> lookup i (f x)) "abcd" 

但是，如果我们将f x移出函数，它将只执行一次。

let f x = trace "!" $ zip x x
    x = "abc"
in map ((f_x i -> lookup i f_x) (f x)) "abcd" 

这可以更容易地重写为

let f x = trace "!" $ zip x x
    x = "abc"
    g f_x i = lookup i f_x
in map (g (f x)) "abcd" 

一般规则是，每次将函数应用于参数时，都会创建函数体的新"副本"。函数应用程序是唯一可能导致表达式重新执行的程序。但是，请注意，有些函数和函数调用在语法上与函数不同。

[1]http://www.haskell.org/haskellwiki/GHC/FAQ#Subexpression_Elimination