Lab 10 - Scheme

A lab aimed at getting accustomed with thinking and writing Scheme, the first exercises are mostly easy, all you have to do is translate what you already know how to do in Python into Scheme.

I enjoyed writing Scheme so much, I also did the Extras. I found the later ones (Q8, Q9) to be a nice challenge. 👍

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/lab/lab10/

Solution: https://github.com/tomthestrom/cs61a/blob/master/lab/lab10/lab10.scm

Solution - extras: https://github.com/tomthestrom/cs61a/blob/master/lab/lab10/lab10_extra.scm

Q1 is non-coding - What Would Scheme Do?

Q2: Over or Under

Define a procedure over-or-under which takes in a number x and a number y and returns the following:

• -1 if x is less than y

• 0 if x is equal to y

• 1 if x is greater than y

(define (over-or-under x y)
  'YOUR-CODE-HERE
)

;;; Tests
(over-or-under 1 2)
; expect -1
(over-or-under 2 1)
; expect 1
(over-or-under 1 1)
; expect 0

Q2: Solution

(define (over-or-under x y)
  (cond
    ((> x y) 1)
    ((< x y) -1)
    (else 0)
    )
)

Q3: Filter Lst

Write a procedure filter-lst, which takes a predicate f and a list lst, and returns a new list containing only elements of the list that satisfy the predicate. The output should contain the elements in the same order that they appeared in the original list.

(define (filter-lst f lst)
  'YOUR-CODE-HERE
)

;;; Tests
(define (even? x)
  (= (modulo x 2) 0))
(filter-lst even? '(0 1 1 2 3 5 8))
; expect (0 2 8)

Q3: Solution

(define (filter-lst f lst)
  (cond
    ((null? lst) nil)
    ((f (car lst)) (cons (car lst) (filter-lst f (cdr lst))))
    (else (filter-lst f (cdr lst)))
    )
)

Q4: Make Adder

Write the procedure make-adder which takes in an initial number, num, and then returns a procedure. This returned procedure takes in a number x and returns the result of x + num.

(define (make-adder num)
  'YOUR-CODE-HERE
)

;;; Tests
(define adder (make-adder 5))
(adder 8)
; expect 13

Q4: Solution

(define (make-adder num)
  (lambda (x) (+ x num))
)

Extras:

Q5: Make a List

Create the list with the following box-and-pointer diagram:

Source: CS61 SU19 - Week 6 - Lab 10

Q5: Solution

(define lst
 '((1) 2 (3 4) 5)
)

Q6: Compose

Write the procedure composed, which takes in procedures f and g and outputs a new procedure. This new procedure takes in a number x and outputs the result of calling f on g of x.

(define (composed f g)
  'YOUR-CODE-HERE
)

Q6: Solution

(define (composed f g)
  (lambda (x) (f(g x)))
)

Q7: Remove

Implement a procedure remove that takes in a list and returns a new list with all instances of item removed from lst. You may assume the list will only consist of numbers and will not have nested lists.

Hint: You might find the filter-lst procedure useful.

(define (remove item lst)
  'YOUR-CODE-HERE
)

Q7: Solution

(define (remove item lst)
  (filter-lst (lambda (x) (not (= item x))) lst)
)

Q8: No Repeats

Implement no-repeats, which takes a list of numbers s as input and returns a list that has all of the unique elements of s in the order that they first appear, but no repeats. For example, (no-repeats (list 5 4 5 4 2 2)) evaluates to (5 4 2).

(define (no-repeats s)
  'YOUR-CODE-HERE
)

Q8: Solution

(define (is-in-lst item lst)
  (cond
    ((null? lst) #f)
    ((= item (car lst)) #t)
    (else (is-in-lst item (cdr lst)))
    )
  )

(define (no-repeats s)
    (
        cond 
                 ((null? s) nil)
                 ((is-in-lst (car s) (cdr s)) (cons (car s) (no-repeats (remove (car s) (cdr s)))))
                 (else (cons (car s) (no-repeats (cdr s))))
                 
    )    
)

Q9: Substitute

Write a procedure substitute that takes three arguments: a list s, an old word, and a new word. It returns a list with the elements of s, but with every occurrence of old replaced by new, even within sub-lists.

(define (substitute s old new)
  'YOUR-CODE-HERE
)

Q9: Solution

(define (substitute s old new)
  (
    cond 
        ((null? s) nil)
        ((pair? (car s))(cons (substitute (car s) old new) (substitute (cdr s) old new)))
        ((eq? old (car s))(cons new (substitute (cdr s) old new)))
        (else (cons (car s) (substitute (cdr s) old new)))
   )
)