CS 135 (Module 6: Lists)

What is a list?

A list is a recursive structure - it is defined in terms of a smaller list

What is a list of zero and what do we call it?

A list of zero is special and we call it the empty list. It is represented in Racket by empty.

What does (cons v lst) do?

It creates a list by adding the value v to the beginning of list lst.

How can lists be built up?

By using cons

What is empty?

A value representing an empty list

(cons v lst):

Consumes a value and a list; produces a new, longer list

(first lst):

Consumes a non-empty list; produces the first value

(rest lst):

Consumes a non-empty list; produces the same list without the first value

(empty? v):

Consumes a value; produces true if it is empty and false otherwise

(cons? v):

Consumes a value; produces true if it is a cons value and false otherwise

(list? v):

Equivalent to (or (cons? v) (empty? v))

What is a cons value?

It is a value produced by (cons v lst). In other words, a list that contains at least one value.

What are the primary tools for extracting values from a list?

first and rest

What is contract for lists?

(listof X) where x may be replaced with any type

List values are

1. empty
2. (cons v l), where v is any Racket value and l is a list value

How are list values given?

Racket list values are traditionally given using constructor notation - the same notation we would use to construct the value.

(first (cons a b)) ->

a, where a and b are values

(rest (cons a b)) ->

b, where a and b are values

(empty? empty)

true

(empty? a) ->

false, where a is any Racket value other than empty

(cons? (cons a b)) ->

true, where a and b are values

(cons? a) ->

false, where a is any Racket value not created using cons

What is a recursive data definition?

A definition that refers to itself

Does the base case refer to itself?

No

A (listof X) is one of:

- empty
- (cons X (listof X))

What is a template?

A template is a general framework within which we fill in specifics.

What is a template derived from?

A data definition

What is the template for processing a (listof X)

;; listof-X-template: (listof X) -> Any
(define (listof-X-template lox)
(cond [(empty? lox) ...]
[(cons? lox) ...]))

Go a step further by applying (rest lox) to listof-X-template as it is a type of (listof X)

;; listof-X-template: (listof X) -> Any
(define (listof-X-template lox)
(cond [(empty? lox) ...]
[(cons? lox) (... (first lox)
(listof-X-template (rest lox)))]))

What are the four crucial questions to help think about functions consuming a list?

1. What should the function produce in the base case?
2. What should the function do to the first element in a non-empty list?
3. What should calling the function of the rest of the list produce?
4. How should the function combine #2 and #3 to produce the answer for the entire list?

What are the answers to these questions?

1. The length of an empty lsit (the base case) is 0.
2. We don't care what the first value is, just that it exists. There's no need to transform it/
3. Calling (count-concerts (rest loc)) should produce the length of the rest of the list, an integer
4. We should combine steps 2 and 3 by adding 1 (because the first element exists) to the result of step 3

When is a function recursive?

A function is recursive when the body of the function involves an application of the same function.

What is a condensed trace?

It is space saving tool used in slides that shows the important steps and skips over the trivial details of a full trace.

It is important that our functions always ___

terminate (stop running and produce an answer)

What are the two conditions?

1. it's the base case, which produces 0 and immediately terminates
2. or, it's the recursive case which applies counts-concerts to a shorter list. Each recursive application is to a shorter list, which must eventually become empty and terminate

What is the final form listof-X-template you should use for functions that consume a list?

;; listof-X-template: (listof X) -> Any
(define (listof-X-template lox)
(cond [(empty? lox) ...]
[(cons? lox) (... (X-template first lox)) ...
... (listof-X-template (rest
lox)) ...)]))

What is simple recursion?

The list template which has the property that the form of the code matches the form of the data definition.

In simple recursion, every argument in a recursive function application is either:

1. unchanged
2. one step closer to a base case according to a data definition

What are the current additional built-in functions?

cons, first, rest, empty?, cons?, list?, append, length, member?

What does negate-list do?

It consumes a list of numbers and produces the same list with each number negated (3 becomes -3)

What is the negate-list template?

(define (negate-list lon)
(cond [(empty? lon) empty]
[else (cons (- (first lon)) (negate-list (rest lon)))]))

In a self-referential data definition (like listof-X):

1. at least one clause (and possible more) will use the definition's name to show how to build a "larger" version of the data
2. at least one clause (and possibly more) must not use the definition's name; these are base cases

What is the shape of a self-referential template?

It will be a cond expression with one clause for each clause in the data definition

What do self-referential data definition clauses lead to?

They lead to recursive expressions in the template

Do base case clauses lead to recursion?

No

What is a string?

A sequence of characters in disguise

What function converts a string to an explicit list of character?

string->list

What converts a list of character into a string?

list->string

What is Racket's notation for the character 'a'?

#\a

What is the result of evaluating (string->list "test")?

(cons #\t (cons #\e (cons #\s (cons #\t empty))))

What is a wrapper function?

It is a simple function that "wraps" the main function and takes care of housekeeping details like converting the string to a list.

Wrapper functions:

1. are short and simple
2. always call another function that does much more
3. sets up the appropriate conditions for calling the other function, usually by transforming one or more of its parameters or providing a starting value for one of its arguments