Discussion 5: Abstract Data Types, Recursion

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

Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. Instead of tackling a complex task all at once, recursion breaks it down into simpler steps until it reaches a base case.

Many students find this topic challenging. Everything gets easier with practice. Please help each other learn.

Q3: Swipe

Implement swipe, which prints the digits of argument n, one per line, first backward then forward. The left-most digit is printed only once. Do not use while or for or str. (Use recursion, of course!)

Run in 61A Code

Q4: Skip Factorial

Define the base case for the skip_factorial function, which returns the product of every other positive integer, starting with n.

Run in 61A Code

Q5: Recursive Hailstone

Recall the hailstone function from Homework 2. First, pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Complete this recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

Run in 61A Code