# 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 a limited learning experience 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 `List`s.

## `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 your `__author__` variable assigned to your name and e-mail address..
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``````
1. 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.
2. 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 `List`s of `int` values, return `True` if every element at every index is equal in both `List`s.

``````>>> 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.

### 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`.