列表为什么列表和导航不一样？ （哈斯克尔）

Question

考虑以下基准：

module Main where 

import qualified Data.List as L 
import qualified Data.Vector.Unboxed as U 
import Criterion.Main 



goodSum :: Int -> Double 
{-# NOINLINE goodSum #-} 
goodSum n = 
    let ints = U.enumFromN 0 (n * n * 10) :: U.Vector Int 
    in U.foldl' (+) 0 $ U.map fromIntegral ints 

badSum :: Int -> Double 
{-# NOINLINE badSum #-} 
badSum n = L.foldl' (+) 0.5 [fromIntegral i | i <- [0 .. 10*n*n]] 

badSum2 :: Int -> Double 
{-# NOINLINE badSum2 #-} 
badSum2 n = L.foldr (+) 0.5 [fromIntegral i | i <- [0 .. 10*n*n]] 

worstSum :: Int -> Double 
{-# NOINLINE worstSum #-} 
worstSum n = L.foldl1' (+) $ do 
    i <- [0 .. n*n] 
    return $ L.foldl1' (+) $ do 
    k <- [0 .. 10] 
    return $ fromIntegral $ k + i 

main = do 
    defaultMain 
    [ bench "good" $ nf goodSum 500 
    , bench "bad" $ nf badSum 500 
    , bench "bad2" $ nf badSum2 500 
    , bench "worst" $ nf worstSum 500 
    ] 

结果：

benchmarking good 
time     1.826 ms (1.819 ms .. 1.835 ms) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     1.810 ms (1.803 ms .. 1.817 ms) 
std dev    23.18 μs (19.91 μs .. 27.96 μs) 

benchmarking bad 
time     38.38 ms (38.07 ms .. 38.74 ms) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     38.23 ms (38.07 ms .. 38.38 ms) 
std dev    298.5 μs (220.6 μs .. 417.8 μs) 

benchmarking bad2 
time     77.87 ms (73.74 ms .. 82.67 ms) 
        0.992 R² (0.976 R² .. 0.998 R²) 
mean     78.14 ms (75.33 ms .. 82.13 ms) 
std dev    5.184 ms (3.056 ms .. 7.966 ms) 
variance introduced by outliers: 19% (moderately inflated) 

benchmarking worst 
time     80.80 ms (79.53 ms .. 82.10 ms) 
        1.000 R² (0.999 R² .. 1.000 R²) 
mean     80.73 ms (80.29 ms .. 81.19 ms) 
std dev    756.9 μs (591.9 μs .. 938.2 μs) 

列表理解为good producers and foldr is a good consumer，那么为什么没有列出导火索？

Answer 1

与你的问题相反，foldr和列表修真了，其实 保险丝。但是，您必须记得foldr的定义，而不是它的尾部递归函数 。前奏定义foldr as，这不会将 编译成像Vector示例那样的紧密循环。芯的用于badSum2产生

foldr k z = go 
    where 
    go []  = z 
    go (y:ys) = y `k` go ys 

最重要的一点是这样的

$wgo_s8AH [Occ=LoopBreaker] :: Int# -> Double# 
$wgo_s8AH = 
    \ (w_s8AD :: Int#) -> 
    case tagToEnum# 
      @ Bool (==# w_s8AD y1_a69V) 
    of _ [Occ=Dead] { 
     False -> 
     case $wgo_s8AH (+# w_s8AD 1) of ww_s8AG { __DEFAULT -> 
     +## (int2Double# w_s8AD) ww_s8AG 
     }; 
     True -> +## (int2Double# w_s8AD) 0.5 

这大致相当于该功能（模装箱算术）

badSum3 :: Int -> Double 
badSum3 n = go 0 
    where 
    stop = 10 * n * n 

    go i | i == stop = fromIntegral i + 0.5 
     | otherwise = fromIntegral i + go (i + 1) 

通过标准运行此，这功能提供与 badSum2相同的运行时间。虽然生成的函数不生成和消耗中间cons单元，但它仍在执行函数调用并执行所有关联的堆栈操作。

基于foldl'版本的糟糕表现归因于foldl'不是一个好消费者的事实，所以它不能与列表理解融合。左边的折叠会产生一个尾递归循环，它遍历列表理解产生的列表，引发所有分配和相关内存操作的开销。

我不知道你是否能得到相同的性能与使用标准列表操作Vector操作，但stream-fusion包装使用不同的融合方法，它可以实现对这个问题类似的性能提供了列表组合程序。

import qualified Data.List.Stream as S 

-- The stream-fusion package does not seem to have `enumFrom` functions 
enumerate :: Int -> [Int] 
enumerate n = S.unfoldr f 0 
    where 
    f i | i > n  = Nothing 
     | otherwise = Just (i, i + 1) 

goodSum2 :: Int -> Double 
goodSum2 n = S.foldl' (+) 0.5 $ S.map fromIntegral $ enumerate (n * n * 10)