什麼是高效實現圖像渲染的純功能數據結構？

Question

圖像和像素渲染是Haskell中最後一件事情之一，我無法爲其選擇一個高效的純功能數據結構。爲了簡單起見，我們來討論一下1D圖片，因爲這些圖片可以很容易地擴展到n-d圖片。我使用拆箱向量作爲代表和他們的可變視圖渲染：

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

這是CPU的渲染，我發現最高效的設計，但它是相當醜陋。對於實現render的純功能結構，顯而易見的答案是使用地圖來表示圖像以及(Position, Pixel)對的列表來表示精靈。類似：

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

哪個O(P * log(N))（P =像素渲染，N =尺寸的圖像的）。它可能看起來log(N)是不可逃避的，但如果你仔細看看它，render幾次通過Image行進相同的路徑（即，如果你插入位置0，然後在位置1，你一直跑到葉子，然後一路向上，然後一路下到鄰居的葉子......）。這看起來像是完全相同的模式，例如zippers可以改善漸近性，這導致我懷疑render可以得到改善。 是否有任何純粹的功能數據結構，允許實施render比O(P*log N)更好？

注：由「單純的功能性」，我特別是指單獨使用也不過Haskell的代數數據類型的結構，即沒有本地原語如Int和Array（即使那些在技術上充當純粹的數據結構幽冥少）。

Answer 1

如果精靈中的位置可以是任意的（例如[(0,x),(7,y),(5000,z)]），那麼看起來很清楚，如果只允許使用有界分支因子的數據結構，您不可能希望比O（P log N） 。

如果精靈中的位置是連續的，那麼您可以使用支持對數切片和連接的Seq（fingertree）在O（logN）時間內實現render。如果你的精靈包含k個不相交的連續序列，那麼你可以重複這個k次O（k log N）render。

但是，我不認爲向兩個維度的擴展很容易，除非您願意放棄O的額外因子（一維中的精靈邊長）。也許有某種避免這種額外因素的finger-k-d樹。

Answer 2

可以使用discrimination包建立你Map在O（N + P）時間：

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