In this third video, on designing an abstract function from two or more
examples of highly repetitive code we're going to work on the signatures of the
abstract functions. The signatures come last because with
abstract functions. They can sometimes be the hardest thing
to do. In order to learn how to write these
signatures, we're first going to have to learn a couple more pieces of notation
that we can use in type comments and signatures for describing them.
So here we go, I'm in parameterization V3.racket and what I need to do now is
finish up the signature for the abstract function contains.
Remember we're abstracting a function from two or more examples of highly
repeptiive code. I can't say that 3 times fast.
And doing that requires us to work backwards through the htdf recipe so it's
time to do the signature. And the way I'm going to do the signature
here is a little bit different than the way we've done it before.
What I'm going to do is I'm going to look at the code and read the signature off of
it. Some programming languages do a thing
like this automatically and it's called type inference.
So here's how it's going to work. The first thing I do, is I look at the
function and I see that. Let's see, there's two arguments, and of
course every function always produces one result.
So there's an error. What do I know about these two arguments?
What I'll do is I'll put a placeholder there to remind me that there's two of
them. [SOUND] And what do I know about these
three positions? What can I write here?
Well when we do this kind of type inference.
We look at the function and we start with this sort of clear thing we can find.
The most unambiguous information about the type of something we can find.
And when I look at this function I see that in it's base case it produces false.
And here it produces true so it's immediately clear to me what type of
value this function produces. It produces a Boolean.
So I can just put Boolean there. I read that because remember there's a
false there and a true there. This function is producing false and
true, it's therefore producing Boolean. Okay, let's keep going.
Let's look at this first Parameter S. What happens to it.
Well let's see. Here S is passed in the recursion, so
that doesn't really tell me anything particularly about it's type.
But look here. Here S is passed as an argument to string
equals. And string equals needs both of its
arguments to be a string. Therefore, s has to be a string.
So I know that the type of the first argument to contains question mark, is
string. Again, let me say how I discovered that.
I see that the first argument to contains s Is used as an argument to string
equals. I know that string equals require both of
its arguments to be strings therefore s has to be a string.
So I could put string up here as the type of the first argument to contains.
That just leaves me with this argument. Let's see what happens with that
argument. Well here I take first and rest of it.
So I know its a list and I'm going to give you a new present here that we can
use in terms of writing types. Which is instead of defining list types
and writing list types the way we've always written them.
I'm going to let you just write list of and then something here and that's
going to mean a list of that. Let me keep going and I'll come back to
this list of thing. If I look here in more detail when I take
first of the list, first of the list ends up being an argument to string equals.
That means first of the list has to be a string because string equals wants its
arguments to all be strings. So this here, this first and rest told me
that los had to be a list, and the fact that this first of los is used as an
argument to string equals. Tells me that it has to be a list of
string. So I can write this like that.
And again just to explain this list of string notation, what you're allowed to
do from now on in the course is any time you want to have a list of type, list of
string, list of boolean, list of drop, list of whatever you want to make it be
Instead of having to define the whole type the way we've been doing with form
data definition, something like this, from now on you don't have to have the
data definition. You can just write open paren list of and
then the type of the elements of the list and a close paren.
So that's a little present here in the middle of how we produce the signature of
abstract functions. So there's the signature of contains.
Let's go on and do the signature of map 2.
It's going to work the same way. Let's see.
Map 2 clearly consumes 2 arguments. And it produces a result.
What do I know about those arguments? Well let's see, this first argument fun,
is a function because right here I'm using it as a function name.
So fun better be a function. So how are we going to write the type of
a function? When it appears in the signature of a
higher order function. Well the way we're going to like do it is
like this we're going to put an open paren and then we're going to put we're
just going to use a paren to wrap itself. We're just going to use parenthesis to
wrap themselves around the signature of the function.
So this part here. Will be the signature of fun because its
the type of the first argument to map2. This'll be the type of the second
argument to map2 and after the error will be what map2 produces.
Okay what else can we tell from here easily.
Well in the base case this function produces empty and in the non-base case
it produces cons of something in the natural recursion.
So this function is clearly producing a list so we can write list of there.
Well, what do we know about the elements of the list?
What can we find out about this parameter?
Well, here we see that this function is taking the first and the rest of It's
second argument, lon. So that means this thing is a list, too.
[SOUND]. Notice I'm gradually building up more and
more knowledge about the signature of the cleat function.
Now, I want to stress here. There's no single right order to go
through these. Okay, I kind of tend to go from the
easiest pieces of information I can pick up about the type to the ones that
require more work. There's different orders you could go
through this. What matters is that you end up with the
right signature for the abstract function.
Okay. So what I know about the elements of this
list. The list which is passed to map two.
Well, to figure that out. I should look for a place that calls
first on the list. And the only place that calls first on
the list is right here. And notice something very interesting,
which is. That first is past immediately to the
function argument to map two. So map two itself never sees the first of
the list. It doesn't really know what it's going to
be at all. What it does know is that whatever type
of thing first is, whatever the type of the elements of the list Is is the same
type that function better be able to accept.
So we've got an interesting thing. This the elements of the list as far as
map two is concernered can be anything but they have to be something that
function is prepared to accept. And so I'm going to introduce a new
notation that'll allow us to express that.
And what we're going to do is say well, you know, the type of the elements in
this list can be anything so we're going to use whats called a type parameter.
And by convention type parameters. Or upper case single letters of the
alphabet. So here, we're saying, you know, the list
can be of any type, call it x, but fn has to prepared to consume that same type x.
So what these two 2 xs mean is they mean anything you want, as long as they're the
same
[INAUDIBLE].
Now, let's look at the type of the result list.
Well, there, we need to look at where the elements are put in the list, and that's
where the cons. There's only one cons in here that builds
up the result. And look at what it's doing.
It's taking whatever the function produces, and sticking it in the list.
Map two itself never really operates on what the function produces.
It just sticks it in the list without looking at it.
So, that means that whenever function produces is going to be the type of the
elements of the list. And we're going to use the same trick
here. Is we're going to say the function can
produce whatever it wants. I'll call it Y, but that's what map two
is putting in the result list. Why?
So let me read that from scratch. What it says, it says hey.
The signature map to is this. Give it a function that consumes x and
produces y. Give it a list of x and it will give you
a list of y. So in the case of square you got a
function from number to number and a list of number and you get back a list of
number. The map2 can do other things.
Why don't you right now assure yourself that map2 can do other things by doing
this little problem where I just want you to write a check except for map2 where
the function argument you pass to map2 is string length.
So write that check expect now. Okay here is the check expect that I
wrote. I said check expect remember I had
prescribed that the function argument had to be string length.
Well that is a function from string to natural.
So that means x has to be string. And y is going to be natural.
So that means the list argument to map 2 has to be a list of string.
[SOUND]. A, b, c, d, e, f, for example.
And what we get back is a list of the string lengths.
List 1, 2, 3. Let check that to see if works.
Great, now just a quick review so far we've introduced three new pieces of
notation. You can write open prin list of followed
by any type and a closed prin and that means a list of that type.
In a function signature if you have to include the signature of a function you
just put parentheses around that function signature, and I've also introduced this
notion of type parameter which allows you to express these kinds of consistency
relationships in signatures where you're saying for example in the case of map two
You know? This function can consume anything it
wants. But whatever it consumes, you better give
me a list of that same thing. Let's do one more.
Here's filter two that we started on. So, let's see.
It consumes two arguments. So the signature starts out looking like
this. And what do we know.
Well let's look at the result position it produces empty sometimes and cons other
times so therefore the thing its producing is clearly a list.
List of something, we do know quite what. Let's see, let's look at it's long
argument. Hm, here we take the first of lon, here
we take the first lon, and here we take the rest of lon, and here we take the
rest of lon. Lon is pretty clearly a list.
So it's a list of something. What about pred?
Well here, we passed pred in the natural recursion, so that doesn't tell us
anything about its type, but here, we call pred as a one argument function.
So pred is clearly a one argument function.
So we'll write this. [SOUND].
Okay, let's keep looking at pred, since we're right there.
Oh this is interesting. Notice that pred is used in the question
expression part of an if. Because this call to pred appears as the
question of an if what does pred have to return.
It has to return a Boolean right. If wants it's question to produce either
true or false. So this is telling us that pred has to
produce a Boolean. Okay, let's look at the argument to pred.
I see, the argument to pred is an element to the list.
So that's telling us that, that, you know?
This position and this position are going to be the same.
Do we know anything more specific about that position?
Let's go look. Let's see.
Here, we call first of lon, it goes directly to pred.
So that doesn't tell us anything more specific.
It doesn't really look like filter two itself ever looks at the elements of the
list. Here it passes it to pred, here it sticks
it in the result list. Filter two never itself operates with
some other primitive. On the elements of the list.
So what that's saying is the elements of the list can be anything except that pred
has to be prepared to consume them as its arguing.
That's what this is saying here is its saying Whatever first lon produces, pred
must be able to consume. Now we've only got one thing left which
is the type of the elements of the result list.
Well, this cons is the only place were we add elements to the results list, here we
just produce empty, here we add elements to the results list.
What do we know about the types of these elements?
Oh, look the only thing that ever gets put in the result list is an element of
the consumed list. What that's saying is you know whatever
comes in is the same type that goes out. So that means that this is also x.
If you call filter two with a list of numbers you get back a list of numbers.
If you call filter two with a list of images you get back a list of image.
If you call filter two with list of string you get back a list of string.
So there you go that's the process of inferring the signature for an abstract
function by looking at the code for the abstract function and piece by piece
inferring what you can about the types of the arguments the abstract function
consumes. And the type of the result the abstract
function produces. In using tight parameters, these x's and
y's, in places where the abstract function is willing to consume data of
any type, but using x and y repeatedly in a single signature to talk about
constraints where the abstract function is willing to consume any type.
But the type of two different parts of its signature must be consistent.