EX05 - List Utility Functions

Art students intentionally reproduce great works of art to develop their own skills and techniques. The purpose isn’t to become an imitator, but to deepen an understanding of important work and styles that came before you.

Reverse engineering algorithms and abstractions in computer science is of the same spirit! In this exercise you will implement algorithms to practice computational thinking. You will gain familiarity with the names and behaviors of commonly useful functions.

Since the work you do is reproducing tried and true abstractions of the past, in the future you can and should use your language’s preferred functions and idioms instead. In this exercise we will show you how to achieve the same functionality using idiomatic Python in the future. Your function implementations may only make use of the built-in len function, and a List object’s methods append and pop.

Specifically off-limits in this exercise are the following. Making use of any of the following will result in no credit for the function you use them in:

• 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
  • Note: You can use + and == for individual elements, just not entire Lists.

count

Given a List of int values, and an int to search for, count should return the number of times the number you are searching for appears in the List. Here is an example use case of your function once completed:

>>> count([1, 0, 1], 1)
2
>>> count([1, 1, 0], 0)
1
>>> count([110, 110, 110], 1)
0

Your implementation should not involve the creation of another List.

Setup and Implementation

1. Create the Python program file
   1. In the exercises directory create a directory named ex05
   2. In the exercises/ex05 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: count
   2. Arguments: A list of integers as well as a number to search for.
   3. Returns: The counteded number of occurences of the number you are searching for.
5. Implement the count function as described above.

Testing

1. Create the Python test file in the exercises/ex05 directory, create a file named utils_test.py
   • 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 count function: from exercises.ex05.utils import count
4. Add a test function, such as:

def test_count_one() -> None:
    """Test counting a single instance of the needle in the haystack."""
    assert count([1, 1, 0, 1, 20, 100], 0) == 1

5. Use the Testing pane to search for tests and try running your test. Once it is failing, see if you can get this test to pass.
6. Add additional tests! Remember to change their function names and rediscover tests as you add them. Test functions must have unique names and their names must begin with test_. Can you think of other examples that are particularly interesting? You probably want to test what happens when the search value isn’t found at all and when it is found more than once. Your goal with testing is to prove the correctness of your implementation.

Idiomatic Python Equivalent of count

Your count function is a reproduction of a Python’s List’s built-in count method. Since it’s a method, rather than a function, notice the list it is counting comes before the dot and the search value is the sole argument to the method call.

>>> [1, 1, 0].count(1)
2
>>> [1, 1, 0].count(0)
1

all

In this exercise you will write a function named all. Given a List of ints and an int, all should return a bool indicating whether or not all the ints in the list are the same as the given int. Example usage:

>>> all([1, 2, 3], 1)
False
>>> all([1, 1, 1], 2)
False
>>> all([1, 1, 1], 1)
True

Continue by defining a skeleton function with the following signature:

1. Name: all
2. Arguments: A list of integers and an int.
3. Returns: A bool, True if all numbers match the indicated number, False otherwise or if the list is empty. This algorithm should work for a list of any length. Hint: remember you can return from inside of a loop to short-circuit its behavior and return immediately.

Testing

You will be responsible for writing tests for this function on your own. Just be sure to remember to add the all function to your import list at the top of your utils_test.py file.

Note that the assert keyword expects a boolean expression following it. You do not need to compare the return value of all with True or False. Consider these example assertions:

1. assert all([1, 1, 1], 1)
2. assert not all([1, 2, 3], 1)

Idiomatic Python Equivalent of all

There is not a directly equivalent built-in function or method for all in Python, but there are some idiomatic ways to achieve this. They involve the use of some concepts we have not arrived at yet (namely either sets or slice subscripts) so we will leave this as a future exercise.

max

Next, you will write a function named max.

The max function is given a List of ints, max should return the largest in the List.

If the List is empty, max should result in a ValueError. We’ll show you how! Examples:

>>> max([1, 3, 2])
3
>>> max([100, 99, 98])
100
>>> max([])
ValueError: max() arg is an empty List

Define a skeleton function with the following signature:

1. Name: max
2. Argument: A list of integers.
3. Returns: An int, the largest number in the List. If the List is empty, raises a ValueError.

The body of your skeleton function can begin as such, which demonstrates how to raise an error:

def max(input: List[int]) -> int:
    if len(input) == 0:
        raise ValueError("max() arg is an empty List")

Testing

We will discuss errors and error handling in more detail in lecture soon. To give you a working test for the case where the input list is empty, here is one you can use in your utils_test.py file. First, add the following imports to the top of your test file (notice, max was added to the list of functions imported from the utils module – don’t forget to do this!):

import pytest
from exercises.ex05.utils import count, all, max

Then, define this test function:

def test_max_of_empty() -> None:
    """Calling the `max` function with an empty List should raise a Value Error."""
    with pytest.raises(ValueError):
        empty_list: List[int] = []
        max(empty_list)

You can safely ignore the type-checking error this test will give you. The grader will not take off for it.

Rediscover tests to find this test and then it should pass based on the skeleton implementation. How exactly this test works is beyond our current place in the course but the idea is this is a pytest idiom for ensuring that this test passes if a ValueError results in the with block and fails otherwise.

Add additional tests to find the max value of the list. Note, you cannot use the built-in max function Python provides in your implementation.

Idiomatic Python Equivalent of max

Your max function is a reproduction of a Python’s built-in max function: https://docs.python.org/3/library/functions.html#max. Python’s version works on collections of many types more broadly, while yours is specifically typed to work with a list of integers.

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.

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.

Define a function with the following signature: 1. Name: is_equal 2. Parameters: Two lists of integers. 3. Returns: True if lists are equal, False otherwise.

Implement the is_equal function as described above.

Testing

1. Import your is_equal function.
2. 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.

Define your function with the following signature.

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 ex05/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]

Next, define a skeleton function with the following signature in ex05/utils.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.

If the length of the list is 0, start > len of the list or end <= 0, return the empty 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]

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 exercises/ex05

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.