Instructions for listDiagrams

Click here to toggle highlighting for goal links

General Overview

This task involves defining six functions whose purpose is to create lists described by specific memory diagrams.

Let's begin with a sample memory diagram and showing several ways to define a function that creates it. Here's the diagram for a list we'll call list0:

We'll consider three different approaches for defining a zero-parameter function makeList0 that creates and returns the top list in the diagram.

Approach 1 for makeList0: Use variables to name shared sublists

In our makeList0 function, it's OK to define as many local variables as we want to help us, even if they don't appear in the diagram. We can use local variables to name shared sublists and then use these variables to achieve the sharing we desire.

We'll introduce variables shared2, shared1, and top, as shown in the following sequence of statements:

Statements	Diagram so far
shared2 = [2]
shared1 = [1, shared2]
top = [shared1, shared2, shared1, shared2]

We can finish by encapsulating the steps for Approach 1 within a zero-parameter function makeList0:

def makeList0():
    """
    Returns the top list depicted in the memory diagram for list0.
    Uses Approach 1 to create the appropriate list structure.
    """
    shared2 = [2]                     
    shared1 = [1, shared2]            
    top = [shared1, shared2, shared1, shared2]
    return top

Approach 2 for makeList0: Use a single variable and assignment to list slots

A second approach for creating the list structure shown for list0 is to use a single variable (call it top) to create an initial list with four slots, where all slots but the last one contain bogus placeholder values that will be replaced in subsequent steps. Then we use assignment to list slots to create extra structure and achieve the desired result.

Statements	Diagram so far
top = [3, 4, 5, [2]]
top[0] = [1, top[3]]
top[1] = top[3] top[2] = top[0]

We can finish by encapsulating the steps for Approach 2 within a zero-parameter function makeList0:

def makeList0():
    """
    Returns the top list depicted in the memory diagram for list0.
    Uses Approach 2 to create the appropriate list structure.
    """
    top = [3, 4, 5, [2]]
    top[0] = [1, top[3]]
    top[1] = top[3] 
    top[2] = top[0]
    return top

Approach 3 for makeList0: Use a single variable and .append

A third approach for creating the list structure shown for list0 is to use a single variable (call it top) and use only calls to the list .append method to create the desired diagram using the following steps:

Statements	Diagram so far
top = [[1]]
top[0].append([2])
top.append(top[0][1])
top.append(top[0])
top.append(top[1])

We can finish by encapsulating the steps for Approach 3 within a zero-parameter function makeList0:

def makeList0():
    """
    Returns the top list depicted in the memory diagram for list0.
    Uses Approach 3 to create the appropriate list structure.
    """
    top = [[1]]
    top[0].append([2])
    top.append(top[0][1])
    top.append(top[0])
    top.append(top[1])
    return top

Your Task: Define Functions to Create the List Structures in Six Memory Diagrams

In the file listDiagrams.py, you will flesh out the definitions of six functions that create and return a list. Each function must have zero parameters and must return the top list for the structure depicted in the associated memory diagram.

In all of your functions, it is OK to use as many local variables as you want to name parts of the memory diagram, even though the memory digrams themselves do not show any variables. See the three versions of makeList0 above for examples of using local variables in this way.

In all of the functions, it is possible to use only a single local variable (like top in Approaches 2 and 3 for makeList0). If you want to give yourself an (ungraded) challenge, write your solutions using at most only local variable.

makeList1

The function makeList1 has zero parameters and returns a list with the following structure:

makeList2

The function makeList2 has zero parameters and returns a list with the following structure:

makeList3

The function makeList3 has zero parameters and returns a list with the following structure:

makeList4

The function makeList4 has zero parameters and returns a list with the following structure:

makeList5

The function makeList5 has zero parameters and returns a list with the following structure:

Note that this diagram contains some string values; "parent", "child1", and "child2" are strings stored in list slots, not variable names (variables are shown without quotes, have an associated box, and do not have arrows pointing to them).

makeList6

(Defining this function is an extra goal.) The function makeList6 has zero parameters and returns a list with the following structure:

Testing your Functions

You cannot tell just from the printed output of your functions whether they have the correct structure. For example, both list1 and list2 have the printed representation:

[[1, 2], 3, [1, 2]]

The Python is operator (covered in Lec 11) is useful for determining which sublists are shared an which are not. For example, executing the statements

list1 = makeList1()
list2 = makeList2()
print('list1[0] is list1[2] =>', list1[0] is list1[2])
print('list2[0] is list2[2] =>', list2[0] is list2[2])

prints

list1[0] is list1[2] => False
list2[0] is list2[2] => True

By using suitable tests involving is (in conjunction with some other tests), it is possible to determine if the lists returned by the six makeListn functions have the correct structure.

As usual, we have supplied a test file test_listDiagrams.py which will use optimism to check that your results are correct, including key parts of their internal structure. We have also provided a file named show_listDiagrams.py which will print out a "memory report" for the result of each of your functions. This is kind of like a memory diagram in text format, and you can compare these to the memory reports shown in the examples below to see if things are correct.

In a memory report, each object gets assigned a label that starts with @, and instead of drawing arrows when one object references another, we write the label of the referenced object.