unfoldr的效率与zipWith相比如何？

Question

在Code Review上，我回答了一个关于naive Haskell fizzbuzz solution的问题，并建议一种向前迭代的实现方式，避免了逐渐增加的质数数量带来的二次成本和几乎完全丢弃模除操作。以下是代码：

fizz :: Int -> String
fizz = const "fizz"

buzz :: Int -> String
buzz = const "buzz"

fizzbuzz :: Int -> String
fizzbuzz = const "fizzbuzz"

fizzbuzzFuncs =  cycle [show, show, fizz, show, buzz, fizz, show, show, fizz, buzz, show, fizz, show, show, fizzbuzz]

toFizzBuzz :: Int -> Int -> [String]
toFizzBuzz start count =
    let offsetFuncs = drop (mod (start - 1) 15) fizzbuzzFuncs
    in take count $ zipWith ($) offsetFuncs [start..]

作为进一步的提示，我建议使用 Data.List.unfoldr 重写它。 使用 unfoldr 的版本是对该代码的明显简单修改，因此除非在 Code Review 上的 OP 坚持认为这很重要（不要给 OP 打雷），否则我不会在此处输入它。 但是，我对比较 unfoldr 解决方案与 zipWith 解决方案的相对效率有疑问。 虽然我不再是 Haskell 新手，但我对 Haskell 内部并不是很了解。 unfoldr 解决方案不需要 [start..] 无限列表，因为它可以直接从 start 展开。 我的想法是:

1. zipWith 解决方案不会缓存每个连续的元素 [start..]，因为没有保留对 [start..] 头部的引用，所以每个元素都会被使用和丢弃。 因此，在那里消耗的内存与 unfoldr 相同。
2. 关于 unfoldr 的性能问题以及最近进行的始终内联的补丁是在我尚未达到的层面上进行的。

因此，我认为这两种方法在内存消耗方面是等价的，但对于相对性能却没有任何想法。希望更了解Haskell的人能指导我理解这个问题。

unfoldr 似乎是生成序列的自然选择，即使其他解决方案更具表现力。我只知道我需要更多地了解它的实际性能。（出于某种原因，我发现 foldr 更容易理解其性能）

注意：unfoldr 使用 Maybe 是我在开始研究这个问题之前首先考虑到的潜在性能问题（也是我完全理解的优化/内联讨论的唯一部分）。因此，我能够立即停止担心 Maybe（使用 Haskell 的最新版本）。

- itsbruce

---

你应该澄清一下，所说的成本是指增加质数数量的成本。 - dfeuer

@dfeuer 已完成。再次感谢您的回答。 - itsbruce

Answer 1

作为最近修改zipWith和unfoldr实现的负责人，我觉得我应该尝试一下解释一下。虽然它们是非常不同的函数，但我可以尝试解释一些它们的属性和变化的意义。

unfoldr

内联化（Inlining）

unfoldr的旧版本（在base-4.8/GHC7.10之前）在顶层使用递归调用自身。 GHC从不对递归函数进行内联优化，因此unfoldr从未被内联。结果，GHC无法看到它与传入的函数如何交互。其中最令人困扰的影响是传入的函数类型为(b -> Maybe (a, b))，实际上会产生Maybe(a, b)值，并分配内存以保存Just和(,)构造函数。通过将unfoldr重构为“worker”和“wrapper”，新代码允许GHC内联它并（在许多情况下）将其与传入的函数融合在一起，因此编译器优化会剥离额外的构造函数。

例如，在GHC7.10下，以下代码：

module Blob where
import Data.List

bloob :: Int -> [Int]
bloob k = unfoldr go 0 where
  go n | n == k    = Nothing
       | otherwise = Just (n * 2, n+1)

使用ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures编译后，会得到核心代码

$wbloob :: Int# -> [Int]
$wbloob =
  \ (ww_sYv :: Int#) ->
    letrec {
      $wgo_sYr :: Int# -> [Int]
      $wgo_sYr =
        \ (ww1_sYp :: Int#) ->
          case tagToEnum# (==# ww1_sYp ww_sYv) of _ {
            False -> : (I# (*# ww1_sYp 2)) ($wgo_sYr (+# ww1_sYp 1));
            True -> []
          }; } in
    $wgo_sYr 0

bloob :: Int -> [Int]
bloob =
  \ (w_sYs :: Int) ->
    case w_sYs of _ { I# ww1_sYv -> $wbloob ww1_sYv }

融合

unfoldr 的另一个变化是重写它以参与 GHC 列表库中使用的“fold/build”融合优化框架。 “fold/build” 融合和较新的、不同平衡的“流融合”（用于 vector 库）的思想是，如果列表由“好生成器”产生，经过“好转换器”转换，并被“好消费者”消耗，则列表 conses 实际上根本不需要被分配。旧版本的 unfoldr 不是一个好的生成器，因此如果您使用 unfoldr 生成一个列表，并使用 foldr 进行消耗，列表的各个部分将被分配（并立即成为垃圾），随着计算的进行。现在，unfoldr 成为了一个好的生成器。因此，您可以编写一个循环，使用 unfoldr、filter 和 foldr，而不必（必须）分配任何内存。

例如，给定上面的 bloob 定义和严格的 {-# INLINE bloob #-} （这些东西有点脆弱；好的生成器有时需要显式地内联才能成为好的生成器），则下面的代码：

hooby :: Int -> Int
hooby = sum . bloob

编译成GHC核心

$whooby :: Int# -> Int#
$whooby =
  \ (ww_s1oP :: Int#) ->
    letrec {
      $wgo_s1oL :: Int# -> Int# -> Int#
      $wgo_s1oL =
        \ (ww1_s1oC :: Int#) (ww2_s1oG :: Int#) ->
          case tagToEnum# (==# ww1_s1oC ww_s1oP) of _ {
            False -> $wgo_s1oL (+# ww1_s1oC 1) (+# ww2_s1oG (*# ww1_s1oC 2));
            True -> ww2_s1oG
          }; } in
    $wgo_s1oL 0 0

hooby :: Int -> Int
hooby =
  \ (w_s1oM :: Int) ->
    case w_s1oM of _ { I# ww1_s1oP ->
    case $whooby ww1_s1oP of ww2_s1oT { __DEFAULT -> I# ww2_s1oT }
    }

这段代码没有列表、Maybe类型和二元组，它唯一进行的分配是用于存储最终结果（应用I#到ww2_s1oT）的Int型变量。整个计算可以合理地预期在机器寄存器中执行。

zipWith

zipWith 有一个有点奇怪的故事。它在fold/build框架中有些尴尬（我相信它与流融合更加契合）。zipWith 可以使它的第一个或第二个列表参数与之融合，并且多年来，列表库试图使其与其中一个融合，如果任意一个是好的生产者。不幸的是，在某些情况下，使它与第二个列表参数融合可能会使程序变得不明确。也就是说，在没有优化编译的情况下使用 zipWith 的程序可以正常工作，但在进行了优化编译后可能会出现错误。这不是一个很好的情况。因此，从base-4.8开始，zipWith 不再尝试与其第二个列表参数融合。如果您希望它与好的生产者融合，则该好的生产者最好在第一个列表参数中。

具体来说，zipWith 的参考实现导致期望例如 zipWith (+) [1,2,3] (1 : 2 : 3 : undefined) 将会返回 [2,4,6]，因为它会在第一个列表结束后立即停止。对于以前的zipWith 实现，如果第二个列表看起来像那样，但是它是由好的生产者生成的，并且如果zipWith 巧合地与其融合而不是第一个列表，则程序将崩溃。

- dfeuer

---

非常感谢。我一开始就看到了可能的问题，但是还不够了解从第一原理推理出其余部分。现在又更接近一步了;-) - itsbruce