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.