11

在代码审查中，我回答了一个关于简单 Haskell fizzbuzz 解决方案的问题，提出了一种向前迭代的实现，避免了增加素数的二次成本并（几乎）完全丢弃模除法。这是代码：

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 没有剧透）。unfoldr但我确实对解决方案与解决方案相比的相对效率有疑问zipWith。虽然我不再是 Haskell 新手，但我也不是 Haskell 内部结构方面的专家。

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

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

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

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

注意：unfoldr的使用Maybe是我遇到的第一个潜在的性能问题，甚至在我开始调查这个问题之前（也是我完全理解的唯一一点优化/内联讨论）。所以我能够立即停止担心Maybe（鉴于 Haskell 的最新版本）。

4

1 回答 1

10

作为负责 and 的最近实现变化的人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是重写它以参与“折叠/构建”融合，这是 GHC 列表库中使用的优化框架。“折叠/构建”融合和更新的、不同平衡的“流融合”（在vector库中使用）的想法是，如果列表由“好的生产者”生成，由“好的转换器”转换，然后被消费由一个“好消费者”，那么列表 conses 根本不需要分配。oldunfoldr不是一个好的生产者，所以如果你生成一个列表并unfoldr用它来消费它，比如说，foldr列表的各个部分将在计算进行时被分配（并立即变成垃圾）。现在，unfoldr是一个很好的生产者，所以你可以写一个循环，比如说，unfoldrfilterfoldr，而不是（必然）分配任何内存。

例如，给定上面的bloob, 和一个 stern的定义{-# 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 }
    }

它没有列表，没有Maybes，也没有对；它执行的唯一分配是Int用于存储最终结果（to 的应用程序I#）ww2_s1oT。可以合理地预期整个计算将在机器寄存器中执行。

zipWith

zipWith有一个奇怪的故事。它有点笨拙地适合折叠/构建框架（我相信它在流融合方面工作得更好）。可以与它的第一个或第二个列表参数进行zipWith融合，并且多年来，列表库试图使其与其中任何一个融合，如果其中一个是一个好的生产者的话。不幸的是，使其与第二个列表参数融合可能会使程序在某些情况下的定义更少。也就是说，一个程序 usingzipWith在没有优化的情况下编译时可以正常工作，但在使用优化编译时会产生错误。这不是一个很好的情况。因此，截至base-4.8，zipWith不再尝试与它的第二个列表参数融合。如果你想让它与一个好的生产者融合，那个好的生产者最好在第一个列表参数中。

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

于 2015-09-11T14:45:13.753 回答