unfoldr 与 zipWith 的效率

Question

在 Code Review 上，我回答了一个关于 naive Haskell fizzbuzz solution by suggesting an implementation that iterates forward 的问题，避免了增加素数的二次成本并（几乎）完全放弃模除法。这是代码：

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 版本是对这段代码的明显、简单的修改，所以我不打算在这里输入它，除非寻求回答我的问题的人坚持认为这很重要（没有剧透 OP 在 Code Review 上）。但我确实对 unfoldr 解决方案与 zipWith 解决方案的相对效率有疑问。虽然我不再是 Haskell 新手，但我不是 Haskell 内部结构方面的专家。

unfoldr 解决方案不需要 [start..] 无限列表，因为它可以简单地从 start 展开。我的想法是

zipWith 解决方案不会按照要求记忆 [start..] 的每个连续元素。每个元素都被使用和丢弃，因为没有保留对 [start..] 头部的引用。所以那里消耗的内存并不比 unfoldr.
对 unfoldr 的性能的担忧以及使它始终内联的最新补丁是在我尚未达到的水平上进行的。

所以我认为两者在内存消耗上是相当的，但不知道相对性能。希望更多消息灵通的 Haskell 读者可以指导我理解这一点。

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

注意：unfoldr 使用 Maybe 是我遇到的第一个潜在性能问题，甚至在我开始调查该问题之前（以及 optimisation/inlining 讨论中我完全理解的唯一部分）。所以我可以立即停止担心 Maybe（鉴于 Haskell 的最新版本）。

Answer 1

作为最近对 zipWith 和 unfoldr 的实现进行更改的负责人，我想我应该尝试一下。我真的不能那么容易地比较它们，因为它们的功能非常不同，但我可以尝试解释它们的一些特性和变化的意义。

`unfoldr`

内联

旧版本的unfoldr（在base-4.8/GHC 7.10之前）是在顶层递归的（它直接调用自己）。 GHC 从不内联递归函数，因此 unfoldr 从未被内联。结果，GHC 看不到它是如何与传递给它的函数交互的。最麻烦的影响是传入的 (b -> Maybe (a, b)) 类型的函数实际上会产生 Maybe (a, b) 值，分配内存来保存 Just 和 (,) 构造函数。通过将 unfoldr 重组为 "worker" 和 "wrapper"，新代码允许 GHC 将其内联并（在许多情况下）将其与传入的函数融合，因此多余的构造函数被剥离通过编译器优化。

例如在GHC 7.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 的另一个变化是重写它以参与 "fold/build" 融合，这是 GHC 列表库中使用的优化框架。 "fold/build" 融合和较新的、不同平衡的 "stream fusion"（在 vector 库中使用）的想法是，如果列表由 "good producer" 生成，则转换为"good transformers"，并被 "good consumer" 消耗，那么实际上根本不需要分配列表 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，也没有对；它执行的唯一分配是用于存储最终结果的 Int（I# 到 ww2_s1oT 的应用）。可以合理地预期整个计算将在机器寄存器中执行。

`zipWith`

zipWith 有个奇怪的故事。它有点笨拙地适合 fold/build 框架（我相信它与流融合一起工作得更好）。可以使 zipWith 与其第一个或第二个列表参数融合，多年来，列表库试图使其与其中任何一个融合，如果其中一个是好的生产者。不幸的是，在某些情况下，让它与其第二个列表参数融合可能会使程序定义较少。也就是说，使用 zipWith 的程序在未经优化编译时可以正常运行，但在经过优化编译时会产生错误。这不是一个好情况。因此，从 base-4.8 开始，zipWith 不再尝试与其第二个列表参数融合。如果你想让它融合一个好的生产者，那个好的生产者最好在第一个列表参数中。

具体来说，zipWith 的参考实现导致期望 zipWith (+) [1,2,3] (1 : 2 : 3 : undefined) 会给出 [2,4,6]，因为它一到达第一个结尾就停止列表。对于之前的 zipWith 实施，如果第二个列表看起来像那样但是是由一个好的制作人制作的，并且如果 zipWith 碰巧与它而不是第一个列表融合，那么它就会繁荣。

unfoldr 与 zipWith 的效率

Efficiency of unfoldr versus zipWith

performance

haskell

functional-programming

unfold

`unfoldr`

内联

融合

`zipWith`