Lab 3: Higher-order functions

Exercise 1

Implement a function (mult-all-pairs lst1 lst2) taking two lists and returning a list of all possible binary products between elements from lst1 and elements from lst2. Mathematically, it could be written by a comprehension term as

$$\{x\cdot y|x\in {\mathrm{lst}}_1,y\in {\mathrm{lst}}_2\}$$

(mult-all-pairs '(1 2 3) '(-2 0))  ; => (-2 0 -4 0 -6 0)`

Once you have it, generalize your function to (f-all-pairs f lst1 lst2) so that the multiplication is replaced by any binary function f:

(f-all-pairs cons '(1 2 3) '(a b))  ; => ((1 . a) (1 . b) (2 . a) (2 .  b) (3 . a) (3 . b))

Hint

These functions are just applications of two nested map functions. For each element x in lst1, we multiply by x all elements in lst2. A function multiplying by x can be created from the multiplication function * by partial application of x, i.e., we take the curryfied version of * and apply it to x yielding ((curry *) x). Once we map ((curry *) x) along lst2, the result is a list. So doing it for each x in lst1 results in a list of lists. Thus we have to flatten the result and append all the lists. This can be done by apply-ing append.

Solution

(define (mult-all-pairs lst1 lst2)
  (apply   ; flatten the result
   append
   (map
    (lambda (x) (map ((curry *) x) lst2)) ; multiply all elements of lst2 by x
    lst1)))                               ; do it for each element x in lst1

(define (f-all-pairs f lst1 lst2)
  (apply
   append
   (map
    (lambda (x) (map ((curry f) x) lst2))
    lst1)))

Exercise 2

Suppose we represent univariate polynomials as lists of monomials. Each monomial of the form $a{x}^n$ is represented as a list (a n) consisting of the coefficient a and the exponent n. Thus the polynomial $2-3x+x^2$ is represented by ((2 0) (-3 1) (1 2)). We assume that each exponent can occur in the polynomial representation at most once. E.g. ((1 0) (2 0)) is not a valid representation. Devise functions (poly+ p1 p2) and (poly* p1 p2) taking as arguments two polynomials p1,p2 and returning their sum and product, respectively. For example, let p1 be ((1 0) (1 1)) (i.e., $p_1(x)=1+x$) and p2 ((-1 0) (1 1) (3 2)) (i.e., $p_2(x)=-1+x+3x^2$). Then

Suppose we represent univariate polynomials as lists of monomials. Each monomial of the form $a{x}^n$ is represented as a list (a n) consisting of the coefficient a and the exponent n. Thus the polynomial $2-3x+x^2$$p_1(x)=1+x$) and p2 ((-1 0) (1 1) (3 2)) (i.e., $p_2(x)=-1+x+3x^2$). Then

Even though it might look tedious, it is not so terrible because we will call higher-order functions to rescue us. Thanks to the folding function foldl, we will reduce our problem just to monomials. Let's start by defining simple operations on monomials. To make our code more comprehensible, we define the following functions extracting the coefficient and the exponent from a monomial.

(define (mono-coeff m) (car m)) ; first component
(define (mono-exp m) (cadr m)) ; second component

Next it is easy to define addition of two monomials of the same exponents, namely

$$a{x}^n+b{x}^n=(a+b)x^n.$$$$a{x}^n+b{x}^n=(a+b)x^n.$$

Similarly, multiplication of monomials is defined by

$$(a{x}^n)(b{x}^k)=ab{x}^{n+k}.$$

Now we come to the main trick. Suppose we have two polynomials $p_1(x)=a_0+a_{1}x$ and $p_2(x)=b_0+b_{1}x+b_2{x}^2$. We can express their sum as:

Now we come to the main trick. Suppose we have two polynomials $p_1(x)=a_0+a_{1}x$ and $p_2(x)=b_0+b_{1}x+b_2{x}^2$. We can express their sum as:

$$p_1(x)+p_2(x)=((p_1(x)+b_0)+b_{1}x)+b_2{x}^2$$

Thus we need to add only a polynomial and a monomial in each step. The repetitive sum can then be done by the foldl function. Similarly, multiplication can be implemented by first computing the products of all monomials using the function f-all-pairs from Exercise 1, and then express the results as

$$p_1(x)\cdot p_2(x)=(((a_0{b}_0+a_0{b}_{1}x)+a_0{b}_2{x}^2)+a_1{b}_{0}x)+\cdots$$

Addition of polynomial and monomial

(define (mono-poly+ mon pol)
  (define (same-exp? m) (= (mono-exp mon) (mono-exp m))) ; #t if m has the same exponent as mon
  (define same-mon (filter same-exp? pol))             ; list containing the monomial of the same exponent or empty list
  (define rest (filter (compose not same-exp?) pol))   ; remaining monomials of different exponents
  (if (null? same-mon)
      (cons mon rest)
      (cons (mono+ mon (car same-mon)) rest)))

Finally, we can apply the folding function foldl to sum all monomials as was shown above. However, there are still two problems we have to deal with. 1) It may happen that the result contains monomials of the form $0x^n$. Such monomials can be clearly filtered out of the result. 2) It is common to sort monomials according to their exponents. Thus we define a function poly-normalize solving these two problems.

Finally, we can apply the folding function foldl to sum all monomials as was shown above. However, there are still two problems we have to deal with. 1) It may happen that the result contains monomials of the form $0x^n$. Such monomials can be clearly filtered out of the result. 2) It is common to sort monomials according to their exponents. Thus we define a function poly-normalize solving these two problems.

Task 1

Write a function linear-combination taking a list of vectors, a list of coefficients and returning the corresponding linear combination. For example, consider a linear combination $2\cdot (1,2,3)-1\cdot (1,0,1)+3\cdot (0,2,0)=(1,10,5)$. Then your implementation should work as follow:

Write a function linear-combination taking a list of vectors, a list of coefficients and returning the corresponding linear combination. For example, consider a linear combination $2\cdot (1,2,3)-1\cdot (1,0,1)+3\cdot (0,2,0)=(1,10,5)$. Then your implementation should work as follow:

Hint

Create first a binary function computing scalar multiplication of a scalar and a vector using map. Then use the fact that map can apply the scalar multiplication to two lists simultaneously (in our case, the list of coefficients and the list of vectors). This results in a list of vectors multiplied by respective coefficients. Then it suffices to sum them component by component.

Solution

(define (vec-scale vec coef)
  (map (curry * coef) vec))

(define (linear-combination vectors coefs)
  (apply map + (map vec-scale vectors coefs)))

Solution

(define (vec-scale vec coef)
  (map (curry * coef) vec))

(define (linear-combination vectors coefs)
  (apply map + (map vec-scale vectors coefs)))

Task 2

$k\ge 1$, so there is no need to define the identity matrix. E.g.

Hint

Use that the matrix multiplication is just a repeated application of the linear-combination function. More precisely, consider $m_1\cdot m_2$. The $i$-th row of the result is just the linear combination of the rows of $m_2$ with the coefficients taken from the $i$-th row of $m_1$. So it suffices to apply the (linear-combination m_2) to each row of $m_1$.

Hint

Use that the matrix multiplication is just a repeated application of the linear-combination function. More precisely, consider $m_1\cdot m_2$. The $i$-th row of the result is just the linear combination of the rows of $m_2$ with the coefficients taken from the $i$-th row of $m_1$. So it suffices to apply the (linear-combination m_2) to each row of $m_1$.

(make-list 5 #\a)  ; => '(#\a #\a #\a #\a #\a)

Solution

(define (matrix* m1 m2)
  (map (curry linear-combination m2) m1))

(define (matrix-expt k mat)
  (foldl matrix* mat (make-list (- k 1) mat)))

Solution

(define (matrix* m1 m2)
  (map (curry linear-combination m2) m1))

(define (matrix-expt k mat)
  (foldl matrix* mat (make-list (- k 1) mat)))