Okay. In this video, I'm going to work through
the design of a Valid Board. And as I said, this is paradoxically the
hardest function in the whole program. But by working systematically, I'm
going to get there bit by bit. The first thing I'm going to do is well,
hmm. I'm going to start to write a template.
And what am I going to put in this template?
Well I have to produce true if no unit on the board has the same value twice.
In other words I'm going to produce false.
What I showed you in the last video, what I reminded you of in the last video is
that there is this constant here units, which is the list of all the units.
So really what I'd like to be able to do here is operate on that list of units to
make sure that all of them are valid. So I sort of wish that I could template
this somehow as doing something on the list of units.
Now this is a slightly different template from before, but we can always put
constants into a template to say that we want to operate on those constants.
And now I'll just go directly to wishing that I could say something.
And what I wish I could say here, is that I wish I could say that all these units
are valid. So I'm going to write a wish-list entry
for that. And I'm going to do it inside a local,
'cuz I think there's going to be several of these upper functions.
I don't have to do this in local. I can do this at top level.
I'm just going to do it in a local to show you that I can.
I'll say that valid units is a function I wish I had.
In it well what's its signature going to be?
Well I'm giving it a list of unit, because that's what units is.
Units is a list of unit. And, I want it to give me back a boolean.
I want it to give me back true if all the units are valid.
So that's a reasonable stub for it, and now I've made some progress.
Because I've said that validating the entire board means validating all the
units. Let's keep going.
How am I going to template valid units? What goes here?
Well, it's dot, dot, dot lou. That's the template for starters.
But how do I template it? Do I template it according to list?
Operating on all, the units in this list of units.
I could template it that way. But what I'm going to remember here, is
that this needs to make sure that every single unit, in the list of units, is
valid. And that's an andmap.
That's an andmap. So I'm going to template it as a call to
andmap. Now I've templated it as a call to
andmap. I need to fit in the dots.
Well, in andmap, the dots in this case, the signature of the dots, this function
right here. The function that we'd stick in right
here has to have the signature, unit to Boolean.
Because I'm calling andmap with a listed unit, and andmap is going to call this
function with each of the units in turn and the function has to produce a
Boolean, so here what we need is a function.
It checks whether an individual unit is valid, well we don't have one, but let's
wish for one. [NOISE].
I'll wish for it right here. That's the stub for it, and its signature
is that it consumes a unit. I'm going to write this this way just for
fun. Unit to Boolean.
So this function, let me get rid of this blank line here.
The first function, valid units, consumes a list of unit and produces a Boolean
saying whether all of them are valid. The second function I wished for, valid
unit consumes an individual unit that produces a Boolean saying whether it's
valid. How am I going to template this?
Well, I could go look at what a unit is. A unit is a list of pause.
Hey a unit is a list of pause. But what does it mean for a unit to be
valid? It means that the unit does not have the
same value twice. Here's an example that uses the unit for
the third row of a board. Here's the unit, that lists all the
positions of the third row, and here's the actual board and its third row.
If I used that unit to read all these values, to read the contents of the third
row. I would get a list like this.
And I need to throw out all the falses, because you are allowed to have more than
one false. If I throw out all the falses, now I just
have the values in that row. And if there's no duplicates there, the
unit's valid. Let's see.
I've gotta read out the unit. I've gotta get rid of the falses or keep
only the numbers, and I've gotta make sure there's no duplicates.
That's three distinct operations on, on the entire value in each step.
That's a function composition. Let's write this, let's template this as
a function composition. Let's see.
The first thing we need to do is read the unit, U, and once we've got the unit, we
need to keep only the values. Right.
I could, I could wish for a function called get rid of the falses.
It would be the same. But I'm going to wish for a function
called keep only the values. And once we've kept only the values, we
need to make sure that there are no duplicates.
We need to ask, are, make sure there's no duplicates.
So that's a function composition wish. And it might look a little more clear if
we do the line breaking like this. I wish now for three functions.
Let's wait the way entry for them define read unit of u.
Okay. Now that's going to produce a list of
values or false. So, we'll stub is as producing empty, and
this goes from unit to list of val or false.
And keep only values. Keep only Values, of one of these lists
of value or false. Is going to produce a list of just the
values. So this consumes list of val or false,
and produces list of val, and no duplicates.
This consumes a list of val, and it produces a Boolean.
[SOUND] And say whether there's no duplicates in there.
So I'm just wishing away. Well, let's see.
Read unit. Read unit consumes a unit, and, fix my
line-breaking here a little bit, and how am I going to template this?
It consumes a unit; and remember, a unit is a list of pause.
And it's gotta read all of those values. So, I could template this according to
list, because a unit is a list of pos. But what I've gotta do for every single
one of those pos's is read its value out of the board.
Read, read from the board the value of that position.
I've got to do it for every single pause in the unit.
This is a map. I'm going to template it as a map.
I'm going to map something over the unit. Now what am I going to map over the unit?
It's some function that consumes a pos and reads that position from the board.
Lets wish for that. This is a function that consumes a pos
and produces what's sitting in the board at that pos.
So it's going to produce either a value or false.
How am I going to template that? Well, let's see.
It's definitely got the pos to work with. And reminding ourselves what a pos is, go
all the way up here. A pos is a natural from zero to 80.
So if I template this according to the template of that natural [UNKNOWN]
non-distinct. I put dot, dot, dot p.
Now, what does this function need to do? Okay, it needs to, we can put it right
here, if we want. Produce contents of board, and by board I
mean this board here, the board right at the top.
Produce contents of the board at p. How do I do that?
Oh, well that's easy remember we have this primitive way down here, read
square. That produces contents of a board,
produces contents of a board at a given position p.
Let's remember the order of arguments to it.
It should be board and then position, and it is.
So this is just read-square board and p. Hey, I finish the function without
wishing for another function, that was kind of great.
All these ones up here are done, ooh that doesn't belong a blank line there.
All these ones up here are done. These are the only ones that I still
haven't completed. I could have maybe been putting bang,
bang, bangs in here to keep them more clear.
Let's see, keep all the values. This consumes the list of values or false
and it produces a list of value. How am I going to template that?
Well, this is a filter of some sort. Filter dot, dot, dot, l o v f.
I'm going to template that that way. Now I need to remember what a value is.
Let me go look. A value is a natural, from one to nine.
So let's see, go back down here to keep only values.
I'm consuming a list of value or false, and I need to produce just the values.
And values are naturals from one to nine. Oh, this is easy.
I'll just filter this with number question mark.
Number question mark will produce false every time it's given false, and then it
will produce true every time it's given a natural from one to nine.
So this will keep just a number. Seems like I'm getting close.
What about no duplicate? But see, no duplicates consumes list of
value, and it needs to produce true. Let's take a moment to write out its
purpose. [SOUND] Reduce true if no value, in l o v
appears twice. How am I going to template that?
Well to see whether something appears twice in a list, I kind of have to go
through every element in the list. And make sure that it doesn't appear
anywhere in the rest of the list, right? Because if I check every element and make
sure that it doesn't appear again later in the list, then I'll know there's not
duplicates. I don't need to know whether something is
duplicated twice. I don't need to know whether something, I
don't need to ask the question, well, does this thing appear earlier in the
list. If I just ask the question, hey for every
element of the list does it appear again later, I'll find all the duplicates.
Notice what I just did here. I just did the example step of the htdf
recipe. I'm not writing check expects, because
I'm not defining a function at top level. And I'm not even writing a complete call
to no duplicates. But what I'm doing is I'm writing down
examples of data that no duplicates is going to have to consume, and using those
examples to help me figure out what to do.
Remember what I said about the recipe, you don't always have to use all of it.
But here this function got a little hard on me, and so I started using a bit more
of the recipe. I pulled in the examples.
I've been using the signature all the way through here.
I use the purpose a couple of times. Here I'm using the signature purpose and
some examples. Even though I'm kind of just writing the
examples on a piece of scratch paper. So it seems like I need to go through the
whole list and I need to go through the whole list doing something a little
different than map or filter or folder do, so I'm going to have to use the full
on list template here. Cond empty l o v something.
Else, oops, let's put this purpose up here, where it will do us more good, else
dot, dot, dot something with first of l o v, and no duplicates of rest of l o v.
I'm just writing the list of template from memory at this point.
Okay, let's fill in the template. Let's see.
If I get to the end of the list. And I haven't found a duplicate yet.
Then that means there are no duplicates. Yay, fantastic, let's produce true.
Otherwise, hm. What I need to ask somehow is I need to
ask the question, hey does this thing appear in the rest of the list?
Does the first appear in the rest? I need to somehow ask that question.
There's a specific question I need to ask there, does the first appear in the rest?
Now, let's see. The first will be a number, but the rest
will be a list, so I'm operating on a list here.
So the operating on arbitrary size data rule comes in.
This dot, dot, dot, has to be a function. And we've seen functions like this before
earlier in this course, we wrote some functions that we gave them names like
contains. To check whether a string appeared in a
list of string. Turns out there's a built in function
like this you can use in dsl and isl called member.
Member is just the built in version of contain...
It tells us whether its first argument appears in the list that's the second
argument. So there's the question, the question is
eh, if I find the first thing in the rest, oh, there's an if here, for sure.
So, if I find the first thing in the rest, then that's bad.
That means there was a duplicate. So since I gave this function a negative
name, I gotta produce false. The answer to the question, are there no
duplicates, is false. I've just found a duplicate.
Otherwise, we do the natural reccursion. Let's see our parens balanced here.
Give it a go. All 20 tests passed.
And I believe, have I commented out the board tests?
Yeah, these board tests are uncommented, so all the tests are now passing.
So look, that function was a little bit complicated, and I walked you through the
I made no mistakes version of it. There's no way you were going to get to
the design of this function just as quickly as I did.
There's no way you were going to get to the design of this function as quickly as
I just did it. So, don't be discouraged if you're
sitting there going. There's no way I would have done that as
quickly. That's not my goal.
What I would like you to be able to do is to see how.
All I did to produce it was follow the design recipes that we've learned in this
course. Now, there's some cases where I chose to
template according to andmap, for example.
And you might have chosen the template according to list of unit.
That would be fine. You'd get there, too.
It would take you a little bit longer to get there 'cuz andmap is, is, is quicker
than, basically doing a concrete version of andmap, but you would have gotten
there. You might not have templated according to
a three function composition right away. That was going to cause you a bit more
trouble but you would have gotten there. What I need you to be able to do at this
point is go back through this and see that this was a reasonable scenario, and
see why I made each choice I made at each point.
But this was a hard function. It's the hardest single function we've
seen so far in this course. In fact it didn't end up being a single
function. It ended up having six helpers.
The key point is that the method we have been learning really did help me get
there. So go through this again and then we'll
give you a problem to work on.