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]