Skip to content

Abstract Data Type

Learning Objectives

At the end of this sub-unit, students should

  • appreciate the benefit data abstraction.
  • know how to design abstract data type.

Type as Operations on the Data

One of the main concept regarding values and types is that the operation on a value depends on the type of the value. If there are type mismatch, we will get an error. Another main concept is about not worrying about the details. We call this abstraction and we have so far abstracted computations into functions.

Then in our explanation of sequence, we introduce a new idea. We define a sequence as a type such that the three operations on sequence are allowed: indexing, slicing, and iteration. There may be more, but at least those three. We will now take this idea further.

Consider a Burger. Obviously, there is no actual burger inside our computer. Instead, we should have a representation of a burger. When we want to represent a burger, what kind of information do we need? Do we need to know each of the molecules that make up the bread, patty, and others?

This is where the idea of data abstraction comes. We do not need to know all of those irrelevant information. What we really need is how to work with the data. In the case of a burger, maybe what we need to be able to do are only the following.

  1. Add ingredients.
  2. Remove ingredients.
  3. Compute the total price based on the price.

We may even restrict the ingredients to only some specific ingredients. Given these operations, our representation of a burger is a simplified representation that allows us to at least solve this. There is no just one representation, there can be many. But the more complex the representation is (e.g., a 3D visualization of a burger), the harder it is for us to implement compared to the simpler representation (e.g., an unordered collection of ingredients).

Regardless of the representation chosen, we call the data type that can perform the above operations as abstract data type (ADT). It is abstact because we do not currently care about the concrete implementation.

Making a Burger

So let us take the idea of the burger and create the ADT for a burger. To do that, we consider the three operations that we need to be able to do and think about the name, parameters, and the expected behavior. All of these typically will be specified in the problem description, but it is also useful to be able to design our own.

  1. Add ingredients: add_ingredient(burger, ingredient).
    • Takes in a burger and an ingredient (a str).
    • The ingredient will be one of the valid ingredient below.
    • Returns a new burger with the ingredient added.
  2. Remove ingredients: remove_ingredient(burger, ingredient)
    • Takes in a burger and an ingredient (a str).
    • If the ingredient is in the burger, then return a new burger with one copy of ingredient removed from burger.
    • Otherwise, return the burger unchanged.

  3. Compute the total price based on the price: compute_price(burger).

    • Takes in a burger.
    • The ingredients in the burger will be one of the valid ingredient below.
    • Return the total price of the burger based on the price of the ingredient below.
    • The price will be given as an integer in the currency ₿.
    Ingredient Price
    Bread 1
    Beef 7
    Chicken 4
    Vegetables 2
    Mushrooms 3
    Cheese 1
    Onions 1
    Hash Brown 2

Now that we know the operations that we need to create. We need to figure out an actual representation. Since the ingredient is a string, we may actually simply use string to represent a burger. This is quite tedious, so we will simply use a tuple.

Once we are set on using a tuple, we need to know what should be the initial burger. There are two choices.

  • An empty tuple.
  • A tuple with two bread: the top and bottom buns.

Again, we can choose either one, so we will look for the simplest one which is an empty tuple1. Given this decision, we can even design a function to create an empty burger.

  • Create an empty burger: make_burger().

The next thing to do is to figure out what to put in the tuple. There are many other possibilities but we will highlight two potential ideas.

  • The ingredient as a string in no specific order.
  • A pair (ingredient, amount) to record how many ingredients in the burger.

The first option is the simplest, so we will choose that. However, we will give an implementation of the second too. You are advised to attempt it on your own first before looking at our implementation.

Burger Design #1

So to recap, our design choices for a burger is the following.

It is a tuple of ingredient (a str) in no specific order.

We want our burger to support the following operations:

  1. make_burger()
  2. add_ingredient(burger, ingredient)
  3. remove_ingredient(burger, ingredient)
  4. compute_price(burger)

For example, a double cheese hamburger can be represented as the following tuple.

('Bread', 'Onions', 'Vegetables', 'Beef', 'Cheese', 'Beef', 'Bread')

The price for this burger is ₿20.

Burger #1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def make_burger():
  return ()

def add_ingredient(burger, ingredient):
  return burger + (ingredient,)  # or return (ingredient,) + burger

def remove_ingredient(burger, ingredient):
  for i in range(len(burger)):
    if burger[i] == ingredient:          # found
      return burger[:i] + burger[i + 1:] # remove
  return burger                          # original

def compute_price(burger):
  price = 0
  for ingredient in burger:
    price = price + ingredient_price(ingredient)
  return price

The implementation of ingredient_price(ingredient) is left as an exercise to the reader. It is simply a sequence of if-statements.

Benefit of ADT

Given an ADT such as burger ADT above, we can say that we have a type which we will call burger. If we are only using the operations defined for burger, then it should not matter what the implementation of a burger is. This is why it is called an abstract data type.

One potential use is the following burger creation. We will use a typical double cheese hamburger.

1
2
3
4
5
6
7
8
9
burger = make_burger()
burger = add_ingredient(burger, 'Bread')
burger = add_ingredient(burger, 'Onions')
burger = add_ingredient(burger, 'Vegetables')
burger = add_ingredient(burger, 'Beef')
burger = add_ingredient(burger, 'Cheese')
burger = add_ingredient(burger, 'Beef')
burger = add_ingredient(burger, 'Bread')
print(compute_price(burger))

1
20

Consider a different implementation of a burger with the following design.

Burger Design #2

Our second design is as follows.

It is a tuple of pair (ingredient, amount) where ingredient is a string and amount is a non-negative integer. If an ingredient is not part of the burger, we either omit the pair or include it with an amount of 0.

We want our burger to support the following operations:

  1. make_burger()
  2. add_ingredient(burger, ingredient)
  3. remove_ingredient(burger, ingredient)
  4. compute_price(burger)

For example, a double cheese hamburger can be represented as the following tuple.

(('Bread', 2), ('Onions', 1), ('Vegetables', 2), ('Beef', 2), ('Cheese', 1))

The price for this burger is ₿20.

Burger #2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def make_burger():
  return ()

def add_ingredient(burger, ingredient):
  for i in range(len(burger)):
    if burger[i][0] == ingredient:
      return burger[:i] + ((ingredient, burger[i][1] + 1),) + burger[i + 1:]
  return burger + ((ingredient, 1),)

def remove_ingredient(burger, ingredient):
  for i in range(len(burger)):
    if burger[i] == ingredient:
      if burger[i][1] > 0:
        return burger[:i] + ((ingredient, burger[i][1] - 1),) + burger[i + 1:]
      else:
        return burger
  return burger

def compute_price(burger):
  price = 0
  for pair in burger:
    price = price + ingredient_price(pair[0]) * pair[1]
  return price

The implementation of ingredient_price(ingredient) is left as an exercise to the reader. It is simply a sequence of if-statements.

If we run the same sequence of code above, we will still get 20 as our answer. This highlights the benefit of using ADT: if we are using only the operations allowed for the data, we do not have to care about the implementation of the data.

Extending the Operation

If we wish to extend the capability of burger, we have two options. The first is to assume a specific implementation (e.g., design #1) and implement the capability (i.e., function) using this assumption. The second is to simply call the 4 functions we have implemented before. Given our discussion on function abstraction, we hope that we can agree that the second approach is better. So let us illustrate this. We will extend the capability of our burger representation by adding the following function.

  • purge_ingredient(burger, ingredient) removes all occurrences of the given ingredient from the burger.

Here is one possible implementation that does not make any assumption on the underlying implementation. The idea is to try to remove an ingredient once. Eventually, there is nothing to remove. At this point, the function has no effect. So we can stop and return the resulting burger.

Purge Ingredient

1
2
3
4
5
6
def purge_ingredient(burger, ingredient):
  prev = burger
  curr = remove_ingredient(burger, ingredient)
  while prev != curr:
    prev, curr = curr, remove_ingredient(burger, ingredient)
  return curr

Try to use this on both implementations above. By design, it should work for both implementation. This is achieved by assuming nothing about how a burger is implemented. Instead, we look only at what can be done on a burger.

The downside is that the function may take longer to complete. The number of iterations needed is potentially enormous as we repeatedly check the burger from left to right instead of looking at each ingredient once.

  1. This can accommodate KFC double down burger which is two friend chicken breast sandwiching a hash brown. ↩