Programming withData Structures and Algorithms
Programming withIn this assignment we will experiment with an alternate representation of lists: two smaller lists joined together. We will use the following data definition.
A join-list-of
'a is either
(one elt) where elt is of type 'a, or(join lst1 lst2) where lst1 and lst2 are both join-lists of 'a.
By installing the join-lists-teach.ss teachpack or the
join-lists-teach2.ss teachpack,
you will have access to the following functions:
empty
empty is used as the empty join-list.
empty?: any → boolean
consumes a datum and returns true
if the datum is the empty join-list (false otherwise).
one: 'a → (join-list-of 'a)
consumes a single datum and returns a one-element join-list
with that datum as the element.
one?: any → boolean
consumes a datum and returns true if the datum is
a singleton join-list (false otherwise).
get: (join-list-of 'a) → 'a
consumes a one-element join-list and returns the one element in that list.
join: (join-list-of 'a) (join-list-of 'a) → (join-list-of 'a)
consumes two join-lists and joins them together into a single list. If one or both
of the input lists are empty, join will simply return the other list unmodified.
Otherwise it will return a join-list containing the first list prepended onto the second.
join?: any → boolean
consumes a datum and returns true if the datum is a join-list
with multiple elements (false otherwise).
split: (join-list-of 'a) ((join-list-of 'a) (join-list-of 'a) → 'b) → 'b
consumes a join-list with two or more elements as a first argument.
As a second argument, it takes a handler which consumes two join-lists.
First split divides its first argument into a prefix and suffix which are
non-empty join-lists that will result in the original list if joined together.
Then split invokes its second argument on this prefix and suffix and returns
what that invocation returns. There is no guarantee that split will divide
the list at the most recent join (indeed, our implementation does not).
join-list?: any → boolean
consumes a datum and returns true if the datum is a join-list (false otherwise).
join-list=?: (join-list-of 'a) (join-list-of 'a) → boolean
checks whether two join-lists are equivalent. Two join-lists are considered equivalent
if they have the same elements in the same order.
When testing your solutions, you will need to compare two join-lists.
However, we have introduced a new type and check-expect cannot check
equality of join-lists. You can either use join-list=?
to compare two join-lists or you can use join-list->list
to convert a join-list into a regular Scheme list. You may also find it
tedious to construct larger join-lists by explicitly making singletons
and joining them together. Instead, you may use the list->join-list
procedure to construct larger join-lists.
Important: While you are free to use list->join-list
and join-list->list for testing and debugging, you may not
use either of these procedures in your solutions in any way!
With the API above, your task is to write the following functions for join-lists.
Note: It may be tempting to write j-first and j-rest,
then implement the other functions with j-first and j-rest
as you would for normal Scheme lists. The functions you write for join-lists should
take advantage of the unique structure of join-lists. It may be necessary to use
j-first and j-rest in some situations, but you should use
split instead where possible.
j-max: (join-list-of 'a) ('a 'a → boolean) → 'a
j-max returns the maximum number in a non-empty list. The second argument to j-max is a comparator on 'a, the type of elements contains in the list, as discussed in class.
j-length: (join-list-of 'a) → number
j-length returns the length of a list.
j-first: (join-list-of 'a) → 'a
j-first returns the first element of a non-empty list.
j-rest: (join-list-of 'a) → (join-list-of 'a)
j-rest returns a list containing all elements but the first of a non-empty list.
j-nth: (join-list-of 'a) number → 'a
j-nth returns the nth element of a list containing at least n elements. For example, j-nth called with second argument 1 should return the first element of the list.
j-map: ('a → 'b) (join-list-of 'a) → (join-list-of 'b)
j-map applies an operator to each element of a list and returns the list of resulting values. The input operator must accept exactly one argument.
j-filter: ('a → boolean) (join-list-of 'a) → (join-list-of 'a)
j-filter applies an operator to each element of a list and returns the list of elements for which the operator returned true. The input operator must accept exactly one argument and return a boolean value.
j-sort: (join-list-of 'a) ('a 'a → boolean) → (join-list-of 'a)
j-sort sorts a list in increasing order. The second argument to j-sort is a comparator on 'a, the type of elements contained in the list, as discussed in class.
j-reduce: ('a 'a → 'a) (join-list-of 'a) → 'a
j-reduce distributes an operator across a non-empty list. That is, given the list of elements e1, e2, ..., en, and the operator op, j-reduce computes the equivalent of e1 op e2 op ... op en.
For instance,
(j-reduce + (list->join-list (list 1 2 3)))
=> 6
(j-reduce max (list->join-list (list 3 1 4 6 2)))
=> 6
(j-reduce join (list->join-list (list (list->join-list (list 1 2))
(list->join-list (list 3 4 5))
(list->join-list (list 6)))))
=> (list->join-list (list 1 2 3 4 5 6))
What should the value of
(j-reduce - (list->join-list (list 1 2 3)))be? Hint: There is more than one possible answer. List all.
Unfortunately, having more than one answer violates the expectation
that j-reduce is a function. The problem is not with j-reduce but
with the use of - (minus) as an argument. What property should the
first argument given to j-reduce demonstrate? Can you argue this from
the description of j-reduce above?
join_lists.ss, with code implementing
each of the above functions with the given type signatures.reduce.[txt,pdf,doc] with your answers to the questions about j-reduce.
As always, these files must be in plain text, pdf, or, if you really must, Word format. If you
use Word, we will accept only Word 2003 (.doc) files. If you are
using Word 2007, you should export to a pdf.
We will not accept Word 2007 (.docx) files because we cannot read them.