Изображения и рендеринг пикселей - одна из последних вещей в Haskell. Я не мог выбрать достаточно эффективную чисто функциональную структуру данных. Для простоты давайте поговорим о 1D
изображениях, так как они могут легко распространяться на n-d изображения. Я использую unboxed векторы как представление и их изменяемый вид для рендеринга:
-- 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
(даже если они технически служат чистыми структурами данных ниже).