这不是双向遍历吗？

Question

在 haskell wiki 的 "programming tips" 部分，我找到了这个例子：

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

无论哪种方式，您都必须对每个项目执行一到两个操作。必要的一项是对谓词的检查。第二个加1取决于谓词的结果。

因此，如果不考虑缓存等的影响，两种情况都会产生相同数量的操作。

得到的图片是第一种情况下有两个单独的遍历，一个收集元素，一个计算元素。给定一个大于缓存可以处理的列表，这将减慢处理速度。这实际上发生在 strict 语言中。

然而 Haskell 的懒惰在这里出现了。由 filter 生成的列表是逐个元素评估（存在）的，因为计数函数 length 需要它。然后，由于 length 仅将它们用于计数而不保留对新创建列表的引用，因此这些元素会立即被释放以进行垃圾回收。所以任何时候，在计算过程中都只有O(1)个内存占用。

在第一个版本中构建结果 "filtered" 列表的开销很小。但与列表很大时出现的缓存效果相比，这通常可以忽略不计。（对于小列表，这可能很重要；这需要测试。）此外，它可能会根据编译器和选择的优化级别进行优化。

Update. 第二个版本实际上会消耗内存，正如其中一条评论所指出的那样。为了公平比较，您需要在正确的地方用累积参数和严格性注释器来编写它，因为（我希望）length 已经这样写了。

Answer 2

您可以使用 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。然后将 main 函数改为使用 countme 并比较结果。我的是：

4.12s 为隐式版本
6.34s 显式版本

如果您关闭优化，那么隐式优化仍然稍快（但不多）。

除了其他人已经解释过的融合和惰性之外，我想另一个原因可能是 length 和 filter 是 Prelude 函数，可以被编译器更好地优化。

Answer 3

为了了解优化器实际做了什么，让我们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，所以我们只有一个循环遍历数据。

这不是双向遍历吗？

Isn't this a double traversal?

haskell

functional-programming

traversal