Lists, Loops, and Higher Order Functions

June 27th, 2019

Announcements

• HW0 is due tonight at 11:59PM on bCourses
• Course Policies Quiz is due tonight at 11:59PM on bCourses
• First Party (optional) is tomorrow from 11AM - 1PM in 200 Sutardja Dai (CS10 lab)
• HW1 has been released and is due Tuesday, July 2nd on Gradescope

Lists

Types of Data in Snap! (review)

• Number
• Text
• Boolean
• Function
• List

Some common lists

Shopping list:

1. Eggs
2. Milk
3. Strawberries
4. Turkey

Grades:

1. 97
2. 84
3. 90
4. 73
5. 78
6. 88

Lists in Snap!

Shopping list

Grades

List

(Demo)

A list is an ordered sequence of zero or more values

• Lists can store any type of data (even lists!)
• Items can be retrieved by index (position)
• Lists are mutable
• Can change number of items, or value at an index.

Control Flow

Control Flow

(Demo)

• Control flow is the order in which the steps of a program are executed

Control Flow Summary

• Line-by-line from top to bottom
• If execution reaches a procedure, run the code in the procedure until either:
• The procedure has no more lines left to run
• Execution reaches a report
• Then return back to where the block was called from

Control Flow Summary

• Predicate
• If the predicate reports true, run the code inside
• If the predicate reports false, skip the code inside
• Continue on to the rest of the program

• Predicate
• If the predicate reports true, run the code inside the if
• If the predicate reports false, run the code inside the else
• Continue on to the rest of the program

Control Flow Summary

• Predicate
• If the predicate reports true, skip the code inside and continue on to the rest of the program
• If the predicate reports false, run the code inside, then check the predicate again

• Set i to the first number
• i
• If i is less than or equal to the second number, run the code inside, change i by 1, and check again
• If i is greater than the second number, continue on to the rest of the program

• item
• If there are more items in the list, set item to the next item of the list, run the code inside, and check again
• If there are no more items in the list, continue on to the rest of the program

Which of the following will say the items of DATA?

A.

​

B.

​

C.

D.

​

E.

Which of the following will say the items of DATA?

A.

​

B.

​

C.

D.

​

E.

Higher-Order Functions (HOFs)

Higher-Order Functions

• A higher-order function is a function that does one or both of the following:
• Takes in a function as an input (domain)
• Outputs a function (range)
• Three common higher-order functions that we use in Snap! are:
• Map
• Keep
• Combine
• We will see more examples of higher-order functions later in the class!

Map

• Apply a function to every item in a list
• Report a new list, using the results of calling the function on each item

function

list

Keep

• Filter items from a list
• Report a new list, with only the items for which the predicate reports true

predicate

list

Combine

• Merge the items of a list into a single value
• Use the results of calling the function repeatedly, until only a single value remains
• Report this single value
• The function (almost) always has 2 empty inputs and is associative
• Example: Addition is associative because (a + b) + c = a + (b + c)

function

list

(Demo)

What is the output?

A.

B.

C. 0

D. 30

E. -30

What is the output?

A.

B.

C. 0

D. 30

E. -30

Summary

• Lists are a new data type that let us group values in order
• Control flow allows for us to manage what parts of a program are executed and in what order
• Map, Keep, and Combine are higher-order functions that work with lists
• The actual implementations of Map, Keep, and Combine are below our level of abstraction