Homework 09 Solutions

Solution Files

Q1: List Comprehensions

Recall that list comprehensions in Python allow us to create lists out of iterables:

[<map-expression> for <name> in <iterable> if <conditional-expression>]

Use a macro to implement list comprehensions in Scheme that can create lists out of lists. Specifically, we want a list-of macro that can be called as follows:

(list-of <map-expression> for <name> in <list> if <conditional-expression>)

Calling list-of will return a new list constructed by doing the following for each element in <list>:

  • Bind <name> to the element.
  • If <conditional-expression> evaluates to a truth-y value, evaluate <map-expression> and add it to the result list.

Here are some examples:

scm> (list-of (* x x) for x in '(3 4 5) if (odd? x))
(9 25)
scm> (list-of 'hi for x in '(1 2 3 4 5 6) if (= (modulo x 3) 0))
(hi hi)
scm> (list-of (car e) for e in '((10) 11 (12) 13 (14 15)) if (list? e))
(10 12 14)

Hint: You may use the built-in map and filter procedures. Check out the Scheme Built-ins reference for more information.

You may find it helpful to refer to the for loop macro introduced in lecture. The filter expression should be transformed using a lambda in a similar way to the map expression in the example.

(define-macro (list-of map-expr for var in lst if filter-expr)
`(map (lambda (,var) ,map-expr) (filter (lambda (,var) ,filter-expr) ,lst)) ) ; Optional filter: (define-macro (list-of map-expr for var in lst . args) (let ((filtered (if (= (length args) 2) `(filter (lambda (,var) ,(car (cdr args))) ,lst) lst))) `(map (lambda (,var) ,map-expr) ,filtered))
)

Use Ok to test your code:

python3 ok -q list-comp

Optional (not graded): Recall also that the if <conditional> portion of the Python list comprehension was optional. Modify your macro so that the Scheme list comprehension does not require a conditional expression.

Refer to the macro form in the Scheme Specification for an explanation of how to do optional macro parameters.

Even though for, in and if don't show up at all in the final Scheme expression returned by the macro, we still need them as macro parameters to ensure we can match the number of terms in the list comprehension form.

From there, the solution is very similar to the for loop example macro you saw in lecture. The one main difference is that we apply a filter onto the sequence before passing it into the map.