Logs of the labs will be available after the last lecture of the week.

# Labs

## Lab 1: Introduction to Scheme

The goal of this lab is to make the students familiar with the IDE we will use for scheme and help them write first simple programs.

#### Dr. Raket IDE

The IDE can be downloaded for free for Linux, Winows, MAC from: https://racket-lang.org/ The students can use the one installed in the lab computers. The teacher may help the students (to a reasonable degree) to get the IDE running on students’ laptops. Explain the language (scheme variant) selection options. 1. Choose in the environment 2. #lang {scheme|r5rs|…}

#### Motivation

Students should understand that learning functional programming is important for improving their programming skills. It helps them master recursion and functional patterns are increasingly common in mainstream programming languages.

#### Scheme basics

Start interaction in REPL. Scheme uses prefix notation for all functions. Let students compute simple formulas, e.g., 2+3/5. For the following exercises, I suggest first explaining the task. Than leaving the students to work on it individually for a few minutes. Discuss their ideas and approach to the problem. Afterwards, a randomly selected student will explain the solution to everyone on the whiteboard with help from the teacher and the other students.

Exercise 1: Use scheme REPL to compute a discriminant of the following quadratic function.

(- (* -3 -3) (* 4 4 5))
=> -71

Exercise 2: Write a function D for computing the discriminant of a quadratic form based of coefficients a, b, c.

(define (D a b c)
(- (* b b) (* 4 a c)))

Exercise 3: Write a function roots that will use the previously defined computation of the discriminant to return the roots of the quadratic function.

(define (roots a b c)
(list
(/ (+ (- b) (sqrt (D a b c))) (* 2 a))
(/ (- (- b) (sqrt (D a b c))) (* 2 a))
)
)

Exercise 4: Write a recursive function my-even that decides whether a number is even using only functions +, -, = (without indirect recursion).

(define (my-even? n)
(cond ((= n 0) #t)
((= n 1) #f)
((> n 0) (my-even? (- n 2)))
(#t (my-even? (+ n 2)))
)
)

Students will likely first forget about the negative numbers. Let them find out what happens with negative input. Relate to best practice rules to avoid infinite recursion. This is an example of analytic recursion.

Exercise 5: Write a function that returns the n-th Fibonacci number.

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))
)
)

Let them try to run (fib 100). Discuss that this function is correct, but very inefficient. Why does it take so much memory? Explain that the stop button and rerun will allow them to continue, if you did not get to that already. This is an example of tree recursion.

Exercise 6: Write a function that returns the n-th Fibonacci number effectively.

Lead the students to realize that if they need an extra “variable”, they can add an argument.
(define (fib-hlp last2 last n)
(if (= 0 n)
(+ last2 last)
(fib-hlp last (+ last2 last) (- n 1))))
(define (fib2 n)
(fib-hlp -1 1 n))
This exercise can be skipped until the next lab if things are going slowly.

Exercise 7: Write a function that returns a list of the first n fibonacci numbers.

(define (fibs n)
(cond ((= 0 n) '())
(#t (cons (fib2 n) (fibs (- n 1))))))

Exercise 8: Using the my-even? Predicate defined previously, write a function that will for a list of numbers return a list of only even numbers in the list.

(define (take-even l)
(cond ((null? l) l)
((my-even? (car l)) (cons (car l) (take-even (cdr l))))
(else (take-even (cdr l)))
)
)

## Lab 2: Recursive functions

The goal of this lab is to practice writing recursive functions in scheme and using the accumulator to make the functions more efficient. Furthermore, the students should practice using let and lambda abstraction.

We explained the first homework assignment.

Exercise 1: Write a recursive function that would reverse a list. For example (1 2 3 4) → (4 3 2 1).

(define (my-reverse l)
(cond ((null? l) l)
(#t (append (my-reverse (cdr l)) (list (car l))))
)
)

Understand why this function is inefficient (has quadratic complexity).

Exercise 2: Write the function from Exercise 1 in a linear time complexity.

(define (my-reverse2 l)
(define (rev-acc l acc)
(cond ((null? l) acc)
(#t (rev-acc (cdr l) (cons (car l) acc)))
)
)
(rev-acc l '())
)
Note that using the accumulator is a general concept.

Exercise 3: Write a function my-flatten that will take any structure of nested lists and return a list of elements in these lists. For example (a b (c d (e) f ()) g) → (a b c d e f g).

(define (my-flatten l)
(cond ((null? l) l)
((list? (car l)) (append ( my-flatten (car l)) (my-flatten (cdr l))))
(#t (cons (car l) (my-flatten (cdr l))))
)
)
This is an example of tree recursion.

Exercise 4: Write a more efficient version of the function from Exercise 3 using accumulator.

(define (my-flatten2 l)
(define (flatten-acc l acc)
(cond ((null? l) acc)
((list? (car l)) (flatten-acc (car l) (flatten-acc (cdr l) acc)))
(#t (cons (car l) (flatten-acc (cdr l) acc)))
)
)
(flatten-acc l '())
)

Exercise 5: Let 2D vectors be defined as list of coordinates (1,2), (4,1). Write a function to compute the Euclidean distance between two vectors. Make sure no computation is performed twice.

(define (dist p1 p2)
(let ((dx (- (car p1) (car p2)))
)
(sqrt (+ (* dx dx) (* dy dy)))
)
)
Remember the function filter explained in the lecture.

Exercise 6: Write a function that removes all duplicate (or more) elements in a list. For example (1 2 3 2 5 1 3 4 2 5 2 1 3) → (1 2 3 5 4). You may use the function filter.

(define (remove-dup l)
(if (null? l) l
(cons (car l)
(remove-dup (filter (lambda (x) (not (equal? (car l) x)))
(cdr l)))
)
)
)

Exercise 7: Write a function that applies a given function to i-the element of a list. For example (apply-at sqrt ‘(4 4 4 4 4) 3) → (4 4 2 4 4).

(define (apply-at fn list pos)
(cond ((= pos 0) (cons (fn (car list)) (cdr list)))
(#t (cons (car list) (apply-at fn (cdr list) (- pos 1))
)
)

Exercise 8: Use apply-at to increment 2nd position in a list of numbers in REPL.

(apply-at (lambda (x) (+ x 1)) '(1 2 3 4) 2)

Exercise 9: Use apply-at to write a function substitute that substitutes the i-th element of a list with a new value. For example (subst ‘a ‘(1 2 3 4) 2) → (1 a 3 4)

(define (subst new list pos)
(apply-at (lambda (x) new) list pos)
)

Exercise 9: (If there is still time) Use function apply-at to write a function apply-at-xy, which will apply the function at position (x,y) in a list of lists. (apply-at-xy sqrt ‘((4 4 4) (4 4 4) (4 4 4)) 2 2) → ((4 4 4) (4 2 4) (4 4 4))

(define (apply-xy fn x y list-of-lists)
(apply-at (lambda (line)
(apply-at fn line x)
) list-of-lists y)
)

## Lab 3: Higher order functions

The goal of this lab is to understand and practice the built-in higher order functions in scheme.

Try out the following simple commands in REPL.

(map sqrt '(1 4 9 16 25))
(map car '((A B) (C) (D E)))
(map max '(3 9 17) '(2 4 11) '(7 3 2))

Exercise 1: Write a function that returns n-th line of the Pascal triangle as a list.

(define (pascal n)
(cond ((= n 1) '(1))
(#t (let ((prev (pascal (- n 1))))
(map + (cons 0 prev) (append prev '(0)))
)
)
)
)

Exercise 2: Use foldr/foldl to implement a function that multiplies all elements in a list.

(define (mult list)
(foldr * 1 list)
)

Exercise 3: Use foldl/foldr to write a function that reverses a list.

(define (reverse4 l)
(foldl cons '() l)
)

Exercise 4: Use foldl/foldr to write a function that returns the minimum of a list.

(define (min list)
(fold (lambda (x y) (if (< x y) x y)) (car list) (cdr list))
)

Exercise 5: Use map/fold to compute a dot product of two vectors represented as lists.

(define (dot-product v w)
(fold + 0 (map * v w))
)

Exercise 6: Use map/fold to compute a product of a matrix and a vectors represented as lists.

(define (mxv m v)
(map (lambda (row) (dot-product row v)) m))

Exercise 7: Use higher order functions to compute transpose of a matrix.

(define (transpose mat)
(apply map (cons list mat)))

Exercise 8: Use higher order functions to implement multiplication of two matrices.

(define (mxm m n)
(let ((cols (transpose n)))
(map (lambda (row) (mxv cols row))
m)))

## Lab 4: Subsets and permutations

The goal of this lab is to practice more complex functions that combine recursion and higher order functions.

We explained the second home assignment.

Exercise 1: Using recursion and higher order functions, write a function that returns a list of all subsets of a given list.

Idea of the algorithm: Take all subsets of a list without first element and return a union of the subsets and the subsets with the removed element added.

(define (power-set s)
(if (null? s) '(())
(let ((rest-ps (power-set (cdr s))))
(append rest-ps (map (lambda (x) (cons (car s) x)) rest-ps)))))

Exercise 2: Using recursion and higher order functions, write a function that returns a list of all permutations of a given list.

Idea of the solution: Take all permutations without one element and put the element to the first position in the result. Do it for all elements in the list and combine the result.

(define (perm-set l)
(if (null? l) '(())
(apply append (map (lambda (x)
(map (lambda (y) (cons x y)) (perm-set (remove x l)))
) l))
))