unfoldr対zipの効率

Question

naive Haskell fizzbuzz solutionに関する質問には、iterates forwardという実装を提案し、増加する素数の二次コストを避け、モジュロ除算を（ほぼ）完全に破棄しました。私はそれがData.List.unfoldrを使用して書き換え提案し、さらにプロンプ​​トとして

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..] 

：ここでは、コードです。 unfoldrバージョンはこのコードの明白で簡単な変更であるため、私の質問に答えたい人が重要であると主張しない限り、ここには入力しません（コードレビューでOP overのスポイラーはありません）。しかし、私はzipWithと比較して、unfoldrソリューションの相対的効率について質問があります。私はもはやハスケルの新生児ではありませんが、私はハスケルの内部についての専門家ではありません。

unfoldrソリューションは、startから簡単に展開できるので、[start..]の無限リストは必要ありません。私の考えでは、それがために頼まれるようzipWithソリューションは[start..]の連続する各要素をmemoizeしない

1. です。 [start ..]の先頭への参照が保持されていないため、各要素が使用されて破棄されます。したがって、メモリが消費されているのはunfoldrです。
2. unfoldrのパフォーマンスとそれが常にインライン化されるようにするための最近のパッチについての懸念は、まだ達成していないレベルで行われています。

私はメモリ消費量は同じですが、相対的な性能については考えていないと思います。より多くの情報を得たHaskellersが私にこれを理解させるように指示することができます。

unfoldrは、他の解決策がより表現力豊かであっても、シーケンスを生成するのに自然なようです。私は実際のパフォーマンスについてもっと理解する必要があることを知っています。

注意（何らかの理由で、私はそのレベルで理解する方がはるかに簡単にfoldrを見つける。）：Maybeのunfoldrの使用は、私も問題を調査開始前に、私に起こった最初の潜在的なパフォーマンスの問題でした（と私が完全に理解している最適化/インライン化の議論のビットのみ）。だから私はすぐにMaybeの心配を止めることができました（最近のバージョンのHaskellを参照）。

Answer 1

zipWithとunfoldrの実装の最近の変更を担当している人物として、私はおそらくこれで刺すべきだと思っていました。彼らは非常に異なった機能を持っているので、私は実際にそれらを簡単に比較することはできませんが、私はそのプロパティのいくつかとその変更の意義を説明しようとすることができます。 （base-4.8/GHC 7.10前に）トップレベルの再帰た

unfoldr

unfoldrの古いバージョンを

インライン化（​​それが直接自分自身と呼ばれます）。 GHCは再帰関数をインライン化しないので、unfoldrは決してインライン化されませんでした。その結果、GHCは、それが渡された関数とどのように相互作用したかを見ることができませんでした。これが最も厄介なのは、型が(b -> Maybe (a, b))の関数が実際にMaybe (a, b)の値を生成し、Justと(,)のコンストラクタを保持するためのメモリを割り当てることでした。 unfoldrを "ワーカー"と "ラッパー"として再構成することにより、新しいコードはGHCにインライン化させ（多くの場合）渡された関数と融合させるので、コンパイラの最適化によって余分なコンストラクタが取り除かれます。例えば、GHC 7.10の下で、ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signaturesとコンパイルされたコード

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) 

はunfoldrに

$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 } 

融合

他の変化が参加するためにそれを書き換えたコアに

リードGHCのリストライブラリで使用されている最適化フレームワークである "fold/build" fusion。 「折りたたみ/構築」融合とより新しい、バランスのとれた「ストリーム融合」（vectorライブラリで使用されている）の両方の考え方は、リストが「良い生産者」によって生産され、「良い変圧器」によって変換され、 "良い消費者"によって消費された場合、リストconsesは決して実際に割り当てられる必要はありません。 unfoldrはで、だったので、unfoldrのリストを作成して、たとえばfoldrでそれを消費した場合、リストの断片は計算が進むにつれて割り当てられ（すぐにガベージになります）さて、unfoldrは良いプロデューサーなので、例えばunfoldr,filter、およびfoldrを使ってループを書くことができますし、必ずしもすべてのメモリーを割り当てる必要はありません。

例えば、bloobの上記の定義、及び船尾{-# INLINE bloob #-}（このようなものは少し脆弱であり、優れた生産者は時々良好であると明示的にインライン化される必要がある）が与えられると、コード

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

はにコンパイルGHCコアないリスト、無Maybe S、無対を有していない

$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 } 
    } 

。それが実行する唯一の割り当ては、最終結果（I#〜ww2_s1oTのアプリケーション）を格納するために使用されるIntです。計算全体がマシンレジスタで実行されることが合理的に期待できます。

zipWith

zipWith奇妙な物語のビットを持っています。それはfold/buildフレームワークにちょっと厄介なものがあります（私はストリーム融合でかなりうまくいくと思います）。 zipWithを最初のリスト引数またはその2番目のリスト引数と融合させることができます。また、長年にわたり、どちらかが良いプロデューサだった場合、リストライブラリはどちらかと融合するように試みました。残念なことに、それを第2のリスト引数と融合させることにより、特定の状況下ではのプログラムがあまり定義されなくなる可能性があります。つまり、を使用するプログラムは、最適化せずにコンパイルするとうまく動作しますが、最適化してコンパイルするとエラーが発生します。これは大きな状況ではありません。したがって、base-4.8の時点では、zipWithはもう2番目のリスト引数との融合を試みません。それを良いプロデューサーと融合させたいのであれば、良いプロデューサーは最初のリストの議論のほうがよいでしょう。

具体的には、zipWithのリファレンス実装では、zipWith (+) [1,2,3] (1 : 2 : 3 : undefined)が[2,4,6]と表示されることが期待されます。これは、最初のリストの最後にヒットするとすぐに停止するためです。前のzipWithの実装では、2番目のリストがそのように見えたが、良いプロデューサによって生成され、zipWithが最初のリストではなく融合した場合、それはブームになります。