COSC 3410 Programming Languages

Fall 2011

Homework Assignment #2

Scheme, the Sequel

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.

Q1 - flatten

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)

Q2 - nth-element

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)
()

Q3 - unique-set

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)

Q4 - majority*?

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

Q5 - mark-depth

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))

Q6 - every*?

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