为什么要避免在Haskell中使用显式递归？

Question

为什么要避免在Haskell中使用显式递归？

6

我是Haskell的新手。

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

当我运行上面链接中提到的示例时，可以看到显式递归在内存方面表现更佳。起初我以为在GHCi上运行不完美，于是我尝试使用stack ghc进行编译。另外，我该如何通过stack 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

- Pawan Kumar

1

显式递归通常意味着你正在解决别人已经为你解决的问题（可能比你更正确或更有效地解决）。 - chepner

你可以将 \x -> x mod 2 == 0 改写为 even。 - Elmex80s

2个回答

6

首先，不要试图使用其他编译方式来理解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)

然而，这是非常误导人的。所有这些内存使用都不是由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)

如果您用以下方式测试 findRec 函数，使用 Ints 数组作为参数:

 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，但这也是非常误导人的。你所看到的不是递归的内存成本，而是“列表构建”的内存成本。

注意，foldr和表达式[1::Int, 3..1000000]都包括一些被称为“列表融合”的魔法。这意味着当它们一起使用时（即当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 }

因此，与其“避免递归”，是列表融合使得 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 时，尽一切可能避免思考如何“优化”你的代码。与我所知道的任何其他语言相比，你编写的代码与编译器生成的代码之间存在巨大的差距，因此现在甚至不要试图去了解它。相反，编写清晰、简单和惯用的代码。如果你现在试图学习高性能代码的“规则”，你会犯错，并学到真正糟糕的编程风格。

- K. A. Buhr

4

其实，这里有一个更好的带回家的教训。特别是当你开始学习 Haskell 时，尽一切可能避免考虑“优化”你的代码。与我所知道的任何其他语言相比，你编写的代码和编译器生成的代码之间存在巨大的鸿沟，因此现在甚至不要试图去理解它。相反，编写清晰、简单和惯用的代码。如果你现在试图学习高性能代码的“规则”，你会全都弄错，并学习到非常糟糕的编程风格。 - K. A. Buhr

1

我建议将这个评论移到答案中。评论是短暂的，而答案是永久的。 - amalloy

非常感谢您的启发。您能否推荐一些资源，其中包含这种水平的解释。 - Pawan Kumar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amalloy · Accepted Answer

你正在测量GHC在执行五十万次模数操作的速度。正如你所预料的那样，无论你如何迭代，“眨眼之间”都是答案。速度上并没有明显差异。

你声称你能看到显式递归使用更少的内存，但是你提供的堆分析数据显示相反的情况：使用显式递归时有更多的分配和更高的最大常驻内存。我不认为这种差异很显著，但如果确实存在，那么你的证据将与你的声明相矛盾。

至于避免使用显式递归的问题，目前还不清楚你读到了讨论串中的哪一部分使你得出这个结论。你链接到一个巨大的讨论串，它本身又链接到另一个巨大的讨论串，有许多相互竞争的意见。我印象最深刻的评论是这不是关于效率的问题，而是关于抽象级别的问题。通过试图衡量其性能来看待这个问题是错误的。