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.