multidimensional arrays

Someone on comp.lang.python remarked

It is just funny how easy horizontal slicing is made (list[:]) but how "difficult" vertical slicing is. It is a common task and one does not realize how often one does need vertical slicing. eg.: getting the keys of dictionary is a vertical slicing, or turning a list into a dict involves vertical slicing...

Just out of pure curiosity: Is there a langue that allows vertical and horizontal slicing and dicing with the same built-in pattern?

The basic problem is, of course, that multidimensional arrays are implemented as arrays of arrays, but that made me wonder in turn - which languages have true multidimensional arrays? (i.e., arrays in which every dimension is treated as equivalent)

Comment viewing options

doesn't fortran 90 allow you

doesn't fortran 90 allow you to do all kind of odd things with array indices (like specify a new array from some sampling of an old one)? i'm pretty sure common lisp does too. and i bet the array languages let you do similar stuff.

Blitz++

You can't create multi-dimensional arrays in a library. Some languages with multi-dimensional arrays (e.g. FISh) even compile to C which doesn't have true multi-dimensional arrays.

More

Obviously you can do cool things with arrays in APL and J. The arrays are truly multi-dimensional, and you can shape and reshapre them in various ways.

PL/I's iSUB facility is pretty cool, too.

Language design problem

iSUB is trying to fix a language design fault. It's nothing more than a weird function definition. If the language was designed properly, arrays and functions could have been used interchangebly. They have the same "signature": a tuple as input and one value as output.

Now that I think about it, I can't recall a language that allows this. Is there a language where you can write a factorial function and slice it like a list: fac[1:20]

Two ways in Mathematica

Table[Factorial[n],{n,1,20}]

Factorial[Table[n,{n,1,20}]]

Functional languages can do these things.

Higher order functions

Do higher order functions that expect functions as argument, also allow arrays, and vice versa?

Re: Higher order functions

See this PDF, Maeder's books and articles, and Wolfram.

There is sample code all over the Internet and you can install the free MathReader on any platform to inspect it.

Most functions have the attribute Listable (look it up). The documentation includes a section on FP, and a rundown on programming paradigms.

For more help please appeal to Google.

Not what I mean

It's all very cool! But listable means that functions automatically map over lists. That's not what I mean.

Let's take a particular example from those pages. NestList is a higher order function. The first argument is a function. Can I use a list instead?

NestList[{1,3,4,2,3}, 0, 6] -> {0, 1, 3, 2, 4, 3, 2, 4}

Talk to my agent about consulting rates

The use cases proposed are not higher order. Factorial is not a higher-order function in the first place. Feeding numerical parameters (or arrays of same) into a function is not a higher-order operation; it is a straight function call. Higher order means that a function appears somewhere in the parameter list. I see no function parameter in the calls that you propose. Rethink what you are asking and why. Do you really care about HOFs, or is it something else that you want? If you feed an array into NestList, how is NestList supposed to know what function you want applied to the list, unless you supply it as a parameter?

I'm signing off now, but you can ask the various user groups or Google for more help.

Big misunderstanding

If you feed an array into NestList, how is NestList supposed to know what function you want applied to the list, unless you supply it as a parameter?

No, no, no! I want the the list to *be* the function.

A function is a mapping from values from its domain to values from its range. Similarly, a list is a mapping from indexes to values. A list can therefore be considered a function. Similarly, multidimensional arrays are mappings from a tuple of indexes to values, just like functions with multiple arguments. I want to know if there are programming languages that acknowledge this, in any way.

Ruby sort of does, in that it

Ruby sort of does, in that it lets you overload the [] operator, and that a[i] = a.at(i) for an array and a.call(i) for a proc. I've seen code written that let you pass in whatever parameter you wanted, as long as it supported the [] operation, so it definitely does support the idiom. However, it doesn't have built-in multidimensional arrays, and methods are treated differently from proc objects.

lists as functions

Hmm, to use a list as a function you need an
infinite list, i.e. a stream. Indeed Streams over A are
"isomorphic" to Nat -> A. What is isomorphic to
functions over binariy trees? I wrote a paper about
this a few years ago.

Boy, I'll say

You're in a bog of terminology confusion that seems more complicated than the actual task, which still eludes me. The whole presentation abuses standard terminology. HOF means HOF; you mean something else, but want to cram it into HOF with elliptical reasoning. That penny tutorial about function domains was nice, but bears no relation to HOF in computer science. I would drop the term HOF.

You picked NestList. NestList returns a list of iterated function applications to a seed expression. We know what f[x] means - f is a function. Replace f with the list {1,2,3}. How shall an array be applied to an expression? What is {1,2,3} of argument [4]? Is it {4,8,12} or {5,6,7} or something else? What is {4,5,6} of argument ["A"]? Not only do you abuse the meaning of HOF, you abuse the meaning of function.

Mathematica allows nonsense inputs; it grants formal manipulations. So Mathematica accepts NestList[{1,2,3},x,6] and produces the expected (nonsense) output: {x, {1,2,3}[x], {1,2,3}[{1,2,3}[x]], ... }.

There is a mathematical sense in which an array represents mathematical function samples, or let us say, delta functions at index coordinates. For these purposes Mathematica offers treatments like interpolating functions, curve fits, and DiracDelta. I don't think those are what you want, but they are the only things that make rational sense of your (mathematical) definition of arrays-as-functions. Otherwise, asserting that "arrays are functions!" is neither a problem statement nor a behavioral specification. It's just meaningless noise.

Mathematica enables fantastic varieties of array manipulation and functional programming, and I have already pointed you in the right directions. It is highly dubious that you can find any problem which cannot be coded elegantly and optimally in Mathematica. Guessing, some hints: Apply replaces the head List with whatever you like, turning arrays into anything. Arrays of functions are possible. Anonymous functions are possible. If you want to consider index values as implicit data, MapIndexed passes them as auxiliary parameters to the mapped function. You can also make index values explicit by various array constructions, e.g. defining each array element as an {index, value} couplet. Probably you should look at MapIndexed, Apply, Thread, level specifications, or maybe Outer and Inner for all I know. Read the friendly help files, Wolfram's are good.

Or, try doing the magic in Lisp, which is more familiar to LtU readers.

Arrays are functions

There is a mathematical sense in which an array represents mathematical function samples, or let us say, delta functions at index coordinates.

No, arrays are functions, not function samples or whatever. The array (or list) [1, 2, 3] is a function from the domain {0, 1, 2} into the set {1, 2, 3}. [1, 2, 3] of [4] is a "type error" because 4 is not on the domain; it's the same as log(-4). The same goes for [4, 5, 6] of ["A"].

You seem to find the idea outrageous, but it's just standard mathematics.

Thank you

I was beginning to think I had got it completely wrong. This is exactly what I was thinking.

Down the rabbit hole

Andrei Formiga: The array (or list) [1, 2, 3] is a function from the domain {0, 1, 2} into the set {1, 2, 3}. Sjoerd Visscher: This is exactly what I was thinking.

The conventional term is array subscript. The need for math, HOFs, or how this latest statement counters my demonstration of NestList gibberish, I fail to see. Sjoerd picked NestList as a test case, and I showed the actual nonsense result. Are you saying that because I missed something about arrays as functions, the NestList result is sensible? I don't see it.

Math is not our disagreement. Modulo formalisms, we said the same thing, that CS arrays can have mathematical interpretations. The choice of formalism (set isomorphisms, delta functions, function samples) is irrelevant. Computer science is our disagreement. Sjoerd seeks vague HOF magic by (a) giving arrays a mathematical function interpretation and (b) eliding the distinction between math and CS to (c) feed arrays-as-functions into HOFs. It doesn't work, guys, and it doesn't even make sense. I did not pick NestList as the test case; Sjoerd did, and I showed the resulting nonsense. Mathematics doesn't define a "type error" (that's a CS concept), and incidentally, log(-4) equals ((i * pi) + log(4)) in mathematics.

An array in CS is a piece of data, like a string or file. A CS array can represent many things (stacks, queues, file sizes, years of employment on successive jobs, etc.). Math functions are one more category of things they can represent; pick your favorite formalism. I do not quibble that mathematical interpretations exist. I quibble over sleight-of-hand re-interpretations as CS functions, and subsequent usefulness in accomplishing Sjoerd's mysterious task (which begs for concrete examples; I can't make heads or tails of his NestList case; it seems bogus to me, and doesn't reflect actual Mathematica output, which I demonstrated.)

Look at a simpler case. I can define a CS function that returns 5 for all inputs. This thing is a CS function, although boring. I can pass this CS function to a HOF. What have I gained? I may as well just use 5 as a straight argument to a plain function, and stop deluding myself that I need or want a HOF.

The situation with arrays is the same. Follow your interpretation faithfully. Take a 3-element array {10,11,12}. We baptise it as a function per your spec. This "function" maps the (array subscript) domain {0,1,2} to the (pseudo-function) range {10,11,12}. We pass this "function" to a HOF per Sjoerd (he wants the HOF, remember). We do that by passing the range {10,11,12} to the HOF. Surprise, we just passed an array to a function.

Call a spade a spade. We passed an array to a function. The recipient may interpret it as a stack, queue, math function, or years of employment, but no such interpretation makes the recipient a HOF in the CS sense, or requires that it be one. What do these weird HOF incantations buy us? What are we really trying to do?

Whatever Sjoerd wants to do, it probably falls into the category of standard array manipulations, functional programming, list comprehensions, or something similar, for which stock tools exist in Mathematica and other packages. So far Sjoerd has not clarified his task or how a mathematical-function interpretation helps it. If we are talking about array subscripts, why can't we just use standard terminology?

The NestList example

Take NestList[{1,3,4,2,3}, 0, 6]

You say then that this produces:

{0, {1,3,4,2,3}[0], {1,3,4,2,3}[{1,3,4,2,3}[0]], ...}

My point is that {1,3,4,2,3}[0] is (almost obviously) reducible to 1. And {1,3,4,2,3}[1] to 3, etc.

That's why I think the result should be {0, 1, 3, 2, 4, 3, 2}

I don't see the point in keeping {1,3,4,2,3}[0] unreduced, and I don't see another valid meaning of the expression.

Pay the cashier on your way out

This answer is what I mean about terminology circles. It begs your question about 'function calling' an array. If the only possible interpretation is array subscript, then just use array subscripts directly (with syntax sugar that suits your fancy). Don't complain that we have a language design problem. See my longer remarks below.

I'm going to be useful

This pure function will allow you to use arrays as functions:

Function[x, Function[y, x[[y]]]]

You could also wrap any array x like this:

(x[[#1]])&

and turn the array into a function.

The only detail to correct your example is that Mathematica starts the index at 1, while 0 indexing an object returns the type (it's actually interesting indexing non-arrays).

NestList[({1, 3, 4, 2, 3}[[#1 + 1]]) &, 0, 6] -> {0, 1, 3, 2, 4, 3, 2}

NestList[({1, 3, 4, 2, 3}[[#1 + 1]]) &, 0, 7] -> {0, 1, 3, 2, 4, 3, 2, 4}

I don't know what Mark's problem is, you must have hit a nerve.

Thanks, now to the point

So arrays don't support the [] operator, and functions don't support the [[]] operator. Just like all other languages I know. (Although usually they are () and [])

There seems to be no language that unites these operators. So I guess there must be a good reason to do that, but I don't see it. Anyone?

Matlab?

In Octave/Matlab, parens serve both these functions. I tend to keep track in my head of which identifiers are functions and which are arrays, suggesting that the indexing distinction makes some sense. Arrays have a dimension/domain that you can query, unlike a typical function, and can only be indexed/called with integers. These additional semantics to me at least make it inconvenient to treat the two as the same sort of thing.

I am receiving mental commands from Altair IV.

I believe that in Scala the "template class" Array[a] is a subtype of Function[Int,a]. In particular, indexing is done via the apply method of class Function[Int,a].

BTW, concerning HOFs and n-dimensional arrays. Define [n] as {0,1,2,... n-1}. A linear array over (i.e., drawing elements from) A of length n is isomorphic to a function [n]->A. A 2-dimensional m-by-n array is representable as a function [m] * [n] -> A. If you curry this, you get [m] -> ([n] -> A), which is isomorphic to the type of linear arrays over [n] -> A of length m, which is isomorphic to the type of linear arrays over [m] -> A of length n.

In answer to Mark's complaint, "What is the point?": the point is that, if we could write functions generic over isomorphism classes of types, then we could reuse functions defined to operate on A-arrays as functions defined to operate on functions of the form [n]->A, and vice versa, and so obtain a more economical and less redundant programming language.

Haskell to the rescue?

Suboptimal, because we can't exchange ($) for (.$.) in all of the available libraries, but:

module GenFun where

import Data.Maybe
import Data.Array

class Mapping a b c | a -> b, a -> c where
(.$.) :: a -> b -> c instance Mapping (a -> b) a b where (.$.) = ($) instance Eq a => Mapping [(a, b)] a b where l .$. el = fromJust $lookup el l instance Ix a => Mapping (Array a b) a b where (.$.) = (!)


It would be cool if ($) was actually defined like (.$.). There are the obvious interactions with laziness, though. Either way, that's a more general function application. (Mental note: think about this for my fantasy language :)

pop-11

Sorry for bumping this old thread, but I just came across this section in the pop-11 primer and remembered this discussion:

Arrays are procedures in Pop-11
.

Not sure if this is exactly what you were after.

Re: More

Even in languages that don't have true multidimensioanl arrays it is possible to have an elegant and fully general syntax for slices, e.g., m[1;;] (same as m[1]), m[;1;] and m[;;1] in K, where m is a 3d structure (actually a list of lists of lists).

Re: More

See Mathematica's documentation for Part and detailed examples to see how All works as a subscript.

Arrays are functions?

Andrei, my experimental language treats arrays as functions with a domain of bounded natural numbers. For example, {3,4,5} is a function with a domain of "the type of natural numbers less than 3".

In my experience, array comprehensions solve the problems of list slicing well. I use a BASIC-inspired function mid(xs,i,n) for slicing which takes elements from the array as, and returns a new array containing just the n elements starting at element i. Thus if a horizontal slice of a 2D array is mid(xs,i,n), a vertical slice is for(xs:xss)mid(xs,i,n). This isn't quite as simple as special-case "multidimensional slicing" syntax could be, but it's reasonable and has the advantage of being very general-purpose.

I treat all arrays as 1D but nestable. Thus there is no syntax like a[i,j] but instead a[i][j]. I think this is the "right way", because it makes higher-order operations like mapping and comprehensions simple -- they don't need to be specialized for arrays of different dimensions and choices of what indices are being iterated over.

Arrays as collections and arrays as mappings (~functions)

(Some of my thoughts on arrays :)

One way to look at (1-dimesional) arrays is like a sequential collection. Sometimes the order matters, sometimes not. The indices doesn't mean much on their own, so one just start indexing at e.g. 0 (or 1 if one likes that better).
Examples : array of subwidgets, array in a queue implementation, array of some kind of collected data (like e.g. user info or experiment result or database record). (Sometimes the indices have specific meaning even though the start index is fixed, of course.)
Language examples : C,Java,Basic,ML,Clean.

Another way is to look at (1-dimesional) arrays is like a partial function from integers to whatever the element type is. A more refined way would then be a total function from a subtype (usually contiguous, from what I know) of integers to the element type. (The implementation of this would then, as we all know, use a memory block as a table instead of how functions are usually implemented.) In this view the indices have a meaning on their own. Here one sometimes also use symbolic constants (e.g. in an "enumeration type") as indices instead of integers in some range. In this case sometimes no special ordering of the constants is intended.
Examples : array indexed by timezone,array holding heap elements (starting from 1,left is 2*i,right is 2*i+1),array indexed by month,array indexed by "paper,scissor and stone",array indexed by lexer/parser token

For multidimensional arrays, one can have nested (~= curried) arrays, where one index out one array and then from that index out again. In this way, there is a total order imposed on the "axes" of the array, and it gets hard to have slices(**) "across" the axis order, e.g. horizontal slices of a 2-dimensional might work, but not vertical slices. (But one might not need any special support from the language to get this limited form of multi-dimensional array slicing here.)
(Another issue here is whether or not the nested arrays on the same level must have the same shape. E.g. of "must" is C (the arrays described by the array types, not the array of pointers variety), E.g. of "don't have to" is Java)
Language examples : C,Java,Pascal(***),Ada.

Or one can have multidimensional arrays where one index out an element with all indices at once. This though probably requires language support for slicing. (One could of course still have nested multidimensional arrays, as well, in the same language.)

One can view this latter kind of multidimensional arrays as arrays that are indexed by a tuple (vector) of individual indices. (One can easily imagine extending the allowable kinds of index types some more ..)

So, there's probably a use for both collection-arrays and mapping-arrays, IMO.

(*) The type of arrays in Haskell still doesn't tell what range the array indices have.

(**) By slice, I mean either that it should be shared with the array it was taken from, or it should be possible to manipulate (e.g. update) the slice in place, or both. (I.e. just a copy of part of the array would not count in the sense used in this post.)

(***) IIRC, Pascal has syntax that looks like non-nested multi-dimensional arrays, but the type is the same as a corresponding nested one, and one can't slice across the axes.

(Hm, got a bit long)

--
Stefan Ljungstrand

Reshaping

One of the cool things you can do with APL (and J) arrays is reshape them. A 1D 12 element array can be operated on as if it a 2D 3*4 array, or a 2*2*3 array etc.

Why is that cool?

I don't see a good use case. When does both a 12 element array and a 2D 3*4 array with the same data make any sense? Ok, it wouldn't hurt to have as an obscure library function, but why did you want to mention this here specifically? (just curious)

When does both a 12 element a

When does both a 12 element array and a 2D 3*4 array with the same data make any sense?

Imagine you have a two-dimensional array of quarterly sales figures. To get the sales for a quarter you index by year (0,1,2...) and then quarter. To get lifetime sales to date, you reshape the array to a single dimension and sum it.

Train derails, not many dead

Apologies for seeming irritated. The problems were abuse of terminology, clarity of problem statement, and utility of the exercise. I feel the same after the latest from Sjoerd and Frank. (Frank, see below.) I tried to escape the conversation earlier, foreseeing this train wreck. But I am trying to help.

Talking about array subscripts without using the accepted term is weird. Maybe that's just me. Nonstandard terms leave unclear whether the novelty lies in the concepts or in the terms. I worry about self-deception. For one example, we might confuse syntax sugar with true language novelty. For another, the anonymous function (x[[#1]])& does not turn an array into a function. It defines an array subscript function. All languages know how to do this, and the terminology is well established. The array remains a piece of data. The function to be associated with the array, if any, remains a question of data interpretation which cannot be automated (auto-deduced). That is why I mentioned interpolating functions and so on. If you have an array, you can apply an interpretation of some sort to construct a function on a domain-specific, case-by-case basis.

In the clarity and utility departments, here is what Mark doesn't get about Sjoerd's NestList example. I missed the motivation for defining an array abstractly as a function from domain to range, then using the range to store domain values (the data interpretation), then feeding the result into a recursive HOF (NestList), then imagining that we achieved some novel language power. This example is very convoluted. Sure, it can be done. How does it help us? Even Frank's formality suffers under this example. Sjoerd's NestList example doesn't have Frank's [n]->A, but [n]->[n]->[n]->[n]->... At this stage we have something more akin to cellular automata than something relevant to programming languages. So forgive my confusion. This expansion clarifies the operation:

 subscriptOf[array_,index_] := Part[array,index+1]; X = {1,3,4,2,3}; seed = 0 subscriptOf[X,seed] subscriptOf[X,subscriptOf[X,seed]] subscriptOf[X,subscriptOf[X,subscriptOf[X,seed]]] subscriptOf[X,subscriptOf[X,subscriptOf[X,subscriptOf[X,seed]]]]   0 1 3 2 4 

It would make sense to talk about Nth subscripts if X were N-dimensional. I asked for simpler examples with concrete utility and relevance. Frank, I'd like you to demonstrate your formalism in 'wish-it-were-possible' pseudo-code with

[n] = {1,2,3,...n}
A = the set of prime numbers
(function: [n] -> A) = Prime[5n]
(function: [m]*[n] -> A) = Prime[5mn]
pick any HOF, but keep things simple (e.g. nonrecursive)

Abstractions are only as good as their best concrete cases, someone has said. They can lead to confusions of their own.

What Frank specified isn't what Sjoerd specified. Taking the "Sjoerd array subscript" of the factorial function, per Sjoerd, is not Frank's reuse functions defined to operate on A-arrays as [higher-order-by-definition] functions defined to operate on functions of the form [n]->A, and vice-versa. Factorial is neither a HOF nor operates on arrays. So it's off Frank's radar. Sjoerd, in his factorial case, wants to reuse a function defined on Z as a function defined on arrays of Z. In Mathematica, Sjoerd's spec is easily satisfied by Listable. That's why I brought it up. You just set the function attribute Listable, and voila, your function now works on arbitrarily dimensioned arrays, element by element. Many of Mathematica's stock functions have this attribute. Hence my demonstration of Table above, and Range below:

 Range[3,12]   {3,4,5,6,7,8,9,10,11,12}   Attributes[Factorial]   {Listable,NumericFunction,Protected}   (* zero-D *) Factorial[3] (* one-D *) Factorial[Range[3,12]] (* two-D *) Factorial[Table[i+j,{i,3,6},{j,0,4}]]   6 {6,24,120,720,5040,40320,362880,3628800,39916800,479001600} {{6,24,120,720,5040},{24,120,720,5040,40320},{120,720,5040,40320,362880},{720, 5040,40320,362880,3628800}} 

This and my first example satisfies Sjoerd's semantic spec. We may quibble over syntax, but surely LtU is above arguments about syntax sugar? (Cough, ahem.) Here is some syntax sugar then. It makes the "Sjoerd array subscript operator" look like a true array subscript (double brackets).

 Clear[myFactorial] myFactorial[n_Integer] := Factorial[n] myFactorial /: myFactorial[[i_Integer]] := myFactorial[i]; SetAttributes[myFactorial, Listable] myFactorial /: myFactorial[[imin_Integer, imax_Integer]] := myFactorial[Range[imin, imax]]; 

Demos:

 (* Normal function call *) myFactorial[12] (* "Sjoerd array subscript" syntax sugar *) myFactorial[[12]]   479001600 479001600   (* Normal function call exploiting Listable *) myFactorial[Range[3,12]] (* "Sjoerd function slice" syntax sugar *) myFactorial[[3,12]]   {6,24,120,720,5040,40320,362880,3628800,39916800,479001600} {6,24,120,720,5040,40320,362880,3628800,39916800,479001600} 

Where's the novelty?

For me the novelty is in minimalistic language design, not utility per se. Take a look at this example:

fib[0] = 1
fib[1] = 1
fib[n] = fib[n-1] + fib[n-2]

You can call this a function definition, or an array definition with some kind of defaulting mechanism.

Comming from Mathematica there may be no good reason to combine functions and arrays. But from a language design perspective I see no good reason to separate them.

Huh?

Ugh, you had to pick another recursive function. Please I beg you, pick another that isn't.

Let's call things what everyone else calls them, shall we? If fib is an array, what are the array dimensions of fib? It's not an array, it's a function.

I showed that Mathmatica does "combine" them, as you like to phrase it - incorrectly I think, but still. Other languages can do the same tricks. However yours seems not a language design issue, but a syntax sugar issue. On that basis I don't think there is any novelty at all.

The semantics of your proposal are that arrays can be functions - but only under an interpretation of array subscript. That's just syntax sugar for array subscripts. Then we have functions that can be arrays - with semantics identical to mappings across arrays. More syntax sugar.

Still, maybe my code snippets will be helpful in some way. Good luck!