In the discussion of srfi 231 on n-dimensional arrays, Bradley Lucier raised an interesting question:
More generally, I've asked in various forums (fora?) about how
people use arrays, in Scheme and other languages, but did not get any
replies. In my studies, it seems that APL turns everything into arrays
(even some control structures in some sense), I've used Matlab and
spreadsheets to teach numerical methods, and I understand vectors,
matrices, and tensors, but I don't know how other people use arrays.
How do you use arrays?
(To be clear: I mean the concept "arrays" not the Racket libary math/array).
Here is another question: have you ever used math/array without using other math stuff (like math/matrix)? If there is a compelling use case for math/array without math-y stuff, should it be separated out from the math collection?
In this context, what is the distinction between 'array' and 'vector'? My understanding of vectors in Racket is that they are what I think of as arrays -- a contiguous block of memory that can be random-accessed quickly via numeric index.
Here's a fun gotcha that I ran into as a Racket newbie who thought vectors were basically arrays. I think this comes up every year in Advent of Code. What happens when you want a two-dimensional array?
;; A 4x4 array initialized to zeros…right?
(define fabric (make-vector 4 (make-vector 4 0)))
(define (poke-square! x y val)
(vector-set! (vector-ref fabric y) x val))
(begin
(poke-square! 1 2 9)
fabric) ; → '#(#(0 9 0 0) #(0 9 0 0) #(0 9 0 0) #(0 9 0 0))
9s in the entire column rather than just in the location 1,2! Apparently when make-vector is given another vector as the second argument it initializes all the slots with a reference to the vector rather than a copy of the vector. I, at least, could find no clues in the docs that would lead me to expect this.
A common workaround is to use a one-dimensional vector and do (vector-ref vec (+ (* y 10) x)) to index the right location.
Racket does have a math package with functions for arrays and matrices but even these are cumbersome for the simple operation of fingering an individual bit somewhere in the middle. There is furthermore a warning at the top of the docs for each that using these libraries without using Typed Racket is 50⨉ slower. I didn’t feel like learning Typed Racket today.
I've been bitten by this behavior myself, but if you sit down and try writing make-vector yourself, you'll find that it's the only sane way to do it; I claim that most other languages either behave the same or weave some kind of deep copying/mutation magic into the language itself. If you consider the alternatives, I think you'll come to the conclusion that this is the right one for Racket.
More generally, I would say that Racket favors mostly-functional code, and that "casual" vectors (I'm writing a small program and I want to keep track of some stuff) are usually most useful in a mutation-heavy setting.
For sure, I’m not saying make-vector is wrong. I’m just saying that I, a single extremely mediocre programmer, experienced some discontinuity when learning Racket on my own and trying to use what I thought of as an “array” (“an n-dimensional matrix of mutable values”). Coming to Racket I thought the vector was the equivalent tool, and it can be, but there are some traps there if n exceeds 1. Untyped Racket doesn’t have any effective tools for multidimensional arrays (in the generic sense above) other than that it’s possible, with care, to hack them yourself using a collection of vectors. Quite a different (not to say wrong!) experience from other languages where it’s just int a[5][5]; a[1][2] = 7; and you’re off to the races.
In this context, what is the distinction between 'array' and 'vector'? My understanding of vectors in Racket is that they are what I think of as arrays -- a contiguous block of memory that can be random-accessed quickly via numeric index.
That's also how I think. Vectors are 1-dimensional arrays.
I should have the context clearer. The question arose while discussing a suggestion for n-dimensional arrays. Maybe I should have asked, what do you use 2, 3, 4, ... dimensional arrays for.
I have a hunch that most of us has implemented 2-dimensional arrays to represent various kinds of "boards" for games. Some use vector of vectors to represent boards. Others use a single vector, but then use rows*i+j to index into the vector - effectively a 2-dimensional array.
What are other uses for 2-, 3-, ... dimensional arrays? That is, what kind of problems do you solve using n-dimensional arrays?
(Whoops, I now see you meant to ask about use cases, not implementations!)
original post
I have sometimes used hash tables, with the coordinates as keys:
(define array (make-hash))
(define (array-ref arr x y)
(hash-ref! arr (+ x (* y 0+1i)) 0)) ; or use (make-rectangular x y)
(define (array-set! arr x y val)
(hash-set! arr (+ x (* y 0+1i)) val))
For 3+ dimensions the coordinates/keys could be a list.
I started attempting a version of @badkinspost here using math/array, but I didn't find as convenient a way as I would have liked to e.g. shift ever position one column to the right, with wraparound. (Though I could have written one on top of array-transform.)
Here is how to rotate columns and rows with wraparound in an array (or any dimension really if you have more than 2 dimensions):
#lang racket
(require math/array)
(define a (array #[#[1 2 3]
#["a" "b" "c"]
#["one" "two" "three"]
#["red" "green" "blue"]]))
;; rotate left with wraparound by column
(array-slice-ref a (list ::... '(1 2 0)))
;; (array #[#[2 3 1]
;; #["b" "c" "a"]
;; #["two" "three" "one"]
;; #["green" "blue" "red"]])
;; rotate left (up?) with wraparound by rows
(array-slice-ref a (list '(1 2 3 0) ::...))
;; (array #[#["a" "b" "c"]
;; #["one" "two" "three"]
;; #["red" "green" "blue"]
;; #[1 2 3]])
The previous code assumes that you know the length of a dimension, but you can also build helpers functions to create the appropriate slicers where the dimensions of the array are not known in advance:
(define (left a dimension)
(define dimension-length (vector-ref (array-shape a) dimension))
(append (list (sub1 dimension-length))
(build-list (sub1 dimension-length) values)))
(define (right a dimension)
(define dimension-length (vector-ref (array-shape a) dimension))
(append (build-list (sub1 dimension-length) add1) '(0)))
EDIT: the array library is a bit verbose, and it is worth considering creating helper functions. For example, you can create a "rotate-columns-left" function, to avoid remembering the array-slice-ref invocation and what it means.
Also, if your algorithm requires rotating the same array several times, it is worth creating and keeping the slice reference:
(define rotation (list ::... (right a 1)))
(array-slice-ref a rotation)
I made this mistake too. (In my defence it was a long time ago.)
Following on from above I suspect people new to Racket will try something like this
from array import *
T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]
T[2] = [11,9]
T[0][3] = 7
for r in T:
for c in r:
print(c,end = " ")
print()
Arrays are used as representations of vectors in many fields of mathematics, especially in physics
(where we even have vectors of infinite length or worse: of uncountably infinite length. For example countably infinite for a quantized observable (such as a rotational momentum (involving summation of an infinite series) or even uncountably infinite (involving integration of a function, for example the radial position of an electron in an atom). I never have seen calculations in systems bigger than omega, but I have heard of studies in math of systems of an omega of or even an omega of omega dimensions.)
Well, I suspect that even nowadays most physicists use Fortran, but the squares of the eigenvalues of rotational momenta can be computed exactly (see for an example: https://github.com/joskoot/nj-symbols), which is possible. Although not trivial, with Racket (or another Scheme) possible but rather difficult in Fortran.
OK, thanks, I think that's what I'm asking, not what does one use arrays for, but what do you use arrays for. It appears to me that your representation of arrays is implicit, rather than using an explicit data structure.
I use arrays for scalar fields, vector fields, multi-dimensional images, various things in image processing.
I'm typically using dense (i.e. non-sparse) 2D arrays, which I do not resize. These are typically backed by a single vector, with y*width+x for indexing. I would only use vector-of-vectors if I needed a ragged array, but it's rare that I need a ragged array in my own code, so I avoid the extra cost.
I care about having efficient random-access reads primarily.
