# definition of an array

I'm teaching a programming class in Python, and I'd like to start with the mathematical definition of an array before discussing how arrays/lists work in Python.

Can someone give me a definition?

-
An array docs.python.org/library/array.html and a list docs.python.org/tutorial/datastructures.html are not the same thing in Python. An array is contiguous in memory and has essentially constant access time. A list (a built-in type) is sparse in memory and has logarithmic access time. These facts are specific to Python and are not generally true in other languages. In more general contexts "list" often means a linked-list which has linear access time but essentially constant insertion time. (I am not a Python expert.) –  Dan Brumleve May 18 '11 at 3:29

I'd go with comparing an array to a matrix. That way when you introduce arrays of arrays, the mental leap will be easier for your students to make.

-
Does python treat an array like a $1\times n$ matrix or more like an $n\times 1$ matrix? –  wckronholm May 18 '11 at 3:40
lewellen and wckronholm, a Python array is not like a matrix because it is linear and parameterized by a "typecode". See the examples in the first link in my comment. –  Dan Brumleve May 18 '11 at 4:12
Dan, I think your interpretation of Ramy's question is focused on how interpreters of python look at arrays (i.e., implementation details more suited for computer science students), vs how end users of the language would look at arrays (e.g., math/physics/etc students). I think that Ramy would benefit presenting both views to his students (given it makes sense for the scope of his class). –  lewellen May 18 '11 at 4:50
lewellen, I agree. "list" and "array" have the same informal meaning but in Python they are different and it is important for a Python programmer to understand this distinction as well as the specific distinction in Python. –  Dan Brumleve May 18 '11 at 5:02
Yeah, the fact is that these programmers are all beginners (otherwise I wouldn't be teaching them!) and though I agree the difference between lists and arrays is important I don't think it'll affect they're overall understanding of lists until they get into some particularly CPU intensive work. Which may never happen. –  Ramy May 18 '11 at 20:55

An array is a tuple with elements taken from a specific set $S$. When the array can contain variables of a specific type, then the set is the set $S$ consists of all possible values of this type.

This is the most general definition, as a mathematician I don't talk about implementation details like the memory structure or the complexity of operations on the array.

It may be useful to consider more specific examples: If you fix a field $k$, consider a $k$ vector space $V$ of dimension $n$ and accept a specific data type of Pyhton as a representation of elements of $k$, you can interpret an one-dimensional $k$-array of length $n$ as a representation of a vector in $V$ (with respect to a fixed basis that is left implicit).

Similarly, one could interpret a two dimensional array of length n*n as representing a matrix, i.e. a linear transformation of $V$ etc.

-