CODEWITHSUNDEEP
haskelldata-structures
user1002430
user1002430

Reputation:

Haskell: Pure data structure that efficiently models a block of memory?

I'm interested in writing a virtual machine that works with a block of memory. I'd like to model the block of memory (say 1MB) with a pure data structure that's still efficient to reads and writes anywhere within the block. Not very interested in a mutable structure. Does such a structure exist?

Upvotes: 2

Views: 383

Answers (2)

ehird
ehird

Reputation: 40787

The vector package offers immutable (and mutable) boxed and unboxed vectors, with all the time complexities you'd expect. The mutable ones are usable from both IO and ST, and you can have an unboxed array of any instance of Storable. It's a lot nicer than the standard array modules.

However, since you mentioned efficient immutable updates, I would suggest using a Map-like data structure; perhaps a HashMap from unordered-containers. It might even be worthwhile to have a map with small unboxed vectors at the leaves, to avoid some tree overhead.

Depending on your use-case, you might also be interested in the standard Data.Sequence, which has O(1) access to the beginning and end, and pretty good access times into the middle of the sequence.

Upvotes: 8

ulidtko
ulidtko

Reputation: 15560

Is Data.Array.ST good enough for you?

Upvotes: 0

Related Questions