Transcript Unit 16

sixteen
lists and compound data
Recap

Names: constants and variables



When evaluated, return a specific data objects
Can make new names with: [define name value]
Applications (aka procedure calls)
[procedure args …]
 Procedure is run with the args as inputs

Conditionals (if expressions)
[if test consequent alternative]
 Evaluate test
 If result was true, evaluate and return consequent, otherwise alternative

Compound procedures
[args … → exp]
 Makes a new procedure with the specified arguments and return value
 Expression for return value can refer to args
How compound procedures are called:
An approximation


[define double [n → [× n 2]]
[double 4]


[[n → [× n 2]] 4] substitute value of double
[ [n → [× n 2] ]
procedure

[× 4 2]

8
arg
4]
body
replace call with body
substitute argument into body
Some primitive data types

Integers (whole numbers)
1, 2, 3, -1, 0, -43589759, etc.

“Floating-point” numbers
3.14159, -44.0, anything with a decimal point


Characters
Booleans (truth values)


Two values: “true” and “false”
Used to represent answers to questions
Note: there are good reasons for having different kinds of number
types, but we’re not going to try to justify them at this point. Just be
aware that they’re there.
Some composite data types

Strings (i.e. text)



Colors




Sequences of characters
“this is a test”, “so is this”
Specify amount of red, green, and blue light for a pixel
One integer (0-255) per “channel” (red, green, blue)
One integer (0-255) for level of opacity (the “α-channel”)
Bitmaps



The kind of image manipulated by a paint program
2-dimensional array of color objects
One color object per pixel of the image
A new composite data type: the list
Lists are sequences of data objects
 Any length
 Any type of data object
 Different types of data can appear in the same
list
Example: a CD database


A list of data objects representing CDs
Each CD is represented as its own list:



Artist
Title
Year
Okay, what can we do with lists?

[list item1 item2 … itemn]
Creates a list containing the specified items, in order

[get list index]




[first list], [second list], …, [tenth list]


Extracts the item from list at position index (a number)
Index counts from zero
So for an 5-element list, the elements are numbered 0, 1, 2, 3, 4
Extracts the specified element of list.
[length list]
Returns the number of items in list

[append list1 list2 … listn]
Creates a new list with all the items in the input lists, in order
Examples

Notice that lists print in the
same bracket notation as code
► [define my-list
[list 1 2 3]]
[1 2 3]

This may seem confusing, but
► [append my-list
[list 4 5 6]]
[1 2 3 4 5 6]



The system doesn’t print code
back at you
So you can’t mistake them for
one another
It will turn out to be really
useful to have lists and code
look the same
► [get [append my-list
[list 4 5 6]]
5]
6
►
Mapping and folding

[fold p start-value list]




[map procedure list]



Joins all the values of list together using procedure p
Mostly useful for summing, multiplying, or otherwise mushing
together the elements of a list
[fold + 0 [list 1 2 3]] returns: “[+ 3 [+ 2 [+ 1 0]]]”
Runs procedure on every element of list and returns their return
values as a new list
[map – [list 1 2 3 4]] returns “[-1 -2 -3 -4]”
We’ll talk later about additional capabilities of map and
fold
How map works (approximately)





[map double [list 1 2 3 4 5]]
[map [n → [× 2 n]]
[list 1 2 3 4 5]]
[list [[n → [× 2 n]] 1]
[[n → [× 2 n]] 2]
[[n → [× 2 n]] 3]
[[n → [× 2 n]] 4]
[[n → [× 2 n]] 5]]
[list [× 2 1]
[[n → [× 2 n]] 2]
[[n → [× 2 n]] 3]
[[n → [× 2 n]] 4]
[[n → [× 2 n]] 5]]
[list 2
[[n → [× 2 n]] 2]
[[n → [× 2 n]] 3]
[[n → [× 2 n]] 4]
[[n → [× 2 n]] 5]]







[list 2
[× 2 2]]
[[n → [× 2 n]] 3]
[[n → [× 2 n]] 4]
[[n → [× 2 n]] 5]]
[list 2
4
[[n → [× 2 n]] 3]
[[n → [× 2 n]] 4]
[[n → [× 2 n]] 5]]
…
[list 2 4 6 8
[[n → [× 2 n]] 5]]
[list 2 4 6 8
[× 2 5]]
[list 2 4 6 8 10]
the list: [2 4 6 8 10]
Averaging

Sum of a list


Mean (average) of list


fold + over all elements
Divide by the length (number
of elements)
RMS (root-mean-square)


A.k.a. standard deviation
Easy:


Take the root of the mean of
the squares of all elements
Get the squares by mapping
square over all the elements
► [define sum
[list → [fold + 0 list]]]
<Procedure sum>
► [define mean
[list → [∕ [sum list]
[length list]]]]
<Procedure mean>
► [define rms
[list → [sqrt [mean [map square list]]]]]
<Procedure rms>
► [define square
[number → [× number number]]]
<Procedure square>
► [rms [list 1 2 3 4 5 6]]
3.8944405226628
Searching and filtering

[list-index predicate list]
Returns the position within list of the first item
that satisfies predicate

[find predicate list]
Same, but returns the item itself

[filter predicate list]
Same, but returns all the items (as a list)
satisfying predicate
Examples

We’ll use this list several
times, so put it in a variable

Find all the numbers in it

Find all the strings

Find just the first number

Find where the first number is

Verify that position really has a
number
► [define silly
[list “a silly” “list”
“with” 2 “numbers
and” 5 “strings”]]
► [filter number? silly]
[2 5]
► [filter string? silly]
["a silly" "list" "with" "numbers
and" "strings"]
► [find number? silly]
2
► [list-index number? silly]
3
► [get silly 3]
2
Any and every item in a list

[any predicate list]
True when any item in
list satisfies predicate

[every predicate list]
True when every item in
list satisfies predicate
► [define cd-database
[list [list “The white album” “The Beatles”]
[list “Sgt. Pepper's Lonely Hearts Club Band”
“The Beatles”]
[list “Pod” “The Breeders”]
[list “Dummy” “Portishead”]]]
► [define artist
[album → [second album]]]
► [define Beatles?
[album → [= [artist album]
“The Beatles”]]]
► [any Beatles? cd-database]
True
► [every Beatles? cd-database]
False
► [filter Beatles? cd-database]
[["The white album" "The Beatles"]
["Sgt. Pepper's Lonely Hearts Club Band" "The
Beatles"]]
How do you count the number of
Beatles albums in the database?
How do you count the number of
Beatles albums in the database?
► [length [filter Beatles? cd-database]]
2

There’s also a built-in count procedure:
[count Beatles? cd-database]

By the way, we’re not holding you responsible for
memorizing all these procedures

For tests, we’ll provide you with the names and arguments for all
the lists procedures you’ll need
How do you get the titles of all
Beatles albums?
How do you get the titles of all
Beatles albums?
► [define album-title
[album → [first album]]]
<Procedure album-title>
► [map album-title
«procedure to apply to each element»
[filter Beatles? cd-database]] «list of elements»
["The white album“ "Sgt. Pepper's Lonely Hearts Club Band"]
►
We’ve slipped an extra feature into this: comments


Anything enclosed in «»s is ignored by the computer.
It’s just there as a note from the programmer
Extracting chunks of lists

[prefix list count]
The first count elements of list

[without-prefix list count]
All but the first count
elements of list

[suffix list count]
[without-suffix list count]
Elements taken from/dropped
from the end rather than
the beginning of the list
► [prefix [list 1 2 3 4] 2]
[1 2]
► [suffix [list 1 2 3 4] 2]
[3 4]
► [without-prefix [list 1 2 3 4] 1]
[2 3 4]
► [without-suffix [list 1 2 3 4] 1]
[1 2 3]
►
Last, but not least, the apply procedure
[apply procedure list]
 Calls procedure and
passes it the
elements of list as
arguments
 Really, really useful
► [apply + [list 1 2 3 4 5]]
15
► [apply max [list 1 2 3 4 5 1]]
5
► [apply get
[list [list 1 2 3 4 5]
2]]
3
► [apply append
[list [list 1 2]
[list 3 4]
[list 5 6]]]
[1 2 3 4 5 6]
Exercise 3

On web site




Build a CD database using lists and strings
Write procedures to extract information from it
Doesn’t require understanding the rest of this
lecture
Due Tuesday
Esoteric issue:
The textual representations of lists



The rest of this lecture is esoteric
You don’t need to fully understand it yet
But


It will teach you a notation that you may find
more convenient
It will let you understand what’s going on if the
system prints something at you in this
notation
The textual representations of lists

How do you call a procedure on the list [1 [2 3]]?
That is, the list with two elements:



The number 1
The list [2 3]
Several ways you could imagine notating it:



[my-procedure [1 [2 3]]]
[my-procedure “[1 [2 3]]”]
[my-procedure [list 1 [list 2 3]]]
Textual representations of lists

We’ve been stuck with: [list 1 [list 2 3]]

Good points


Bad points




Unambiguous
More typing
Looks different from the printed representation
Slower than providing a pre-made list
How can we notate pre-made lists as
arguments?

Need another kind of quotation mark
The quote operator


We use single-quotes to notate lists
Just like quoting strings but



Result is a list, not a string
Use single-quote, not double-quote
Only use it at the beginning:

‘[1 [2 3]] is the equivalent of [list 1 [list 2 3]]
More on quoting


‘[1 2 3]
‘[1 [2 3]]



Do not put ‘ inside of ‘ as in: ‘[1 ‘[2 3]]
‘[1 “foo”]
‘[1 foo]



≈ [list 1 2 3]
≈ [list 1 [list 2 3]]
≈ [list 1 “foo”]
≠ ‘[1 “foo”]
‘[1 foo] isn’t illegal syntax
And it isn’t a list with a string
It’s a list with a new kind of data object: a symbol
Symbols

Like strings but:


They can only be individual words – no spaces,
brackets, etc.
When embedded in a quoted list, you don’t need any
extra quote marks


Use eq? to check if two symbols are the same, not
string=?



‘[a b c] vs. ‘[“a” “b” “c”]
Good because eq? happens to be a lot faster than string=?
Faster and more convenient than strings
Less flexible than strings
Ow, my head hurts

[+ a 1] is a procedure call expression


Returns the value of the variable a + 1
‘[+ a 1] is not a procedure call expression

It’s a quoted list:






First element is the symbol +
Second element is the symbol a
Third element is the number 1
The + isn’t a reference to adding
The a isn’t a reference to the variable a
‘a is the symbol a, not the variable a
Don’t panic


Yes, quote is confusing
But you’ll get used to it



We’ll ease into using it
It will turn out to be mind-bogglingly useful
Just remember it isn’t really any different
from the quotation marks in strings