EX07 - List Utility Functions Continued

The following exercises are extensions of those in the previous set. These utility functions continue to emphasize practice algorithmic thinking. In this exercise you will also continue testing the functions you write by writing tests which demonstrate their correctness in a variety of cases.

For this second set of functions you are permitted to use for in loops and, if you’d like, range objects. Note, however, the limitations below still apply and there are some algorithms which are best implemented using subscription and indices directly. These exercises give an opportunity to think through the possible different means of implementations and you should aim to implement the simplist while still avoiding the following limitations:

• Cannot use other built-in function besides len - specifically not max, min, slice
• Cannot use slice notation in conjunction with the subscription operator
• Cannot use the List class’s + or == operators nor built-in methods beyond append

You are permitted to use any of the above in your test functions, though.

is_equal

Given two Lists of int values, return True if every element at every index is equal in both Lists.

>>> is_equal([1, 0, 1], [1, 0, 1])
True
>>> is_equal([1, 1, 0], [1, 0, 1]))
False

Your implementation should not assume the lengths of each List are equal.

This concept is called deep equality. Two separate List objects on the heap may be distinct objects, such that if you changed one the other would remain the same. However, two distinct objects can be deeply equal to one another if what they are made of is equal to each other in essence.

Setup and Implementation

1. Create the Python program file
   1. In the comp110/exercises directory create a directory named ex07_list
   2. In the comp110/exercises/ex07_list directory create a file named utils.py
2. Add in a docstring describing your file in a complete sentence, as well as an __author__ variable containing your PID as a str.
3. At the top of your file, type from typing import List. This will allow you to make use of the List type in Python.
4. Next, define a skeleton function with the following signature:
   1. Name: is_equal
   2. Parameters: Two lists of integers.
   3. Returns: True if lists are equal, False otherwise.
5. Implement the is_equal function as described above.

Testing

1. Create the Python test file in the comp110/exercises/ex07_list directory, create a file named utils_7_test.py
   • We are adding the 7 just because the name collision with the previous exercise’ test names would have otherwise cause issues.
   • Notice this file is named with the suffix _test.py indicating to the PyTest framework this file should be searched for test functions.
2. Add in a standard, descriptive docstring as well as an __author__ variable containing your PID as a str.
3. Import your is_equal function.
4. Add tests to cover not just the case where lists are equal, but think carefully through cases of lists that are not equal in different ways, including lengths.

Idiomatic Python Equivalent of is_equal

Your is_equal function is a reproduction of a Python’s List’s built-in == operator when used on two List objects. Compound types, such as List and even custom ones such as those we will write soon, can define their own algorithms for operators such as == through what is called operator overloading.

>>> [1, 1, 0] == [1, 1, 0]
True
>>> [1, 1, 0] == [1, 0, 1]
False

concat

In this exercise you will write a function named concat. Given two Lists of ints, concat should generate a new List which contains all of the elements of the first list followed by all of the elements of the second list.

Setup and Implementation

Define your function in the ex07_list/utils.py file.

1. Name: concat
2. Parameters: Two lists of ints.
3. Returns: A List containing all elements of the first list, followed by all elements of the second list.

concat should NOT mutate (modify) either of the arguments passed to it.

Testing

Add tests to the ex07_list/utils_test.py file which demonstrate the correctness of your concat function. Be sure to consider edge cases which include empty lists on either side.

Idiomatic Python Equivalent of is_equal

Python’s List objects use operator overloading to appropriate the + operator for concatenation, just like with str values:

>>> [1, 1, 0] + [1, 1, 0]
[1, 1, 0, 1, 1, 0]

Note that a new List, with the elements copied from each of the operands, results from the evaluation of concatenating two lists, just like your function implements.

sub

In this exercise you will write a function named sub. Given a List of ints, a start index, and an end index (not inclusive), sub should generate a List which is a subset of the given list, between the specified start index and the end index - 1. This function should not mutate its input list.

Example usage:

>>> a_list = [10, 20, 30, 40]
>>> sub(a_list, 1, 3)
[20, 30]

Setup

Next, define a skeleton function with the following signature in ex07_list/utils_test.py:

1. Name: sub
2. Parameters: A list and two ints, where the first int serves as a start index and the second int serves as an end index (not inclusive).
3. Returns: A List which is a subset of the given list, between the specified start index and the end index - 1.

If the start index is negative, start from the beginning of the list. If the end index is greater than the length of the list, end with the end of the list.

Testing

Add tests to assert the correctness of your implementation.

Idiomatic Python Equivalent of sub

Python has a special subscription notation called slice notation related to the built-in slice function. Typically, in Python, you would achieve the results of sub with the following, an example of slice indexing:

>>> a_list = [10, 20, 30, 40]
>>> a_list[1:3]
[20, 30]

splice

In this exercise you will write a function named splice. Given a List of ints, an index, and another List of ints, splice should generate a new List. The new List should contain the Elements of the first list, with the Elements of the second list spliced in at (inserted at) the specified index. For example:

>>> splice([1, 1, 1, 1], 2, [0, 0, 0, 0])
[1, 1, 0, 0, 0, 0, 1, 1]

Setup

Define a skeleton function with the following signature:

1. Name: splice
2. Parameters: An int list, an int index, and another int list, where the index will be used to know where to insert the second list into the first list.
3. Returns: A new List containing elements of the second list “spliced” into those of the first.

Neither input list should be mutated in the above.

If the index is negative, insert the second list before the first list.

If the index is greater than the length of the first list, append the second list directly following the fist list.

Hint: You can implement splice in terms of two functions you previously implemented in this exercse rather than from scratch. You are encouraged to make use of the functions implemented earlier. Imagine how you can break down the splice process in terms of other functions written, rather than not making use of any.

Testing

There are a number of edge cases you will want to carefully test for the splice function. Think about tests for empty lists and different locations of the index in the first list.

Idiomatic Python Equivalent of splice

Python developers would likely combine the use of the overloaded + operator and the slice subscription notation to pull off splice in a simple, single line of code. See if you can figure out how, based on the examples of these concepts in earlier idioms above, after you’ve implemented your version of splice.

Hand-in

Go ahead and delete any submission zips lingering around in your workspace from the previous exercise.

When you are ready to submit for grading, close out any open Python Debug Console terminals using the Trash Can and then open up a clean, new terminal.

python -m tools.submission comp110/exercises/ex07_list

This should produce a submission timestamped with the current date/time for uploading on Gradescope.

Submissions on Gradescope will open as soon as it is ready and an email will be sent out.