HW6 - Scheme, Tail Recursion, Macros

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/hw/hw06/

Solution: https://github.com/tomthestrom/cs61a/blob/master/homeworks/hw06/hw06.scm

Scheme

Q1: Thane of Cadr

Define the procedures cadr and caddr, which return the second and third elements of a list, respectively:

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)
  'YOUR-CODE-HERE
)

(define (caddr s)
  'YOUR-CODE-HERE
)

Q1: Solution

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)
  (car (cdr s))
)

(define (caddr s)
  (car (cddr s))
)

Q2: Unique

Implement unique, which takes in a list s and returns a new list containing the same elements as s with duplicates removed.

scm> (unique '(1 2 1 3 2 3 1))
(1 2 3)
scm> (unique '(a b c a a b b c))
(a b c)

(define (unique s)
  'YOUR-CODE-HERE
)

Q2: Solution

(define (remove-item s item)
    (filter (
            lambda (x) (not(eq? x item))
            )
    s
    )
)

(define (unique s)
    (if (null? s)
    nil
    (cons (car s) (unique(remove-item s (car s))))
    )
)

Q3: Cons All

Implement cons-all, which takes in an element first and a list of lists rests, and adds first to the beginning of each list in rests:

scm> (cons-all 1 '((2 3) (2 4) (3 5)))
((1 2 3) (1 2 4) (1 3 5))

(define (cons-all first rests)
  'replace-this-line)

Q3: Solution

(define (cons-all first rests)
  (map (lambda (rest) (cons first rest)) rests)
  )

Q4: List Change

Implement the list-change procedure, which lists all of the ways to make change for a positive integer total amount of money, using a list of currency denominations, which is sorted in descending order. The resulting list of ways of making change should also be returned in descending order.

To make change for 10 with the denominations (25, 10, 5, 1), we get the possibilities:

10
5, 5
5, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1

To make change for 5 with the denominations (4, 3, 2, 1), we get the possibilities:

4, 1
3, 2
3, 1, 1
2, 2, 1
2, 1, 1, 1
1, 1, 1, 1, 1

Therefore, your function should behave as follows for these two inputs

scm> (list-change 10 '(25 10 5 1))
((10) (5 5) (5 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1))
scm> (list-change 5 '(4 3 2 1))
((4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1))

;; List all ways to make change for TOTAL with DENOMS
(define (list-change total denoms)
  'YOUR-CODE-HERE
  )

Q4: Solution

(define (list-change total denoms)
    (cond
        ((> 0 total) nil)
        ((null? denoms) nil)
        ((= 0 total) (list ()))
        (else (append(cons-all (car denoms) (list-change (- total (car denoms)) denoms)) (list-change total (cdr denoms))))
        ) 
) 

Tail Recursion

Q5: Replicate

Below is an implementation of the replicate function, which was seen in Discussion 08. replicate takes in an element x and an integer n, and returns a list with x repeated n times.

(define (replicate x n)
	(if (= n 0) 
		nil
		(cons x (replicate x (- n 1)))))

Update this implementation of replicate to be tail recursive. It should have identical functionality to the non-tail recursive version.

(define (replicate x n)
  'YOUR-CODE-HERE
  )

Q5: Solution

(define (replicate x n)
    (define (replicate-tail x curr-len accumulator)
        (if (= n curr-len)
            accumulator
            (replicate-tail x (+ curr-len 1) (append accumulator (list x)))
            )
        )
    (replicate-tail x 0 (list))
    )

Q6: Accumulate

Fill in the definition for the procedure accumulate, which combines the first n natural numbers according to the following parameters:

1. combiner: a function of two arguments

2. start: a number with which to start combining

3. n: the number of natural numbers to combine

4. term: a function of one argument that computes the nth term of a sequence

For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the combiner, and starting our product at 1:

scm> (define (identity x) x)
scm> (accumulate * 1 5 identity)  ; 1 * 1 * 2 * 3 * 4 * 5
120

We can also find the sum of the squares of the same numbers by using the addition operator as the combiner and square as the term:

scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square)  ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
55
scm> (accumulate + 5 5 square)  ; 5 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
60

(define (accumulate combiner start n term)
  'YOUR-CODE-HERE
)

Q6: Solution

(define (accumulate combiner start n term)
    (if (= n 1)
        (combiner start (term 1))
        (combiner start (accumulate combiner (term n) (- n 1) term))
    )
)

Q7: Tail Recursive Accumulate

Update your implementation of accumulate to be tail recursive. It should still pass all the tests for "regular" accumulate!

You may assume that the input combiner and term procedures are properly tail recursive.

Q7: Solution

(define (accumulate-tail combiner start n term)
      (define (accumulate x accumulated)
        ( if (= x 1)
          (combiner accumulated (term x))
          (accumulate (- x 1) (combiner accumulated (term x)))
        ))
    (accumulate (- n 1) (combiner start (term n)))
)

Macros

Q8: 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.

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)

(define-macro (list-of map-expr for var in lst if filter-expr)
  'YOUR-CODE-HERE
)

Q8: Solution

(define-macro (list-of map-expr for var in lst if filter-expr)
  `(map (lambda (,var) ,map-expr) (filter (lambda (,var) ,filter-expr) ,lst))
)