Appropriate representation for lazy array in Haskell

Question

I'm trying to make a program that has massive updates on one large array, but evaluates only few times. I want computations to be lazy as possible, but I can't find out which Array representation is good for my case. To be specific, I want my array to:

have fixed size
access in constant time
update n elements in O(n)
lazy evaluated

How to approach these requirements? As a sub-question: are there libraries specifically geared for this use case?

EDIT:

Maybe my question wasn't specific enough, so I'll try to explain about my case more.

I'm trying to represent various size of image which can be either relatively small(about 1200x800), or much larger than that(at least 8000x8000). Also, there will be lots of layers for one image, which means that if I want to draw image on screen, there will be lots of updates on frame buffer image. I thought if I can exploit lazy-evaluated nature of haskell, I would be able to write on frame buffer only once, rather than overwriting same pixel at each updates.

I'm aware of several options for representing array in haskell, but all of those doesn't seem to fit in my case. For example:

Data.Seq, Data.IntTrie : can't be accessed in constant time
Data.Vector, Data.Array : update n elements takes more than O(n)
Unboxed variants : not lazy-evaluated(I guess?)

What approach should I take in this situation?

This kind of question is off topic (though it's a good question, I have often wondered about this too). Seq certainly aims in the right direction, perhaps you could change your question to ask whether that specific type fulfills your requirements. — leftaroundabout
– leftaroundabout, Commented Dec 3, 2016 at 13:59
@leftaroundabout sorry about that, but could you tell me why this is off topic? — Remagpie
– Remagpie, Commented Dec 3, 2016 at 14:03
@leftaroundabout I have edited the question in an attempt to tone down the recommendation aspect. (@Yang: Quoting the relevant question closure reason: "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.") — duplode
– duplode, Commented Dec 3, 2016 at 14:08
"but evaluates only few times"/"lazy evaluated" - I don't understand your requirements here. — jberryman
– jberryman, Commented Dec 3, 2016 at 17:09
@Yang Repa has a delayed representation which allows you to manipulate "delayed" arrays where actual allocation happens only when you try to materialize the array in an unboxed (and necessarily strict) form using something like computeUnboxedP. IIRC delayed arrays aren't strict. — Alec
– Alec, Commented Dec 4, 2016 at 5:49

Alec · Accepted Answer · 2016-12-04 09:24:04Z

One library to consider is repa. One of the key ideas in repa is that the Array type is parametrized over its underlying representation. A sample of these is

the delayed representation D for arrays that "aren't real" - they just compute elements on demand;
the unboxed vector representations U for unboxed data
the boxed vector representation V for boxed data (use only if you can't make an Unbox instance of your data)
a reference to a foreign buffer F, especially useful if you want to be writing into some foreign bitmap graphics buffer

When you compile your code, delayed arrays will get optimized away. It goes without saying that the unboxed arrays have O(1) access. For your case, you will probably just be using arrays of shape DIM2 (2D arrays).

For demonstration purposes, here is a program that does something similar to what you want: It takes in a list of bitmap layers and their offsets, as well as background bitmap. Then, it draws these layers on top of the bitmap background. It depends on repa-io for loading the images into repa arrays.

import Data.Array.Repa.IO.BMP
import Data.Array.Repa.Shape
import Data.Array.Repa
import Data.Word

-- This is our internal representation of a bitmap
type Image s = Array s DIM2 (Word8, Word8, Word8)
data Layer s = Layer { image :: Image s, offset :: (Int, Int) }

drawLayersOnBg :: Image U -> [Layer U] -> Image D
drawLayersOnBg background layers = foldl (\bg (Layer im (x,y)) -> overlay bg (ix2 y x) im) (delay background) layers
  where
    overlay :: Image D -> DIM2 -> Image U -> Image D
    overlay bg off ov = backpermuteDft bg
                                       (\i -> let i' = i `subDim` off
                                                 in if extent ov `inShape` I'
                                                      then Just i'
                                                      else Nothing)
                                       ov

    subDim :: DIM2 -> DIM2 -> DIM2
    subDim (Z :. y :. x) (Z :. dy :. dx) = ix2 (y - dy) (x - dx)

main = do
  Right bg <- readImageFromBMP "background.bmp"
  Right l1 <- readImageFromBMP "layer1.bmp"
  Right l2 <- readImageFromBMP "layer2.bmp"
  Right l3 <- readImageFromBMP "layer3.bmp"

  out <- computeP $ drawLayersOnBg bg [ Layer l1 (200,100) , Layer l2 (100, 200), Layer l3 (-300,400) ]
  writeImageToBMP "out.bmp" out

With some random bitmaps from the internet I got this as an output:

If I wanted to, I could even have used fromForeignPtr to read bitmaps straight from some foreign memory buffer and computeIntoP instead of computeP to write the bitmap output straight into some foreign memory buffer (no intermediate allocations). If you need high-performance, those are especially interesting.

Collectives™ on Stack Overflow

Appropriate representation for lazy array in Haskell

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related