In this video, we're going to start a big function design problem that's going to
last through several videos and it will lead us eventually to designing five
functions. That's not at all unusual.
In some function design problems you design many more functions than that.
Imagine, for example, designing a function that consumes a location and
drives a car from its current position to that location.
I think you could easily imagine that, that would involve many, many, many
functions. The one we're going to do now though,
starts with one function, and we'll end up designing five.
The basic problem is, we have a bunch of pictures or images, that we want to be
able to store and present in different ways.
This problem will do a simple version of the presentation.
And later on, we'll set the stage for a more elaborate version.
Okay. So there's two parts to this problem.
First we have to design a data definition to represent an arbitrary number of
images, and then, we'll design a function to arrange those images in a nice way.
The video will pause here, while you go ahead and do part A, design a data
definition to represent an arbitrary number of images.
I strongly recommend that you take the time to do this yourself right now rather
than just restart the video. But of course nobody's watching so you
can just restart the video if you want to.
Here's my solution for the list of image data definition.
It's an ordinary self-referential data defintion of the kind we saw.
Previously. There's two cases: the base case and the
self-reference case. And, I've got an example of the empty
list, as well as an example of a list that has a couple images in it.
There's the template. This week you're allowed to not start
including template rules used. That means you don't have to write the
template rules used. So, I'm not going to write the template
rules used. But as you read it I think you can go
through the template rules used in your mind fairly quickly.
It's a one of with two cases so there's a two case con.
The first case is atomic distinct empty. We have the usual empty loi dot dot dot.
And then there's a cons of a primitive type.
Image. So we just have first loi, there's no
call to a natural helper, and the natural recursion.
There we go, there's that data definition.
Now let's get on to, designing the functions.
We'll make another part of the file called functions.
And we're supposed to design a function called arrange images that consumes an
arbitrary number of images, so that means it consumes list of image, and it
produces an image. In which they're all laid out left to
right. That's going to produce a single image,
where all the images are laid out, left to right in increasing order of size.
So what does it have to do? It has to, lay out images left to right,
in increasing order of size. Okay?
So, a good start for this function is just define, arrange images loi.
And a good stop is black. By this point we've seen that these
functions that produce images, often use blank both in their stub and in their
base case. So, I am going to go ahead and make a
constant for it, "square 0 solid," "white".
Yeah, I got a constant I can use here in this stub/g.
I'll run everything, my stub is well formed.
Let's do some check expect, let's see check expect arrange images empty.
Well if I ask you to arrange an empty list of images, then that's just going to
prove blank. And let's see.
We want to do one for a non-empty list. It should be at least two long.
Let's see, we need to arrange images. And what I'm going to do is, I'm going to
use the same list that I define up above. But I'm not going to refer to it as a
constant. And I'll tell you why I'm going to do
that. Which is, it's going to make it easier
for me to understand my Check Expect as an example, if I actually include the
full calls to rectangle here. 'Cuz I really understand what I'm seeing.
So now let's see if I need to arrange those images left to right in increasing
order of size. Well, the area of this image is 200, and
the area of this image is 600, so they already are in increasing order of size.
So I think this is going to be the side of this rectangle, then this rectangle.
And also blank. Now you might ask, why are you putting
the blank there? If the blank is blank.
In other words, it's nothing that you see, then it doesn't really make sense to
put it there. Because it's blank.
Well, that's true. But the reason I'm putting the blank
there, is remember, check-expects are examples before they are tests.
And by putting the blank there, I'm kind of reminding myself, you know, what
gets built up is the blank from the empty and then the other two images.
That's why I'm putting the blank there. It's to make it clear to myself.
Not just what the actual final image is. But in some sense, why it's the image
that it is. We'll run it.
They fail, but they're well formed. That's great.
Now, I'm going to get the template. I'm going to put the template in.
I'll rename it. I'll rename the natural recursion, I'll
comment out the stub. And now, I'm going to think for a minute.
And what I'm going to do is, I'm going to go back and reread the purpose.
And the purpose says, lay out images left to right in increasing order of size.
Now what is that meaning? Well, if I think about it for a minute,
what it means is, sort images in increasing order of size and then lay
them out left to right. Really, what I have to do to make them
problem what is first, I have to take the entire list of images and I have to sort
that entire list. And then, I have to lay those out left to
right with [UNKNOWN]. I can't really go through the images one
at a time, and sort each image and lay each image out.
The sorting has to be done to the whole list.
And then the laying out has to be done at the whole list.
This is what's called a function composition problem.
And if we go to the design recipes page, there's a special entry for function
composition. And it says that you use function
composition, when a function must perform two or more distinct and complete
operations on the consumed data. For example, and then has this example
that's convenient, a function that must sort and lay out a list of images.
I won't read through the page now, you should do that afterwards, very
carefully. Now, what happens in function composition
is that we discard the entire template, and we replace it with a function
composition, such as this one. And it's called a function composition,
because what it says is, it says, first, sort the entire list, first call sort
images to sort the entire list then take the result of that call layout images on
it, to lay out the entire list. So the functions happen one after
another, each on the output of the previous function.
So this is a two function composition. You could also have problems that had 3
or 4 or 5 functions. They tend to be weighted more towards the
smaller number. This is a two function composition.
Now of course I've wished for some functions that don't exist yet, so I
better do wish list entries. Let's see, layout images consumes list of
image and produces image, place images beside each other in order of lists.
It's a wish list entry, so we'll do that and it's got to produce some image.
So that's the wish list entry for layout-images.
Let's look at sort-images. Well, sort-images consumes a ListOfImage
and it produces a ListOfImage. Sort images.
In increasing order of size. It's a wishlist entry.
Now this is a function that produces a list, so we could put just empty as the
stub here. What I'm going to do instead of putting
empty is I'm going to put loi. Because I know that when the stub was
called the loi will be a list of image. And so if I produce loi, I know I'll be
producing a list of image. And you'll see a little bit later that
this slightly different stub, this slightly more clever stub.
Actually helps us in seeing how the program is coming together, so I'm
putting that as my stub. Now that I've set up these wishlists and
I know that this is a function composition function, there's one more
thing I have to do. Which is I have to go back and think
about these tests one more time, and here's why.
If a function is a function composition function, then the tests for it have to
make sure that it's composing the functions properly.
They don't have to exhaustively test the individual functions.
The tests for layout images will test layout images, and the test for sort
images will test sort images. The test for range images have to make
sure that a range images is calling layout images and sort images properly.
One thing this means is that when you go to a function composition you don't need
to test the base case. But another thing it means is that
because this function is supposed to both sort and arrange, this test isn't good
enough. Because a version of this function that
just did the rendering, would work, because these are already in the right
order. So I need a second test, I need at least
one more test, in which I make sure I'll just swap these two rectangles around.
And I won't swap them down here, because the point is that what Arrange Images
need to do is call Sort Images to rearrange these in the right order.
And then present them. So now,I feel like I've really tested
that arrange images is doing both jobs, both the sorting and the laying out.
At this point, you're basically done with arrange imagines.
If you ran it, the test would run but fail, the reason they would run is
because we have the wishlist entries. But they would fail.
Because the wish list entries aren't doing the proper thing for either of
these functions. So to recap this video.
Remember, the first part of the week is about more rules for helper functions.
More rules for when to split one function into multiple other functions.
And in this video, what we saw, is the function composition rule which says that
we should use a function composition when a single function must perform two or
more complete operations on the entire consumed data.
In this case for example, we have to sort List of images and then lay out the list
of images. That's a function composition problem.
So what I'm going to to do with this picture here, is I'm going to keep
updating it through the next several videos.
To show how we've broken the original problem of doing arrange-images down into
multiple functions and which rule we used at each point.
When you start to get into bigger programs, lots of programmers keep an
actual pad of paper by their desk, to kind of keep track of where they are in
something. The wish list entries are good for that,
but some notes on pieces of paper like this are good for it too.
There's also professional programming environments, like Eclipse, that can help
you in some ways draw pictures like this. To keep track of where you are as well.
That's something you could learn about in another course.