Transcript
the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu quick quick recap of what we did last time so last time we introduced um this idea of decomposition and abstraction and we started putting that into our programs these were sort of high level Concepts and we achieved them using these concrete things called functions in our programs and functions allowed us to create code that was coherent that was that had some structure to it and was reusable okay and from now on in problem sets and in lectures I'm going to be using functions a lot so make sure that you understand how they work uh and all of those details so today we're going to introduce two new data types and they're called compound data types because they're actually data types that are made up of other data types particularly ins floats booleans and strings and actually not just these but other data types as well so that's why they're called compound data types so we're going to look at a new data type called a tupal and a new dat data type called a list and then we're going to talk about these ideas that come about with uh specifically with lists all right so let's go right into tupal okay so if you recall strings strings were sequences of characters okay tupal are going to be similar to strings in that they're going to be sequences of something except that tupal aren't just sequences of characters they can be sequences of of anything they're a collection of data where that data can be of any type okay so the so a tupal can contain elements that are integers floats strings and so on tupal are immutable and if you recall we talked about this word a little bit uh when we talked about strings so that means once you create a tupal object you can't modify it so just like when you created a string object you weren't able you were not a allowed to modify it so the way we create tuples are with these open and close parentheses you this shouldn't be confused with a function because there's nothing there's no there's no this isn't a function call it's just how you represent a tupal for a function call you'd have something right before the parenthesis okay this is just how we chose to represent a tupal and just a plain open and closed parentheses represents an empty tupal so it's of length zero there's nothing in it whoops you can create a tupal that contains some elements by separating each element with a comma so in this case this is a tuple that can be accessed with a variable T that contains three elements the first is an integer the second in a is a string and the third is another integer much like strings we can index into tupal to find out values at uh particular indices so you read this as T at position Z so the Tuple represented by uh variable T at position Z will evaluate to two because again we start counting from zero in computer science so that brings us gives us the first element just like strings we can concatenate TS together that just means add them together so if we add these two tupal together we just get back one larger Tuple that's just those two uh the elements of all of those tupal just put together in one larger tupal again much like strings we can slice into tupes so T slice from index one until index two remember we go until this stop minus one so this only gives us one element inside the tupal and this is not a mistake this extra comma here actually represents a tupal object okay if I didn't have this comma here then this would just be a string the parentheses would just would wouldn't really make any difference but the comma here makes it clear to python that this is a tupal with only one element in it we can slice even further to get a tupal with two elements and we can do the usual operations like get the length of a tupal which says how many elements are in my Tuple and Len of this T would evaluate to three because there are three elements inside the tall each element again separated by the comma and just like strings if we try to change a value inside the Tuple in this case I wanted to try to change the value of of the um the second the second element to four python doesn't allow that because tupal are immutable okay so why would we want to use tups tups are actually useful in a couple of different uh scenarios so recall a few lectures ago we looked at this code where we tried to swap the values of variables X and Y and this first code actually didn't work because you're overwriting the value for x right so instead what we ended up doing was creating this temporary variable where we stored the value of x and then we overwrote it and then we used the temporary variable Well turns out this thre liner code right here can actually be written in one line using tupal so you say x comma Y is equal to Y comma X and python goes in and says what's the value of y and assigns it to X and then what's the value of x and assigns it to Y okay extending on that we can actually use tuples to return more than one value from a function so functions you're only allowed to return one object okay so you're not allowed to return more than one object however if we use an a tuple object and if that's the thing that we return we can actually get around this sort of rule by putting in as many values as we want inside the tupo object and then we can return as many values as we'd like so in this specific example I'm trying to calculate the quotient and remainder when we divide X by y so this is a function definition here and down here I'm calling the function with four and five so when I make the function call oops four gets assigned to X and five gets assigned to Y right so then Q is going to be the integer division when X is is divided by Y and this double slash just means it's it's like casting their result to an integer it says divide it keep the whole number part and just delete everything else U be uh beyond the decimal point so when you divide four by five this Q is actually going to be zero it's zero point something and I don't care about the point something and then the remainder is just using the percent operator so when I divide four by five the the remainder is going to be four and notice that I'm going to be returning q and R which are these two values that I calculated inside my function and I'm returning them in the context of this Tuple right so I'm only returning one object which is a tuple it just so happens that I'm populating that object with a few a few different values okay so when I return When the function returns here this is going to say 0 comma 4 that's the twole it's going to return right Q is going to be zero and R is going to be four so then this line here quote REM equals 04 is basically this little it's sort of like what we did up here so it assigns quote to four quot sorry quote to zero and REM to four okay so we can use tles this is very useful we can use them to return more than one value from a function so tup are great might seem a little bit confusing at first but they're actually pretty useful because they hold collections of data so here I wrote a function which I can apply to any set of data okay and I'll explain what this function does and then we can apply it to some data and you can see that you can extract some very basic information from whatever set of data that you happen to collect so here's a function called get data and it does all of this stuff in here and in the actual code associated with the lecture I actually said what the condition on a tuple was so it has to be a tuple of a certain um that that looks a certain way and this is the way that it has to look so it's one Tuple the outer Square the outer uh parentheses out here represent the fact that it's a tupal and the elements of this tupal are actually other tupal right so the first element's a tupal object the second element is a tupal object and third one's a tuple object and so on and each one of these inner tle objects are actually going to contain two elements the first being an integer and the second being a string okay so that's sort of the precondition that this function assumes on a tuple before it can before it it it actually it can work all right so given a tupal that looks like that what's the function going to do it's first creating two empty tupal one is called nums and one is called words and then there's a for Loop and notice here the for Loop is going to iterate over every element inside the tupal remember in strings when we were able to use for Loops that iterated over the characters directly as opposed to over the indices where we're doing the same sort of thing here instead of iterating over the indices we're going to iterate over the tupal object at each position okay so first time through the loop T here is going to be this first Tuple the second time through the loop T is going to be this Tuple and the third time it's going to be this exact twole object okay so each time through the loop what I'm doing is I'm going to have this nums tupal that I'm going to keep adding to and each time I'm going to create a new object and reassign it to this variable nums and each time through the loop I'm looking at what the previous value of nums was so what was my previous tupal and I'm going to add it with this Singleton tupal so it's a tupal of one character or one element this element being T at position zero so you have to sort wrap your mind wrap wrap your mind around how this is working so if T is going to be this tle element right here then T at position zero is going to be this blue bar here so it represents the integer portion of the Tuple okay so as we're going through the loop this nums is going to get populated with all of the integers from every one of my Tuple inside Tuple objects so that's basically what this line here is doing at the same time I'm also populating this words tupal and the word stupo is a little bit different because I'm not adding every single one of these string objects so T position one being the string part of the inner tupal I'm actually adding the string part only if it's not already in my words list okay so here I'm essentially grabbing all of the unique strings from my list these last sort of three lines three four lines here just do a little bit of arithmetic on it saying okay now I have my all of the numbers here what's the minimum out of all of these and then what's the maximum out of all of these and then this unique words variable tells me how many unique words do I have in my original tubal so this feels sort of generic so let's let's let's run it on some data so here I have it I tested it on some test data and then I got some actual data okay and this actual data that I wanted to analyze was Taylor Swift data and representing the integer portion of the tupal representing a year and the string portion of the tupal representing the um the person who she wrote a song about that year okay so some real world data that we're working with here um very important that we know this this information okay so with this data I can run it I can plug it into my this function that I wrote up here and I'm going to actually comment this out so it doesn't get cluttered and if I run it this is the part where I'm calling my function I'm calling it with this data here t-swift being this Tuple of tupes and what I get back is up here line 38 is the return from the function being a large Tuple and that large tupal I'm then assigning it to my own Tuple in my program and then I'm just writing out printing out some statement here okay so I'm getting the minimum year the maximum year and then the number of people so I can show you that it works if I replace one of these names with another one that I already have in here so instead of writing a song about five people she would have wrote a song about four people yay it worked okay okay so so that's tupes and remember or recall keep in mind tupes were immutable now we're going to look at a very very similar data structure to tupes called list except that instead of lists being immutable lists are going to be mutable object objects okay so much like lists they're going to contain elements of any type or objects of any type you denote them with you denote a list with square brackets instead of uh parentheses and the difference being that they're going to be mutable objects instead of immutable so cre creating an empty list you just do open close square brackets you can have a list of elements of different types even oops even a list of of lists so one of the elements being a list as usual you can apply length on a list and that tells you how many elements are in it this is going to tell you how many elements are in your list l so it's not going to look any further than that right so it's going to say this is an integer this is a string this is an integer this is a list it's not going to say how many elements are in this list okay it's just going to look at the outer sort of the shell of of the shell of elements indexing and slicing works the same way so L at position zero gives you the value two you can index into a list and then do something with the value that you get back so L at position two says that's this value there and add one to it l at position three that's going to be this list here notice it evaluates to another list you're not allowed to index outside of the length of the list so that's going to give you an error because we only have four elements and you can also have expressions for your index so this python just replaces I with two here and say what's and says what's L at position one and it grabs that from in there okay so very very similar to to the kinds of operations we've seen on strings and and tupal okay the one difference and that's what we're going to focus on for the rest of this class is that lists are mutable mutable objects okay so what does that mean internally internally that means let's say we have a list L and we assign it uh sorry let's say we have a variable L that's going to point to a list with three elements two one and three okay they're all each each element is an integer when we were dealing with with tupal or with strings if we reassigned if we tried to do this line right here we had an error but this is actually allowed with lists so when you execute that line Python's going to look at that middle element and it's going to change its value from a one to a five and that's just due to the mutability nature of the list okay so not notice that this list variable this this variable L which originally pointed to this list points to the exact same list we haven't created a new object in memory we're just modifying the same object in memory okay and you're going to see why this is important as we look at a few side effects that can happen when when you have this so I've said this a couple times before but it's um it'll make your life a lot easier if you try to think of of when you when you want to iterate through a list if you try to think about iterating through the through the elements directly it's a lot more pythonic I've used that word before so this is sort of a common pattern that you're going to see where you're iterating over the list elements directly right we've done it over tupal we've done it over strings so these are identical codes they do the exact same thing except on the left you're going from you're going through 0 1 two three and so on and then you're indexing into each one of these uh each one of these uh numbers to get the element value whereas on the right this this L uh loop variable I is going to have the element value itself okay so this code on the right is a lot cleaner okay so now let's look at some operations that we can do on lists okay so there's a lot more operations that we can do on lists because of their mutability aspect than we can do on tupes or strings for example okay so here's a few of them and they're going to take advantage of of this mutability uh concept so we can add elements directly to the end of the list using this funky looking notation l.
append and then the element we we want to add to the end okay and this operation mutates the list so if I have L is equal to 213 and I append the element five to the end then L the same L is going to point to the same object except it's going to have an extra number at the end five okay but now what's this dot right we haven't really seen this before okay and it's going to become apparent what it means in a few lectures from now but for the moment you can think of this of this dot as an operation it's it's like applying a function except that the function that you're applying can only work on certain types of objects okay so in this case a pend for example is the function we're trying to apply and we want to apply it to whatever is before the dot which is the object okay and a Pen's only been defined to work with a list object for example which which is why we're using the dot in this case we wouldn't be able to use a pend on an integer for example because it that sort of function is not defined on an integer so for now you'll sort of have to remember or or or uh remember which which are functions that work with a DOT and which are functions like Len that aren't with a dot but in a couple lectures I promise it'll be a lot clearer okay so for now just think of it as whatever is before the dot is the object you're applying a function to and whatever is after the dot is the function you're applying on the object okay okay so we can add things to the end of our list we can also combine lists together using the plus operator okay the plus operator does not mutate the list okay instead it gives you a new list that's the sum of those two lists combined so in this case if L1 is 213 and L2 is 456 when we add those two lists together that's going to give us an entirely new list leaving L1 and L2 the same and that's why we have to um we have to uh assign the result of the addition to a new list otherwise the results lost if you want to mutate a list directly and make it longer by the elements within another list then you can use this extend um function or extend method okay and this is going to mutate L1 directly so if L1 was 213 if you extend it by the list 06 it's just going to tack on 06 to L1 directly so notice L1 has been mutated okay okay so that's adding add things to lists we can also delete things from lists right we don't just want to keep adding to our lists because then they'd become very very big so let's see how we can delete some some items from our list there's a few ways first one being you can use this Dell function and this says delete from the list L the element at this index okay so you give it the index 0 1 two or whatever you want to whatever index you want to delete the element at if you just want to delete the element at the end of the list that's the farthest right you do L.P if you want to remove a specific element so you know there's somewhere in your list there's you know there's the number five and you want to delete it from the list then you say l.
remove and you say what element you want to remove and that only removes the very first occurrence of it so if there's two fives in your list then it's only going to remove the very first one okay so let's take a look at this sort of sequence of um sequence of commands so we have first L is equal to this this long list here okay and I want to mention that all of these operations are going to mutate our list which is why I wrote this uh comment here that says assume that you're doing these in order okay so as you're doing these in order you're going to be mutating your list and if you're mutating your list you have to remember that you're working with this new mutated list okay so the first thing we're doing is we're removing two from our list so when you remove two this says look for an element with the value two and take it away from the list so that's the very first one here so the list we're left with is just everything after it then I want to remove three from the list and notice there's two of them there's this three here and there's this three here so we're going to remove only the first one okay which is this one here so the list we're left with is 1 6370 then we're going to delete from the list L the element at position one so starting counting from zero the element at position one is this one here so we've removed that and we're left with 1 370 and then when we do l.
pop that's going to delete the element furthest to the right so at the end of the list which is that zero so then we're left with only 1 three and seven okay and l. poop is often useful because it tells you the return value from l. poop is going to be the value that it removed so in this case it's going to return zero I want to mention though that some of the so so these functions all mutate the list you have to be careful with return values so these are all you can all you can think of all of these as functions right that operate on a list EX ex that what these functions do is they take in the list and they modify it okay but as functions they obviously return something back to whoever called them right and often times they're going to return the value none okay so for example if you are going to do l.
remove two and you print that out that might print out none for you okay so you can't just assign the value of this to a variable and expect it to be the mutated list right the list that the list got mutated the list that got mutated is the list that was passed into here okay we're going to look at one example in a few slides that's going to show this okay another thing that we can do and this is often useful when you're working with data is to convert lists to Strings and then strings to lists okay sometimes it might be useful to work with with strings as opposed to a list and vice versa okay so this first line here list s takes in a string and casts it to a list so much like we cast a float to an integer for example you're just casting a string to a list here and when you do that at this line so if this is your s here when you do list s this is going to give you a list looks like this where every single character and S is going to be its own element so that means every character is going to be a string and it's going to be separated by a comma so including spaces okay sometimes you don't want each character in the list to be at own element sometimes you want for example if you're given a sentence you might want to have everything in between spaces being its own element so that'll give you every word in the sentence for example okay in that case you're going to use split in this case I've split over the less than sign but again if you're doing the uh the sentence example you might want to split on a space so this is going to take everything in between the sign that you're interested in in this case the less than sign and it's going to set it as a separate element in the list okay so that's how you convert strings uh strings to list and sometimes you're given a a list and you might want to convert it to a string so that's where this join uh method or function is useful so this is an empty string so it's just open close quote right away no space so this just joins every every one of the elements in the list together so it return the string ABC and then you can join on any character that you would want so in this case you can join on the underscore okay so it'll put whatever characters in here in between every one of the elements in your list okay pretty useful functions okay couple other operations we can do on lists and these are also pretty useful is to sort lists and to reverse lists and many many others uh in the python uh documentation so sort and sorted both sort lists but one of them mutates the list and the other one does not and sometimes it's useful to use one and sometimes it's useful to use the other okay so if I have this list L is equal to 9603 sorted you can think of it as give me the sorted version of L gives you back the sorted version of L so it returns a new list that's the sorted version of the input list and does not mutate l so it keeps L the exact same way so this will be replaced by the sorted version of the list which you can assign to a variable and then do whatever you want with it like L2 is equal to sorted L for example okay and it keeps L the same on the other hand if you just want to mutate l and you don't care about getting another copy that's sorted you just do l.
sort and that's going to automatically sort L for you and L now contain l l is now the sorted uh the sorted version of L similarly reverse is going to take L and reverse all the character all the elements in it so the last one is the first one the second last one is the second one and so on so lists are mutable we've said that so many times this like but what exactly does that mean what implications does that um does that have okay once again this next part of the lecture python tutor um just type you know paste all the code in and go step by step to see exactly what's um what's happening so lists are mutable as you have variable variable names so for example L is equal to some list that L is going to be pointing to the list in memory okay and since it's a mutable object this list you can have more than one variable that points to the exact same object in memory okay and if you have more than one variable that points to the same object in memory if that object in memory is changed then when you access it through any one of these variables they're all going to give you the changed um the changed object value okay so the key phrase to keep in mind when you're dealing with lists is what side effects could happen right if you're mutating a list if you're doing operations on lists what what side effects you know what variables might be affected by by this change okay let's come back down to earth for a second okay this will wake a lot of people up okay so let's do an analogy with um with people okay let's say we have a person a person this case Justin Bieber is going to be an object right I'm an object right I'm like the number three Bieber's an object he's like number five right we're different objects we're both of type people okay let's say a a person has different attributes right let's say we can let's say he gets two attributes to begin with he's a singer and he's rich okay I can refer to this person object by many different names right his full name his stage name all of the fan girls call him by these names um people who dislike him call him by other names that I didn't put up here okay but he's known by any by all these different names they're all aliases or nicknames that point to this same person object right okay so originally let's say I say Justin Bieber is a singer and Rich those are the two attributes I've originally assigned to him and then let's say I want to assign a different attribute to him and say Justin Bieber is singer a rich and a troublemaker I'm being kind here okay okay so if I say Justin Bieber is these three has these three attributes so it's the same person I'm referring to then all of his nicknames right are going to refer to this exact same person so all of his nicknames are going to or aliases will refer to the same person object right with these changed attributes okay does that make sense okay so that sort of idea arises in lists so list is like a person object whose value you whose attributes can change for example and as they change all of the different aliases for this object will point to this changed object okay so let's see a few examples I apologize if this is a little a little small but this I basically copy and pasted from the python tutor which is just in the in uh from the code from today's lecture okay so I have this uh these lines of code here the first couple of lines really just show what happens when you're dealing with non-mutable objects so with non-mutable objects you have two separate objects that get their own values and that's it end of story with lists however it there's something different that happens so I have warm is a variable and it's going to be equal to this list so warm is going to point to this list here red yellow orange it contains three elements hot is equal to warm means I'm creating an alias for this list and I'm and the aliens is Alias is going to be with this variable hot so notice warm and hot point to the exact same object so on line eight when I append a when I append this string pink to my object since both of these two variables point to the exact same object if I'm trying to access this object through either variable they're going both going to print out the same thing okay and that's the side effect that's the side effect of of lists being lists being mutable okay if you want to create an entirely new copy of the list then you can clone it which sounds really cool but really it's just making a copy of the list and you clone it using this little notation here which is open close square brackets with a colon and we've sort of seen this notation here and this tells python this is zero sorry this is zero and this is length uh cool I guess but it basically says take every element create a new list with those exact same elements um and assign it to the variable chill so here if I originally have cool as equal to blue green gray right here when I clone it on line two with that with that funky notation I'm creating a new copy of it and then on the next line when I'm appending another element to the to the copy notice I'm just altering the copy the original stayed the same because I've cloned it okay so if you don't want to have this the side effect side effect issue then you should clone your your uh your variable your list okay so let's see a slightly more complicated example example where you're going to see the difference between sort and sorted in the context of this uh mutability and and side effects issue okay so once again let's create this warm is equal to red yellow orange so that's what warm is going to point to this list and then sorted warm is equal to warm do sort so do sort mutates so as soon as I do that that list warm is now the sorted version of it and notice that I've assigned the return of this to sorted warm and the return is none because l.
sort or do do sort mutated the list right it didn't return turn a m a sorted version of the list it mutated the list itself okay so when I print warm and I print sorted warm I'm printing the mutated version and then this none here sorted on the other hand returns it doesn't sorted does not sort the list that uh that's given to it and instead it returns a sorted version of the list so in this case if cool is equal to these three col gray green blue if I do sorted cool it's going to return the sorted version of that list which is blue green gray and it's assigned to the variable sorted cool so when I print them it's going to show me the two separate lists one being the original unsorted one and one being the sorted version last one's a little bit more complicated but it shows that even though you you have nested um even though you can have nested lists you still you're not you you you're not you don't escape this idea of of um uh side effects so first I'm going to create warm is equal to these two colors yellow orange so warm is points to these two colors hot is equal to this one list a list with one element bright colors is going to be a list and the element inside the list is a list itself so since it's a listed so this is your list and the element inside here which is a list itself is actually just pointing to whatever warm is that object okay then I do then I append hot to my bright colors so the next element here is going to be another list which means it's just pointing to this other list here it's not creating a copy of it okay so each one of these elements here is actually just pointing to these two lists here so if I modified either one of these then bright colors would also be modified so let's say I add pink here to my hot list we have red and pink then notice that bright colors the first element points to this list and the second element points to this list which I've just modified last thing is I'll let you try this as an exercise in Python tutor but the idea here being you should be careful as you're writing a for Loop that iterates over a list that you're modifying inside the list in this case I'm trying to go through the list L1 and if I find an item that's in L1 and L2 I want to delete it from L1 so one and two are also in L2 so I want to delete them from L1 and be left with 34 however the code on the left here doesn't actually do what I think it's doing because here I'm I'm modifying a list as I'm iterating over it and behind the scenes python keeps this this keeps track of the index and doesn't update the index as it's as you're changing the list so it figures out the length of the list to begin with and how many indices it has and doesn't update it as you're removing items from the list so the solution to that is to make a copy of the list first iterate over the copy which will remain intact and modify the list that you want to modify inside the loop so please run both of these in the python tutor and you'll see that what ends up happening is on the left you're going to skip over one element okay so you so your code so that's that's going to be the wrong code all right