The language for this homework is:

#lang plait |

- In addition to lists, this assignment uses
*vectors*, and*sets*. The following functions may be useful:`set-add`

,`set-member?`

,`set-union`

,`vector-ref`

, where the set data structure are those we developed in Tutorial 7. - One of the points of this assignment is to solve a not completely trivial problem without using mutation. A natural technique is to pass an extra parameter and provide an updated version of a value to recursive calls (i.e. like we do for tail recursion).
- Probably the easiest way to traverse the heap is [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
- In order to track which objects have been discovered you probably need to define one or more
*helper functions*with an extra parameter of a set/list/vector of known objects.

- Use the following type declarations to define an abstract
representation of a heap. Each heap location either has a list of
indices
(locations of referenced objects) or is a primitive value.
(define-type Object [object (refs : (Listof Number))] [primitive]) (define-type-alias Heap (Vectorof Object)) (define-type-alias LocSet (Setof Number))

- Write a function
`search-one-root`

that searches the heap for a single root. Your function should have the following type.(has-type search-one-root : (Number Heap -> LocSet))

- Here is some test data and tests for
`search-one-root`

(define heap1 (vector (object (list 1 2)) (primitive) (object (list 2)))) (define heap2 (vector (object (list 0 1)) (object (list 2)) (object (list 0)))) (test (search-one-root 0 heap1) (set 0 1 2)) (test (search-one-root 1 heap1) (set 1)) (test (search-one-root 0 heap2) (set 0 1 2)) (test (search-one-root 1 heap2) (set 0 1 2))

- Write a function
`find-live`

with the following type signature

The purpose of(has-type find-live : ((Listof Number) Heap -> LocSet))

`find-live`

is to find the locations of all objects reachable from a given set of roots. Here are some tests for`find-live`

(test (find-live '(1) heap1) (set 1)) (test (find-live '(0) heap1) (set 0 1 2)) (test (find-live '(1 2) heap2) (set 0 1 2))

- As always, make sure you have enough tests for your code. The automated
coverage testing is a
*minimal*requirement. - Finally, define minutes-spent as usual.