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 SExpr. An inverted SExpr 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 SExpr and a symbol outputs the path to the leftmost occurence of that symbol in the SExpr. 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), because it’s the 0th element of (the 2th element of (the 1th element of the s-expression)).

For writing down the return type of this function, you might find the following data definition helpful:

; A [Maybe X] is one of

; - X

; - #false

; INTERPRETATION: represents only *possibly* having a value of a particular type

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 B} [A -> Boolean] [A -> B] [A -> A] A -> [List-of 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?