程序代写代做代考 data structure scheme Hey, these are great but…not all elements are created equal

Hey, these are great but…not all elements are created equal
If list is a list, it is easy to get to the first element: (car list). The last element, however, takes more work to find. This is an inherent feature (and, sometimes, shortcoming) of this “data structure.”
(define (last-element l)
(if (null? (cdr l))
(car l)
(last-element (cdr l))))
> (last-element ‘(5 4 3 2 1))
1

Append: Place one list after another.
Basic operation on lists: place one after the other:
Append(11 12 13)to(1 2 3) (1 2 3 11 12 13)
It’s easy: (define (append list1 list2) ; in R5RS (if (null? list1)


Then…
list2
(cons (car list1)
(append (cdr list1) list2))))
>(append ‘(1 2 3) ‘(13 14 15))
(1 2 3 13 14 15)

How long does this take?
A good measure of the “time taken” by a Scheme function (without looping constructs, which we will discuss later) is simply the number of recursive calls it generates.
(append list1 list2) involves a total of length(lista) recursive calls. (Why? I needs to find the end of the list.)
(append list1 list2)
(append (cdr list1) list2)


(append (cdr (cdr list1)) list2)

Back to asymmetry: Reversing a list. Not as easy as you thought…
Reversing a list. One strategy: peel off the first element; reverse the rest; append the first element to the end. This yields:
(define (reverse items)
(if (null? items)
‘()
(append (reverse (cdr items))
(list (car items)))))
Then… > (reverse ‘(1 2 3 4 5)) (5 4 3 2 1)

Even after all that work: This reverse has a serious problem
How long does it take to reverse a list? (One good way to measure the running time of a SCHEME function is to measure the total number of procedure calls it generates.)
If the list has n elements, reverse is called on each prefix. There are about n of these, which looks OK.
However, each reverse also calls append. If reverse is called with a list of k elements, the append needs to step all the way through this list in order to get to the end, generating k total calls to append.
✤ All in all, this is roughly n + (n-1) + … + 1 calls; about n2/2. Surely we can reverse a list in roughly n steps!


Appending the car once the rest of the list is reversed is costly…
…what if we pass the car along as a parameter, asking our next-in- line to take care of the job of appending it to the resulting list?
(define (reverse items)
(define (reverse-iter r-items rest)
(if (null? r-items)
rest
(reverse-iter (cdr r-items)
(cons (car r-items) rest))))
(reverse-iter items ‘())
Note: this simply generates ~n recursive calls!

Visually
r-items
rest
(cdr r-items)
(cons (car r-items) rest))
1
2
3
4
5
6


2
3
4
5
6


3
4
5
6

2
1

4
5
6

3
2
1

5
6

4
3
2
1

6

5
4
3
2
1

6
5
4
3
2
1

Let’s consider another data type


The names used for functions and variables: e.g. x, f, car, empty?, sum, product
These are of type symbol, and they evaluate to their assigned values, e.g. when you evaluate (sqrt 4) you evaluate sqrt (a function) and 4 (a number), and apply that function to the value of the number, obtaining 2.
A symbol may also have a symbol as its value, but that requires using quotation.

Need to quote?
> (define a 10)
> (define b 20)
> (list a b)
(10 20)
What if we wanted (a b)?

Need to quote!
>(define a 10)
>(define b 20)
>(list ‘a ‘b)
(a b)
Could also use ‘(a b)
>(define teacher ‘(robert mccartney))
>teacher
(robert mccartney)
>(car teacher)
robert

Functions for checking types
(pair? x) #t if value of x is a pair
(list? y) #t if value of y is a list (i.e. a pair or the empty list) (symbol? w) #t if value of w is a symbol
(number? z) #t if value of z is a number

Examples
>(define a ‘fred)
>(define b ‘(10))
>(define c ‘())
>(symbol? a)
>(symbol? b)
>(symbol? ‘b)
>(list? b)
>(list? c)
>(pair? b)
>(pair? c)
>(number? b)
>(number? (car b))

Functions for checking equality
(= x y) #t if values of x and y are equal numbers (eq? x y) #t values of x and y are equal symbols,
(or equal numbers of the same kind, or refer to the same thing)
(equal? x y) #t if either(= x y), or(eq? x y), or x and y are both lists and their elements are equal? , that is
(and (equal? (car x)(car y)) (equal? (cdr x)(cdr y))
Note: the empty list is treated like a symbol for equality,
(eq? ‘() ‘()) => #t

Examples
> (define a ‘(fred))
> (define b ‘(10))
> (define c ‘())
> (define d a)
>(eq? (car a) ‘fred)
>(eq? a ‘(fred))
>(equal? a ‘(fred))
>(eq? a d)
>(eq? b 10.0)
>(= b 10.0)
>(eq? c ‘())
>(eq? c (cdr a))

Count the atoms in a list (top-level)
Define recursively: {0 if x is ‘()
(count-atoms x) = (+ 1 (count-atoms(cdr x))
if (car x) is not a list
(count-atoms (cdr x)) otherwise
(define (count-atoms x)
(cond ((null? x) 0)
((not (list? (car x))
(+ 1 (count-atoms (cdr x))))
(else
(count-atoms (cdr x)))))

Count the atoms in a nested list
Define recursively: {
0 if x is ‘()
(ncount-atoms x) = 1 if x is not a list
(+ (ncount-atoms (car x))
(ncount-atoms (cdr x))) otherwise
(define (ncount-atoms x)
(cond ((null? x) 0)
((not (list? x)) 1)
(else
(+ (ncount-atoms (car x))
(ncount-atoms (cdr x))))))

Example: use lists to represent sets
A set is a collection of things without repeats
Using lists:
✤ Define a function to see whether a set is empty
✤ Define a function to see whether something is an element of a set
✤ Define a function to add an element to a set
✤ Then define other set operations in terms of the above functions
✤ Note: if x is a set, (cdr x) is also a set.

Some of these are easy
(define (empty-set? x)
(null? x))

Set membership
Is x an element of set y?
✤ Nothing is in the empty list
x is in set y if it is equal to the first element of y, or is in the y excluding its first element (think car and cdr)
(define (element-of-set? x set)
(cond ((null? set) #f)
((equal? x (car set)) #t)
(else
(element-of-set? x (cdr set)))))

Add element to a set
(adjoin-set x set):
if x is already in set, result is set, otherwise add x to the front of the list
(define (adjoin-set? x set)
(if (element-of-set? x set)
set
(cons x set)))

Set intersection
(intersect-set x y)
✤ If either x or y is empty, the intersection is empty set.
if the first element of x is in y, then the intersection is the first of x added to the intersection of the rest of x with y
✤ if the first element of x is not in y, then the intersection is the intersection of the rest of x and y
(define (intersect-set x y)
(cond ((or (empty-set? x)(empty-set? y)) ‘())
((element-of-set? (car x) y)
(cons (car x)(intersect-set (cdr x) y))
(else
(intersect-set (cdr x) y))))

Finding the smallest
Objective
Write a function that finds the smallest element in a list Inductive definition
Base case?
List of one element…. Induction?
Smallest between the head and smallest in tail






The Scheme code
One auxiliary function to choose the smallest among 2 One plain induction on the list.
(define (smallest l)
(define (smaller a b) (if (< a b) a b)) (if (null? (cdr l)) (car l) (smaller (car l) (smallest (cdr l))))) ✤ ✤ Removing from a list ✤ ✤ ✤ ✤ Goal Remove a single occurrence of a value from a list Inductive definition Base case: Easy: empty list Induction: If we have a match: If we don’t: remove from the tail and preserve the head. ✤ ✤ done! Just return the tail. ✤ ✤ The Scheme code One plain induction on the list. v: the value to remove elements: the list to remove it from (define (remove v elements) (if (null? elements) elements (if (equal? v (car elements)) (cdr elements) (cons (car elements) (remove v (cdr elements)))))) ✤ ✤ ✤