The abstract functions we've designed so far seem very useful.
Lots of list functions feel like map two or filter two.
In fact, map and filter are so useful that they are built in to the immediate
student language. It provides them as what are called built
in abstract list functions, and in fact, it provides several more built in
abstract list functions. In this video, what I want to talk about
is how you can use these built in abstract functions when you're coding one
of your own functions. So we'll look at how to decide which
built in function. Is appropriate in a given situation.
And then how to set yourself up to use it properly.
I'm in the using built ins starter dot racket file, and this file just starts
out defining some useful data and functions that will let us have more
interesting examples below And now I just want to talk about what some of these
built in abstract functions are. You can get a list of all the built in
abstract functions by going to the course website, going to the language page,
which you can always select from here on the left hand side, going to the end of
the language page, and here's a list of all the abstract functions.
For example the third one in the list is map.
Which was the 1st abstract function we did.
And it's got it's signature and more than 1 line purpose, hmmm, and the header,
which allows them to name parameters and write the purpose more concisely.
Let's jump back over to racquet and see some of these functions in action.
I've got some check expects here to demonstrate them.
And what I'm going to do is run them. Now, there's going to be a couple of
failing tests. But those are actually from farther down
in the file. These check-expects here are working, and
I'm actually going to also demo them down here, just to drive home what's
happening. So I'll take this and copy it and go down
to the Interactions area, and if I map the predicate positive Over a list of
numbers while I get back the result of calling positive with each of those
numbers, which in this case is true, false, true, false.
If on the other hand I use filter with negative.
I get only the negative numbers, minus 2 and minus 4.
Is an abstract function we didn't abstract before but I think you'll see
what it is pretty quickly, this is foldr. And if I call foldr with plus 0 and the
list 1, 2, 3, I get 6. Foldr is the abstraction of sum and
product. Plus is the combination, 0 is the base
case result. And that's the list that it operates on.
The way to think about it is that folder is filling in the ordinary template for
operating on a list of x. So folder in some sense is the abstract
function for the list of x template. And we can use it in other kinds of ways,
for example, [SOUND] here we're doing the product function that we did before.
Now Build List is one we haven't seen before.
Let's jump over to its documentation. What it says about build lists is that it
consumes a natural number, and a function which is self consumes a natural number
and produces x. And this function produces a list of
those x's. And what it does is it calls the
function, it produces a list. Of calling the function on zero...all the
way up to calling the function on minus n1.
Let me show you that more concretely. I need to tell you first that there's
this funny function in Racket which was made pretty much exclusively to use with.
Build list and some other abstract functions.
This function is called identity. And all identity does is whatever you
give it as an argument, it gives you back.
So it's the identity function, it produces its argument.
If I use identity with build list Let's say I say build list of three, and
identity. I get the list zero, one, two.
Because look, what's it doing? It's calling identity on zero.
It's calling identity on one. It's calling identity on two.
And it's stopping there because two is 3 minus 1.
And it's making a list of those results. Here's another one.
If I say Build list square on four I'll get oops, I got the arguments backwards.
[SOUND] Build list 4 on sqr, I get 0 which is the square of 0, 1 which is the
square of 1, 4 which is the square of 2, and 9 which is the square of 3.
Build-list is a funny thing we'll see why we want to use it a little bit later.
Here's some problems that are all of the same form, they've all got the beginning
of a function design And they're at the template code, the body stage.
And what I'm going to show you how to do is how to recognize that this is a case
that you could code the body by calling a built abstract function.
The basic trick is to, first kind of get the insight, hey you know.
This feels like it's a fairly generic operation on the list, maybe there's a
built in abstract function, I wonder which one it is?
But after awhile you get pretty good at doing it just kind of automatically.
But until then the way to do it is to compare the signature of the function
you're trying to design; here it's list of image to list of image.
To the signatures of the built-in abstract functions, which I've got here,
minus their function argument. So now, I'm taking away their function
argument, and so what I'm going to do is compare a list of image, to list of image
to these signatures. Well, it doesn't match the first one.
It doesn't match a build list, 'cuz that can, seems natural.
It matches both of the next two because listof image to listof image matches
listof x to listof x, and also matches listof x to listof y cause remember x and
y don't have to be different they just can be different.
And it doesn't match any of the remaining ones because list of image sure as heck
isn't boolean and the last two functions take two arguments.
So it's either filter or map and in this case of course, it's filter because this
if filtering behavior. We're potentially producing Fewer
elements in the result list than in the consumed list.
That's what filter does, map always produces 1 element in the result list for
each element in the consumed list. So this is a filter and the way we're
going to template it is like this, we're going to say, hey this is a filter I
won't know what argument to pass it. Here, but I do know it gets the list
here. Now this is the template.
Now at this point in the course, you don't really for your own purposes, need
to save the template, right? Templating is starting to become
something that you understand the structure of If you can write it down
quickly, you write it and go, or you copy if from a data definition.
I'm going to leave it here just for your purposes so you can understand what we
did here today in this video. Let me copy it and now comment that one
out. And now you have to, as usual, fill in
the dots. And the question is, what is the
predicate that we pass to filter? Again, if I go look at the complete
signature for filter. It's first argument is a function that
consumes x, and produces Boolean. Its second argument is a list of x.
And its result is a list of x. So this needs to be a predicate here.
It needs to be a predicate that consumes x.
Now you may not remember this because it went by quickly, but at the top of this
file, there's a predicate called Wide Question Mark.
Which consumes an image which is what x is in this case, and produces a boolean,
and it produces two of the images wide. So, this is what we want.
We'll go back down to wide only and we'll just put [SOUND] y question mark in
there. And one of the things that's nice about
using built in abstract functions, is that your function definitions get really
short. And they get really short, they get so
short that you might even be tempted to write them on one line.
The book sometimes calls that a one-liner, but But let me note, that you
know, what it means to be a one-liner is that it's very short.
So that's really still, for all intents and purposes a one-liner.
It's very short, it's very simple because we used the abstract function.
And let me make one more point here about the benefit of using The built in
abstract functions. It's already up here above, but you might
not have noticed it before. Notice that I don't have a base case test
here. And the reason I don't have a base case
test is that the built in abstract functions are already thoroughly tested.
I know that they're base case behavior is going to be correct.
So I don't really need the base case test for the built in abstract function.
So when you use one of them, you don't have to follow the normal rule about
starting with a base case test. Let me do another one quickly.
List of Image to Boolean are all the images in loi tall and I'm asking are all
the images in loi one Tall. Let's go look at what l o i 1 is.
See l o i 1 has all of these rectangles in it, so they're clearly not all tall.
Other the other hand, let's see if I just took.
One and three, they would all be tall. So, let me go back down there and add
that as a second test. So, now I've improved the set up a bit,
and the question is which built in abstract list function is this?
Let's see, I consume A list of image, I produce a bullion, I take the abstract
list function signatures, I remove their function argument, which one matches,
well it's and map or, or map. And if I go to the language page and look
at the description of and map and or map. In that, it says, produce true if p
produces true for every element of lox whereas or is for some element of lox.
And unsurprisingly, I probably could have done this without looking here, but since
this purpose is are all the images in loi all-tall.
This is going to be an and map, so I'll say define all-tall.
loi, and map, dot, dot, dot. loi.
And this time I'm not even going to preserve the template.
I'll just have briefly this template stage.
And now I have to decide what goes in the and map.
And of course it's the predicate, tall question mark.
Let's see. That test is passing.
The first failing test is after that. First failing test is sum.
I need to let you do sum as an exercise now and I want you to go through the
whole process I've just shown. Compare the signature of sum to the
signature of all the other functions. I'm going to give you a hint here though.
I do want you to compare the process. This, but I am going to give you a hint
here, which is that the function that you're looking for here is Folder.
So go ahead and do this as an exercise, and when we come back I'll do the last
one. So here was my solution for sum, and I
just want to show you one little thing that you could do in the middle of it
that might make it a bit easier. Once you figure out its folder, and you
have the template with the two sets of dots because remember folder's going to
need Two arguments in addition to the list.
One thing you could do is go decorate those dots with their type.
So since the signature of folder is y, list of x to y.
And since we want to produce a number, that means y has to be a number.
So that means first argument of folder, which is supposed to be a function x, y
to y. Let's see, x we know is number, y is
number. So, this first set of dots actually has
to have that type. The second set of dots, the second
argument to folder has to be a y, we know that's number now.
So that second set of dots has to have type number and that helps you when you
go to fill in the dots. You know that the first set of dots needs
to be a function and with that signature, in this case, it's plus.
[SOUND] You know that the second set of dots needs to be a number, in this case,
zero. So that's a little thing to do for these
more complicated ones like Folder, where These multiple arguments is you can kind
of, once you've decided which function to use, then you know what types your Xs and
Ys are, and you can decorate your template a little bit more with the types
you need. Let me do this one last one, which is a
little bit tricky. You don't have to follow it if you don't
want to. Here's a funny one.
I'm, I'm consuming a natural and producing a natural and I'm trying to add
up the first n natural numbers. Hmm.
Well, that's natural to natural. And that doesn't match any of these;
there's only one of them that consumes the natural and it produces a list.
That's build-list. On the other hand, there are two of them
that are willing to produce something other than a list, foldr and foldl.
Ignore foldl for now. Let's see, build-list will go from a
natural to a list, and foldl will go from a list back to something else like a
natural. So this is going to be templated as a
composition of folder and build list. We need to do two things.
[SOUND]. We're going to folder with a function
argument. And some base case value, and a list.
Where are we going to get the list? We're going to get that from build list,
with a natural argument, in this case the original n.
And some function. Now how do we fill them in?
Well build-list already does produce the first n natural numbers, if we say
build-list n and identity Let me, let me save this template so you can look at it
as we go. We'll comment out the stub.
We'll comment out the temapate. If we say build this with n in identity,
that's going to give us the first n natural numbers because if we call it
with n equals two for example, we'll get zero and one.
The first n natural numbers. So there's a list of the first n natural
numbers. Now, I need to add them up.
Well that's just the old sum function plus and zero.
So, now you see why build list is there. Build list is there because it's often
useful to produce the list argument to folder.
This is a way of saying let folder do something to a bunch of natural numbers.
That's build lists role. And in fact lots of languages have
something like this. Python has something called range, which
works exactly this way. So there's examples of using built-in
abstract functions and simplify the final two stages of the function recipe, the
templating stage and the coding the details of the body stage.
The basic idea is first you get an idea that hey this function is amenable to be
coded as a call to a built-in abstract function.
Then you figure out which built in abstract function it is then you template
that way and then you work out the details.
There's going to be a number of practice problems on this because this is the
thing that really takes some practice. Remember a perfectly viable way to do
this is to first code the function the old fashioned way.
First code it out using the ordinary list template, and fill it all in.
And then maybe once you've got that, think to yourself, well which abstract
function is that? You don't have to jump directly to that
abstract function if that seems too hard. Remember the basic idea of the recipe.
The basic idea of the recipe is always write down the easiest thing you know how
to write in that. List, and then go from there.
So if the easiest thing you know how to write next is the old-fashioned template
and filling it in, write that and then go from there to the call to the built-in
abstract function. If, on the other hand, you think you can
figure out which built-in abstract function to use, go directly to
templating a call to that and then filling in the details.