two dimensional arrays

[Martin DeMello]

How do you make a two-dimensional array of a given size? (e.g. (make-
array '(i j)) in common lisp)

I want to do stuff like, e.g., representing a chessboard, where I can
index into cells and update them.

martin

[Chouser]

For something like that, I think I'd want to use a clojure persistent
data structure -- perhaps a sorted-map or hash-map using a vector for
each key:

(assoc board [4 1] "black king")

Rich used a vector of vectors in his ants demo:

(let [row (vec (replicate 8 nil))
board (vec (replicate row 8))]
(assoc board 1 (assoc (board 1) 5 "black pawn")))

If you're really sure you want a non-thread-safe mutable Java array,
you can get an 8x8 array of Objects:
(make-array Object 8 8)

--Chouser

[Mark H.]

If you don't like vector-of-vectors or maps, you could write some
syntactic sugar for mapping two-dimensional indexing onto a one-
dimensionally-indexed vector, e.g., for an n x n array with Fortran-
style indexing:

(i, j) -> i + n*j

mfh

[Martin DeMello]

On Oct 8, 8:06 am, "Mark H." <mark.hoem...@gmail.com> wrote:
>
> If you don't like vector-of-vectors or maps, you could write some
> syntactic sugar for mapping two-dimensional indexing onto a one-
> dimensionally-indexed vector, e.g., for an n x n array with Fortran-
> style indexing:
>
> (i, j) -> i + n*j

That was my first thought, but I was hoping there was a library for
this already. It seems to be a surprisingly uncommon use case (not
just in clojure, I've ended up implementing something like that in
several languages) - I'd have thought 2d rectangular arrays were a lot
more popular a data structure than that.

martin

[Raoul Duke]

> just in clojure, I've ended up implementing something like that in
> several languages) - I'd have thought 2d rectangular arrays were a lot
> more popular a data structure than that

ja, it has always boggled my mind that such things are generally
lacking standardization in languages.

[Mark H.]

On Oct 8, 9:54 am, Martin DeMello <martindeme...@gmail.com> wrote:
> That was my first thought, but I was hoping there was a library for
> this already. It seems to be a surprisingly uncommon use case (not
> just in clojure, I've ended up implementing something like that in
> several languages) - I'd have thought 2d rectangular arrays were a lot
> more popular a data structure than that.

Java doesn't even have real 2-D arrays, just syntactic sugar for array-
of-arrays. Storage of the rows (indexing is row-oriented in Java,
like in C) is not guaranteed contiguous because Java's representation
of 2-D arrays is an array-of-references-to-arrays (e.g., each "row"
can have a different length) rather than a contiguous chunk of storage
mapped to 2-D indices. It shouldn't be hard to sugar yourself up such
a mapping. However, if you find yourself doing this a lot, you might
want to think about a more Clojure-like idiom that doesn't require
destructive updates and minimizes consing for local changes (e.g., a
quadtree).

mfh

[Martin DeMello]

On Oct 9, 12:29 pm, "Mark H." <mark.hoem...@gmail.com> wrote:
> a mapping.  However, if you find yourself doing this a lot, you might
> want to think about a more Clojure-like idiom that doesn't require
> destructive updates and minimizes consing for local changes (e.g., a
> quadtree).

Interesting idea, but typical operations will be iterating along the
cells in a given row or column, so a 2d doubly-linked list would
probably work better than any sort of space-partitioning tree. But
then I lose easy random access to a cell. Vector(-of-vectors) and {[x
y] => cell} do seem like my best bets here.

martin

[Mark H.]

Depends on what you want with the data structure. Some people might
want to take slices of matrices -- e.g., the following (in Matlab
notation):

A( 1:2:end, 1:3:end )

which is a matrix containing every second row and every third column
of A. Implementing this is much easier and more efficient if all the
data is in a single flat array, than if it's a vector of vectors.
Also, imagine the pain of matrix-matrix multiplication with a list-of-
lists. But if you always mean to iterate rowwise over your 2-D array,
then list-of-lists is just fine.

mfh

[Mark H.]

On Oct 11, 10:23 pm, "Mark H." <mark.hoem...@gmail.com> wrote:
> Some people might want to take slices of matrices -- e.g., the following
> (in Matlab notation):
>
> A( 1:2:end, 1:3:end )
>
> which is a matrix containing every second row and every third column
> of A.  

Speaking of which, what's the right idiom to take a 2-D slice of a 2-D
array in Clojure? It's not really a seq because the slice implements
the same interface as an array (with random access to elements).
Also, a seq of seqs would constrain iteration either to a rowwise or
columnwise direction, whereas the user might want to iterate both ways
over the same slice (e.g., for the matrix-matrix multiplication C <- A
* A, one might iterate rowwise over the left A and columnwise over the
right A).

mfh

[Rich Hickey]

As this discussion highlights, Clojure doesn't have a proper notion of
multidimensional arrays or vectors. I saw a presentation on IBM's X10
[1] and was impressed by their point-indexed arrays. I think there are
some good ideas in there that might inspire a nice contribution to
Clojure.

Rich

[1] http://x10-lang.org/

[Mark H.]

On Oct 12, 7:08 am, Rich Hickey <richhic...@gmail.com> wrote:
> As this discussion highlights, Clojure doesn't have a proper notion of
> multidimensional arrays or vectors. I saw a presentation on IBM's X10
> [1] and was impressed by their point-indexed arrays. I think there are
> some good ideas in there that might inspire a nice contribution to
> Clojure.
>
> Rich
>
> [1]http://x10-lang.org/

The parallel HPC language Titanium [1] has similar constructs. They
are useful for expressing computations on regular grids. You could
have constructs like "for all points p in domain D" and also have an
idea of "neighbors" of p (north, south, east, west, up, down). D
might have interesting boundary conditions (e.g., reflecting or
periodic) and the "for all" construct would be aware of this when
computing neighbors. I could see this being useful for games
(collision detection perhaps, or wave propagation).

When I work with matrices I generally want actual 2-D indices, and
also the ability to partition and slice matrices. The right syntax
there might be different than with regular grids: I don't generally
think of "neighbors" of a matrix entry, rather of entire slices
related to that entry. Of course grids and matrices could look the
same underneath but the usual notation is different.

In your copious free time, of course ;-) I mention it only because
there are different notations for the same underlying construct, which
is interesting for language designers.

mfh

[1] http://titanium.cs.berkeley.edu/