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.