13

私は Haskell がとても好きですが、スペース リークが少し気になります。私は通常、Haskell の型システムが C++ よりも安全だと考えていますが、C スタイルのループを使用すると、メモリ不足にならずに完了できると確信できますが、Haskell の「フォールド」は注意しない限りメモリ不足になる可能性があります。適切なフィールドは厳密です。

Haskell 型システムを使用して、サンクを構築しない方法でさまざまな構成をコンパイルおよび実行できるようにするライブラリがあるかどうか疑問に思っていました。たとえば、no_thunk_foldサンクを構築できる方法で使用すると、コンパイラ エラーがスローされます。これが私ができることを制限する可能性があることは理解していますが、オプションとして使用できるいくつかの機能が必要ですスペースの。

4

2 に答える 2

10

遅延評価のマイナス面が気になるようですね。折り畳み、ループ、再帰が定数メモリで処理されるようにする必要があります。

iteratee ライブラリは、この問題を 解決 する ために作成 されました 。

最も人気があり、最近のものは パイプと コンジットです。どちらも iteratee モデルを超えています。

パイプライブラリは、 バグを排除し、設計の一貫性が効率的でありながら高いレベルの抽象化を可能にするために、理論的に健全であることを重視しています (私の言葉は著者ではありません)。また、必要に応じて双方向ストリームも提供します。これは、これまでライブラリに固有の利点です。

コンジットは、 パイプほど理論的には確立されていませんが、現在、http ストリーム、xml ストリームなどを解析および処理するために、より多くの関連ライブラリが構築されているという大きな利点があります。パッケージページのハックインでコンジットセクションをチェックしてください。Haskellの大規模でよく知られている Web フレームワークの 1 つとして使用され ています。

パイプ ライブラリ、特にプロキシ トランスフォーマー スタックを作成する機能を使用して、ストリーミング アプリケーションを作成することを楽しんでいます。Web ページを取得したり、いくつかの xml を解析したりする必要があるときは、コンジット ライブラリを使用しています。

また、最初の公式リリースを行ったばかりの io-streamsについても言及する必要があり ます。その目的は特に IO であり、その名前にあるのは当然のことであり、より単純な型の機械、より少ない型パラメーター、そして パイプまたは コンジットを利用しています。主なマイナス面は、IO モナドで立ち往生しているため、純粋なコードにはあまり役に立たないことです。

{-# language NoMonoMorphismRestriction #-}                                       
import Control.Proxy

簡単な翻訳から始めます。

map (+1) [1..10]

になります：

runProxy $ mapD (+1) <-< fromListS [1..10]

iteratee like は、単純な翻訳のためにもう少し冗長な提供を提供しますが、より大きな例で大きな利益をもたらします。

定数空間でフィボナッチ数を生成するプロキシ、パイプ ライブラリの例

fibsP = runIdentityK $ (\a -> do respond 1                                       
                                 respond 1                                       
                                 go 1 1)                                         
  where                                                                          
    go fm2 fm1 = do  -- fm2, fm1 represents fib(n-2) and fib(n-1)                                                            
        let fn = fm2 + fm1                                                       
        respond fn -- sends fn downstream                                                              
        go fm1 fn

これらは、runProxy $ fibsP >-> printD を使用して stdout にストリーミングできます -- printD はダウンストリームの値のみを出力します。プロキシはパイプ パッケージの双方向のオファーです。

プロキシ チュートリアルとコンジット チュートリアルをチェックしてください。私が見つけたばかりの FP Complete の Haskell の学校にあります。

平均を見つける 1 つの方法は次のとおりです。

> ((_,l),s) <- (`runStateT` 0) $ (`runStateT` 0) $ runProxy $  foldlD' ( flip $ const (+1)) <-< raiseK (foldlD' (+)) <-< fromListS [1..10::Int]
> let m = (fromIntegral . getSum) s / (fromIntegral . getSum) l
5.5

これで、マップの追加やプロキシのフィルタリングが簡単になりました。

> ((_,l),s) <- (`runStateT` 0) $ (`runStateT` 0) $ runProxy $  foldlD' ( flip $ const (+1)) <-< raiseK (foldlD' (+)) <-< filterD even <-< fromListS [1..10::Int]

編集: 状態モナドを利用するために書き直されたコード。

アップデート：

コンパス可能な方法で大量のデータ ストリームに対して複数の計算を実行し、直接再帰を記述する方法については、ブログ記事の美しい折りたたみで説明されています。フォールドはデータに変換され、厳密なアキュムレータを使用して結合されます。私はこの方法を定期的に使用したことはありませんが、厳密さが必要な場所を分離して適用しやすくしているようです。また、Applicative を使用して同じメソッドを実装し、好みによっては読みやすい別の質問の同様の質問への回答も参照する必要があります。

于 2013-03-13T01:30:51.700 に答える
7

Haskell の型システムではそれができません。これは、完全にポリモーフィックな項を使用して、任意の量の RAM を食べることで証明できます。

takeArbitraryRAM :: Integer -> a -> a
takeArbitraryRAM i a = last $ go i a where
  go n x | n < 0 = [x]
  go n x | otherwise = x:go (n-1) x

やりたいことを行うには、下位構造型が必要です。線形論理は、ラムダ計算の効率的に計算可能なフラグメントに対応します (ただし、再帰も制御する必要があります)。構造公理を追加すると、超指数関数的な時間を取ることができます。

Haskell では、インデックス モナドを使用して一部のリソースを管理する目的で線形型を偽造できます。残念ながら、空間と時間は言語に組み込まれているため、それを行うことはできません。コメントで提案されていることを実行し、Haskell DSL を使用してパフォーマンスの限界があるコードを生成することはできますが、この DSL の計算用語は任意の時間がかかり、任意のスペースを使用する可能性があります。

スペースリークの心配はありません。それらをキャッチします。プロフィール。複雑さの限界を証明するコードの理由。使用している言語に関係なく、これを行う必要があります。

于 2013-03-13T08:35:40.627 に答える