In this video, I'm going to design one more function operating on arbitrary
arity trees, so much of this will be familiar.
But the design of this function introduces a new and important concept
called backtracking search. So, let's go find the problem.
It's in fs-v3.racket. And we'll scroll down here.
And we're supposed to design a function that consumes string and element.
Let me write that down. String element.
And looks for a data element with the given name.
If it finds that element it produces the data.
Otherwise it produces false. It produces the data, let's see what that
means. So, I'm looking in one of these trees for
an element with a given name. Alright, the string is the name so that's
why I got the string as an argument. I'm looking for an element with the name
equal to the sting I was given. And if I find it I produce the data,
which is an integer. So, going back down here to where we
were, we're going to produce integer if we find it.
And otherwise we produce false. So, that's different.
That's something we've never done before. What's happening here is this function is
going to go look for an element with the given name and sometimes it's going to
produce the data, otherwise it's going to produce false.
Well, written functions that say whether a given string in a listed string, that
that function always produces a Boolean, true or false?
Here, we're going to produce the data if we find it or false otherwise and we need
a little extension to how we write function signatures to do this.
And what you're going to do is you're going to say, whatever type it would
produce if it succeeds or false. So, this is a special form of signature
that's particularly applicable to backtracking search.
Now, in some programming languages, in most recent programming languages,
there's a more sophisticated mechanism called exceptions for dealing with this
kind of case. To keep BSL simple, BSL doesn't have
exceptions. But the basic way we're doing
backtracking here can easily be adapted to a language that does have exceptions.
So let's see. Search a given tree for an element with
the given, given, given name. Produce data if found false otherwise.
Let's do some stubs. We're operating on two mutually
referential types. So, there's going to be two functions.
Define fine, dash dash element. Which will consume an element.
But it will also consume a name. Some string.
And for the stub, we'll just assume it always fails.
It'll produce false. And define find, dash, dash.
List of element, which will consume a list of element, but it will also consume
the name that it's looking for, false. Okay, so those are the stubs and we
should put the signature for the second function.
ListOfElement, string and list of element.
And again we never quite now here for sure, but let's put integer or false.
Okay, let's do some examples. Let's start with the base case, we know
that in this case, the base case is the -loe function called with empty for the
loe. That's where the mututal reference and
self-reference cycles all stop. So, we'll say check, expect.
Find-loe, let's say we're looking for F3 in empty and of course we can't find F3
in empty because it's not anything in empty at all so that'll produce false.
Now, let's do another simple case. Let's say, check, expect, let's look It's
find dash dash loe and find dash dash element.
Let's say we're looking for something named F3 in F1.
Well, that's false. There's nothing named F3 in F1.
And most of these other tests are going to be find an element.
So, we'll make that something we could copy.
But what if we look for F3 and F3? Well, if we look for F3 and F3, we do
find it. We find it right away, 'cuz F3 is F3, and
so we return the data, which is three. Okay.
So, that's the base case, and two very simple, immediate success or immediate
failure cases, let's try to do another case, let's look for F3 in D4.
Well, that's false we don't find F3 in D4.
But what about looking for F1 in D4. Well, we do find that F1 is the first
child of D4. So, this is going to produce 1.
But what about a case where what we're looking for is not the first child of D4
but one of the later childs of D4. We should try that case because it kind
of corresponds to searching in a list and making sure we search beyond the first
element. So, if I look for F2 in D4, I'm going to
find, so the data will be 2. Seems like we should also try a case
where we're looking in an element that has some.
But what we're looking for is actually the element itself.
So, let's see what happens when we look for D4 and D4.
Well, anything that has subs has data 0. So, this is going to produce 0.
And let's try one more big one, find--element.
Let's try looking for F3 in D6. That's the far-right child.
And that would produce three. So, that seems like a pretty exhaustive
set of tests. Let's run those tests to make sure
they're well formed. They're all running and most are failing
so they are well formed and let's save that.
Okay, now let's go get the template. There's 2 of them of course, here they
are. We'll go back down to the function that
we're working on, we'll come in at the two stubs, placed in the templates,
uncomment those. Now, there the remaining find--element is
that and here is the natural mutual recursion.
Copy that. Here's the function name.
Here's the natural recursion and here's the natural mutual recursion.
And there's one more thing to do here. These are functions that can consume two
arguments. They consume the element or the list of
element and also the name of the element we're looking for.
So, we have to add a parameter n there. And we have to add a parameter n there.
And remember, I said whenever you have a recursion and it also applies for mutual
recursion. When you add a parameter, you should be
sure to go put a note to yourself at each recursive or mutually recursive call to
say, hey, you're going to need something here, you're going to need a parameter.
Now, we could wait till later to fill in those question marks.
But in this case, I know that once I start looking for given n, the whole way
down the tree, I'm going to be looking for the same n.
So, n is never going to change, n is always the same value.
So, I'm just going to keep passing n in all the recursive calls.
I could feel it in now. Now, if that's not clear to you or if you
don't think it would have clear to you this early, that's fine, you can leave
the question mark and fill them in later. I can just tell now that this function
doesn't change the end as it goes so I might as well fill it in now.
Okay, now let's see. Start at the base case example, if we
find loe in empty, that's false, that puts a false here, which of course makes
sense if you're looking for something in nothing and you can't find it.
But here's a case that says, if we're looking for F3 and F1, we don't find it.
If we're looking for F3 and F3, we do find it.
So, it seems like that when we're looking at an element, there's kind of two cases.
This is the case where we find it right away.
Right there and right there we find it right away in those two cases.
And then there's the case where we don't find it right away.
So, that suggest an if in find--element. And the question is you know, is the name
of this current element the name that we're looking for?
So, both names are string. This nice little note here that I put in
the template reminds me of that. Is the name of this element the name I'm
looking for is the question. One thing about this little note I put in
the template, in some other kinds of programming languages and in more
sophisticated programming environments. This would be automatically given to you.
You could just kind of hover here and it would say, oh, that's going to produce a
string. So, we're just replicating a feature that
you might get in some other languages already.
I like putting it here explicitly to help you understand kind of where it's really
coming from. We'll delete it now.
So, let's see. If the name of the current element is the
name we're looking for, then what are we supposed to do?
Well, we're supposed to produce that element's data.
So, there we go. We'll just produce its data.
And if the name we're looking for isn't the current element.
Well, what are we supposed to do in that case?
Well, these other examples are saying that you keep looking.
We got to go look in all the children. In other words, we got to do the natural
neutral recursion and we should follow the standard advice, which is to trust
the natural neutral recursion. This is going to go look in the children
and whatever it produces will be the answer.
Now, lets go down here. Now, we're looking at a list of elements
and we don't actually have an example for this.
So, let's put in an example for this. Let's say check, I'm going to put it
right here because it's the, it's really a little bit simpler than the D4 example.
I'm going to say find element. Find--loe I mean, in cons F1, cons F2
empty. This is the subs of D4.
Okay, this is the subs of D4. So, actually I'm not putting this in the
right place. I should really be putting this up here.
This is the sub of D4. And I'm finding, what do I want to find
in there? Lets say I want to find F2.
Can I find F2 in there? Yes, that should produce 2.
And we'll add another one. Can I find F3 in there?
And the answer to that is false. Now, I can really understand that these
examples all have a bit more structure. It is really the base case example,
there's the has no children examples when we're looking in F but not looking in
anything that has children. And then this example here is, is a quite
similar example because I'm moving it up here now because its really an immediate
success example, this doesn't go looking at children.
So, we look at nothing, look at things that have no children.
We don't look in the children. Here, we look in lists of children.
And now we start looking in things where we have to look at the element itself,
and its children. So now, I've got the examples ordered
more in terms of their complexity. And so find, dash, dash, loe, is really
kind of here and here. Now, let's see.
What are these two mutual recursions going to do?
These two natural, mutual recursions, what are they going to do?
This will produce integer or false depending on whether it's found in first
of loe. Let's make that a little bit more
compact. If n is found in first of loe.
And this second one will produce integer false is n is found in rest of loe.
Now, if we find it in the first, there's no use looking in the rest.
We're supposed to find one of them, we don't need to find more than one.
So, that suggests an if. Now what's the question?
Well if this thing produces false If it can't find it, this natural mutual
incursion produces False, if it can't find it.
So, and I apologize for the double negative here, but if it doesn't produce
False that means it found it in the first.
So, they way I'm going to phrase this question is, if not false that and that
will mean is its is it found in the first?
Is, it's found in first loe and if it is found in first loe well then that's what
we want. That value that came back, which is going
to be an integer is what we want. And if it isn't found in the first of
loe, well, then we better go look in the rest of the loe.
That's the natural recursion. Now, let me just note this question here,
which I've phrased as not false, find--element.
I can also phrase this question as (integer?
(find--element-n (first loe))). In other words, I could have used
integer? Instead of not-false.
The reason I used not-false is that it's more general for backtracking functions,
when we see other backtracking functions. We'll have the same not false pattern.
So, let's see. Maybe hopefully, I'm done, and I am.
All the tests pass. Now, why is this called back tracking?
Well, let's just step through a couple examples.
Let's add one more example to this. Will put it up here.
Let's look in D6 for D6. Well, if we look at this tree, we start
at D6 and we're looking for D6 and immediately we find it so we're done.
Now, here's another example. Let's look at D6.
We'll add one more here. Let's look in D6 for F1.
Whenever I add an example, I actually should run it.
Just to be sure it's working. And they are.
Now, let's look in D6 for F1. What happens is we start at the top of
the tree, we start at D6. It's not F1, so we go to the subs.
We go to the first of the subs, which is D4.
It's not F1. So, we go to the subs.
We go to the first of the subs, which is F1 and it is F1.
So, we found what we want and we produce one.
And now, let's look at what happens in this case, where we look in D6 for F3.
Well, again, we start at D6. We haven't found F3.
We go to D4. We haven't found F3.
We go to F1. We haven't found F3.
We go up to D4, now we look at F2 we still haven't found F3.
We go back up to D4, we go back up to D6, now we come down to D5 we still haven't
found it, we go down to F3, we found it. And each time we get to a failing node
with no sub elements, those are called leaves because they have no branches, no
branches anymore. Each time we get to a failing leaf and we
go back up to its parent and then try the next.
The next sub, that's called back tracking.
We back up to the previous branch and go down the next branch and that's why this
is called back tracking surge because it has this pattern of going all the way
down to branches, looking for what we want.
And anywhere we fail, we produce false to go back to the next branch and then that
goes to the next sub, 'kay? And this if not false of looking in the
first branch, pattern is emblematic of backtracking search.
And as I said, we'll see more back-tracking search examples later in
the course.