3

次の例は、次の問題を示していますData.Sequence。

{-# LANGUAGE BangPatterns #-}
module Main where

import qualified Data.Sequence as S
import Data.Sequence ((|>), ViewL(..))
import Data.List (foldl')
import GHC.AssertNF

update !init !x = init |> x

main =
   do let !seq = foldl' update S.empty [1..10]
      assertNF seq

印刷します

Parameter not in normal form: 1 thunks found:
Deep (One (S# 1)) (_thunk (Deep (One ...) (_thunk ... ... ... ...) (Three ... ... ...) 93) (S# 95) (S# 96) (S# 97)) (Three (S# 98) (S# 99) (S# 100)) 100

ただし、ドキュメントにはData.Sequenceすべての操作が厳密であると記載されているため、挿入後にツリーが完全に評価されないのはなぜですか？いくつかの複雑さの限界を保証する必要がありますか？

ここでの怠惰はあまり好きではないので|>、後部への追加と前部からの列挙をサポートする、より厳密な、または同様のデータ構造があるのではないかと思います。

4

2 に答える 2

13

Data.Sequenceは、要素が厳密で、桁が厳密なデータ構造であり、背骨が怠惰です。

data FingerTree a
    = Empty
    | Single a
    | Deep {-# UNPACK #-} !Int !(Digit a) (FingerTree (Node a)) !(Digit a)

これは、挿入された値が評価されて保存されることを意味しますが、構造のスパインはクエリでのみ評価されます。それはあなたが望むものであることがよくあります-より小さなデータ構造。

背骨を厳密に固定したい場合は、挿入コストが高くなりますが、どこか別の場所で得られる可能性があります。

背骨が厳密になるようにfingertreesパッケージを変更してみて、実際に高速かどうかを確認してください。結果を知りたいと思います。

余談ですが、「ここでは怠惰はあまり好きではありません」というのは、背骨の怠惰なデータ構造を避ける良い理由ではありません。[a]がスパイン厳密である場合、それはひどいデータ型になります。Data.Sequenceについても同じことが言えます。スパインの厳密さがユースケースにとって間違ったセマンティクスである理由を定量化する必要があります。

于 2013-02-08T11:04:43.187 に答える
11

フィンガーツリーの優れたパフォーマンスは、怠惰に依存します。ヒンズー、ラルフから引用するには; Paterson、Ross（2006）、「Finger Trees：A Simple General-Purpose DataStructure」：

...構造は怠惰を本質的に利用していますが、遅延評価プリミティブを提供する厳密な言語にも適しています。

そしてその特性を分析するとき：

...したがって、一連の操作では、平均コストは一定です。

遅延評価を使用してサブツリーが一時停止されている場合、同じ境界が永続的な設定に保持されます。これにより、後続の操作がそこまで下がる必要があるまで、脊椎の深部での変換が行われないことが保証されます。安全で危険な数字の上記の特性のために、その時までに、この高価な評価の代償を払うのに十分な安価な浅い操作が実行されているでしょう。

したがって、実装をレイジーからストリクトに変更すると、（使用する操作と順序によっては）時間計算量の限界が失われる可能性があります。

于 2013-02-08T12:54:38.007 に答える