square, and double are given.
(define (comb f g)
(lambda (x) (f (g x))))
(define (square n) (* n n))
(define (double n) (+ n n))
Please show how the expression ((comb square double) 5) is evaluated.
Please define a function (root f a b) approximating a root of f
between a and b using the half-interval-method.
Please define a function (iter f n), whose value is the function fn.
Please define the following functions for lists.
a) (append l m), whose value is the concatenation of the lists l i m.
b) (last l), whose value is the last element of the list l.
c) (reverse l), whose value is the list l in reversed order.
d) (delete x l), whose value is the list l without the element x.
e) (pairing l1 l2), that builds a list of pairs out of the lists l1 and l2. Example:
> (pairing '(1 2 3) '(a b c))
'((1.a) (2.b) (3.c))
f) (split x l), that splits l into two lists l1 and l2.
l1 contains the element of l smaller than
x and l2 the elements greater than x.
a) Please define a function (square-list l), whose value is the list of squares of all elements of l.
b) Please define a function (mapf f l), whose value is the list of values f(e) for all elements e of l.
c) Please define a function (filter pred l), whose value is the list of all elements of l
fulfilling pedicate pred.
Using lists to represent binary trees (see lecture notes) please define functions
(memberTree? element tree), (sumTree tree), (inorder tree) and (mapTree f tree).
Proszę zdefiniować arytmetykę liczb wymiernich na podstawie liczb całkowitych.
a) Please complete the definition of function diff as presented in the lecture.
b) Please modify functions make-sum and make-product so that function diff
returns normalized terms - this means for example y instead of (* y 1).
c) Please extend the definition of function diff, so that it can handle terms u^n
for natural number n - using the rule
d(u^n) / dx = n * u^(n-1) * du / dx .
Please define a function (eval expression values) which evaluates boolean expressions.
expression is a list whose first element gives the "type" of the boolean expression,
the remaining elements are the subexpressions -
for example '(and x (not y)) represents the expression x∧¬y.
values is a list of variables together with their corresponding boolean value.
Examples: > (define values '((x . #f) (y . #t) (z . #f)))
values
> (eval '(and y (not x)) values)
#t
> (eval '(and y (and (not x) z))) values)
#f
> (eval '(and y #t) values)
#t
Using function fold please define the following functions for lists.
a) (prod l)
b) (length l)
c) (delete x l)
d) (reverse l)
e) (map f l)
f) (filter pred l)
g) (forall pred l).
Please complete the arithmetics of complex numbers as presented in the lecture
a) using manifest types.
b) using message passing.
c) Suppose the following definitions are given.
(define z1 (make-rectangular -1 3))
(define z2 (make-polar 2 -2))
Please explain how the expression (angle (+c z1 z2)) is evaluated.
In Scheme one can define functions with an arbitrary number of arguments:
(define (f x y z . l) (...))
means, that function f has at least three arguments (x,y and z).
If f is called with more than three arguments the remaining ones are collected in list l .
a) Please define a function plus, which sums up any number of numbers.
b) Please define a function par for an arbitrary number of (one-argumented) functions fi.
Function par returns a (one-argumented) function,
which for an argument x returns a list of all fi(x).
Example:
> ((par id square cube) 3)
(3 9 27)
> ((par double double) 5)
(10 10)
Please - again - define a function (fibonacci n) whose value is the n-th element of the
Fibonacci sequence - this time by computing the n-th power of the matrix
Suppose the following definitions are given.
(define m 1) (define n 1)
(define (p m) (define (q n)
(pp 5)) (define (qq x)
(define (pp x) (+ x n))
(+ x m)) (qq 5))
What are the values of the expressions (p 11) and (q 11)?
Justify Your answers using the environment model.
Suppose the following definitions are given.
(define a 2)
(define (p a)
(define (pp b)
(set! a (+ b 1))
(* a b))
(pp 2))
What is the value of the expression (p 5)? What is the value of a after evaluating (p 5)?
Justify Your answers using the environment model.
a) Please define a function (make-konto balance) generating an account
with balance dollars.
The following operations should be possible:
withdraw money, deposit money and checking balance.
b) Suppose now the following definition.
(define k1 (make-konto 100))
Using the environment model please show, how the following expressions are evaluated.
> ((k1 'withdraw) 40)
> (k1 'balance)
> ((k1 'deposit) 10)
> (k1 'balance)
c) Please modify function make-konto, so that an account with a password is generated -
that is operations are only carried out, if the correct password is given.
Example:
(define k2 (make-konto 100 'password))
k2
> ((k2 'passowrd 'withdraw) 40)
60
> ((k2 'wrong-password 'withdraw) 20)
incorrect password
Having introduced destructive functions the order in which arguements are evaluated
can have impact on a function's result:
Please define a (simple :-) function f, so that
(+ (f 0) (f 1)) evaluates to 0, if the arguments are evaluated from left to right, but
(+ (f 0) (f 1)) evaluates to 1, if the arguments are evaluated from right to left.
Please define a function (counting-version f), where f is a one-argument function.
Its value is a one-argument function, which both computes f and counts how often f
has been called.
Example:
> (define sq (counting-version square))
sq
> (sq 5)
25
> (sq 7)
49
> (sq 'how-often)
2
> (sq 'reset)
0
> (sq 'how-often)
0
Assume that the following expessions have been evaluated.
(define x (mcons 'a (mcons 'b '())))
(define z1 (mcons x x))
(define z2 (mcons (mcons 'a (mcons 'b '()))
(mcons (mcons 'a (mcons 'b '())) '())))
(set-mcar! (mcar z1) 'g)
(set-mcar! (mcar z2) 'g)
What are the values of z1 and z2?
a) Please define a destructive version append! of append.
b) Suppose the following definitions are given.
(define letters '(a b))
(define numbers '(1 2))
What is the value of (append letters numbers), and what are the values of letters and
numbers after evaluating (append letters numbers)?
What is the value of (append! letters numbers), and what are the values of letters and
numbers after evaluating (append! letters )?
c) Please draw the box diagram for letters and letters-letters after evaluation of
(define letters '(a b c))
(define letters-letters (append! letters letters))
What happens if now (append! letters-letters '()) is evaluated?
Please implement stacks analogous to queues.