What is a purely functional data structure that efficiently implements rendering to an image?

Question

Images and pixel-rendering are one of the last things in Haskell I couldn't pick an efficient enough purely functional data structure for. For simplicity, lets talk about 1D images, since those can easily extended to n-d images. I'm using unboxed vectors as the representation and their mutable view for rendering:

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

This is the most performant design for CPU-rendering I found, yet it is rather ugly. For a purely functional structure that implements render, the obvious answer would be to use a map to represent the Image and a list of (Position, Pixel) pairs to represent the sprite. Something like:

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

Which is O(P * log(N)) (P = pixels to render, N = size of the image). It might look that the log(N) is unescapable, but if you see it carefully, render is traveling the same paths through Image several times (i.e., if you insert at position 0, then at position 1, you are running all way down to a leaf, then all way up, then all way down to the neighbor leaf...). That looks like the exact same pattern for which zippers, for instance, can improve the asymptotics, which leads me to suspect render can be improved. Is there any purely functional data structure that allows implementing render better than O(P*log N)?

Note: by "purely functional", I specifically mean a structure that uses nothing but Haskell's algebraic datatypes alone, i.e., without native primitives such as Int and Array (even though those are technically served as pure data structures nether less).

Answer 1

If the positions in a sprite can be arbitrary (e.g. [(0,x),(7,y),(5000,z)]) it seems pretty clear that you can't hope to do better than O(P log N) if you are only allowed to use data structures of bounded branching factor.

If the positions in a sprite are contiguous then you could use a Seq (fingertree) which supports logarithmic slicing and concatenation to implement render in O(log N) time. If your sprite consists of k disjoint contiguous sequences then you can repeat this k times for O(k log N) render.

However, I don't think the extension to two dimensions is as easy as you make it sound unless you are willing to give up an extra factor of O(side length of sprite in one dimension). Perhaps there is some kind of finger-k-d tree that avoids this extra factor.

Answer 2

You can use the discrimination package to build your Map in O(n+p) time:

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