OCaml Tuples Records Algebraic Data Types Tutorial

[00:00:01]welcome everyone to this fourth uh video on on an introduction course to uh functional programming in camel and uh my name is david broman and uh today i'm going to teach you a little bit about tuples records and in particular on algebraic data types that are really useful when you're constructing programs so it's all about how to construct data and how to deconstruct the data and to use that in programs and we'll continue to use this uh repel editor in the triocamel pro so you don't need to install anything yet to be able to do some fun coding okay so let's start with tuples what is a tuple well it's it's basically a a way to compose together data a with a fixed number of elements so we have for example an integer but if we want to have two integers stored together we can create a pair and this is a tuple with two elements where both of the elements are of type integer so if you look at the type signature here you see that the the type is written with a star it says that this is a tuple two with two elements in with of types int and int and this particular value was three and four so you can have that for for example to have a five elements [Music] now four three elements and and you see here that these uh it's just three parts here so what is the difference to a list well a tuple always has a fixed number so if you define a type it has it says the type says how many elements you have whereas a list you can have a type but there will be we can be any number of elements in that list another difference is that a list always have to have the same type for all elements whereas the table can have different uh different types for the different elements so for example if you write like three high and ten we get here a tuple where you see that we have an int string int right and this can then be used later on when you construct data let's see here how do we deconstruct it well there are special functions it's called first and second for tuples where there are only two elements you can for example if you if we define a a tuple here that we call uh wow and 55 right then t we can do like this if we write first t we get the first element of the tuple if you write first second t we get the second element if we have a triple so say that we had high one and five and the first we get a a type error saying that you cannot do that because the first and second only works for for tuples which have two elements so if you want to deconstruct things that are longer you need to use a some sort of pattern matching and one way is to do pattern matching using the match construct so let's define a and look at this uh this new a tuple let's let's take a tuple again and and we say that we have uh wow and we can do true there as well we see that we have three different types here if we want to uh match out this we can we can actually let's see here let's do this and and do it another one so we have four elements here and in if we want to match here we can match on t and then with and then we write the pattern and the pattern looks exactly as as you do when you construct in tuples but you can use the wild card if you want to ignore something so if we just want to match out the string here we just like this and then we have to say that we we ignore the rest [Music] and then we just do like this s [Music] then we extracted out the s if we want to extract out say the the two ins here we can ignore this one and then call this one x1 and x2 so these are then as before pattern variables so they you you give them names and then you can use them later on so now we know that both of these one were integers and then we can extend it out and then for example sum them together so you see that we for this particular integer for this particular tuple we we could then extract out this so this match expression then works for any tuple here that has this type a specific type here which now happens to be this this tuple okay another way of doing this is that you can actually use a let to deconstruct so you can do this with tuples because it's at compile time we know how many elements and which types you have so let's see again that we want to do this then we can write the let it actually you write the pattern to the left so here if say that we wanted to extract the boolean value here we can do like this [Music] equals to t and we get now we have defined b that can be used later on if we we can also have all of them here x1 x2 and we have extracted out all all the different values inside the tuple another way of doing this when you construct data is to use immutable records so these are records where you can actually you don't update values inside the records but you just give them uh names so it's very much like a tuple but where you give different fields names so let's uh look at an example let's go into the editor because if you use records you need to define the type of the record and you just write type and then let's call this a person [Music] and here we got a person type and say that you have two fields name string and you have to end that with the semicolon and then age it now we defined a a person and and the type of that person and let's uh evaluate that and we see that we it says that we have a type and the type looks like this so it actually in the type it stores what is the name of these different fields and then if we want to construct something a record you let's say that we give this a new construction a name here p1 person one name equals to zara and h equals to 23.

[00:07:50]we have a person sarah with age 23 and if we want p1 we we just get it if we want to get out just the name we write p1.name if what we want to get out the h we just write like that and if i write something else wow it doesn't work because that field doesn't exist right so you can check that now you cannot destructively update this but we could for example define a new person we can we can update this immutably let's see what happens then say that we have sarah and h with this one p1 p1 but we want to change uh her age to four so then i can use this p1 with construct and then i just say h is equal to four which means that it will return this person but update it with just this field so you see that we still have sarah but now h4 but this did not change p1 so if we look at p1 it is still 23. so we just constructed a new record with with this information so if we want to this new record we can give that a new name p2 [Music] and then we still have p1 you see here we are not changing anything like in in in other imperative language where we are doing destructive updates we are just creating new values but we can we don't have to retype all parts of the record but just update some of the fields okay um now let's jump into what's called algebraic data types and this is is pretty exciting and and important and so say that you you can use integers for many things but sometimes you want to give names to things instead say that you want to have a new type which we call country and we define different countries here right denmark germany [Music] say china usa okay so we have now a new type where we can it's a little bit like an enum in in c and these these each of these different elements are constructors you can construct now new uh data items like denmark or germany and the type is is country and we should spell it correctly country so let's evaluate the code so we have a new type and if i write denmark i get an element of type country that is denmark or china and we can use that and we can patent match and so forth on it so let's see here now let's say that we want to create a function that is returning the con you know a country calling code for for that country so let's call that calling code country um so now country here is this is a type and here i just happen to give a name of a parameter with the same same name but they are not related and we could call this parameter whatever we want of course do we do a match [Music] a country [Music] with [Music] oh and we shouldn't do that like this and then we say denmark and you have to look it up but i haven't done that already so denmark's got country code 45 ceremony code 49 china 86 [Music] correct and usa got number one so i guess they were the first one to define this okay so we have the country code and then let's check this so that means that if i now call the this function code and i write germany [Music] it returns 49. so we have created this data type that we can be used as a value and then now we return different values depending on on the on the blockbuster return here like this okay well um what if we now added sweden as well what happens now so so now we see here that we have one country here uh but we have sweden here but we don't have not added any matching what happens if we call sweden here with that let's just see what what the compiler says here well it gives a warning not an error says in this pattern it's not exhaustive so this is really nice feature of camel is that it checks that your pattern matching is complete and it it's very useful when you are refactoring code and so on because it will tell you places where you have been missing where you need to do the updates but it's actually still a legal program so you if we do like this we get the result but now if we call with sweden [Music] we get a runtime error so this warning tells you that you should actually fix it but if you don't fix it you get a random error okay so so let's fix that so we have sweden [Music] and we know that that is go to 46 [Music] and now we can go to sweden and we get that and we didn't get any compile time errors for warrants now let's say that you we actually want to provide some more information with sweden we we also want to say what is the population of sweden but we we don't say it for any other cod we just happened to say it for sweden okay then you can add add this kind of extra information for some of these types and you use this off keyword and after that comes the type and now it's just one type but we can have couples as we'll see quite soon okay so you have this in here and and then we evaluate this and now we should get an error a type error because it says that the contract of sweden expects one argument right because we added an argument but this one does not have an argument so we need to fix this this this uh here and um and we can basically just add that like this stating that it's got one argument and then um then you you basically say the wild card but just please ignore it and then it's fine right okay so let's say let's continue with this example well we've said that this was the population but it giving it just interior might be not that easy to read so what we can do we can create a type alias so we write population here [Music] station so this is just a type alias we say that population is the same thing as in and then we can use this here instead so this doesn't change the program it just gives if you check it it's also okay it just gives it's a little bit more readable when you read the data type so it's often when you read functional programs these data types tells you a lot about the program you see the structure of the program and then you have functions operating on these data types so let's try this uh out here again now we can call you know define denmark again right but when we do sweden here we cannot just do sweden because it expects one argument so we want to add something and let's say the population of sweden now i write this in [Music] today's numbers i mean it's changes all the time i think it's about 10.3 millions right now so we have defined now something of the population of sweden right and that means that we can still call the calling code oh we cannot and it's requires this you need a parenthesis uh around this to be able to work and and since just to see here we will use i i use uh parenthesis for this as well right now but but it's not needed it's it's when you have tuples you this will also work right now okay and now the next task is to to create a function that extracts the population of the country so please try to do that write the function now that extracts the population of the country and let's call that pop just and then count three and try to do that and take a pause and then come back and now we say that we have done that so then [Music] what do we do we we do match on country with and then you need to imagine denmark um right and what what should we do with this we could do like this we could then mark should it match what should we say about the population here i mean we don't know so that's a little bit weird now we have defined population here but we don't have the population so but we need to return something so so let's for now we will fix this in a better way later on but let's just say now okay denmark is zero and and and then we have germany [Music] zero and so forth and and maybe you recall from a previous lecture that you don't have to write this over and over again you can you can actually but it's like this you don't have to repeat the out end result there and then you have china and usa [Music] and sweden [Music] we have the actual value so let's just do that like that we have the p the population and we return the population and that's it so let's see here so if we say we can give this [Music] let's s equals to sweden right and then we can write just pop s and we get the population but if we write pop denmark we get zero okay um okay can you write this in a different way yes just to recall the shorthand notice way of doing is that you you don't have to do the match but then you have to use the last argument remove that so this is the same thing right might be a little bit unclear to some people but uh it's shorter so yeah you you can do it do this in a way if you want to but if we continue with this style we can also actually in this case write it even shorter so we we do this sweden here p e and then we do a match all through so it's basically wild card anything that is not sweden you do like zero [Music] this will give the same result the question is why did i do this when you can do this kind of short form well there is a benefit of repeating all this and really put this in and that is because if i now add another country later on this function will complain and say oh you forgot the case and this means because maybe you don't want to do this maybe this new case actually you want to treat it differently but in if you do it in this style it everything will be accepted so it in that sense it's easy to add things but it might be that you have then forgotten to do the right thing on this this this branch so i for larger programs i even if it's a little bit more tedious to to write out all these ones uh it's it's often recommended because when you're refactoring code it it's it's kind of more robust to changes yeah so this was just defining some data structures but these are pretty simple data structures with some constructor and then you can stick on some data but it gets even more interesting when we have recursive data structures and what we're talking about here are variants or also called algebraic data types so these are types where you have constructors and attached data to it so let's let's look at some new [Music] programs here and now we have this we will have the we can actually remove the populations part here like this um but keep the rest let's look at a tree so let's create a binary tree here type 3 is equal to and then we say that we have a tree with nodes we have a node of 3 3.

[00:22:58]so here we have now a tuple as you see with a star here so we have two elements and this is a node in a binary tree but it refers to self so it's recursive definition you don't have to write direct here when you define the type and then we say that we have a leaf in this binary tree with a string so we all the leaves include some information a string but you can add any kind of information here and have more constructors and so on let's do that and then um let's define a a tree just say how do we construct a tree well we just write the constructors so first we have a a perhaps a node [Music] and then that node should contain two things x and y right but and we just replace this maybe we want to have a node there as well and then we have a leaf maybe and the leaf contains a a first you say it's something it's called first and then we have another leaf [Music] thing second [Music] okay and we close that little node and then we have one more there and let's put a leaf there as well we call that a last okay and we check that looks correct and we evaluate and now we have a tree so we create this tree here t1 and with just one tree we can create other trees like let's we can create a a t2 where we just say it's just maybe t2 is is less interesting it's just it's just a leaf hi right so we can custom construct different trees now and they are recursively defined as you see because you can have node inside nodes right then you can draw this on paper as a tree which makes it a bit simpler to to to view of course okay so now the next task is to write a function that pretty prints that means that we are actually cr returning a string that prints all these information so so the interpreter here is kind of pretty printing for you but say that you have a program you want to pretty print this in some other way you can you need to create a string a function that does that so the task is to do that and and let rec pretty let's call that the function and let's use this shorter hand where we have a function so that means that the first argument here now is is the is the tree so try it out and do that and i'll give the answer now um so you could then pat a match and you have to patent match on on the different things so you need to add patterns for each of the things each of the constructors in the in the type so here you have a node and you have to give pattern names for the two parts left and right three let's just write left and right here and then let's do something with it and we want to return now the string representation so let's write node maybe we can use it just to show that this is different from from the once generated and we do like this and then we concatenate this with a pre a recursive call to ourselves now we will print the print the first node the left node here so we call ourselves and that will return a string that will be then concatenated here and we also add a comma just to make it and look nice and then pretty r so we are pretty printing the right part of the tree [Music] and then we end this okay and then if we got a leaf [Music] we maybe just say leave with big letters kept the letters and we can do like this if we want to actually get the quotation mark in here so you have the back escape it and then s and let's do the same thing there like this okay check no it was an error ah see here lead leaf it should be called leaf okay and now let's run that so if we want to grab this t1 here right and if we want to call and pretty print using our 3d printed function we'll just call pretty and t1 and here we go we get this and you see the difference that we decided to pretty print and call it with capital letters here okay nice um this is our first recursive function our next task would be to write the function that counts the number of leaves so let's break count leaves so the task is to do that now you want to count the number of leads you have to recursively go down and count the number of leaves and pause and now i will show you one solution left right do that again count [Music] leaves left so this will recursively go down and count all the leaves in the left branch and then we do the same things on the right branch right so we are going through down left right right branch and then in the end summing it up the only thing we have to do here is also to to then we can ignore the content of the leaf and just say that we have one leaf and then we will recursively go down and up and count let's check it and then we say count eaves and we can do it for t1 and as we saw here in t1 we have one two three leaves right and we should get three back yeah that's correct [Music] hmm right now let's say that we want to write this a function um that returns the all the lists so we want to append together we want to create a list of all the strings that we have in the leaves so you want to have a list of all this we want to dive through the whole tree and just pick out all these leaves and put them in a list and return the list let's write this recursive procedure for that so let's call that string list one and if you do that now you need to um you need to think about how to do this and try to now we will write two versions of this one where you're using list append and then when one where we're not doing it and then we'll discuss the benefits of and drawbacks of these approaches so try to do that now and pause and now i give the solution so we give a node left right and so then we want to append two strings so we do a list append and then we recursively recall ourselves string list one left and string list one and right [Music] so this means that we are recursively going down and there we're also appending and then we're combining everything together in the end and for the leaf we just take the string [Music] and return the string well will this work no because list append assumes that there comes lists so we might need to put this into a list directly here and this is called a singleton list and so we try this out and see here so string list one and we do this again for t1 [Music] and what we get is a list where we extracted out all the values from the leaves cool well what is the problem with this um well list append is a little bit dangerous because it's actually has to go through the first list when it's appending and and and then before it can append so it depends all these two this this other one uh so it it and we when we do this over and over again we get a pretty bad complexity so what we can do here is to to write this instead using a accumulator pattern so we and then we kind of go through everything and you'll see that this really looks like a fold but now we're doing it on a tree in this lecture we will not talk about how to do folds and maps and so on trees because there are approaches to this but i will not cover this in in this first basic uh tutorial uh so for now try to write recursive functions over over uh the over the data structures in instead except for lists where you should use the the standard functions all right so let's do this and call this string list 2 and then we have a a a tree now we can just give it a tree so we want to have this accumulator pattern but let's do it with a nested function as we did in the previous previous one so you don't have to provide this accumulator start a value from the outside so then instead we do this let rec work where we have an accumulator and and then we write function inside here okay and now we do this node left and right so what do we want to do now with the accumulator well we we want to call this work function because we want to accumulate and you know every time we we get we want to recursively call first the left and then the right and while we're doing that we just want to go through down in the tree so what we do then is to try to work and then in in this inside here we just write work again [Music] so this means that we first will do work on the left branch and we'll just pass in the accumulator and then we will work on the right branch so the resulting accumulator is given here to the second one when we do it to the right and then in the leaf wanted to create a list so we just append the string to the list using a cons in right and now we just have to start off like this work three what will happen then we will we'll start off with an empty list and then traverse the tree but as before this will with the doing this we're accumulating will will refer the order so say that we want to have the right the same order we need to also do a list reverse and then i hit the wrong button here like this list reverse and we got it and it checks so so this list two now should do the same thing as list one we evaluate it and we can try it out two and it does the same thing right we extract the the elements and we get the right order so you can see here that we wrote it using a recursive pattern and we got the same same result right so you can do a lot of things with trees you can or or other data structures here with the when you define this with algebraic data structures you can traverse the trees collect information update the trees you change the trees but you always return a new tree and it turns out that still if it sounds like this would be very inefficient but the compiler will compile it very efficiently so even you know returning new trees all the time results in very efficient implementations now let's look at this code again this tree node here what was the i mean this looks good but we have now decided that we will we we only have the same we always have the same type here it needs to be a string say that we want to make this polymorphic as well so we want to say that well we don't want to decide here which tree we have we just want to say which uh that we can have any any value in the leaves then you type this by giving a type variable here and then you need to provide that type variable in every place you use it in your recursively defined type and here we then get the tree so now we say that have this tree but we can later on decide what is the actual type that we store inside the leaf node this means that we can still have what we had here before we can you can look at this [Music] we can just copy this again [Music] like this so if we run this we get here we see the leaf node second and so on and we it works when we look at the tree here we see that we wrote this type and this is exactly what a camel will say is the type with these type variables but we can also hear by another one let's t2 where we have say a node and then a node and then we give integers instead i mean leaf here [Music] or maybe we have a node and when we have a leaf and 20 the leaf 15 and then we had to add another oh like this if we run this again you see here that we t1 and t2 are both using the same type definition of the tree but we instantiate it with different values so then if we now copy here the count leaves here again and copy it down here and actually we can remove some of these ones just to make it a bit yes as well okay now we see this count leaves here we this countless is counting the leaves but we didn't actually use this this variable here and of the type so if we look at that one we see that it the count leaves is has the type any this it doesn't matter if it's an integer string you can take any of these trees and count the number of leaves so we can say count leaves t1 e3 and t2 is 3. so you see that now we have a polymorphic type but also we can use polymorphic functions on them that works for any any tree and that has this definition but this doesn't matter which kind of value if we were using the fact that it was a string then it will only work for trees that are of stream now let's write another uh polymorphic function so we want to now to write a polymorphic function that has the following signature we wanted to have it as like a to a to b and then three two three so here we now want to have a function that takes a tree and and updates it so we wanted to update and change all the values inside this tree to be some of some other type or some other value so it's kind of a you basically it's like a a map where you are mapping and updating all the leaves the values of the leaves let's define that function let rick update [Music] f and we use this shorthand so this is the the second argument is now the the actual three and please try to do that see if you can figure it out how to do this function that updates the values of the leaves and now i'll show you the results here so we have a node we just deconstruct it and then construct the vn and and we call update recursively in the down in the in the tree then we call update recursively on the right side okay um and then on the leaf that's where we're going to do the change we have a value and and we just construct it again but we apply f on it and that's it check it run it and let's do an update on t1 so let's say that we do update we want to do an update on on the on the tree t1 and and we write in lambda here we say that x is now the element so it's for t1 it would be the string and we say that we add for example this to the string [Music] let's see here um what did go wrong this type has type string 3 but an expression was of this way more complicated format let's see here what did i do wrong well you see i happened to write twice this was the mistake here [Music] here we go now you see that i was updating this tree and everywhere we added this dash dash to the leaves and this can be an arbitrary big tree of course and we can do the same thing i mean if if we apply this to t2 it will say that it's not compatible because t2 was defined with a with integers so let's write another update function uh where we do something with the with the leaves and say that we are just adding a number to it [Music] see here update fun and we forgot the x there and we're just adding the number like t2 had originally in that you see here we are returning a new tree we are not changing anything t t2 is still got the value we were just returning a new tree where we updated so we always transform and create new trees we never update the trees themselves okay that is enough about the trees you can do it just play around and try out different examples with these trees and the last thing i wanted to show you was what is called option types so we saw that this problem that we had here before with the option types was that you could not extract out the values here uh from from a country code when we wrote that this pop function we returned zero all the time right we returned four denmark germany and so on we got the value zero and but the population of sweden we could extract out we we do not want to do that i mean it's it's kind of strange to say that the population is zero so we we actually want to say that either it's okay here we got the population or oh we don't have the population and this is where you have can have this option type or sometimes called the sum type and and this we can look at it in the top level here to see just clear out some um so an option type has two possible values either it's none you see this is the option type option and it's got a any kind of type containing it because the alternative is that you have some and that is that then you provide the value you have sum for example it says that oh you have a value is 10 or you have none so you either an option type is that either sum you have the value or none you did not have the value and this sum is is polymorphic so you can use like for strings or whatever type and then it says in the type here that the option type here this is an option type of type int and this is an option type of type string and this this part is actually stating what is the type that is constructed so you see here the option type is actually just a correct data type that we could have defined ourselves but in the in the common documentation and in the standard library these option types are already defined so it's kind of standard to use them [Music] let's let's use it here just to again then re rewrite the um the pop function here but return the population that is expressed the population but just return [Music] return the the value of of the population if it is sweden for all other cases we should just return um none and we can do that just like this let's now write the proper usa and instead of zero as we had before we returned none and for sweden we return sum and then give the valley p if we evaluate this [Music] if we write pop germany now we'll get none if we write pop sweden [Music] and we have [Music] say that we just had 100 people in the country it returns some and you can pat a match on this so typically you return and then you do different things depending on what you what kind of value you have on that so say that you wanted to print the population and you you call pop and you get the population and then you want to print the value you say that we are using a this library printf we can open this and then we we can use this without we can also write it directly with the dot notation that we did before but we can also open a a module so let print pop function we have one argument there and none so now we just said if it's none maybe we want to just write out uh [Music] relation is not available okay and for some value we basically say just what is the population and the printf here is this is very similar to to you know c c and standard c printf and then we buy it okay so then we'll print out either we print out there is not available or we will actually print it out and we can do whatever so it's just that this is a very good way of doing error handling in a functional way you're returning a either it went okay or it went wrong and then you evaluate this and we got an error we forgot something we forgot to say that printf here here we basically say that oh we should provide something to print and we forgot to do it and the compiler is smart enough to discover this so that we forgot to add v because that's what we are printing right so if we run right uh population and um we got this uh to sweden here and say sweden 100 [Music] and then we do like this and then we do print pop and it's prints that you can actually use also show you the pipe operator here instead of nesting it in this way we can actually send the result to the next operator printful okay and if we repeat this but we take denmark instead [Music] it will print population is not available great um this is basically what i wanted to show you about algebraic data types so we're just shown this on very small examples but i mean uh in the course that this is designed for we are going to write a compiler so you can do this you know have arbitrary complex structures when you when you operate on on trees and data structures so i hope you got the main points of this and thank you for listening to this video in the last lecture uh of this uh introduction i i'm going to show you a little bit about you know exception handling that is some more things about side effects some things are exceptions and also about basic i o input output so you can get started to write actual programs so thank you for listening take care