Skip to content

Multi Dimensional Array

Learning Objectives

At the end of this sub-unit, students should

  • understand the difference between array and list of list.
  • understand the inductive view of array and list of list.

Terminology

Recap our inductive definition of a list.

Inductive List

1
2
list :: []               # empty list
     :: [item] ++ list   # the first item (list[0]) followed by the rest of the list (list[1:])

List of List

We know that item can actually be anything including another list. If we are only considering the item as either a list or not a list, we can expand our inductive definition to the following.

Inductive Nested List

1
2
3
list :: []               # empty list
     :: [item] ++ list   # non-list followed by list
     :: [list] ++ list   # list followed by list

We call this a nested list or a list of list because we do not put any restriction on the structure of the inner list. An example of a list of list is shown below.

1
2
3
4
lst1 = [1, 2, 3]
lst2 = ['A', 'B']
lst3 = [lst1, lst2, 'CS1010S']
print(lst3)

1
[[1, 2, 3], ['A', 'B'], 'CS1010S']

Array

If we put a restriction on the inner list, we can get a more regular structure. We will first define a structure called list[n] to mean a list with exactly n non-list element.

1
list[n] :: [e1, e2, ..., en]

Now we can define a table with n columns as a list where each item is exactly of type list[n].

Table

1
2
3
list[n] :: [e1, e2, ..., en]
table :: []
      :: [list[n]] ++ table

This is a 2-dimensional structure that is just our typical table. An example is given below. The code is shown on the left and the corresponding tabular form is shown on the right. We give an additional meaning to each column in the tabular form that is part of the header.

  • Code

    1
2
3
4
5
6
7
8
9
    >>> table = [
...   [4, 'CS1010S'],
...   [4, 'CS2030S'],
...   [4, 'CS2040S'],
...   [8, 'CS3203']
... ]
...
[[4, 'CS1010S'], [4, 'CS2030S'],
 [4, 'CS2040S'], [8, 'CS3203']]

  • Tabular

    MC Course Code
    4 CS1010S
    4 CS2030S
    4 CS2040S
    8 CS3203

Differences

We can extend this table into a higher-dimensional structure. Instead of a table, we can also have a rectangular cuboid or even higher dimensions. Most of the time, we will be dealing with 2-dimensional array.

But the main idea of an array is that it must have a regular structure. If we look back at the table, we can describe it using two numbers: r and c. We say that r is the number of rows and c is the number of columns. The size of the table is r * c.

As our representation of table above shows, a table is a list of rows. There are r number of element on the table which corresponds to the number of rows. Each row is a list with c element that corresponds to the number of columns.

To access the ith row and jth column of a table tbl, we can use the following expression.

1
tbl[i][j]

How do we remember this? We can use the popular nursery rhyme to help us.

Row, Row, Row, your Boat.

So the first index is the row and not the column.

On the other hand, a list of list need not have a regular structure. So a table is a list of list but not all list of list is a table. If we extend this to higher dimensions, we simply say that the regular structure is called an array. Of course, this terminology is not universal because the term array is already used by many other programming language to mean a list.

Higher Dimensional Array

We know that a table is a 2-dimensional array. What about a 3-dimensional array? First, we consider another kind of 2-dimensional array. The non-list element of this 2-dimensional array is a in integer with a value between 0 and 255 inclusive of both.

What is this 2-dimensional array? Depending on the interpretation of the integer number, it can be almost anything. But in our interpretation, it is a black and white image. In this representation, the integer value is called the grayscale value with 0 representing black and 255 representing white. This element is also called the pixel (picture element). The row and column indexes represent the position of the pixel on the image.

Using this representation, we can draw a right arrow as follows.

BW01

BW02

1
2
3
4
5
6
7
img = [
  [255, 255, 128, 255, 255],
  [255, 255,  64, 128, 255],
  [  0,   0,   0,  64, 128],
  [255, 255,  64, 128, 255],
  [255, 255, 128, 255, 255]
]

How do we expand this into higher dimension? We can store more information. Instead of storing only the grayscale value, we can store three colors: red, green, and blue. It can be shown that these three colors are sufficient to construct all possible colors. So now we have 3-dimensional array by replacing 255 by [255, 255, 255].

What about higher dimension still? In video, we can represent the entire colored image as an element of a list called a frame. This list is ordered by time. In modern standard, each element is an image to be displayed for 1/60 of a second to make up 60fps (i.e., frame-per-second). A better standard is 1/120 of a second for 120fps.

Another potential extension to higher dimension is to extend the physical dimension. Instead of representing a flat image, we can instead represent a volume. This element is called a voxel (volume element) and this is one way we can represent a 3-dimensional colored model. It is a 4-dimensional array as we need one dimension to represent the color. Of course we can also then represent a moving 3-dimensional colored model as a 5-dimensional array by further adding the dimension of time.

Summary

Summary

Terminology Description
List of List A list where each element is either an inner list or an item that is not a list. There must be at least one element that is a list in the outer list.
Array A list of list with a regular structure forming a rectangular cuboid.