EX11 - Algorithms on a Generic Data Structure

Overview

In these exercises you will implement a few algorithms to process a singly-linked list data structure defined to be generic for any type T. Just like in the List Utility functions, these functions will be pure and are well suited for writing test cases. As such, you will also write test cases demonstrating their usage and verifying their correctness.

Setup

In the comp110/exercises directory, create a subdirectory named ex11_generics.

generics.py

In the ex11_generics directory, create a file named generics.py and establish the following starting contents (which is a reproduction of what we wrote in class today):

"""Utility functions that operate on a generically defined linked list Node."""

from __future__ import annotations
from typing import TypeVar, Generic, Optional, List

T = TypeVar("T")


class Node(Generic[T]):
    """A generic linked list Node for any data type T."""

    data: T
    next: Optional[Node[T]]

    def __init__(self, data: T, next: Optional[Node[T]]):
        """Construct a Node in a Linked list that forms head of a new list."""
        self.data = data
        self.next = next

    def __repr__(self) -> str:
        """Produce a string representation of a linked list."""
        if self.next is None:
            return f"{self.data} -> None"
        else:
            return f"{self.data} -> {self.next}"


def is_equal(lhs: Optional[Node[T]], rhs: Optional[Node[T]]) -> bool:
    """Test if two linked lists are deeply (values and order) equal to one another."""
    if lhs is None and rhs is None:
        return True
    elif lhs is None or rhs is None or lhs.data != rhs.data:
        return False
    else:
        return is_equal(lhs.next, rhs.next)

Notice the is_equal function is reproduced from what we developed together in lecture today. You will want to define this function in the same module as Node to be sure they are referencing the same Node definition.

generics_test.py

Establish a file for your test definitions. For today’s exercise we expect you to be able to setup the test file independently. Look toward the last exercise for inspiration and remember to check equality you’ll need to use the function we developed in lecture today (and reproduced in generics.py as is_equal).

Requirements

You must use recursive function calls to implement the functions below. If you use loops your work for that function will be disqualified.

linkify

Given a List[T], your linkify function should return a Linked List of Nodes with the same values, in the same order, as the input List.

You will find it helpful to use Python’s slice subscription notation here, which we haven’t discussed in full but you should now be able to pickup quickly. Try the following in the REPL:

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

Notice when using slice notation a new List is returned to you whose values start with the first index number, inclusive, and end with the index number following the colon, exclusive. If you leave off the starting index, it defaults to 0. If you leave off the ending index, it defaults to the len of the List.

A skeleton for linkify is:

def linkify(items: List[T]) -> Optional[Node[T]]:
    return None

Example usage:

>>> linkify([1, 2, 3])
1 -> 2 -> 3 -> None
>>> linkify(["Hello", "World"])
Hello -> World -> None

After you are certain of the correctness of your linkify function, you may find it valuable to use in writing test cases for the following functions.

scale

Given a head Node[float] of a linked list and a float factor to scale by, return a new linked list of Node[float]s where each value in the original list is scaled (multiplied) by the scaling factor.

Example usage:

>>> scale(linkify([1.0, 2.0, 3.0]), 2.0)
2.0 -> 4.0 -> 6.0 -> None

Skeleton function implementation:

def scale(head: Optional[Node[float]], factor: float) -> Optional[Node[float]]:
    return None

concat

Given two linked lists, return an entirely new linked list where the first list is followed by the second list. You should not reuse any existing Node objects in the implementation of this function.

Hint #1: You will need to fully process both lists.

Hint #2: You do not need to make forward progress in both lists at each step.

Caution: Your function may appear to work locally but will have points deducted if you do not make new Node objects that correspond to each of the original Node objects in both linked lists.

Example usage:

>>> scale(linkify([1.0, 2.0, 3.0]), 2.0)
2.0 -> 4.0 -> 6.0 -> None
>>> concat(linkify([1, 2, 3]), linkify([4, 5, 6]))
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
>>> concat(linkify(["Hello"]), linkify(["World"]))
Hello -> World -> None

Skeleton function implementation:

def concat(lhs: Optional[Node[T]], rhs: Optional[Node[T]]) -> Optional[Node[T]]:
    return None

Hand-in is Open

You should write your own tests to be confident of your implementations. None of these functions require much code to complete, but will take some mental gymnastics to think about approaching recursively.

Remember: Focus on what you need to do with only the head node and then leave the rest of the problem working through the rest of the list to the recursive function call.

Type Checking Hints

It is possible to write functionally correct programs that do not satisfy the constraints of the type checker. The reason for this a combination of naivete on the type checker’s part, as well as some gnarly theoretical computer science related to the halting problem which you’ll learn about in COMP455.

The short story is a type checker is typically not going to be able to reason through every possible code path in the same way you’re able to. For example, if you have a function that declares it returns Optional[int], and you call that function, then you are going to need to check for the possibility of None as a return value. This is true even if before the function call you made some other test about the argument that convinced you the function call would return an int. Typically this is a sign you can rewrite your logic to be both easier to follow while also satisfying the type checker. Think about making your test of None based on the returned value of the recursive call rather than on the argument before the call is made. Play around with the code and challenge yourself to rewrite it. This is a puzzle and it’s good practice that forces you to grapple with solving the same problem from different angles of attack.