画像へのレンダリングを効率的に実装する純粋に機能的なデータ構造とは何ですか？

Question

画像とピクセルレンダリングがハスケルの最後のものの1つ私は効率的な十分に機能的なデータ構造を選ぶことができませんでした。簡潔にするため、1Dの画像については、n-d画像に簡単に拡張できるので、話をしてください。これは私が見つけたCPUレンダリングのための最もパフォーマンスの高いデザインです

-- An 1D image is an unboxed vector of Pixels 
type Position = Int 
data Image = Image { size :: Position, buffer :: UV.Vector Pixel } 

-- A sprite is a recipe to draw something to an Image 
newtype Sprite = Sprite (forall s . 
    -> (Position -> Pixel -> ST s()) -- setPixel 
    -> ST s())      -- ST action that renders to Image 

-- Things that can be rendered to screen provide a sprite 
class Renderable a where 
    getSprite a :: a -> Sprite 

-- `render` applies all sprites, mutably, in sequence. `O(P)` (where P = pixels to draw) 
render :: [Sprite] -> Image -> Image 
render draws (Image size buffer) = Image size $ runST $ do ... 

、まだそれはかなり醜いです：私は、レンダリングのための表現とその可変ビューとして、非ボックス化ベクトルを使用しています。 renderを実装する純粋に機能的な構造の場合、明らかな答えは、マップを使用して画像を表現し、(Position, Pixel)ペアのリストを使用してスプライトを表すことです。以下のようなもの：O(P * log(N))ある

-- 1D for simplicity 
type Position = Int 

-- An image is a map from positions to colors 
type Image = Map Position Pixel 

-- A sprite is, too, a map from positions to colors 
type Sprite = [(Position, Pixel)] 

-- Rendering is just inserting each pixel in sequence 
-- (Not tested.) 
render :: [Sprite] -> Image -> Image 
render sprites image = foldr renderSprite image sprites 
    where renderSprite sprite image = foldr (uncurry insert) image sprites 

（P =レンダリングする画素、N画像のサイズ=）。 log(N)は回避できないと思われるかもしれませんが、慎重に参照すると、Imageを通して同じパスを移動しています（つまり、位置0に挿入してから位置1に挿入すると、そして、すべての道を上にして、隣りの葉に至るまで）。それは正確に同じパターンのように見えるzippersは、漸進性を改善することができ、私には疑いをもたらすrenderを改善することができます。 O(P*log N)よりも、renderを実装することができる純粋に機能的なデータ構造はありますか？

注：「純粋に機能」によって、私は特に一人でHaskellの代数的データ型だけを使用しない構造を意味し、すなわち、そのようIntやArrayなどのネイティブのプリミティブなし（純粋なデータ構造は以下ネザーとしてそれらを技術的に提供されていても）。

Answer 1

スプライト内の位置が任意である場合（例えば、[(0,x),(7,y),(5000,z)]）、有界分岐ファクタのデータ構造のみを使用できる場合は、O（P log N）よりもうまくいくとは思えません。 。

スプライト内の位置が連続している場合は、対角スライスと連結をサポートしてO（ログN）時間にrenderを実装するSeq（指先）を使用できます。あなたのスプライトがk個の互いに素な連続シーケンスで構成されている場合、O（k log N）renderに対してこのk回を繰り返すことができます。

しかし、Oの余分な要素（1次元のスプライトの辺の長さ）をあきらめない限り、2次元への拡張は簡単ではないと思います。おそらく、この余分な要素を避けるフィンガー-k-dツリーがあります。

Answer 2

はあなたのMap Oで（N + P）の時間を構築するためにdiscriminationパッケージを使用することができます。

`Array`または` UArray`について

render sprites image 
    = flip union image 
    . toMapWith (\new old -> new) 
    . concat 
    $ sprites