This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language “fits together” to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. The three parts are not quite equal in length: Part A is almost as substantial as Part B and Part C combined. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.
More Nested Patterns
Loading...
Do curso por University of Washington
Linguagens de Programação, Parte A
816 ratings
Na lição
Section 2 and Homework 2
This section is a particularly rewarding one where a lot of ideas come together to reveal a surprisingly elegant underlying structure in ML. As usual, start with the welcome reading, dive into the material, and leave plenty of time to approach the programming assignment methodically.
Conheça os instrutores
Dan GrossmanProfessor
Computer Science & Engineering
[SOUND] In this segment, I want to show some more examples of using nested
pattern matching. So let's just do it.
Let's jump over here and let's write some code.
The first example I want to write is a function that I'll call non-decreasing.
it's just going to take a list of integers and return a [INAUDIBLE].
And true means that, at no point in the list, do you find a number that is
smaller than the number that comes before it.
Alright, so if we did this our old fashioned way with simple pattern
matching we might case on whether the list is empty or not.
x colon onto x is prime. And the empty list, that's definitely
true. You never see a decreasing situation.
But in this case, I kind of need to look at the next element as well.
And so you might, now do another pattern match on that tail of the list.
And if that were empty, well this would be the situation, where you have a one
element list. And that's also non-decreasing.
Otherwise, you would add that next element of the list, and then really, the
tail. And you would have to say, make sure that
X is less than or equal to Y and also that, we were non-decreasing.
Actually, and a common bug would be to say y is
prime, that's actually wrong, you actually need x is prime, in order to
make sure you're checking every position, and not just every other position.
So this would work, but these nested case expressions are a little clumsy.
And with nested patterns, we can express what I consider to be a more direct and
elegant algorithm. So in, the empty list case is just fine.
I have no problem with that. But now, let's use nested pattern
matching to handle the one element case directly.
So this pattern will match when x's is some head of the list, which we can match
against x, and then the rest of the list matches against the empty list.
So this pattern will match exactly against one element lists.
So we can just write true. And then, if that does not match, now we
can have another pattern, which is maybe, let's say, head cons onto neck.
Get it, get it? That's the thing in the list after the
head. Maybe on to rest,
okay? and this pattern matches all lists that have two or more elements cause head
will match the first, neck will match the second, and rest will match the rest of
the list. And now we can just check that indeed
head is less than or equal to neck. And also non-decreasing, neck cons onto
rest, all right, something like that. And that is it.
That's our whole function, and the type checker will actually make sure that our
patterns are exhaustive, and indeed they are.
We have a case for the empty list, a case for the one-element list, and a case for
all lists that have two or more elements. All right?
So that's another example of massive pattern matching that I actually rather
like. one little thing we can do to clean this
up. Whenever you have a variable that you're
not using in the corresponding branch, you can also write underscore.
That's a slightly better style. What it does, is it's just like a
variable pattern, it always matches, but it doesn't actually introduce a variable.
And that makes your code a little easier to read.
It says to the reader of your code, that you don't actually need what's in that
position, you just need that it's there. All right, so that's fine.
Now let's do another example. this one's a little sillier but it shows
something that I find quite common and convenient.
I'm going to define a little data type for the sine of a number, so p for
positive, n for negative, z for zero. And now what I want to do is write a
little function, multsin, it's going to take a pair of integers.
And it's going to return. So it takes two integers.
It's going to return the sign of the number you would get if you multiplied
those numbers together. But it's not actually going to do the
multiplication. I'm going to define a little helper
function here inside my function that just tells you the sign of a number.
and so if you have zero then you end up with z.
Otherwise, you get positive of x is greater than zero, is negative, and I'm
going to use that to figure out the sign that you get when you multiply X1 and X2.
Now it turns out there's in the extreme nine different cases based on the sign of
X1 and the sign of X2. Three possibilities for each, three times
three is nine. and if I tried to do this with nested
case expressions it would get a little messy.
But what if I just pattern matched on the pair, of calling sign with X1 and calling
sign with X2? And now what I could do right here is
simply have my nine cases. So I could have z comma z and have a case
for that. I could have p comma z.
I could have n comma z and so on. And I would continue that for nine cases.
And it would, the code would read like a nice table of exactly what the answers
should be for each combination. But we can do even let, better than that
when we realize that patterns are matched in order.
And so we know that if either thing is Z, the result will be Z, because if you
multiply anything by zero you get zero. And so let's use these nested patterns to
clean that up a bit. And let's say that if I have this first
pattern. So if the sign of X1 is zero, then no
matter what the sign of X2 is. So I could have a variable here like Y,
or I could use underscore since I don't actually care what that sign is.
And that's it. That's three of my nine cases, just
handled like that. And here's another three.
If the second position is z, then the entire thing is z.
So I've already handled six of my nine cases.
And now, in handling, the other, the remaining cases.
I can use the fact that I now know neither position will be z,
because I've already handled all those cases.
so another possibility is if both things are positive.
Then the result is positive. Another possibility is if both things are
negative, then the result is positive.
And there's two more cases, N comma P which would be negative, and P comma N
which would be negative. And, not only do I have a nice table
here, but my type checker will again check I haven't left anything out and
that's pretty neat. by the way, you can do this slightly
differently. You could just here at the end use a
single wildcard which will match anything including a pair and say hey, in all
remaining cases, the answer is negative. Now you'd better get rid of these or the
type checker will complain that you have unreachable, impossible cases.
and now whether this as I now have it written, is better style.
Or the one where I don't have this line, and instead I have these two as better
style, is really a matter of taste. The way I have it now is a little bit
shorter. It kind of reads nicely, it says,
otherwise the result is negative. But you are giving up a little bit of the
type checkers helpfulness, because if I wrote this.
The type checker will still say that this pattern match is exhaustive, but my
code's now wrong, because I forgot the case of N comma N, whereas if I leave
this case out and do it this way, here, the type checker will, in fact, give a
warning, telling me that the N comma N case has been forgotten.
In fact, lemme show you that. Use more nested patterns dot SML.
And in fact, up here, it says, warning, match non-exhaustive.
And then you can go and look at it, and try to puzzle out which case you forgot,
okay? But nonetheless, let's just leave it as
this one, since that's the shortest version and sometimes people like to see
nice and short code. Let me finish up with one more much
simpler example. which is just to compute the length of a
list, so we've done this plenty of times, at least things very similar to it.
If you have the empty list then return zero, otherwise x pull in, x is prime,
one plus line of x is prime. And this is just another example even
though there's not anything particularly nested or fancy here, where I would argue
it's a little better style to go ahead and put this underscore here to emphasize
that we don't care about the value at the head of the list, we just care that we
have a non-empty list, and we do need the tail because we need to call Len
recursively, with x as prime. All right,
so those are examples, let me switch back to the slides very briefly here to just
talk a little bit more about style and how these nested patterns lead to elegant
and concise code, and give you an intuition on how to look for
opportunities for nested pattern matching.
And the first is to try to avoid, where convenient, nested case expressions.
If instead of having nested case expressions, you can just have more
branches using nested pattern matching, it often leads to simpler code.
We saw that with unzip three in the previous segment, and we saw that with
non decreasing in this segment. That's not to say that nested case
expressions are always a bad idea. It's just a good hint to yourself to look
and see if nested patterns might be a little better.
Another very common idiom is to match against a couple of data types.
So instead of pattern matching against one data type, and then another data
type, and then another one, go ahead and match against a couple all at once.
We just saw that with the malt sign example where I matched against two
things of type sgn. We also saw that in the zip3 example.
Where we actually matched against a triple of lists and that was in the
previous segment. And finally, as a separate issue of
style, I do encourage you to use wild cards instead of variables.
A variable and a wild card both match against everything.
The difference is the variable actually introduces a local binding for the thing
it matched against. And the wild card does not.
And when you don't need that corresponding data in the branch,
wildcard concisely communicates that to the person reading your code.
That is instant pattern matching. In the next segment, we'll take a step
back, and give a more precise definition of how nested pattern matching is
actually defined in ML and similar programming languages.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
