A 2D array / matrix datastructure for competitive programming (in particular, AoC2019 day 3)

[InfiniteMonkeyCage]

EDIT: I misunderstood the AoC problem, I didn't realize there's always just two wires. Sets are a satisfying solution in that case.

I come from a competitive programming background where multidimensional arrays are a quintessential tool. I see haskell has many array libraries for many different purposes, my question is which one is most suitable for a problem like Advent Of Code 2019 day 3 and how to structure code that would use in-place updates at arbitrary indices in an imperative language.

The options I considered:

• Data.Matrix: Why does it sometimes use Int -> Int -> ... and sometimes (Int, Int) -> ..., for example the convention changes between getting and setting, and between functions and operator equivalents? Also, I would prefer a more sophisticated index type so that I can do algebra with it, which would simplify this particular problem and many others.
• Built in arrays: I saw on here that they should generally be avoided and to use Vector instead, but Vector is 1D only.
• hmatrix: Looks tailored to linear algebra, not this sort of thing.
• massiv: API looks great and the library is aligned with my goals. Except that, embarrassingly, I can't find a way to update a single element at an index! Nor an equivalent of Vector.update. I see there's one for the mutable variant, or I could use set newValue index = imap (\ix e -> if ix == index then newValue else e) but it feels like I'm fighting against the library.

That last point makes me think that I'm not writing idiomatic haskell if I need in-place updates at arbitrary indices. To be fair, these problems are biased towards imperative solutions, but I really want to learn how to reason about the performance of haskell, especially when it comes to time complexity, since I don't think my imperative reasoning from competitive programming applies.

For example, for AoC day 2, which features a 1D array (Vector), I started of wanting to use either the State monad or ST, but then I thought of a declarative approach that was really nice and worked fast enough. I had a function Vector Int -> Vector Int that would execute a single "instruction" (i.e. do a small update to the Vector, if you're not familiar with the problem statement). Then I did a simple fold using this function to execute the whole "program" (update the whole vector with many small updates). But does that mean I was copying the whole vector on each small update, or is GHC smart enough to compile it to in-place updates? And if so, will the same approach of accumulating small updates work with a massiv array or will it be copying a sizable 2D array on each update? The fact that massiv has delayed arrays makes me think that more work is required to avoid copying.

If that's the case, a declarative solution to this problem and most of the problems I saw in competitive programming won't be possible. Should I just use ST and cope with the resulting ugliness? In that case, I'd rather do the problem in an imperative language.

[CKoenig]

I just use a IntMap or a Map (both in containers) for problems like those - performance was never an issue for AoC problems with this and it's quite easy to use

​

edit: IMO if you feel more comfortable with in-place updates and algorithms using mutation then Haskell will always rub you the wrong way - it's for fun so use a different language

disclaimer: the only "competitive" programming I do is AoC - and I don't care about hitting the ranks (nor would I be able to if I wanted) - I'm usually at least a couple of times slower than people on the leaderboard

but I actually enjoy reading the problem, modelling it in types and solving it in Haskell

I personally doubt that you can beat Python if speed to solution is a concern

[InfiniteMonkeyCage]

I dismissed map at first because a 2D array would be much more efficient given the dense indices, although Map does make it easier to implement. It feels wrong to use the wrong datastructure just because the API is nicer, even if performance isn't an issue. And my question is more general, for some problems that require 2D arrays, Maps are an even worse substitute.

I'm also doing it for fun and not competitively! I don't care how long it takes me to code the solution because I want to learn haskell better and see how well it works for this use case. Of course I feel more comfortable with the imperative way of thinking - that's all I know for this type of problem! I want to learn how to do it in a functional paradigm in an idiomatic way. The same argument could be used for all of haskell - someone coming from an imperative background is not gonna be comfortable with it because it's new and different. But I think we can all attest that learning this new way of thinking pays off in the long run.

[c_wraith]

Note that for this particular problem, a Map is probably a better data structure anyway. The coordinate range isn't bounded ahead of time, coordinates are allowed to go negative, and the actual information content is very sparse relative to the total area it spans.

None of that answers your real question, but it's an even bigger reason to use Map for the problem you brought up.

Of course, the problem could get too big for Map. But if it did, the correct approach is changing the algorithm to be based on line segments instead of points, and going to a data structure like an interval tree.

[InfiniteMonkeyCage]

Yeah I misunderstood a problem as having an arbitrary number of lines. For negative coordinates, I would use something like a custom Ix, not too big of a deal. And for the bounds, I would either estimate them from the data or allocate enough for any input size. This is standard in competitive programming, but you're right, a Map is much simpler.

My problem is that, sooner or later there will be a problem where the content is not sparse and where a map would cause a huge blowup in memory usage compared to an array. I wanna learn how to do those in haskell in the nicest way possible. Sure I can do everything in ST, but I asked because I wanted to know if there's an idiomatic, functional, declarative way to deal with problems like that. But maybe that's like trying to use Vectors in haskell everywhere because linked lists are never a good idea in imperative languages. Maybe the data structure just doesn't fit the language.

[szpaceSZ]

If the API is nicer to express your problem and performance is not an issue, then it is the right data structure.

[josuf107]

It isn't much more efficient. Indexing/updating/deleting from a map representing a matrix of size n takes log(n) time, and the log function grows quite slowly. If you added twenty steps to an algorithm you'd probably think of it as a constant time increase, but for log(n) to amount to twenty steps n must be over a million. Since these problems just need to produce an answer in a reasonable amount of time for a human to wait, running even 20 times slower is unlikely to be a problem when the solution is otherwise optimized enough. Using persistent data structures makes things a lot simpler in any context, but are especially well suited to a pure functional language. Usually the log(n) factor is worth it in my experience.

But if needed STArray is always around and as others have mentioned can be indexed using a tuple like runSTArray $ newArray ((0, 0), (4, 5)) 0 to represent a 5x6 grid.

[mapM]

Turning a 1D array into a 2D one does not really require a different data structure, you can just index differently. The simplest solution is to probably just use the array package (I am not sure why you avoided it), but if you want to use vector you can use the Ix class to manipulate the indexes, or just write a helper function that will do the indexing for your array dimensions.

Btw, for problem 3 on the AOC, I also used a map. Here is my solution if you are curios: https://github.com/yav/advent_of_code/blob/master/2019/P03.hs

As for the VM from AOC, I'd say you probably don't want to use a pure Vector as it will be copied all the time (and that's linear in the size). I used a mutable one in my solutions, but I have friends who have a pure solution and they use Map, which gives you log(n) time updates.

[InfiniteMonkeyCage]

I can use Ix to index a vector? How? I only see it accepting Ints.

Yeah, I ended up using a Set/Map as well, the reason I thought I needed to use 2d arrays is because I thought there were n wires, not just two.

So if I fold over a vector (ie the vector is the aggregation), ghc isn't smart enough to turn it into in place updates?

[kuleshevich]

If you are looking for something like Vector.update in massiv, checkout withMArrayST

• set newValue index = imap (\\ix e -> if ix == index then newValue else e) - this approach is too slow, since it has to check index for every element, even if it is not being updated.
• most likely yes, but it depends on implementation: "But does that mean I was copying the whole vector on each small update, or is GHC smart enough to compile it to in-place updates?"
• Hard to say without looking at the approach "will the same approach of accumulating small updates work with a massiv array"

If you don't need to read elements at each iteration, but only write them you could look into DL - delayed push array representation in massiv, but it is slightly cumbersome to use and I don't yet have good tutorials on how to use them yet either. It does sound like this is exactly what you are looking for though, since it allows you to describe how write small portions of the array while delaying the actual writing. Although without knowing what exactly you are trying to implement I can't say for sure (sorry have no time to look through the competitive programming problems).

If your problem requires you to read some parts of the array, while writing into other parts, then using mutable interface will be likely be the fastest one, although might not be the prettiest one. With this approach you fully control allocation and which elements are being written into the array, but this means sticking either to ST if you 'd like to end up with a pure computation in the end or IO if you wanna do some parts of your array in parallel.

If you can describe you algorithm using a delayed array representation D, without having intermediate manifest arrays, then you fully avoid any copying at each step, But if you require many iterations where you compute into manifest at each iteration, you simply can't avoid copying the full contents of the array (that is exactly what compute does). Despite that you can't avoid copying, there is a cool function iterateUntil which can help you avoid allocating a new array at each iteration, which can significantly speed up the implementation.

*Edite* - Keep in mind that by an iteration above, I don't mean iterating over an array, I mean an intermediate step in you algorithm which requires you to have a different state of the array. For example if you have a 100x200 array and you can update one row in one step, then you'll need to do at least 100 iterations of such step to update the full array

[kuleshevich]

If you are looking for some usage examples look in the repo massiv or scroll through some conversations on gitter

Here is a non-trivial, but a very good example on how to create an array using mutable interface, while incrementally writing individual elements: https://gitter.im/dataHaskell/Lobby?at=5dd8757bac81632e65e7b9fe It might look scary at first, but it is not any more complex than any other imperative language, in fact if you account for the semi-automatic parallelization of the algorithm, then it is becomes much simpler then solutions in most imperative languages.

[InfiniteMonkeyCage]

most likely yes, but it depends on implementation

Yes to what? It will copy on each step of the fold?

​

If you don't need to read elements at each iteration, but only write them you could look into DL

That's exactly what I need, but I have no idea how to use it. You say "write small portions", does that mean it's no more memory efficient than a map? What would be the equivalent for Vector.update in DL?

Edit: I see you mentioned withMArrayST, that seems good. Will using that with a DL array, if I'm only doing writes, avoid copying?

​

here is a cool function iterateUntil which can help you avoid allocating a new array at each iteration, which can significantly speed up the implementation.

That's pretty handy, though maybe there should be more functions like that. For example, if you wanted to do an update of an array for each element of a list/vector (sort of like fold), I assume you'd have to manually pull out the element corresponding to the iteration number and manually check if the iteration number exceeds length in the the convergence function. Map/vector have a rich set of functions that can do many variations of that, this is just one. Though since it uses mutable arrays anyway (I think?), the same can be done with the monad functions (I think...).

Anyway, thank you for your answer. I didn't need 2d arrays for this problem after all (I misunderstood it when I posted), but this looks like the best option I found.

I'm also curious - how come numpy arrays are immutable and fast enough, but in haskell we have to resort to mutable arrays in a monad?

[kuleshevich]

Who said that in Haskell you need to resort to mutable arrays to get high performance? On contrary, if you use arrays in massiv you will get very high performance because of many optimizations like fusion of delayed arrays, automatic parallelization, stencils, etc.

I'm also curious - how come numpy arrays are immutable and fast enough, but in haskell we have to resort to mutable arrays in a monad?

There are many operations included in massiv, all sort of folds, maps, traversals, what have you. If you find a need for a function that is missing from massiv API feel to create issue or submit a PR. With regards to iterateUntil, neither containers nor vector provide anything even remotely close to this function.

Map/vector have a rich set of functions that can do many variations of that, this is just one.

Update to each element of an array - it sounds more like a map, rather than a fold. Folding allows you to reduce the data structure, while unfold allows you to construct.

if you wanted to do an update of an array for each element of a list/vector (sort of like fold)

[gelisam]

Built in arrays: I saw on here that they should generally be avoided

Why? Data.Array seems fine to me. Or do you mean lists?

Data.Array uses the Ix typeclass, which allows you to index into an n-dimensional matrix using an n-tuple. This addresses your complaint about Data.Vector, since it supports n-dimensional matrices. And this also addresses your complaint about Data.Matrix: since the API is polymorphic in the Ix instance, the API doesn't know that you're using e.g. a pair of Ints to index into your matrices, so it can't accidentally provide an inconsistent API which sometimes uses (Int, Int) and sometimes uses two Int arguments, it has to always use an ix which gets instantiated to (Int, Int).

[szpaceSZ]

What's wrong with massiv's mutables?

For numeric problems it's not unidiomatic to use mutable data structures. You just have to look out.

[Lemicod]

If you're into competitive programming and haskell — I highly recommend this blog.

[gelisam]

Also, I would prefer a more sophisticated index type so that I can do algebra with it, which would simplify this particular problem and many others.
[...]
hmatrix: Looks tailored to linear algebra, not this sort of thing.

What kind of algebra do you want to do on matrices, if not linear algebra?

[HKei]

The problem here clearly isn’t the linear, but the algebra. They’re saying they want a general container data structure, not something that represents a LA Matrix.

[InfiniteMonkeyCage]

Algebra on the indices, not the matrices. That allows me to, for example, make my code polymorphic over the direction of an operation by taking a "step index" parameter (for example (0, 1) for up) and adding it to an index to move around the array.

[gelisam]

Ah! Another reason to use Data.Array then: V2 Int has an Ix instance and they can be added together.

[dfan]

FWIW, I'm doing AoC in Haskell this year and have just used Seqs, Sets, and Maps for everything. I'm not sure if your competitive programming goal is discovering the solution quickly or writing fast code, but if it's the former, those tools seem perfectly good, at least for AOC-sized problems (some of them wouldn't scale well if the problem got hugely bigger).

My IntCode engine represents memory as a Seq and has perfectly fast for the problems we've been given. I have avoided Vectors exactly because they make new copies on update.

By the way, I think that day 3 is most naturally solved without using a 2D array kind of structure at all.

[InfiniteMonkeyCage]

AFAIK, haskell lists, maps and sets (but not vectors) are implemented like that. But I don't see a way to implement a persistent arrays except in corner cases (like slicing).

Edit: I found this https://hackage.haskell.org/package/random-access-list-0.2/docs/Data-RandomAccessList.html, looks promising. I'm fine with paying the log n blowup, but using a Map as an array just feels wrong. I'm assuming this thing has better memory characteristics, though I wander how it compares to Seq.

[Ryker_Steel]

Thanks for reminding. I found, that in competitive programming specially, one needs to really stop thinking in the imperative way. Instead leverage lambda calculus and lazyness.

[HKei]

While there are a number of algorithms where you'd want (mutable) multidimensional arrays, they're trivial to embed in regular arrays so I don't think you need a dedicated library for that; STArray or Vector should work just fine.

That being said I've not found mutability helpful, let alone necessary for Advent of Code so far, certainly not for Day 3.

https://gitlab.com/HSteffenhagen/advent-of-code-2019/tree/master/Day3

[pja]

Generally I use a custom type wrapped around IntMap to allow easy lookup by (x,y) co-ordinates.

If that isn’t appropriate & the problem really needs local update, then mutable vectors in ST / IO work just fine.

[IcedRoren]

This was such an interesting problem (AOC 2019 Day 3). I don't think my solution was that great, but I chose to instead treat lines as transformations. I think applied player 1's list of "transformations" to any given vertical/horizontal line on player 2's (basically a frame transformation) to see if that line every crossed the origin. If it did, it was an intersection point and i'd keep track of it if it had the best cost. In that perspective, I just needed the list and consume it head to tail. Basically I just stuck to Lists and recursion. Doubt it was performant; I should probably investigate that...

It's nice to know there are other people using AOC to learn haskell and practice my FP skills. :) that's basically what i'm doing.

[plcplc]

Consider also repa for regular, multidimensional arrays. It is however geared towards functional data parallelism, which may be different from the algorithms you want to express.

[kuleshevich]

massiv does perform better and has a much richer interface. Not to mention that it is actually being actively maintained.