Due: Wednesday, Sept 14, 11:00am CDT

Submit: Turn in a single Scheme source file called "hw2.scm" using the`turnin` command on the Systems Lab machines. Include the names of all authors at the top of the file in a comment block.
Work is to be completed individually, using only the Scheme constructs
covered in class (TLS Ch 1-6) and the arithmetic and logical primitives.

Submit: Turn in a single Scheme source file called "hw2.scm" using the

Define a function "flatten" which takes a list (possibly containing
sublists) and returns a new list with all of the atoms at the top
level (i.e. no sublists).

Examples:

> (flatten '((a) ((b c)) (((d) e)) (f)))

(a b c d e f)

Examples:

> (flatten '((a) ((b c)) (((d) e)) (f)))

(a b c d e f)

Define a function "nth-element" which takes a list and an index 'n',
and returns the S-expression at the n-th location in the list. (The
index should be zero-based, meaning that index '0' refers to the first
item of the list.)

Examples:

> (nth-element '(a b c) 0)

a

> (nth-element '(a b c) 2)

c

> (nth-element '(a b c) 5)

()

Examples:

> (nth-element '(a b c) 0)

a

> (nth-element '(a b c) 2)

c

> (nth-element '(a b c) 5)

()

Define a function "unique-set" which takes as input a complex list and
returns a simple list containing each item (non-pair) exactly
once. Items should appear in the output list in the same order in
which they first occured in the input list.

Examples:

> (unique-set '(a b c))

(a b c)

> (unique-set '(a b a a b b c a c b))

(a b c)

> (unique-set '(a ((b a) b) (c)))

(a b c)

Examples:

> (unique-set '(a b c))

(a b c)

> (unique-set '(a b a a b b c a c b))

(a b c)

> (unique-set '(a ((b a) b) (c)))

(a b c)

Define a predicate "majority*?" which takes a complex list and returns
#t only if one of the items comprises more than half of the total
items in the list.

Examples:

> (majority*? '(a b c))

#f

> (majority*? '(a b a))

#t

Examples:

> (majority*? '(a b c))

#f

> (majority*? '(a b a))

#t

Define a function "mark-depth" which takes a complex list and replaces
each atom with a two item list containing the atom and an integer
indicating the depth in the list. (Top-level items are at depth 0,
sub-lists are depth 1, and so on.)

Examples:

> (mark-depth '(a b c))

((a 0) (b 0) (c 0))

> (mark-depth '(a (b (c)) ((d) e f) ((g)) h i))

((a 0) ((b 1) ((c 2))) (((d 2)) (e 1) (f 1)) (((g 2))) (h 0) (i 0))

Examples:

> (mark-depth '(a b c))

((a 0) (b 0) (c 0))

> (mark-depth '(a (b (c)) ((d) e f) ((g)) h i))

((a 0) ((b 1) ((c 2))) (((d 2)) (e 1) (f 1)) (((g 2))) (h 0) (i 0))

Define a function "every*?" which takes a predicate and a list, and
returns #t if and only if the predicate is true for every item in the
list.

Examples:

> (every*? number? '(1 2 3 4))

#t

> (every*? null? '(() () (() a) ))

#f

Examples:

> (every*? number? '(1 2 3 4))

#t

> (every*? null? '(() () (() a) ))

#f

Back

[Revised 2011 Sep 06 17:38 DWB]