So, let's see. 
Form of the information determines the 
type comments. 
Type comments determine the template. 
Template determines the form of the 
functions. 
Then when we have repetitive functions, 
we can abstract them into an abstract 
function. 
Could there be a way to shorten that 
route? 
In fact, there is. 
In fact, there's a way to go from type 
comments directly to abstract functions, 
and then lots of the functions we write, 
just become very short. 
We're not going to take quite that 
shortcut in this video. 
What we're going to do in this video is 
go directly from templates to abstract 
functions. 
And that will take us all the way back to 
something we saw when we first looked at 
list functions. 
Remember the table of list functions, and 
we just looked at what to fill in to each 
position in the template? 
Now what's going to happen is lots of our 
functions on lists and arbitrary arity 
trees or any other kind of recursive 
structure are going to get real short. 
And generating the abstract function is 
going to get real automatic. 
I'm in fold-functions-starter.rkt, and at 
this point in the course the type listof 
X means list of x is one of empty or cons 
x ListOfX, and you know, we interpret 
that. 
What is there to interpret it as, as list 
of X? 
In the template for list of x is the 
ordinary list template, two cases con, if 
it's empty something. 
Otherwise, dot, dot, dot, the first of 
locks, fun for locks, rest of locks, and 
I've renamed the parameter to locks 
because it's a list of x. 
Now here's the problem, and the problem 
is to design an abstract fold function 
for a list of x. 
So you might ask, what the heck's a fold 
function. 
Let me show you. 
Here's the idea. 
The idea is to design an abstract 
function based directly off the template. 
So again, I'm going to work backwards 
through the steps of HDBO. 
I'm going to copy the template. 
And I'm going to call the function fold. 
It's actually going to be the foldr 
function. 
But I'll just call it fold. 
Then, I'm going to say, gee, there's two 
sets of dots. 
I'm going to introduce one parameter for 
each set of dots. 
And I should give them some good names. 
Now, this one is the base case result, so 
I introduce parameter called b. 
And I'll use it in this position. 
There it is, I'm also getting rid of the 
parenths, because b is the final result, 
it's not the function of no arguments. 
So there b is now standing for the first 
set of dots, and this one is a function 
that's called to take the first of the 
list and combine it with the result of 
the natural recursion. 
So, I'll call that fn and just like 
convention we put the function arguments 
early and abstract functions. 
So I ordered the arguments that way you 
can order them the other way I just want 
this to end up being exactly like foldr. 
So now I've got the function. 
Now I've got the function. 
Now let's do some tests for it some check 
expects. 
Well it's the abstract function for the 
list template so I know some of the 
things that it can do. 
If I say fold with plus and zero and list 
one, two, three, I get The sum of that 
list which is 6. 
If I say fold with times 1 and the list 1 
2 3, I get the product of that list which 
is also 6. 
And I could try those to make sure I 
understand this function properly. 
Oh, what happened here is I forgot to 
rename the recursion and I forgot to add 
the parameters to the recursion. 
Huh. 
You're always making mistakes in this 
business. 
Now I've renamed the natural recursion 
and I added the parameters in the natural 
recursion. 
[SOUND]. 
Now, these tests are tests from later in 
the file. 
So we're not going to worry about them. 
These failing tests are from later in the 
file. 
Let me comment that out, so we won't see 
that ugly highlighting. 
My tests for fold are working. 
[SOUND]. 
So now, what's the purpose? 
Well, if you didn't have a more abstract 
way of writing the purpose. 
If you didn't know that this was fold R. 
It would be enough to say [SOUND] the 
abstract fold function for list of X. 
Because that's what a fold function. 
You take the template. 
We define a function based on the 
template with an additional parameter for 
each set of dots and that's and what a 
fold function is. 
Now let's figure out the signature. 
Well, and now that this is an, even 
though both of these examples are list of 
number It started with the list of x 
template. 
So you know that this third parameter is 
really list of x. 
[SOUND]. 
Now, this makes it quite clear that the 
result isn't list of x. 
It isn't even a list at all. 
It's something else. 
Now it happens to be numbering both of 
these cases, so you might just want to 
put Number there. 
But, what you should do instead is think, 
can I make it do something else? 
Can I make it, for example, add up some 
string? 
For example, can I do fold string append 
with the empty string and the empty zone. 
And list a, bc, def. 
Let's see. 
Adding or appending all those strings 
together should produce abcdef. 
And that test it's working. 
The test that's failing is later in the 
file. 
So that test is working, so that tells me 
that the result isn't always a number, it 
can be something else. 
Now in both of these cases it's listof 
string to string. 
So that might make me write X there. 
Now I gotta try to make it do something 
else. 
I gotta see can I construct an example 
where the final result Isn't the same as 
the type of the elements of the consumed 
list. 
So you could try to construct that 
example, or you could look at the code, 
and say to yourself well, each of these 
has to be an x. 
Those are always. 
The type of the first argument of the 
function, so let me back up here, and say 
the first argument of the function has to 
be an X. 
The second argument of the function is 
the result of the recursion, which of 
course is the type of the base. 
And always the result of the function. 
There's nothing here that says that this 
type and this type really have to be the 
same, so this could actually be y and 
then if, if this whole thing is going to 
produce a y Then that means that the type 
of the second argument to the function is 
a y. 
And the function has to produce a y. 
And also, the type of b has to be y. 
[SOUND]. 
So what that says is, give me, give fold. 
A value of type y, the base case value of 
type y, and a list of x in a function 
that consumes an x, a y, and produces a 
y. 
And it will go through the entire list 
producing the final y, and that's in fact 
the signature for folder. 
Now that you have fold, if you didn't 
have it already, but now that you have 
it, you can of course use it in lots of 
ways. 
You've already done some in an earlier 
video. 
So, I'll just pause here and ask you to 
do it again if you're a little unsure 
about how fold is working. 
Just To improve your confidence that you 
understand what fold does. 
So here's kind of an optional in video 
quiz question for you. 
And here is the result I ended up with. 
It of course is exactly equivalent to 
this first check expect, or it, it's 
essentially equivalent to this first 
check expect. 
The function argument to fold is plus. 
The base case value is zero and the list 
argument is the list. 
Here is a similar one for adding together 
a list of images. 
Do this exercise now. 
And here's the definition that I ended up 
with. 
I call fold with beside as the 
composition with the white, square as the 
base, n with the list of images. 
If you remember all the way back to that 
table. 
Then I showed you in the first week on 
list functions -- and I showed you the 
different ways you could fill in that 
table? 
You can now see the different ways that 
you can fill in fold. 
Plus and zero gives you sum; times and 1 
gives you product Beside and a blank 
square gives you juxtapose. 
You can do all sorts of things will fold 
because fold really is the abstract 
function for the list of x type. 
It's the abstract function for the list 
of x type. 
You take the template. 
You add one parameter for each dot dot 
dot in the template. 
There's a funny thing you can do which is 
to give fold parameters that will just 
produce the same result that comes in, so 
if I just say copy list... 
Of lox and I call fold and in the 
composition position I put cons and in 
the base result position I put empty, 
then this function copy list just 
produces whatever result it's given. 
Copy listof produces empty. 
Copy listof list 123 produces list 123. 
Because we're filling cons into this 
combination position of empty into the 
base position. 
And again, going back to that table, the 
line for copy list is cons and empty. 
And that just produces a copy of the 
list. 
List. 
So that's kind of neat. 
That's fold for a list. 
Now watch this. 
Design an abstract fold function for 
Element. 
Remember Element was the arbitrary arity 
tree that we looked at last week. 
Well, there's the template for element, 
in which I've already grouped it with 
local into an outer function and the two 
inner functions. 
So if I start with that, and now I'm 
going to design this abstract fold 
function. 
 >> Let's see I'll put the design down 
here. 
It's going to be called fold element. 
I can't call it fold again because I 
already used that name. 
Fold element, and now let's see. 
There's two function positions. 
There's combine one, which will be here, 
and combine two, which will be here, and 
there's one space, which will be here. 
And there it is. 
I've got, I've got the bold function. 
Well let's see. 
What's a check expect for what it can do? 
Well this is going to be a little bit 
more complicated. 
Because c1 and c2are more interesting 
functions. 
But let's try to do a check expect for 
the case. 
Where we build a list of all the names in 
the tray. 
We're going to need a helper function for 
that, so I'm going to start with a local. 
And we're going to say, fold element, and 
in the argument, let's say the argument 
is going to be D6. 
[INAUDIBLE]. 
That'll be the actual trace. 
So now, we need two combination 
functions. 
Let's see, c1 goes right here. 
And I'm just going to define it here with 
that name, define c1. 
And it consumes three arguments. 
It consumes a name, a data. 
And the result of the natural recursion, 
which in this case, of course, is 
going to be a list of names. 
And what does this have to do? 
Well, it's going to ignore the data and 
cons the name onto los. 
And now, let's see, what does c2 have to 
do? 
The reason I'm defining c1 and c2 using a 
local. 
Is, they're a little bit more 
complicated, or perhaps they're more 
complicated anyways. 
But c two has to do is, let's see, both 
of these natural occurrences are going to 
produce a list of names, or a list of 
strings, and I just have to combine them 
together. 
Oh, well if I've got two lists of 
strings, and I want a single list of 
string. 
That's just append c2 isn't really that 
complicated. 
So let's see its fold element c1 append 
and empty is the base. 
And does that produce. 
What's the result we're after here? 
Remember what the tree looks like, and 
it's D6 comes first, and then D4, and 
then F1 and F2, and then D5, and then f3, 
F3 that would be the result. 
Let's see if that works. 
Whoops, what did I do wrong here? 
Cons expects two arguments, but found 
only one. 
Oh, yeah. 
Huh. 
That's not right. 
I need to cons n onto los. 
And this test is failing. 
It means that this test is succeeding. 
So, pretty cool here. 
I managed to make a list of all the names 
in the tree, using the abstract function 
fold element. 
So the purpose is, the abstract fold 
function for element. 
And of course, that means it's also for 
list of element. 
Because that is involved in element. 
[SOUND]. 
Probably just leave that out, because it 
originally consumes element. 
Now we gotta get a signature. 
let's see. 
In this template, I've already got the 
type produced by these two selectors 
annotated here. 
And I'm going to start by adding two more 
annotations. 
There are these two mutually recursive 
functions, and I don't know what types 
they produce. 
I don't know what types they produce yet 
in the abstract function because they 
might produce different things depending 
on c1 and c2. 
I'm going to start by saying 
fn-for-element in general produces X and 
fn-for-loe in general produces Y. 
I've just introduced two type variables 
to let me talk about what fn-for-element 
produces, and fn-for-loe produces. 
Why is that a good idea? 
Well, why. 
[INAUDIBLE]. 
Now, let's look at the signature fold 
element. 
Well, let's see. 
The first argument to fold element is c1. 
And c1's a function. 
So I'll just start by saying, well, it's 
a function. 
So it's going to look like that. 
Now, let's see. 
It's a function of three arguments. 
The first one is a string. 
So I'll say string. 
The second one is an integer. 
The third one is the result of 
fn-for-loe. 
Well what's the type of the result of 
fn-for-loe? 
Well I decided that that was going to be 
a Y. 
So I'll just put y there, so let's see. 
C1 consumes a string, an integer, and a 
y, because it's the fun for loe, and what 
does it produce? 
Well I decided that it was going to 
produce x, so I'll just put x there. 
Now I'm working on the. 
Second argument to fold element, in other 
words c2. 
c2 is a function, it gets used right 
there as a function so I'll just start by 
putting that, now I'll fill that in. 
It's a function of two arguments. 
The first is a result of fn-for-element 
and fn-for-element produces x. 
So that means the type of the first is x. 
The second argument to see, too, is a 
result of fn-for-loe. 
So that means it's type is y. 
And c2 has to be willing to produce 
whatever fn-for-loe is supposed to 
produce, because c2 is calling in a 
result. 
Position for fn-for-loe. 
So that mean c2 has to produce a Y, all 
right. 
That's the c2 argument to fold element. 
Let's at b, where is b? 
Well b is the base case result of 
fn-for-loe, that means b has to have the 
same type as fn-for-loe produces. 
So that's got to be a Y. 
E has to be of type Y. 
And then I'll delineate E. 
Well E of course is an element. 
And finally, we need the result type of 
the entire fold element. 
Let's see fold element produces whatever 
fun for element produces, and fun for 
element we decided produced x so, this 
whole thing is going to produce x. 
So there you go, there's the signature 
for a mutually recursive abstract 
function, an abstract function operating 
on an arbitrary arity tree. 
And I did it basically the same way that 
I’ve been doing the signatures for 
abstract functions from the beginning, 
with the one addition that in this case 
because there is these two inner 
functions, I went ahead fairly early on 
and gave type parameters for each of 
their results. 
So I said fn-for-element e produces X and 
fn-for-loe produces Y. 
And then I just use the typer inference 
reading the types off and building up 
what I can tell about the types to get to 
this signature. 
Abstract fold functions on more complex 
data on types with mutual references are 
pretty cool. 
They let you write some very interesting 
functions very compactly. 
Why don't you play around with them in 
the exercises coming up... 
[SOUND] 
[BLANK_AUDIO]