OK. In this segment,
we're going to start studying data and ML that's built out of smaller pieces of data.
We're going to start with pairs.
So, we've seen numbers, we've seen booleans,
those are basic data values and we've seen
various ways to program with them like conditionals or variables or functions.
But we need some way to build up things that have fields,
multiple parts of them.
This is essential in any programming language.
If you have programmed in a language like Java,
you've probably programmed with arrays that contain multiple pieces or you've
programmed with classes that had multiple fields that sort of thing.
In ML, we are going to take a very sort of fundamental approach to it.
We are going to start with tuples,
which are a very direct way to have a fixed number of different data items,
each of which can have different types and then in later segments,
we'll start programming with lists that can have
any length at run-time but all the pieces have to have the same type.
These are not the only forms of compound data we will study
but they will be enough for the first homework assignment and they'll get us started.
So, we'll start with pairs,
and the way I want you to think about pairs is that they are
just things with two parts and so in terms of new
language constructs we need a way to build
pairs and we need a way to access the pieces of pairs.
So, here on this slide I have
the pair building expression and I have the answers to our three questions about them.
In terms of syntax,
we are going to write two expressions.
We are going to separate them by a comma,
put them in parentheses and that's the syntax for building a pair.
What are the evaluation rules?
Well what we are going to do is evaluate 'e1' to some value.
Call it 'v1', 'e2' to a value called 'v2' and then that pair of values will be a value.
So, one val new kind of value,
something that's done evaluating,
is a pair that holds itself values.
We also have a new kind of type for these pairs.
So, if 'e1' has some type say 'ta' and 'e2' has some type
say 'tb' then the pair expression will have 'ta * tb'.
So, just as the two parts of the pair,
the types of those parts separated by a star.
So, that's how we build pair expressions now how do we access the pieces?
Well, I will show you a different way in the future but for now let's use these two
constructs '#1' of an expression and '#2' of an expression.
The evaluation rules are that we are going to evaluate that expression 'e' to
some value it's going to be a pair and then '#1' will return the first part of that pair,
and then '#2' would return the second part of the pair.
So if 'x' is say the pair of four and 17 and we said '#1' of 'x', we'd get back 4.
Type checking works similarly that 'e' in there better have a pair type,
so it better be some 'ta * tb'.
Otherwise this access expression doesn't type check and then '#1'
of 'e' would have type 'ta' and '#2' of 'e' would have typed 'tb'.
So those really are the rules but like anything you tend
to really understand how they work by writing some programs and trying them out.
So, let's just write a few functions that take or return pairs.
So, how about I start with a 'swap' function maybe it
takes one argument I'll call it 'pr' for pair
maybe it has type 'int*bool' so it
takes something whose first part is an 'int' and second part is a 'bool'.
And maybe what I want to return is a new pair where I build
the first piece out of '#2' of pair and the second piece out of '#1' of pair. All right.
So I'll show you in a second an example of how that works.
In the meantime, how about I just write some other functions here.
How about I take,
write a function that takes two pairs both of which have type 'int * int'
and just adds up those four pieces that are in there.
So what I want to return is '#1' of pair one plus '#2' of pair one.
I can grab these four pieces in any order I want.
'#1' of pair two plus '#2' of pair two.
It's a perfectly reasonable function that takes as
arguments two 'int * int' and returns an int.
So the type of this whole thing would be '(int * int) * (int * int)',
and it returns an 'int' let's put that in a comment. All right?
Let's do a couple of more.
Oh, here's one that I really like because this is something that's just
completely natural to do and a pain to do in many programming languages.
Let's take in a numerator and denominator x and y so just two arguments of type and.
And let's return X divided by Y and the remainder of x and y.
Now these operators have strange names in ML;
div and mod but I can still write this.
All I'm doing here is returning a pair of two expressions
the result of X div Y and the result of X mod Y and so this function is
going to take in two 'ints' * 'int' and it's going to return a pair of
'ints' three to val print loop and we actually print this
out won't write those parentheses but it's just that simple.
All right. How about one more,
how about we take in a pair of integers and we sort that pair.
So we're going to return a pair of 'int' * 'int' and if the first part of the pair
is less than the second part of the pair
then we'll just return the pair we started with because it's already sorted.
Otherwise, let's swap it around and return '#2' of pair, '#1' of pair.
All right? So that seems like a good set of example functions.
Let's real quickly go over here,
make sure that I actually wrote those correctly and they load up here, good.
We see that swap is has type 'int'*'bool' arrow 'bool'*'int'.
So how about I try that out how about I tried calling it with seven and true and I get
true seven if I call it with let's say minus
four and false should get false and minus four.
Now, you might be thinking how does ML know that I'm
calling it with a pair and not calling it with two arguments.
Well, in a future lecture I will show you the ML that's actually
exactly the same thing but for now we'll keep them as separate concepts.
And let me try one more here how about sort pair of (3,4).
I just get back the pair (3,4) of type 'int'*'int'
and if instead I had maybe had a value that
was (4,3) and then I said sort pair of X it would come back (3,4).
Of course, I could have just directly asked
sort pair (4,3) I would get the same answer of course.
OK. So that's programming with pairs.
Let's go back to the slides here and show you that while that's
really all there is the pairs we can,
in fact, generalize this idea to tuples.
So a pair is just a two tuple.
In general you can have any number of pieces.
So to build a tuple with n pieces you just have
n expression separated by commas the type of that thing will be
all the types of the expressions separated by stars or something like
'int'*'int'*'int' would be a triple where
each piece was 'int' and you access the pieces with '#1 e,
#2 e, #3 e' and so forth.
So you'll get a lot of experience on this because 'int'*'int*int' is in
fact a common type for a lot of the problems on the first homework assignment.
I also want to emphasize that without adding
anything new to our language the rules I already showed you.
You can nest tuples and other kinds of expressions as deep as you like.
So, I have a few examples here on the slide we could type these into
the redeveloped print loop or into an M-L file as well.
But for example, if you write seven comma and then in it's own pair true comma nine.
Well that's going to be a pair where the first part has type 'int'
the second part is also a pair of type ('bool'*'int').
So the overall type is ('int*') parenthesis ('bool'*'int').
Therefore, if you took that x 1 and you applied the hash to
operation to it (#2 x1) is going to give back a ('bool'*'int').
So if we then added #1 of that so #1 of #2 of x
1 that would give you back something of type bool and in fact x 2 would evaluate to true.
Similarly, x 3 which is this #2 of x 1 makes perfect sense.
The result we look up X-1 in our environment we get (7,
(true, 9)) we do #2 that,
we're going to get (true, 9) and that's
a perfectly reasonable value of type ('bool'*'int') that we can then bind to x 3.
And of course, these things can nest however deep you want.
So, in this last line here maybe it's hard to
follow all the parentheses or whatever but we just have
a pair whose first part is a pair of 'ints' and
whose second part is two pairs of pairs of 'ints' sorry,
it's a pair of a pair of 'ints' hard to talk about
easy to program with and you can see the type written here. So that's tuples.
