Now we're going to look at another form of data called an arbitrary arity tree.
And as we'll see, this form of data is characterized by having two cycles in the
type comments. It'll be the most complex form of data
we've seen so far. But don't worry, a pretty incredible
thing is going to happen here. Because of everything we've learned about
type comments, and references, and templates, and trusting the natural
recursion, desinging functions that operate on arbitrary arity trees is
actually going to be very simple. It's only to be a very little bit harder.
Than designing functions that operate on lists.
That's what you'll see, as we work through these next couple of videos.
So here's what I mean by file system, and again this could just as well be a photo
organizer or something like that, but when I look at the files I'm organizing
for this class. There's a desktop.
On my desktop there's these folders, and there's a folder called Mook, and in
there there's a folder called Current, and in there there's a whole bunch of
other folder including one called Starters, and then there's week three.
And here is all the starters that you had a little earlier in the course.
So what we need to do is to come up with one or more data definitions, that can
help us represent an information structure like this.
We're going to simplify it a little bit. We're not going to worry about the actual
contents of the files, we're just going to worry about a directory
structure like this, that has files in it.
And for the actual contents of the files, let's just assume they hold a single
number, a single integer is all each file holds.
If I redraw it this way then it looks like, or at least to a computer
scientist, it looks like a tree. This is an arbitrary arity tree and I'll,
I'll say why it's that in a minute. First let me say why it looks to me like
a tree. It's because computer scientists draw
trees upside down. We're kind of drawing the roots or
something. And let me just point something out about
this. What I'm going to say about this tree, or
this model of an arbitrary area tree, is that each element can have sub elements.
So for example, mooc has a sub element or a sub folder current, and current has a
number of sub folders. And Starters has sub-folders.
But Aisle-Starter just has data. It's a file that just has data.
And to simplify things for now we're going to say that the only data it can
have is just a single integer. We're not going to model storing the
actual contents of the files in here. Now why is it called arbitrary arity?
Well unlike lists which were arbitrarily long in one dimension or arbitrarily wide
in one dimension, this arbitrary arity tree is arbitrary sized in two
dimensions. And given folder or directory like w03
can have an arbitrary number of elements in it.
Current has a number of them, starters has a number of them, w03 has a number of
them. So it can be arbitrarily wide.
In addition, the structure can be arbitrarily deep.
This particular one is one, two, three, four, five deep but it could be deeper.
Remember arbitrary doesn't mean large and it doesn't mean random, it just means
that before we start out, we don't know how big it will be.
Now, in order to deal with this arbitrary size in two dimensions, structure that
this has. The key thing that we're about to see, is
that it's going to require two cycles in the type reference graph.
Remember, in order to have an arbitrarily-sized list, we had one self
reference cycle in the type reference graph.
Here we're going to see that we end up having two of them.
So now let's turn to DrRacket and start looking at that.
Now I'm in fs-starter.rkt, and what I have here is the beginning of two data
definitions that can be used to represent arbitrary [UNKNOWN] like this one.
So first is the structure definition, elt, which has three fields: main, data,
and subs. And of course we have to keep reading to
know what that's about. And there's a type element and it says,
element is a make element, string integer, list of element.
An element is an element in the file system.
So that's going to be something like from our picture [UNKNOWN] or current or
lecture exercises or starters. And what I'm saying here, because we said
in the analysis that an element could either have sub-elements, or it could
have data. I'm saying here that there's data which
can be an integer. And there's subs, which is going to be an
arbitrary number of elements, and it says if the data is zero, then subs is
considered to be a list of sub elements. If data is not zero, then subs is
ignored. There are other ways to do this, where,
instead of having an element have both fields, in other words both data and
subs. You make two different kinds of elements.
I thought this was simpler for our purposes for now.
And then, what's list development, well, list development is just an ordinary list
of type like we've seen several times now.
It's just a list of file system elements. Now let's see if this can build up the
structure we want. So what I'm saying here, is f1 is an
element called f one. It has a nonzero data.
So its like an ordinary file. That's why I called it f and its subs are
supposed to be empty. Its subs are ignored basically so I just
put empty. So that's F1.
F2 is just like F1. It's another file.
It happens to have the contents with the date of 2.
And F3 is the same. Now, what's D4?
Well, D4 has 0 for the data, so that means we're going to pay attention to the
sub. And what subs does it have?
Well, it has two subs, F1 and F2. So that looks like this.
And then, D5 has a single sub, F3, and then D6 has both D4 and D5.
So that little set of examples there. Runs up this directory structure here,
and I think we could see now pretty clearly, it looks like we can build an
arbitrary arity tree here. Let's see why that is.
And if we look at list development, list development has a self reference in it.
And that's what's allowing a directory's list of sub elements to be arbitrarily
long. That's what lets this list have F1 and F2
and this one have D4 and D5 and clearly those could be as long as they want.
Now, in addition to that self reference. Notice that there's a reference here from
the middle of the list of element type back to the element type.
We've seen that kind of reference before. But hang on, 'cuz there's something else
going on here. There's also a reference from the element
type down to list development. Now, those two references together form
what's called a mutual references. So we're going to label them, MR.
Because you can go from the definition of list development, up to element.
And the definition of element down to list development, and there's a cycle
there, a mutual reference cycle. So, in addition to the soft reference
cycle, which is letting one directory have an arbitrary number of immediate
subdirectories. The mutual reference cycle between list
development and element, is letting that be arbitrarily deep.
So, D6 can have an arbitrary number of sub-directories, D4 and 5, and each of
those can have an arbitrary number of sub-directories.
And so on, and so on, and so on. And so what you can see here, is that
these two cycles in the type comments, the self reference cycle and the mutual
reference cycle, support an arbitrary arity tree.
A tree that can be arbitrarily deep and arbitrarily wide at any point.
One quick note about these arrows and the way you label mutual reference arrows.
The way I do it is, first I draw all the arrows.
Then I label all the self reference arrows.
Then I put my finger on an arrow, and I start following it around through the
types. And if I ever come back to that same
arrow, then all those arrows along the way were part of a mutual reference
cycle. And then any arrows that aren't part of
the usual reference cycle and aren't part of the self reference cycle are just
ordinary reference arrows. In this case, when there's just two types
it's easy. But sometimes you can have mutual
reference through three or four or five or six or more types.
And then it's a little harder to get the arrows right.
It's very important to get them right. We're going to see it helps us a lot with
the templating that we'll do in the next video.