這不是雙遍歷嗎？

Question

在「編程技巧」的haskell wiki的部分，我發現這個例子：

count :: (a -> Bool) -> [a] -> Int 
count p = length . filter p 

據說這是

count :: (a -> Bool) -> [a] -> Int 
count _ [] = 0 
count p (x:xs) 
    | p x  = 1 + count p xs 
    | otherwise =  count p xs 

一個更好的選擇哪家，在可讀性方面，我完全同意。

但是，是不是一個雙遍歷，因此實際上比顯式遞歸函數更糟？ GHC中的懶惰是否意味着這相當於優化之後的單次遍歷？哪個實施更快，爲什麼？

Answer 1

所以，看看有什麼優化實際上呢，讓我們look at the core：

% ghc -O2 -ddump-simpl Temp.hs 
[1 of 1] Compiling Temp    (Temp.hs, Temp.o) 

==================== Tidy Core ==================== 
Result size of Tidy Core = {terms: 29, types: 26, coercions: 0} 

Temp.count 
    :: forall a_arN. 
    (a_arN -> GHC.Types.Bool) -> [a_arN] -> GHC.Types.Int 
[GblId, 
Arity=2, 
Caf=NoCafRefs, 
Str=DmdType <L,C(U)><S,1*U>, 
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True, 
     ConLike=True, WorkFree=True, Expandable=True, 
     Guidance=IF_ARGS [60 0] 191 0}] 
Temp.count = 
    \ (@ a_aMA) 
    (p_arV :: a_aMA -> GHC.Types.Bool) 
    (eta_B1 :: [a_aMA]) -> 
    letrec { 
     go_aNr [Occ=LoopBreaker] 
     :: [a_aMA] -> GHC.Prim.Int# -> GHC.Types.Int 
     [LclId, Arity=1, Str=DmdType <S,1*U>] 
     go_aNr = 
     \ (ds_aNs :: [a_aMA]) -> 
      case ds_aNs of _ [Occ=Dead] { 
      [] -> GHC.Types.I#; 
      : y_aNx ys_aNy -> 
       case p_arV y_aNx of _ [Occ=Dead] { 
       GHC.Types.False -> go_aNr ys_aNy; 
       GHC.Types.True -> 
        let { 
        g_a10B [Dmd=<L,C(U)>] :: GHC.Prim.Int# -> GHC.Types.Int 
        [LclId, Str=DmdType] 
        g_a10B = go_aNr ys_aNy } in 
        \ (x_a10C :: GHC.Prim.Int#) -> g_a10B (GHC.Prim.+# x_a10C 1) 
       } 
      }; } in 
    go_aNr eta_B1 0 

清潔它一點：

Temp.count :: forall aType. (aType -> Bool) -> [aType] -> Int 
Temp.count = \(@ aType) (p :: aType -> Bool) (as :: [aType]) -> 
    letrec { 
    go :: [aType] -> GHC.Prim.Int# -> Int 
    go = \(xs :: [aType]) -> 
     case xs of _ { 
     [] -> I#; -- constructor to make a GHC.Prim.Int# into an Int 
     : y ys -> 
      case p y of _ { 
      False -> go ys; 
      True -> 
       let { 
       go' :: GHC.Prim.Int# -> Int 
       go' = go ys 
       } in \(x :: GHC.Prim.Int#) -> go' (GHC.Prim.+# x 1) 
      } 
     }; 
    } in go as 0 

由於我們在拆箱類型GHC.Prim.Int#，all the additions are strict操作，所以我們只有一個循環的數據。

Answer 2

無論哪種方式，你必須執行一個或兩個操作每個項目。必要的是檢查謂詞。第二個加1取決於謂詞的結果。

因此，如果您不考慮緩存等的影響，這兩種情況都會生成相同數量的操作。

我們得到的圖像是在第一種情況下有兩個獨立的遍歷，一個是收集元素，一個是對它們進行計數。如果列表大於緩存可處理的列表，則會減慢處理速度。這實際上發生在嚴格的語言中。

但是哈斯克爾的懶惰在這裏出現了。由filter生成的列表被逐元素地評估（出現），因爲計數功能length需要它。然後，因爲length僅將它們用於計數並且不保留對新創建列表的引用，所以元素立即可以被垃圾收集。所以在任何時候，在計算過程中只有O(1)的內存被佔用。

在第一個版本中構造最終的「過濾」列表會有一點點開銷。但與列表較大時的緩存效果相比，這通常可以忽略不計。 （對於小列表可能很重要;這需要測試。）此外，根據編譯器和選擇的優化級別，它可能會被優化。

更新。第二個版本實際上會消耗內存，正如在其中一個評論中指出的那樣。爲了公平的比較，你需要在正確的地方用積累參數和嚴格註釋器來編寫它，因爲（我預計）length已經這樣寫。

Answer 3

您可以測試版本與profiling速度更快，例如：

module Main where 


main :: IO() 
main = print countme' 

count' :: (a -> Bool) -> [a] -> Int 
count' p = length . filter p 

count :: (a -> Bool) -> [a] -> Int 
count _ [] = 0 
count p (x:xs) 
    | p x  = 1 + count p xs 
    | otherwise =  count p xs 


list = [0..93823249] 

countme' = count' (\x -> x `mod` 15 == 0) list 
countme = count (\x -> x `mod` 15 == 0) list 

然後運行ghc -O2 -prof -fprof-auto -rtsopts Main.hs和./Main +RTS -p。它將產生文件Main.prof。然後將主要功能改爲使用countme代替並比較結果。我的是：

• 4.12s的隱含版本
• 6。34s

如果關閉優化，那麼隱式的仍然稍微（但不是很快）。

除了已經被其他人解釋過的融合和懶惰之外，我想另一個原因可能是length和filter是Prelude函數，並且可以被編譯器更好地優化。