Discussion 4: Mutability, Abstract Data Types

Abstract Data Types

Data abstraction is a powerful concept in computer science that allows programmers to treat code as objects — for example, car objects, chair objects, people objects, etc. That way, programmers don't have to worry about how code is implemented — they just have to know what it does.

Data abstraction mimics how we think about the world. For example, when you want to drive a car, you don’t need to know how the engine was built or what kind of material the tires are made of. You just have to know how to turn the wheel and press the gas pedal.

An abstract data type consists of two types of functions:

  • Constructors: functions that build the abstract data type.
  • Selectors: functions that retrieve information from the data type.

Q1: Word

In this problem, we will implement two data abstractions from scratch to represent a language! Let's first build an abstraction for words, which will compose each language.

The word abstraction stores:

  1. a word's name
  2. a word's definition in English

Your first job will be to create the constructors and selectors for the word type in two ways (denoted by a and b).

  • A clean, typical approach would be to use a list pair to bundle together attributes of our type. Can you come up with two other implementations of the word ADT? Some ideas include using a dictionary or higher-order functions!

Note: Concerning ourselves with the implementation of this ADT does put us "beneath" the abstraction barrier. However, a takeaway from this problem is that as we move towards higher-level functionalities (like translation), we no longer have to worry about the specifics of our original implementation. These low-level details are abstracted away by our constructors and selectors!

Run in 61A Code

Q2: Language

Now, implement an abstraction for language. The language ADT stores:

  1. a language's name
  2. a list of word's present in the language

Finally, using both the word and language ADTs, implement the two following functions:

  • translate, which takes source_word, a word abstraction, and returns the name of the translated word in the target language. If the word cannot be found, return 'Undefined'.
  • update, which updates a language's list of words with new_word.

Hint: When we translate a word to a different language, what attribute of the word remains the same? From there, it's just about searching for and accessing that attribute at the right location!

Hint: With abstract data types, we can construct ("create") and select ("read") data, but we can't exactly mutate them. To "update" a language, we should instead construct and return a new language altogether!

Run in 61A Code

Mutability

Q3: Shuffle

Define a function shuffle that takes a sequence with an even number of elements (cards) and creates a new list that interleaves the elements of the first half with the elements of the second half.

To interleave two sequences s0 and s1 is to create a new sequence such that the new sequence contains (in this order) the first element of s0, the first element of s1, the second element of s0, the second element of s1, and so on.

Note: If you're running into an issue where the special heart / diamond / spades / clubs symbols are erroring in the doctests, feel free to copy paste the below doctests into your file as these don't use the special characters and should not give an "illegal multibyte sequence" error.

Run in 61A Code