Computational Thinking & Lists “Finger Exercises”

For all the exercises where you are writing functions, we strongly encourage you to put these into a file, then load the file into Python, as you previously did with the “Hello, World!” example. That way, you are practicing using the software as you will usually use it. You'll also have a file of code to turn to as a study guide or reference. We are not asking you to turn your work on these exercises, though.

What Makes Code Good?

Throughout the course, we want to emphasize thinking about the processes of algorithm design and algorithm implementation. Now, we want to introduce two good ideas that should help you in both steps.

Let's return to our temperature conversion problem from the previous finger exercises. Copy-and-paste the previously provided code for convertF2C and convertC2F, if you didn't previously save it.

To continue the exercise, find the conversion formula for degrees Celsius to Kelvin, and define the function convertC2K.

def convertC2K(C):
    """Converts a temperature in degrees Celsius to Kelvin."""
    return C+273.15

The mathematical formula is simple, and the code just uses the formula. Nothing too exciting yet.

But, we did add one thing: a documentation string, which is a string describing what the code does. It kind of sticks out like a sore thumb, as its placed immediately after the function's header and surrounded by three quotes.

Even though the function name is reasonably mnemonic, it's standard practice to include a documentation string that describes what the function accomplishes. From the big picture of Computational Thinking, it is important not only to think about what our code is supposed to do, but to articulate this to anyone who might read our code.

(Note: The following depends on editor. It works in IDLE.) As one pragmatic benefit, this documentation string is displayed to us when using the code. Type slowly, and observe the pop-up displayed in the following examples.

First, use a function without a documentation string:
```
convertF2C(64)
    
```
Next, use a function with a documentation string:
```
convertC2K(337.15)
    
```

Next, we want a function to convert Fahrenheit to Kelvin. We could yet again look up the appropriate magic formula and type it in, but we now have a better approach available! We can decompose the problem using what we have already solved before! Given a temperature in degrees Fahrenheit, we can obtain the equivalent temperature in degrees Celsius (convertF2C). Then, we can similarly obtain the equivalent temperature in Kelvin (convertC2K).

def convertF2K(F):
    """Converts a temperature in degrees Fahrenheit to Kelvin."""
    return convertC2K(convertF2C(F))

All we are doing is combining operations, just like we've previously combined addition and multiplication in a single formula. The only difference is that we've defined these operations ourselves.

Reusing code is not only conceptually simpler, it generally leads to fewer mistakes. Here, we just used two simple functions, and your editor might have even helped find the appropriate functions. That's less error-prone that typing in yet another mathematical formula.

Also, we've once again used a documentation string. We'll do this with every single function we present from now on, and so should you.

Beginning with Lists

So far, we've seen two kinds of data: numbers and strings. If we have lots of data, we name each one separately, e.g.,

```
a=1
b=3
c=7
d=-10
    
```

But, we often want to consider a collection of data as a unit. Consider a shopping list or a course roster — we have one list with many items in it.

A list is one common way to combine multiple data items into a single item. It is an ordered collection of elements, i.e., there is a designated first element, second element, etc. A list is mutable, or changeable, in that you can add and delete elements of the list. We will see other types of data collections later.

Creating a list

One way to create a list is to use square brackets surrounding the elements of the list, separated by commas. For example,

```
[0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
    
```
```
["x", "y", "z", "z", "y"]
    
```
Lists can have different kinds of values:
```
[42, "the answer"]
    
```

["milk", "eggs", "cookies", "chicken", "veggies"]

The empty list:
```
 []     
    
```
Lists can themselves contain lists:
```
[[1], [1,2], [1,2,3]]
    
```
The list containing the empty list:
```
[[]]
    
```
This is not the same as the empty list! It has one element.

What if you needed a list with a thousand or a hundred thousand elements? What if the required length was in a variable? There must be some alternate way to create lists. The most common option is to use the built-in function range. There are several ways to use it — try these examples:

```
range(10)
    
```
```
range(10,21)
    
```
```
range(10,21,2)
    
```

If you haven't figured out the pattern from these examples, here are two good ways for finding out what a function does:

```
help(range)
    
```
Look in the Python Standard Library for the function range. In computer terminology, a library is a collection of functions and other features that is available in the language.

What can you do with a list?

Let's make a list to use in the upcoming examples.

shopping = ["milk", "eggs", "cookies", "chicken", "veggies"]

Accessing a single element

To access any particular element of a list, use square brackets after the list's name and an index value to denote which element to retrieve. The index value is an integer starting at 0, that is, 0 refers to the first value, 1 to the second, etc.

```
shopping[0]
    
```
```
shopping[3]
    
```

You can use negative index values to count back from the end of the list.

```
shopping[0]
    
```

How would you access "cookies" from the list using a negative index?

```
shopping[-3]
    
```

Accessing multiple elements

To retrieve the value of multiple, contiguous elements of a list, specify two index values, a starting value and an ending value, separated by a colon. A list will be returned, containing elements from the list, starting with the starting index value up to but not including the ending index value.

```
shopping[2:4]
    
```

In Python, this is known as a slice.

Sometimes you want to get all elements up to the n^th element or all elements beyond the n^th element. We can achieve this by simply leaving out either the starting or ending index.

```
shopping[:3]
    
```
```
shopping[3:]
    
```

Appending elements to a list

We can add additional elements to the end of a list.

```
shopping.append("oranges")
    
```

It is important to understand that the list shopping has been altered by the addition of the string "oranges" at the end.

```
shopping
    
```

This syntax, using the dot (period) between the variable name shopping and the function (actually, a method) name append means that the append function “belongs” to the shopping list object. Many objects in Python have built-in functions that are associated with them and that can be accessed using the dot notation.

Can we append multiple elements to a list using append?

shopping.append(["blueberries","sugar","eggs"])

What does the list look like now? Can you explain why?

Let's try the extend function, instead:

shopping.extend(["blueberries","sugar","eggs"])

And now what does the list look like?

Changing elements

To set the value of a particular element, simply use the same syntax as was used to access that element, but put it on the left side of the equals sign. The desired value goes on the right side of the equals sign.

```
shopping[1]="yogurt"
    
```

Or you can change multiple values at once like this:

shopping[1:3]=["carrots","lettuce","bananas"]

Some other very useful list operations

To find the length of a list:
```
len(shopping)
    
```
To sum the numbers in a list:
```
numbers = [5,3,9,2]
sum(numbers)
    
```
To put the list elements in order:
```
numbers = [5,3,9,2]
numbers.sort()
    
```

Iterating (a.k.a. Looping)

So we can now make lists and tuples and fill them with all sorts of values. Now what? We need to process all those values in order to extract something useful out of them. For instance, how can we step through a list one element at a time? Here we introduce one techniques: the for loop.

Iterating over list elements

A for loop fundamentally steps through all the elements of an iterable entity, which is anything that has elements that can be stepped through one at a time. The beauty of a for loop, however, lies in the fact that it will also perform a given sequence of operations for every element that it iterates through.

Let's try a very simple example:

numbers = [1,6,0,3,7]
for number in numbers:
    print number

In turn, each element of the list numbers is placed in the variable number. The indented code, the loop body, is performed for each value that number takes on. So, in this case, number becomes 1, and that is printed, then number becomes 6, and that is printed, etc. I.e., this prints each element of the list, from first to last.

We can take this idea to define a function to print the elements of whatever list is given to the function.

def printList(aList):
    """Print each list value on a separate line."""
    for value in aList:
        print value

printList(shopping)
printList(range(10))

As you can see, this works regardless of the kinds of data in the input list, so the variable name value seemed more appropriate.

Also, this is the first time we've used two levels of indentation. Python uses indentation to group code. All the code inside the function definition needs to be indented under the def. Furthermore, all the code inside the loop needs to be indented under the for.

To do something a bit more useful, let's sum the squares of a list of numbers, a common computation in statistics.

def sumSquares(numbers):
    """Given a list of numbers, returns the sum of their squares."""
    sum = 0
    for number in numbers:
        sum = sum + number*number
    return sum

sumSquares([5,3,8])

This code initializes the variable sum to be zero. Then, for each list value in turn, we'll call the value number and add its square to sum. Finally, we return the computed sum. Thus, this function works by repeatedly changing sum to be more and more of the eventual result. We often call this “accumulating” the result, and sum is an accumulator variable.

This also illustrates the use of local variables briefly discussed in the previous finger exercises. The variable number is local to the loop — the name doesn't mean anything outside the loop. Similarly, the variables numbers and sum are local to the function. Again, this allows us to choose variable names without worrying about what names are used in other code.

Similarly, we could instead build a new list of the squares of the original list values.

def squareList(numbers):
    """Given a list of numbers, returns a list of the numbers squared."""
    squares = []
    for number in numbers:
        squares.append(number*number)
    return squares

squareList([5,3,8])

Again, we are accumulating the desired value, which this time is a list.

Follow these ideas to define functions that accomplish the following:

Returns the product of a list of numbers

def productList(numbers):
    """Given a list of numbers, returns the product of the numbers."""
    product = 1
    for number in numbers:
        product = product * number
    return product

Returns the concatenation of a list of strings

def concatenateList(strings):
    """Given a list of strings, returns the concatenation of the strings."""
    result = ""
    for string in strings:
        result = result + string
    return result

(Challenge) Returns a histogram of a list of scores (0—99) by quartiles. E.g., quartiles([60,20,34,99,90]) returns [[20],[34],[60],[99,90]].

def quartiles(scores):
    """Given a list of scores between 0 and 99, returns 
       a list of four lists, each with the scores in the corresponding
       quartile."""
    quartiles = [[],[],[],[]]
    for score in scores:
        quartile = int(score/25)
        quartiles[quartile].append(score)
    return quartiles

Iterating using `range`

As we've seen The function range returns a list, and we can iterate over its values as above. There are two basic reasons to do this, each of which is a reasonably common special case of looping.

First, we might want to loop a specific number of times, and we aren't starting with a list to loop over. For example, to create a list of the first n squares, we could write the following:

def firstSquares(n):
    """Given N, returns the first N squares."""
    squares = []
    for number in range(n):
        squares.append(n*n)
    return squares

Of course, a better solution would follow the general rule of reusing our existing code:

def firstSquares(n):
    """Given N, returns the first N squares."""
    return squareList(range(n))

Second, we may have a list to loop over, but we may want more control over which elements we want to consider. As an example, we'll first just present an alternate definition for printList:

def printList(aList):
    """Print each list value on a separate line."""
    for i in range(len(aList)):
        print aList[i]

printList(shopping)
printList(range(10))

Clearly, this version is more complicated than the original, but let's understand this before moving on to a more motivating example of this style of loop. Here, the variable i has the values 0, 1, 2, etc., in turn. In the loop body, we use i as a list index to look into the input list, thus looking at each position.

The power of this idea is that instead looping over all the indices in order, we could change this code to loop over the indices in some other order or just some of the indices. We can accomplish that by changing either the range(len(…)) part or the [i] part. As a simple example, here are two ways to print every other element of a list, starting with the second element.

def printOddIndices(aList):
    """Print every other list value, starting with the second,
       on a separate line."""
    for i in range(1,len(aList),2):
        print aList[i]

def printOddIndices(aList):
    """Print every other list value, starting with the second,
       on a separate line."""
    for i in range(len(aList)/2):
        print aList[i*2+1]

Try these out, and make sure you understand how the indices are being computed.

Looping over list elements, as we first did, is generally simpler and preferred, but looping over indices is more flexible.

Additional optional readings about Python lists

Python Tutorial: Lists
Wikibooks: Python Programming Lists

Khan Academy: Python lists, Python for loops
Dive Into Python: Lists
Python Course: for loops Strings and Lists

A couple odds-and-ends with strings

We can use the len function and loops on strings, too! A string can be considered to be similar to a list — it is an ordered collection of single characters.

```
s = "abcd"
len(s)
    
```

def printCharacters(aString):
    """Print each string character on a separate line."""
    for char in aString:
        print char

Note that the original printList and this printCharacters are actually identical, except that the variable names are different. We can often take advantage of this and write code that just loops over a data collection, and not care what kind of collection it is.

Finding More Operations

There are lots of other built-in functions available. Probably the best ways to discover them are to browse the Python Standard Library and simply search the web.

As a specific example, consider looking for a square root function. Searching the web, the first hit listed (for me, using Google) is this page, which is part of the Python Standard Library. Browsing down, we find an entry for math.sqrt. This tells us several things — it exists, it has the abbreviated name sqrt, and it is in the math module.

A module is just a file of Python code. Each time you write code in a file, you are creating a module.

Let's try using it.

```
sqrt(36)
    
```

What happens? The problem is that the math module isn't loaded into Python automatically. We need to do that. We'll mention two alternate ways of doing this.

A longer, but safer form. You can use math.sqrt and define something called sqrt without the two getting confused.
```
import math
math.sqrt(36)
math.sqrt(49)
    
```
This form allows you do omit the math. part, but be careful if you've defined something called sqrt, too!
```
from math import sqrt
sqrt(36)
sqrt(49)
    
```