Haskell Most Efficient Mutable Data Structure

Question

I am writing a game program in Haskell that currently has a data type like this

data World = World {
    worldPlayer :: !(IORef GameObject),
    worldEntities :: ![IORef GameObject],
    ...
}

Each update, the following update is written to the player IORef:

updatePlayer :: GameObject -> [IORef GameObject] -> IO GameObject

In this function, it checks for collision on each object, then moves the player. But I would like the updatePlayer function to be pure, so I need to use a different data structure.

The most obvious idea is to take the [IORef GameObject] from the world and transform it into an IO [GameObject] by calling readIORef on each index. But this would be very inefficient.

Another possible way I found to do this is using Data.Vector.MVector and Data.Vector.Generic.unsafeUnfreeze and unsafeFreeze, which have O(1) performance to do worldEntities :: !(MVector (PrimState IO) GameObject). The problem is that unsafeUnfreeze and unsafeFreeze only work on certain data types.

I also found IOArray, so I could use IOArray Int GameObject, but I cannot find a way to convert IOArrays into an immutable structure.

Last, I could just do IORef [GameObject] or IORef (Vector GameObject), but I am unsure how efficient this would be.

What is the most efficient way to do this?

Do you actually need a mutable data structure? Are you sure returning a new data structure each update is not fast enough? — Tom Ellis
– Tom Ellis, Commented Jan 29, 2014 at 23:51
@TomEllis I think that would be very inefficient, if you mean calculating the whole World every update. — functorial
– functorial, Commented Jan 29, 2014 at 23:59
It depends what GameObject is precisely. Returning a new object will certainly be less efficient than mutating, but probably not as much as you think, and it's certainly a lot easier! It can actually be very fast if little changes between updates and you can share a lot of the old structure. — Tom Ellis
– Tom Ellis, Commented Jan 30, 2014 at 0:02
@ala-rucnuru is your game implementation using concurrency? If not it's possible you're misunderstanding IORef. Maybe you could give a bit more of your game code? — jberryman
– jberryman, Commented Jan 30, 2014 at 0:06
First of all, you should absolutely make sure if you need to struggle for performance so desperately. Write a mock-up first to find bottlenecks, then think of optimization. Remember, premature optimization is the root of all evil. — user3974391
– user3974391, Commented Jan 30, 2014 at 4:41

Matvey Aksenov · Accepted Answer · 2014-01-30 14:33:20Z

5

You can use lenses instead of mutable objects, to get "setter-like" behavior. Try that before messing around with mutable state, which is very ugly in Haskell (intentionally ugly, to discourage you from doing it).

(Edit to add: "setter-like" syntax. Lens "setters" still create new references to the "set"ted result, so you still need to sequence your main loop to read from the returned value from the setter, you can't re-read an old (immutable) reference to get an updated value, of course.)

edited Jan 30, 2014 at 14:33

Matvey Aksenov

3,9013 gold badges26 silver badges45 bronze badges

answered Jan 30, 2014 at 1:27

misterbee

5,1823 gold badges27 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

trolox Over a year ago

It's absolutely not true that Haskell deliberately makes things like mutable state ugly in order to discourage their use; that would be a terrible language decision. Mutable state in Haskell is appropriately compartmentalized from pure code, yes, but ST monad code really isn't appreciably uglier than any other imperative language (though I guess that's a pretty subjective topic).

Collectives™ on Stack Overflow

Haskell Most Efficient Mutable Data Structure

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related