optimization - 在Haskell中优化部分计算

我很好奇如何优化此代码:

fun n = (sum l, f $ f0 l, g $ g0 l)
  where l = map h [1..n]

假设f，f0，g，g0和h都很昂贵，但是l的创建和存储非常昂贵。

如所写，l一直存储，直到对返回的元组进行完全求值或垃圾回收为止。而是应在执行任何一个时都执行length l，f0 l和g0 l，但是应该延迟f和g。

看来此行为可以通过以下方式解决:

fun n = a `seq` b `seq` c `seq` (a, f b, g c)
  where
    l = map h [1..n]
    a = sum l
    b = inline f0 $ l
    c = inline g0 $ l

或非常相似:

fun n = (a,b,c) `deepSeq` (a, f b, g c)
  where ...

我们也许可以指定一些内部类型来实现相同的效果，这看起来很痛苦。还有其他选择吗？

另外，我显然希望inline能够使编译器将sum，f0和g0融合到一个循环中，该循环逐项构造和使用l。我可以通过手动内联将其明确显示出来，但这太糟了。有没有办法明确阻止列表l的创建和/或强制内联？如果内联或融合在编译过程中失败，会产生警告或错误的语用？

顺便说一句，我很好奇为什么在Prelude中seq都将inline，lazy，let x = x in x等都定义为。这是否只是为它们提供了供编译器覆盖的定义？

最佳答案

如果您想确定的话，唯一的办法就是自己动手做。对于任何给定的编译器版本，您都可以尝试几种源格式，并检查生成的core/assembly/llvm字节码/是否满足您的要求。但这可能会因每个新的编译器版本而中断。

如果你写

fun n = a `seq` b `seq` c `seq` (a, f b, g c)
  where
    l = map h [1..n]
    a = sum l
    b = inline f0 $ l
    c = inline g0 $ l

或其deepseq版本，编译器也许能够合并a，b和c的计算，以便在单次遍历l时并行执行(而不是在并发意义上)，但就目前而言，我宁愿坚信GHC不会，如果JHC或UHC做到了，我会感到惊讶。为此，计算b和c的结构必须足够简单。

跨编译器和编译器版本移植获得所需结果的唯一方法是自己完成。至少在接下来的几年中。

根据f0和g0的不同，它可能很简单，例如使用适当的累加器类型和组合函数进行严格的左折，就像著名的平均值

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Double

average :: [Double] -> Double
average = ratio . foldl' count (P 0 0)
  where
    ratio (P n s) = s / fromIntegral n
    count (P n s) x = P (n+1) (s+x)

但是如果f0和/或g0的结构不合适，比如说一个左折，另一个折右，则可能无法一次遍历。在这种情况下，选择是在重新创建l和存储l之间。通过显式共享(l)可以很容易地存储where l = map h [1..n]，但是如果编译器执行了一些常见的子表达式消除操作，则很难重新创建它(不幸的是，即使GHC很少执行CSE，它也倾向于共享该形式的列表) )。对于GHC，标志fno-cse和-fno-full-laziness可以帮助避免不必要的共享。