任何函数式语言编译器/运行时是否会在适用时将所有链式迭代减少为一个？从程序员的角度来看，我们可以使用惰性和流等结构来优化功能代码，但我有兴趣了解故事的另一面。我的功能示例是用 Scala 编写的，但请不要将您的答案局限于该语言。
功能方式：
// I assume the following line of code will go
// through the collection 3 times, one for creating it
// one for filtering it and one for summing it
val sum = (1L to 1000000L).filter(_ % 2 == 0).sum // => 250000500000
我希望编译器优化为以下命令式等价物：
/* One iteration only */
long sum, i;
for (i = 1L, sum = 0L; i <= 1000000L; i++) {
if (i % 2 == 0)
sum += i;
}
Haskell 根据定义是一种非严格语言，我知道的所有实现都使用惰性求值来提供非严格语义。
类似的代码（带有开始和结束的参数，所以编译时评估是不可能的）
val :: Int -> Int -> Int
val low high = sum $ filter even [low .. high]
仅通过一次遍历计算总和，并且在恒定的小内存中。[low .. high]是 for 的语法糖，for的enumFromTo low high定义基本上是enumFromToInt
enumFromTo x y
| y < x = []
| otherwise = go x
where
go k = k : if k == y then [] else go (k+1)
（实际上，GHC 的实现使用 unboxedInt#是为了提高 worker 的效率go，但这对语义没有影响；对于其他Integral类型，定义类似）。
的定义filter是
filter :: (a -> Bool) -> [a] -> [a]
filter _pred [] = []
filter pred (x:xs)
| pred x = x : filter pred xs
| otherwise = filter pred xs
和sum：
sum l = sum' l 0
where
sum' [] a = a
sum' (x:xs) a = sum' xs (a+x)
组装起来，即使没有任何优化，评估也会继续进行
sum' (filter even (enumFromTo 1 6)) 0
-- Now it must be determined whether the first argument of sum' is [] or not
-- For that, the application of filter must be evaluated
-- For that, enumFromTo must be evaluated
~> sum' (filter even (1 : go 2)) 0
-- Now filter knows which equation to use, unfortunately, `even 1` is False
~> sum' (filter even (go 2)) 0
~> sum' (filter even (2 : go 3)) 0
-- 2 is even, so
~> sum' (2 : filter even (go 3)) 0
~> sum' (filter even (go 3)) (0+2)
-- Once again, sum asks whether filter is done or not, so filter demands another value or []
-- from go
~> sum' (filter even (3 : go 4)) 2
~> sum' (filter even (go 4)) 2
~> sum' (filter even (4 : go 5)) 2
~> sum' (4 : filter even (go 5)) 2
~> sum' (filter even (go 5)) (2+4)
~> sum' (filter even (5 : go 6)) 6
~> sum' (filter even (go 6)) 6
~> sum' (filter even (6 : [])) 6
~> sum' (6 : filter even []) 6
~> sum' (filter even []) (6+6)
~> sum' [] 12
~> 12
这当然比循环效率低，因为对于枚举的每个元素，都必须生成一个列表单元格，然后对于每个通过过滤器的元素，必须生成一个列表单元格，然后立即被总和消耗.
让我们检查一下内存使用量确实很小：
module Main (main) where
import System.Environment (getArgs)
main :: IO ()
main = do
args <- getArgs
let (low, high) = case args of
(a:b:_) -> (read a, read b)
_ -> error "Want two args"
print $ sum $ filter even [low :: Int .. high]
并运行它，
$ ./sumEvens +RTS -s -RTS 1 1000000
250000500000
40,071,856 bytes allocated in the heap
12,504 bytes copied during GC
44,416 bytes maximum residency (2 sample(s))
21,120 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 75 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.00s 0.00s 0.0002s 0.0003s
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 6.1% (7.6% elapsed)
Alloc rate 4,367,976,530 bytes per MUT second
Productivity 91.8% of total user, 115.8% of total elapsed
它为 50 万个列表单元(1)分配了大约 40MB，并进行了一些更改，但最大驻留量约为 44KB。以 1000 万的上限运行它，总体分配（和运行时间）增长了 10 倍（减去常量），但最大驻留时间保持不变。
(1) GHC 将枚举和过滤器融合在一起，只产生类型为 的范围内的偶数Int。不幸的是，它不能融合sum，因为那是一个左折叠，而 GHC 的融合框架只融合右折叠。
现在，为了融合sum，必须做很多工作来教 GHC 用重写规则来做到这一点。幸运的是，包中的许多算法已经这样做了vector，如果我们使用它，
module Main where
import qualified Data.Vector.Unboxed as U
import System.Environment (getArgs)
val :: Int -> Int -> Int
val low high = U.sum . U.filter even $ U.enumFromN low (high - low + 1)
main :: IO ()
main = do
args <- getArgs
let (low, high) = case args of
(a:b:_) -> (read a, read b)
_ -> error "Want two args"
print $ val low high
我们得到了一个更快的程序，它甚至不再分配任何列表单元，管道实际上被重写为循环：
$ ./sumFilter +RTS -s -RTS 1 10000000
25000005000000
72,640 bytes allocated in the heap
3,512 bytes copied during GC
44,416 bytes maximum residency (1 sample(s))
17,024 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 0 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.01s elapsed)
%GC time 1.0% (1.2% elapsed)
Alloc rate 7,361,805 bytes per MUT second
Productivity 97.7% of total user, 111.5% of total elapsed
这是 GHC 为 (the worker of) 生产的核心val，如果有人感兴趣的话：
Rec {
Main.main_$s$wfoldlM'_loop [Occ=LoopBreaker]
:: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=3, Caf=NoCafRefs, Str=DmdType LLL]
Main.main_$s$wfoldlM'_loop =
\ (sc_s303 :: GHC.Prim.Int#)
(sc1_s304 :: GHC.Prim.Int#)
(sc2_s305 :: GHC.Prim.Int#) ->
case GHC.Prim.># sc1_s304 0 of _ {
GHC.Types.False -> sc_s303;
GHC.Types.True ->
case GHC.Prim.remInt# sc2_s305 2 of _ {
__DEFAULT ->
Main.main_$s$wfoldlM'_loop
sc_s303 (GHC.Prim.-# sc1_s304 1) (GHC.Prim.+# sc2_s305 1);
0 ->
Main.main_$s$wfoldlM'_loop
(GHC.Prim.+# sc_s303 sc2_s305)
(GHC.Prim.-# sc1_s304 1)
(GHC.Prim.+# sc2_s305 1)
}
}
end Rec }
理论上，正如一位评论者所写，编译器可以在编译时将其简化为结果。使用某些宏可以做到这一点并非不可想象，但在一般情况下不太可能。
如果你插入一个.view调用，你会在 Scala 中获得惰性语义，因此只会执行一次迭代，尽管它不像你的命令式代码那么简单：
val lz = (1L to 1000000L).view.filter(_ % 2 == 0) // SeqView (lazy)!
lz.sum
PS你的假设是错误的，否则会有三个迭代。(1L to 1000000L)创建一个NumericRange不涉及对元素进行任何迭代的 a。因此，这可以为.view您节省一次迭代。
几年前，我发布了两篇关于这个主题的博客文章：
http://jnordenberg.blogspot.de/2010/03/scala-stream-fusion-and-specialization.html http://jnordenberg.blogspot.de/2010/05/scala-stream-fusion-and-specialization.html
请注意，Scala 编译器完成的专业化和优化从那时起已经有了很大的改进（可能在 Hotspot 中也是如此），所以今天的结果可能会更好。