3

私は Haskell のリストについて考えていましたが、他の言語では、すべてにリストを使用するわけではないと考えました。確かに、後で値が必要な場合はリストを保存したいかもしれませんが、それが 1 回限りの場合、たとえば から反復する[1..n]場合、実際に必要なのはインクリメントされる変数だけであるリストを使用する必要はありません。

また、「リストの融合」について読んだところ、Haskell コンパイラはこの最適化を実装して中間リストを排除しようとしますが、しばしば失敗し、ガベージ コレクターが 1 回しか使用されないリストをクリーンアップする必要があることに気付きました。

また、注意を怠ると、リストを簡単に共有できます。つまり、ガベージ コレクターがリストをクリーンアップしないため、以前は定数空間で実行するように設計されていたアルゴリズムでメモリが不足する可能性があります。

したがって、少なくともリストを実際に「保存」したくない場合は、リストを完全に避けるのが最善だと思いました。

その後、次のようconduitに書かれている に出会いました。

ストリーミング データの問題を解決し、コンスタント メモリ内のデータ ストリームの生成、変換、および消費を可能にします。

これは完璧に聞こえました。リソースの取得と解放の問題conduitのために設計されていることは知っていますが、リストの代わりにドロップインとして使用できますか?IO

たとえば、次のことができますか。

fold f3 $ take 10 $ map f2 $ unfold f1 init_value

そして、適切に配置されたいくつかの型注釈を使用して、リストの代わりにプロセス全体にコンジットを使用しますか?

おそらくそのclassy-preludeようなコードが許可されることを望んでいましたが、よくわかりません。可能であれば、誰かが上記のように例を挙げてもらえますか?

4

2 に答える 2

8

リストの計算は、 の場合と同じ状況で一定のメモリにストリームされconduitます。中間データ構造の有無は、定数メモリで実行されるかどうかには影響しません。変更されるのは、それが存在する定数メモリの効率とサイズだけです。

コンジットが同等のリスト計算よりも少ないメモリで実行されるとは思わないでください。コンジット ステップはリスト セルよりもオーバーヘッドが大きいため、実際にはより多くのメモリを使用する必要があります。また、現在、コンジットにはストリーム フュージョンがありません。それはライブラリに組み込まれませんでしたが、誰かが少し前にそれを実験しました。一方、リストは多くの状況で融合して、中間データ構造を削除できます。

覚えておくべき重要なことは、ストリーミングは必ずしも森林破壊 (つまり、中間データ構造の除去) を意味するわけではないということです。

于 2013-01-15T04:13:36.770 に答える
4

conduitは、この種のユースケース向けに設計されたものではありませんが、理論的にはそのように使用できます。リストを直接処理するよりもmarkdown、追加の配管を使用する方が便利なパッケージで個人的にそうしました。conduit

これを と組み合わせるとclassy-prelude-conduit、比較的単純なコードが得られます。そして、classy-prelude-conduit にさらにエクスポートを追加して、このユース ケースをより適切に最適化できます。今のところ、上で説明した内容の基本的な要点に沿った例を次に示します。

{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE OverloadedStrings #-}
import ClassyPrelude.Conduit
import Data.Conduit.List (unfold, isolate)
import Data.Functor.Identity (runIdentity)

main = putStrLn
     $ runIdentity
     $ unfold f1 init_value
    $$ map f2
    =$ isolate 10
    =$ fold f3 ""

f1 :: (Int, Int) -> Maybe (Int, (Int, Int))
f1 (x, y) = Just (x, (y, x + y))

init_value = (1, 1)

f2 :: Int -> Text
f2 = show

f3 :: Text -> Text -> Text
f3 x y = x ++ y ++ "\n"
于 2013-01-15T04:18:01.063 に答える