为什么要避免 Haskell 中的显式递归？

Question

我是 Haskell 的新手。

在研究 foldr 时，许多人建议使用它并避免可能导致内存效率低下代码的显式递归。 https://www.reddit.com/r/haskell/comments/1nb80j/proper_use_of_recursion_in_haskell/

因为我是运行上面提到的样本link。我可以看到显式递归在内存方面做得更好。首先我认为可能是 GHCi 上的运行不接近完美基准，我尝试使用 stack ghc 编译它。顺便说一句，我如何通过堆栈 ghc 传递编译器优化标志。我从表达式 避免显式递归 .

中遗漏了什么

find p = foldr go Nothing
    where go x rest = if p x then Just x else rest

findRec :: (a -> Bool) -> [a] -> Maybe a
findRec _ [] = Nothing
findRec p (x:xs) = if p x then Just x else (findRec p xs)

main :: IO ()
main = print $ find (\x -> x `mod` 2 == 0) [1, 3..1000000] 
main = print $ findRec (\x -> x `mod` 2 == 0) [1, 3..1000000] 

-- find
Nothing
      92,081,224 bytes allocated in the heap
           9,392 bytes copied during GC
          58,848 bytes maximum residency (2 sample(s))
          26,704 bytes maximum slop
               0 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0        87 colls,     0 par    0.000s   0.000s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.000s   0.001s     0.0004s    0.0008s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.031s  (  0.043s elapsed)
  GC      time    0.000s  (  0.001s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.031s  (  0.044s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    2,946,599,168 bytes per MUT second

  Productivity 100.0% of total user, 96.8% of total elapsed

-- findRec
Nothing
      76,048,432 bytes allocated in the heap
          13,768 bytes copied during GC
          42,928 bytes maximum residency (2 sample(s))
          26,704 bytes maximum slop
               0 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0        71 colls,     0 par    0.000s   0.000s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.000s   0.001s     0.0004s    0.0007s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.031s  (  0.038s elapsed)
  GC      time    0.000s  (  0.001s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.031s  (  0.039s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    2,433,549,824 bytes per MUT second

  Productivity 100.0% of total user, 96.6% of total elapsed

Answer 1

您正在测量 GHC 进行 50 万次模运算的速度。如您所料，无论您如何迭代，"in the blink of an eye" 都是答案。速度没有明显区别

您声称您可以看到显式递归使用的内存更少，但您提供的堆分析数据显示相反的情况：使用显式递归时分配更多，最大驻留更高。我认为差异不大，但如果存在差异，那么您的证据将与您的主张相矛盾。

至于为什么要避免显式递归的问题，您并不清楚您是在阅读该线程的哪一部分后得出结论的。你链接到一个巨大的线程，它本身链接到另一个巨大的线程，有许多不同的意见。对我来说最突出的评论是 it's not about efficiency, it's about levels of abstraction。您试图通过衡量其性能来看待它的方式是错误的。

Answer 2

首先，不要尝试使用优化编译以外的任何方法来了解 GHC 编译代码的性能：

$ stack ghc -- -O2 Find.hs
$ ./Find +RTS -s

使用 -O2 标志（和 GHC 版本 8.6.4），您的 find 执行如下：

      16,051,544 bytes allocated in the heap
          14,184 bytes copied during GC
          44,576 bytes maximum residency (2 sample(s))
          29,152 bytes maximum slop
               0 MB total memory in use (0 MB lost due to fragmentation)

然而，这是非常具有误导性的。 None 的内存使用是由于 foldr 执行的循环。相反，这都是由于使用了盒装 Integers。如果您切换到使用编译器可以拆箱的普通 Ints：

main = print $ find (\x -> x `mod` 2 == 0) [1::Int, 3..1000000]
                                             ^^^^^

内存性能发生巨大变化，展示了 foldr:

的真实内存成本

      51,544 bytes allocated in the heap
       3,480 bytes copied during GC
      44,576 bytes maximum residency (1 sample(s))
      25,056 bytes maximum slop
           0 MB total memory in use (0 MB lost due to fragmentation)

如果你像这样用 Ints 测试 findRec：

 main = print $ findRec (\x -> x `mod` 2 == 0) [1::Int, 3..1000000]

你会看到更差的内存性能：

  40,051,528 bytes allocated in the heap
      14,992 bytes copied during GC
      44,576 bytes maximum residency (2 sample(s))
      29,152 bytes maximum slop
           0 MB total memory in use (0 MB lost due to fragmentation)

这似乎是一个令人信服的案例，即应优先避免递归而不是 foldr，但这也非常具有误导性。您在这里看到的是不是递归的内存成本，而是 "list building".

的内存成本

看，foldr 和表达式 [1::Int, 3..1000000] 都包含一些叫做 "list fusion" 的魔法。这意味着当它们一起使用时（即，当 foldr 应用于 [1::Int 3..1000000] 时），可以执行优化以完全消除创建 Haskell 列表。至关重要的是，foldr 代码，即使使用列表融合，也会编译成如下所示的递归代码：

main_go
  = \ x ->
      case gtInteger# x lim of {
        __DEFAULT ->
          case eqInteger# (modInteger x lvl) lvl1 of {
            __DEFAULT -> main_go (plusInteger x lvl);
                      -- ^^^^^^^ - SEE?  IT'S JUST RECURSION
            1# -> Just x
          };
        1# -> Nothing
      }
end Rec }

因此，是列表融合而不是 "avoiding recursion" 使 find 比 findRec 更快。

您可以通过考虑以下的性能来证明这是真的：

find1 :: Int -> Maybe Int
find1 n | n >= 1000000 = Nothing
        | n `mod` 2 == 0 = Just n
        | otherwise = find1 (n+2)

main :: IO ()
main = print $ find1 1

即使这使用递归，它也不会生成列表（或使用盒装 Integers），因此它的运行方式与 foldr 版本一样：

      51,544 bytes allocated in the heap
       3,480 bytes copied during GC
      44,576 bytes maximum residency (1 sample(s))
      25,056 bytes maximum slop
           0 MB total memory in use (0 MB lost due to fragmentation)

那么，带回家的课程是什么？

始终使用 ghc -O2 对 Haskell 代码进行基准测试，从不使用没有优化标志的 GHCi 或 ghc。
任何 Reddit 帖子中只有不到 10% 的人知道他们在说什么。
foldr 有时可以在应用列表融合等特殊优化时比显式递归执行得更好。
但在一般情况下，显式递归的性能与 foldr 或其他专门构造一样好。
此外，优化 Haskell 代码很难。

实际上，这是一个更好（更严肃）的带回家的课程。尤其是当您开始使用 Haskell 时，尽一切努力避免考虑 "optimizing" 您的代码。与我所知道的任何其他语言相比，您编写的代码与编译器生成的代码之间存在着巨大的鸿沟，所以现在甚至不要试图弄清楚。相反，编写清晰、直接和惯用的代码。如果您现在尝试学习 "rules" 以获得高性能代码，您将把它们全都弄错，并且学习非常糟糕的编程风格。

为什么要避免 Haskell 中的显式递归？

Why to avoid Explicit recursion in Haskell?

recursion

haskell

fold