Skip to content

Abstract Data Type

Learning Objectives

At the end of this sub-unit, students should

  • know how to design abstract data type using dictionary.

Name vs Index

Our previous implementation of ADT uses tuple because we have not learnt about dictionary. Consider the implementation of a cartesian coordinate (x, y) as follows.

Cartesian Coordinate with Tuple

1
2
3
4
5
6
7
8
def make_coord(x, y):
  return (x, y)

def get_x(coord):
  return coord[0]

def get_y(coord):
  return coord[1]

What is the problem with this design? If we never break abstraction, then nothing is wrong. However, if we are working in a group, then we may come into arguments on whether the x-coordinate should be at index 0 or 1.

One of the way to resolve this problem is to not care about the ordering and use unordered collection. Now we need to name the property instead of using a number. Once our code becomes larger, remembering which index corresponds to which property can be quite complicated. This may complicate reading the code that is within the abstraction.

For instance, consider the following code.

1
2
def f(c1, c2):
  return (((c1[0] - c2[0]) ** 2) + ((c1[1] - c2[1]) ** 2)) ** 0.5

Of course, the way the code is written is bad. It can easily be improved with a proper variable naming. But the use of indexes still complicates reading the code. We can improve this by naming the properties as follows.

Cartesian Coordinate with Dictionary

1
2
3
4
5
6
7
8
def make_coord(x, y):
  return { 'x': x, 'y': y }

def get_x(coord):
  return coord['x']

def get_y(coord):
  return coord['y']

We use the key 'x' to represent the x-coordinate and the key 'y' to represent the y-coordinate. Now the code above can be written in a more readable way.

1
2
def f(c1, c2):
  return (((c1['x'] - c2['x']) ** 2) + ((c1['y'] - c2['y']) ** 2)) ** 0.5

We can always argue that we can still be fighting about the proper naming of the properties. Who is to say that 'x' is better than 'x-coord'. However, hopefully we can agree that it is still easier to read than the index 0.

This will be more useful with more properties. For instance, a student can be represented as either one of the following. Which one is easier to read when used?

  • Tuple

    1
2
3
4
5
6
7
    def make_student(name, year, faculty, gpa):
  return (
    name,
    year,
    faculty,
    gpa
  )

  • Dictionary

    1
2
3
4
5
6
7
    def make_student(name, year, faculty, gpa):
  return {
    'name':    name,
    'year':    year,
    'faculty': faculty,
    'gpa':     gpa
  }