0
$\begingroup$

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?

  • 0
    An array http://docs.python.org/library/array.html and a list http://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.)2011-05-18

2 Answers 2

2

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.

  • 1
    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.2011-05-18
0

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.