Homework 8b

MUST BE DONE SOLO

Due Date Thu at 9:00pm (Week 8)

Purpose SExp practice and unfold

Exercises

S-Expressions

While you do not have to provide examples or a template for S-expressions, you may find them helpful.

Exercise 1 Design the function topsy-turvy, which inverts the order of an S-expression. An inverted S-expression should not only have the orders of its list reversed, but each individual element of the list should also be inverted. Note the symbols themselves should be left as-is.

Exercise 2 Design the function find-path, which given an S-expression and a symbol outputs the path to the leftmost occurence of that symbol in the S-expression. If that symbol is not present, the function should output #false. As an example, the path to 'wish in 'wish would be '(), and in '(though (i might (wish))) would be '(1 2 0).

Unfold

The list abstractions that we have seen thus far, like map, filter, and foldr, all abstract over some common pattern of recursion. At a high level, for instance, foldr combines elements of a list into some result.

We can define a similar higher-order function that abstracts over the pattern of somehow turning one value into a list of values by applying some function(s). This function is aptly named unfold and defined below:

(: unfold ((%a -> Boolean) (%a -> %b) (%a -> %a) %a -> (ListOf %b)))

(define (unfold pred? f g val)

(if (pred? val)

'()

(cons (f val) (unfold pred? f g (g val)))))

If the predicate is true, we return an empty list. Otherwise, we take result of calling f with val to give us a first element and add it onto a recursive call, where the value is updated by using g.

Exercise 3 make-list is a function built in to *SL that takes in a natural number n and a value, and produces a list containing that value n times.

Write your own version of make-list, called make-list-unfold that uses unfold and no other built-in list abstractions.

Exercise 4 unfold is a surprisingly powerful function! To demonstrate this, implement your own version of map, called map-unfold, using just unfold and no other built-in list abstractions. Hint: what is the signature of map? What is the signature of unfold?