Racket Lists

Loading...

From the course by University of Washington

Programming Languages, Part B

409 ratings

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

University of Washington

Programming Languages, Part B

409 ratings

[As described below, this is Part B of a 3-part course. Participants should complete Part A first -- Part B "dives right in" and refers often to material from Part A.] 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 of Part A. Part B assumes successful completion of Part A. 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. 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.

From the lesson

Section 5 and Homework 4 (First Module with Racket)

Let's get started programming with Racket and then learning idioms related to delaying evaluation. The welcome message has a few additional comments about picking up a new language and how to approach the homework assignment, so let's get started...

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

[MUSIC]

We continue our introduction to Racket by learning about Racket lists.

This will go quickly because Racket lists work a lot like MLs lists.

In particular, the way we used ML lists in section one

where we used the functions to access the pieces of a list.

So let me just go over the primitives and then I'll write some examples, and

again because it works a lot like an ML, I suspect this will not be too surprising.

In fact, it will be reassuring to see some of the same ideas in a different language.

The way we write the empty list is with the word null.

In ML, we would have written bracket bracket, the empty list we write null.

It's fine.

By the way if you have seen scheme, this is different.

In scheme, you often wrote it parenthesis parenthesis, that will not work in Racket.

We will use null to write the empty list.

If you want to build a list, use the function cons.

It won't surprise us the name Racket, that's going to come first before

the two arguments just like plus comes before the arguments to plus.

This is what in ML, we wrote with colon, colon between the two arguments.

So cons will take an element in a list and create a list one element longer.

If you have a list, and you want to get the head, use this built in function car.

And if you want to get the tail, use this built-in function cdr, spelled C-D-R,

pronounced cdr.

This is what in ML was the head function hd.

And the tail function tl.

And finally, to see if a list is empty or not, we can use null?

which we often just pronounced null or if you prefer null.

And this is what in ML was the null function, N-U-L-L.

So perhaps little confusing that we write the empty list N-U-L-L and

asked if a list is empty with the null?

function, but every language has it's different names for things.

Just a couple of more things on the slide that you see here.

If you wanted to build a long list, you don't have to say cons of three,

of cons of four, of cons of five.

There's a provided function list that takes a bunch of arguments and

makes a list out of these arguments.

So if you pass at en expressions, it evaluates those en expressions and

makes a list of length en.

We had similar built in, in fact syntactic sugar and ML for

when we wanted to do this.

And finally, I should talk about these names car and cdr.

Why on earth would you have the function for

accessing the first part of a list we called car and the rest of the list cdr?

Don't try to figure this out in terms of English.

It's a historical accident going back several decades, and

some of the original machines that this sort of language was implemented on,

these things should not be called this but it's too late we're stuck with them.

Okay, so that's everything we need but it will make a lot more sense after we just

write a few functions, simple things like were it used to.

So lets first right a function.

I have a comment here, sum all the numbers in a list, okay?

So remember, I could define a variable sum and then lambda taken a list xs.

I prefer instead the syntactic sugar version of doing exactly the same thing,

so I added that parenthesis and then the arguments.

This is a one argument function, and now at this point we are very comfortable at

the recursive solution to this function.

If the list is empty, so I'm calling the null?

function with my argument, then 0, it's the second argument to if.

The 3rd argument to if will be a function car,

call the function plus with the result of calling the function car on xs.

I.e., the head of the list with calling

sum recursively with the cdr of the list, okay?

So that's the end of the called a cdr, the end of the call to sum,

the end of the call to plus, the end of the if, and the end of the define.

If you're not use the languages like this,

you might find it funny that I ended with so many parentheses.

It's incredibly natural, you get used to it.

It's exactly that I have to finish all these calls and

then I have a perfectly good syntactic function.

And I could go ahead and run this, and

try sum of how about the list with 3 4 5 6, and I would get 18, okay?

No problem.

By the way, we'll talk about this much, much more, but

if you do something like this,

this would quote on quote compile because there's no type checker to stop us.

But we'll get an error and

DrRacket even tries to tell us where this error occur in the code, and

it's says that plus expects a number and you gave it a string hi, okay?

So that's our first example of a list function.

Let's do a couple more.

You know my favorite which is append.

It turns out append is built into Racket.

We could shadow it but I find shadowing confusing ,so how about I call it

my-append taking into lists xs and ys.

By the way in the previous segment and this one, you'll notice I sometimes

have hyphens in my variable names or here in my function name.

That's perfectly allowed in Racket, it's just a syntactic thing to get used to.

In many languages, we prefer to write it like this or like this.

All of these work, it's just a bit more of the convention in Racket

to separate the words of our variables and function names with a hyphen.

Every language is entitled to its own conventions.

Okay, my-append is a function that takes two lists, xs and ys.

If xs is empty, return ys otherwise cons,

the first element of xs, on to the result

of appending the rest of xs on to ys.

It was beautiful in ML, it's beautiful in Racket.

Let me show you those closed parentheses again,

finish the recursive called my-append.

There were call to cons, the conditional, and the define.

This will work great, so that's append.

And let's do one more, how about map?

So we see something with a higher order function, works just fine.

Again, this one is built in, so how about I call it my-map.

Map as an ML takes in two arguments, f and xs.

Remember in Racket, this is really a two argument functions, so

this isn't toppling or carrying.

And we know how map should work.

It should apply after every element of xs and

return a list of the same length with the result of those calls.

So if you have a zero length, zero list, you end up with null, all right?

So I asked here, is xs null?

If it is, I want to return the empty list.

I could have written xs here, but I wanted to show using the null value, okay?

The variable null is essentially bound to the empty list.

Otherwise cons f of car of xs.

All right, so what have I done so far?

I got the head of the list and I called f with that head of the list.

So that's my first argument to cons.

And then my second argument to cons,

I can hit return here if I want it to indent nicely.

Is to call map recursively with the same f and the rest of the list.

And the call to cdr, call to my-map, call to cons, the if, and the define.

Okay, so that's map and we can run all this,

and we'll see if we do that I do now have a function my-append.

The ripple will say, that's a procedure.

The same way ML likes to say that's a function.

I'm not going to print anything else out for you.

My-map is also a procedure.

If I try to call my-map with just one argument like lambda x plus x1,

this will be an error, and that's because my-map expects two arguments.

But, okay, let's go ahead and call my-map with two arguments.

In fact, let's define a variable foo to be the result

of calling my-map with this little anonymous function, plus x and 1.

So what I've written just here, you see highlighted in the gray,

is just an anonymous function.

Takes in one argument, x that it's in its own parentheses and

the function body is a call to plus with x and 1.

And then for my second argument to my map, how about cons 3

onto cons 4 onto cons 5 onto null.

Of course I could have used the list function to write this more concisely but

I want you to get used to lots of parentheses.

This is not hard to read.

That's the list containing 3, 4, and 5.

Close the call to my map, close the call to define, hit return.

That worked just fine.

The ripple doesn't tell us anything.

It was happy to do that definition, but if I asked to evaluate foo,

it will tell me that that is the list 4 5 6.

The way the ripple prints lists, is with this quote, and then the list elements.

And that's fine that really is the list (cons 4

(cons 5 (cons 6 null) and we'll see that because if I evaluate this,

I will get the same thing printed by the ripple.

So that's our practice with list functions,

again they work a lot like in ML.

They're just as convenient and powerful, recursion is just as useful.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play