Stream: ideas

Topic: Multidimensional matrix support

Elias Mulhall (Oct 04 2023 at 18:46):

As I'm working through Advent of Code puzzles I'm reminded that every time I do AoC I hit a speed bump when there's a problem that requires modeling a 2D or 3D matrix of data. Just from clicking around on random puzzles, 2022 day 8 is 2d data, while 2021 day 19 is 3d data. When I reach these kinds of problems I'll either skip it, suffer through, or (most likely) switch to a more imperative language.

This might be one of those things that's more important for AoC than real world applications (I don't think Roc is attracting the data science crowed any time soon), but in the short term it might be worthwhile to have a library to point people to that supports basic matrix operations.

Luke Boswell (Oct 04 2023 at 19:52):

I think @Hannes has started on a math library https://github.com/Hasnep/roc-math

Luke Boswell (Oct 04 2023 at 19:53):

Maybe that would be a good place for something like this?

Luke Boswell (Oct 04 2023 at 19:54):

I think Richard has a proposal for adding SIMD to Roc which would be necessary to make this kind of library very fast I assume.

Bryce Miller (Oct 04 2023 at 22:25):

An approach that worked for me when trying to represent a Sudoku grid in Elm was to flatten it into a single array, and use functions to translate between coordinates and indexes. That made it a lot less painful.

Bryce Miller (Oct 04 2023 at 22:28):

Still more hassle than multidimensional fixed-length arrays though.

Bryce Miller (Oct 04 2023 at 23:10):

# Tic-Tac-Toe Grid

Cell : [X, O, Empty]

Coord : {
    row : Nat,
    col : Nat,
}

Grid := List Cell

initGrid : Grid
initGrid = List.repeat Empty 9 |> @Grid

coordToIndex : Coord -> Nat
coordToIndex = \coord ->
    normalizedRow =
        if coord.row > 2 then
            2
        else if coord.row < 0 then
            0
        else
            coord.row

    normalizedCol =
        if coord.col > 2 then
            2
        else if coord.col < 0 then
            0
        else
            coord.col
    (normalizedRow * 3) + normalizedCol

indexToCoord : Nat -> Coord
indexToCoord =
    \index ->
        row = index // 3
        col = index % 3
        { row, col }

getByCoord : Grid, Coord -> Result Cell
getByCoord = \@Grid cells, coord ->

    List.get cells (coordToIndex coord)
    |> Result.withDefault Empty

Bryce Miller (Oct 04 2023 at 23:10):

^^ A simple example based on a Tic Tac Toe grid

Bryce Miller (Oct 04 2023 at 23:22):

As an aside, if there were a way to add a fixed-length array to the Roc stdlib that would be amazing!

Hannes (Oct 04 2023 at 23:27):

Luke Boswell said:

I think Hannes has started on a math library https://github.com/Hasnep/roc-math

Matrices are definitely on my to-do list, but there's a lot to implement, so if someone else does it before i get round to it that'd be great :grinning_face_with_smiling_eyes:

Brendan Hansknecht (Oct 04 2023 at 23:35):

This is probably something to remain in userland and libraries (maybe eventually depending on some added simd builtins)

Declan Joseph Maguire (Oct 10 2023 at 12:16):

Brendan Hansknecht said:

This is probably something to remain in userland and libraries (maybe eventually depending on some added simd builtins)

Hmm, at the very least I'd like the syntax to have the tools for a library author to make a reasonable implementation, if that's the case. Plus, there's more industries than data science who like nice multidimensional arrays. I don't find it totally ludicrous that someone might one day build some Roc to handle something in a game engine, and that's full of matrices and such.

Anton (Oct 10 2023 at 12:27):

Uhu, we've talked about before about Roc being able to replace something like Lua for game engine scripting. I don't know if it's common for scripts like that to actually work with matrices. I know very little about game engines though :sweat_smile:

Declan Joseph Maguire (Oct 10 2023 at 12:37):

It's pretty common. Hell, even shifting back to the data space, it's incredibly common to use python as a scripting language when dealing with hefty boi multidimensional matrices, because all the heavy lifting is being done by libraries with python as an effective wrapped. Especially in language that allow explicit pass-by-reference, that's not uncommon.

Though yes, in practice most matrices in a game engine would be enclosed in another layer of abstraction. But it's not terribly unheard of to pass a long list of transformation matrices, for example.

Anton (Oct 10 2023 at 14:00):

Sized matrix/vector types in Futhark could provide inspiration if we ever wanted to go in that direction.

Elias Mulhall (Oct 10 2023 at 14:42):

I'm currently putting together a fixed-size 2D array module for solving Advent Of Code problems in a nice way. It uses the data structure @Bryce Miller suggested where the data is a flat list. I don't have a strong grasp on what will/won't be performant, so the focus is more on finding an API that feels nice to use.

Declan Joseph Maguire (Oct 10 2023 at 14:53):

Flat lists are how all multidimensional arrays are implemented under the hood. After all, how else does a computer store a pile of numbers with a specific ordering? In fact big libraries like Numpy and such will have a separate bit of data, that tells you information about the shape of the array. It's super useful when you want to do something like "transpose this array and multiply it by another", because you get an O(1) operation where you redefine the bit of metadata rather than an O(n) operation of moving all the elements around. Similar to how you can "reverse" a list by just having a flag marking which way to read it. There's a whole pile of stuff like slices and views which rely on these concepts.

Being able to do this is crucial to performance, because it also lets you build functions that can assume their arguments have optimally structured data. Like, consider multiplying two matrices. Each entry in the result is a function of a row of entries in one matrix, and a column in the other. If both flatten their data the same way, one will map to contiguous memory, while the other doesn't, creating cache misses and preventing SIMD.

Further nonsense can be achieved by expoiting knowledge and symmetry, like only storing half the values of a traspose-symmetric array, or only storing non-zero entires in a "sparse" array.

Bryce Miller (Oct 10 2023 at 15:32):

Brendan Hansknecht said:

This is probably something to remain in userland and libraries (maybe eventually depending on some added simd builtins)

Is this in regard to matrices or fixed-size arrays?

Last updated: Jun 16 2026 at 16:19 UTC