评估策略

Question

如何在Haskell中的以下示例中对函数求值进行推理:

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

在GHC,有时(f x)是对各元素只计算一次,有时一次xs,这取决于究竟f和g是.当f x计算成本昂贵时,这可能很重要.它刚刚绊倒了我正在帮助的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

你的例子确实完全不同.

在第一个示例中,map的参数是g (f x)并且被传递一次,map最有可能是部分应用的函数.如果g (f x),当应用于参数中map评价其第一个参数,那么这将是一次完成,然后在thunk(FX)将与结果进行更新.

因此,在您的第一个示例中,最多f x将评估一次.

您的第二个示例需要进行更深入的分析,然后编译器才能得出结论:(fx)在lambda表达式中始终是常量.也许它永远不会优化它,因为它可能知道痕迹不是很合理.因此,这可以在跟踪时评估4次,在不跟踪时评估4次或1次.

Answer 3

这实际上取决于GHC的优化,正如您所知道的那样.

在最好做的事情就是研究GHC核心,你优化程序后得到的.我会查看生成的Core并检查是否f x有自己的let声明map.

如果你想确定,那么你应该f x将其分解为自己在a中分配的变量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