Programming with
Data Structures and Algorithms

Join Lists

In 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


By installing the teachpack or the teachpack, you will have access to the following functions:


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!

The Problems

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.

Some Questions about j-reduce

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?

What to turn in: