User’s Guide, Chapter 5: Lists of Lists, Functions, and Recursion¶
In the last Chapter, we discussed Python Lists, how the
Stream object is similar to a List, and how
we can put Note objects into a Stream, look
at their offsets, and .show() the Stream in MusicXML or as text.
We ended by putting one Stream inside another Stream, which
seemed like a neat trick until we discovered that we couldn’t get at the
elements inside the inner Stream.
In this chapter we will work on how to exploit the power of nested
Streams. We’ll begin with a discussion of recursive lists (since
Streams work a lot like lists). Those with some programming will
probably want to skip to the following section.
Lists of Lists¶
Lists (similar to Arrays in other languages) can hold all sorts of other things inside them including other lists. So let’s begin by creating two lists:
listA = [10, 20, 30]
listB = [1, 2, 3, listA]
Now when we look at listB, we’ll see that listA is inside it:
listB
[1, 2, 3, [10, 20, 30]]
Notice that when we look at the length (len()) of listB it shows
that there are 4 elements, not 6:
len(listB)
4
That’s because the fourth element of listB (which, you’ll recall, is
called listB[3] not listB[4]) is itself a list, listA:
listB[3]
[10, 20, 30]
listB[3] is listA
True
So if we want to get the third element of listA, there is an easy way to do it:
listA[2]
30
But we can also think that 30 is also the third element of the
fourth element of listB. So we can write this instead:
listB[3][2]
30
Oh, and since each of these is the last elements of their respective lists, we could instead write:
listB[-1][-1]
30
which means “get the last element of the last element of listB”
But what if we just wanted to know every number stored anywhere in listB, even if that number is inside a list itself? This won’t work:
for number in listB:
print(number)
1
2
3
[10, 20, 30]
Instead, we have to test to see if each “number” in listB is
actually a number or a list. And if it’s a list, we should find each
number in that and print it instead. Here’s a slightly more complicated
set of commands to do that:
for thing in listB:
if isinstance(thing, list):
for number in thing:
print(number)
else:
print(thing)
1
2
3
10
20
30
listB – we call it “thing” here, because we’re not sure if it’s a
number of a list. Then in the next line
if isinstance(thing, list): checks if the thing is a list. If that
is True then we get to an inner loop, where we look at “thing”
(which in this case is listA, but the program doesn’t know that)
and get the “number” from it. But if “thing” is not a list, that’s
where the else comes in, which is what we run if we don’t have a
list, which just says, print the number.listB, numbers and other lists.) If you get an error, be sure
not to forget the ending “:” or to indent the next line.Functions and Recursion¶
But what if we did this:
listC = [100, 200, 300, listB]
Now since listB contains listA, we end up with a list within a list within a list:
listC
[100, 200, 300, [1, 2, 3, [10, 20, 30]]]
If we wanted to print all the numbers in listC, we could write an ugly set of commands like this one (I’ll understand if you don’t actually want to type this and just want to trust me that this works):
for thing in listC:
if isinstance(thing, list):
for innerThing in thing:
if isinstance(innerThing, list):
for number in innerThing:
print(number)
else:
print(innerThing)
else:
print(thing)
100
200
300
1
2
3
10
20
30
Whew! If this were the only way to do it, I wouldn’t blame you if you
decided that programming just wasn’t worth the headache. Especially
since you’ve probably already guessed that we could make:
listD = [4, 5, listC, 6, 7] and get another layer of lists.
Fortunately, there’s a little bit of programming magic called
“recursion” that we can use to get to the heart of the matter. Notice
that in the code I just wrote, there are a few lines that are basically
the same (with a few words changed) as other parts of the code. With
recursive coding, we’ll find a way to save those lines to reuse them.
Type these six lines:
def flatPrint(myList):
for thing in myList:
if isinstance(thing, list):
flatPrint(thing)
else:
print(thing)
What we’ve done is created a new function called ‘’flatPrint’’ which reaches into lists of lists and prints anything that is in them.
Now try:
flatPrint(listC)
100
200
300
1
2
3
10
20
30
It works! But how? Here’s how functions work in general (skip this, if you know all about functions):
The def statement says that we’re going to ‘’define’’ a new
function. After the word def comes the name of the function –
something we’ll be able to call it to use it later. (We call the process
of taking nested structures and turning them into something linear
“flattening” them, like crushing a cardboard box. Since this is a
flattener that also prints what’s inside it, flatPrint is a good
name for it. Notice that just like with variables, case matters in
Python, so flatPrint isn’t the same as flatprint or
Flatprint or FlAtPrInT.)
After “flatPrint”, within parentheses comes the variable name
myList. Notice that we haven’t used the name myList yet – it
doesn’t exist. What myList means here is that any time we use the
function flatPrint, whatever the name of the list was, within
flatPrint it will be called myList. So you could say
flatPrint(listC), as we just did, and within the function
flatPrint, listC will be known as myList.
Here’s a simpler function that will explain that better. squareMe
takes in a number and prints its square:
def squareMe(number):
print(number * number)
Now we can try:
squareMe(10)
100
squareMe(2.5)
6.25
pi = 3.14
squareMe(pi)
9.8596
Notice two things in the last case. First that pi isn’t exactly 3.14 –
we all know that; I just wanted to make sure the math teachers in the
room didn’t go into conniptions. Second that we gave the variable pi
to the function squareMe. But within the function squareMe we
didn’t write: print(pi * pi); instead within the function, pi
(or any other variable or number) will simply be called number. (By
the way, instead of writing print(number * number) we could have
written print(number**2) since ’’ ** ’’ is how Python denotes
exponents).
At the end of a function, you can either print something out, or
return a value, which can be used for anything else. Here’s
cubeMe which works a lot like squareMe, but it cubes the number
and instead of printing it, it returns it:
def cubeMe(number):
return number * number * number
Because we’re not printing number, we can assign the value of cubeMe
to another variable:
x = cubeMe(2)
x
8
y = cubeMe(x)
y
512
Notice that if x = cubeMe(2) and y = cubeMe(x) then we can
substitute cubeMe(2) for x and write:
y = cubeMe(cubeMe(2))
y
512
Thus, using return instead of print is more powerful, so after
finishing with flatPrint, we’ll mostly write return and not
print functions.
So, getting back to flatPrint, which you’ll recall is (I’m adding
commented line numbers again so I can refer to them):
def flatPrint(myList): # 1
for thing in myList: # 2
if isinstance(thing, list): # 3
flatPrint(thing) # 4
else: # 5
print(thing) # 6
Let’s look at it line by line.
Line 1, as we said, defines the function called flatPrint which
expects a list which we’ll call myList.
Line 2, says “for each thing that is inside myList, grab it and call it
thing.” Once we’re done with thing, the program will jump back
to line 2 to get the next thing.
Line 3, checks if thing is a list. If so, we do line 4. If not we
jump to line 5.
Line 4: This is where the magic happens. We know now that thing is a
list. So how do we print a list (which might have other lists inside of
it)? We use flatPrint! In essence flatPrint uses its own power
of discerning between lists and numbers to print any internal lists. We
call functions that use (“call”) themselves recursive functions and
the process of using recursive functions is called recursion. It’s a
powerful tool and one we’ll use in music21 a lot.
Line 5, is where we jump to from line 3 if thing is not a list, so
then Python executes line 6
Line 6, simply prints thing, which we know by now is a number.
A warning: unlike some programming languages (Java, C, etc.), Python
never checks that what you pass to flatPrint actually is a list. So
you can try doing something like flatPrint(30) but since 30
isn’t a list, you’ll get an error:
flatPrint(30)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-25-ea562a34cf18> in <module>
----> 1 flatPrint(30)
<ipython-input-24-4772cf1d5b5b> in flatPrint(myList)
1 def flatPrint(myList): # 1
----> 2 for thing in myList: # 2
3 if isinstance(thing, list): # 3
4 flatPrint(thing) # 4
5 else: # 5
TypeError: 'int' object is not iterable
For more information on data structures (lists, lists of lists, and things we didn’t get to, I suggest watching Google’s Python tutorial, especially class 2).
Wrapup¶
In this chapter we looked at how we can look inside lists of lists,
which will be important when we consider how to work with Streams of
Streams in music21, to look at Measures within Parts within
a Score. We also learned how to define a function and write
recursive functions to do powerful work in just a few lines of code. In
the next chapter we apply all this to music with
Streams of Streams.