План:

  • Функции от по-висок ред


Задача 0: Разгледайте следните дефиниции. Какво е общото между тях? Как да избегнем повторението?

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))

(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

(define (sum-e a b)
  (if (> a b)
      0
      (+ (/ 1 (fact a)) (sum-e (+ a 1) b))))


Задача 1: Напишете функция от по-висок ред (sum term a next b), която улавя общото от трите дефиниции и параметризира специфичното.


Задача 2: Използвайки sum, имплементирайте следните функции:

  • (sum-of-cubes n) - сумата от кубовете на числата от 1 до n
  • (sum-of-integers n) - сумата на числата от 1 до n
  • (approx-e n) - n-тата частична сума на числовия ред \( \sum_{n=0}^ \infty \frac{1}{n!} \)


Задача 3: Чрез sum дефинирайте функция (integral f a b), която пресмята определения интеграл \( \int_{a}^{b}{f(x)dx} \), като използва Римановата сума \( \Delta \cdot \sum_{k=0}^{n}{f(a + \frac{(2k+1)\Delta}{2})} \), където \( \Delta \rightarrow 0, n = \frac{b-a}{\Delta} - 1 \).


Задача 4: Дефинирайте итеративен вариант на функцията sum.

(define (sum term a next b)
  (define (iter a result)
    (if <??> 
  	<??> 
  	(iter <??> <??>)))
  (iter <??> <??>))


Задача 5: Дефинирайте функция product, която е аналог на sum и прави точно това, което очаквате.


Задача 6: Покажете, как sum и product могат да бъдат изразени чрез по-общата функция (accumulate combiner null-value term a next b). Имплементирайте accumulate. С нейна помощ имплементирайте (fact n).


Задача 7: Функцията accumulate също може да се обобщи, т.че да натрупва само стойности, които отговарят на дадено условие. Дефинирайте функция (filtered-accumulate combiner null-value pred term a next b), която акумулира само тези стойности, които удовлетворяват предиката pred. Използвайте filtered-accumulate, за да имплементирате функциите:

  • (sum-of-prime-squares n), пресмятаща сумата от квадратите на простите числа, ненадвишаващи n
  • (double-fact n), пресмятаща n!!, където n!! е произведението на числата от 1 до n, които имат еднаква четност с n


Задача 8: Като използвате, че  \( f'(x_0) = lim_{ \Delta \rightarrow 0 } \frac{f(x_0 + \Delta) - f(x_0)}{\Delta} \), дефинирайте функцията (derivative f), която приема функция на една променлива f и връща друга функция - нейната производна f'.

(define (cube x) (* x x x))
(define f (derivative cube)) ; f should compute 3*x^2

(f 1) ; => 3.000000248221113
(f 2) ; => 12.000000992884452
(f 3) ; => 27.000002233990017


Задача 9: Напишете функция (constantly c), която връща константната функция \( f(x) = c \).

(define forever-21 (constantly 21))
(forever-21 21) ; => 21
(forever-21 29) ; => 21
(forever-21 52) ; => 21


Задача 10: Напишете функция (flip f), която разменя аргументите на двуместна функция f.

(define cons^ (flip cons))
(cons^ 2 3) ; => (3 . 2)


Задача 11: Напишете функция (curry-3 f), която връща curried вариант на триместна функция f.

(define +' (curry-3 +))
(((+' 1) 2) 3) ; => 6


Задача 12: Напишете функция (compose f g), която връща функцията \( f \circ g \).

(define f (compose inc square)) ; x^2 + 1
(f 4) ; => 17
(f 7) ; => 50


Задача 13: Напишете функция (complement p), която приема предикат и връща неговото отрицание.

(define (less-than-5? x) (< x 5))
(define f (complement less-than-5?))
(f 3) ; => #f
(f 5) ; => #t
(f 7) ; => #t


Задача 14: Напишете функция (iterate n f), която повдига функцията f на n-та степен. Пример: \( f^0(x) = x \); \( f^3(x) = f(f(f(x))) \); Чрез нея дефинирайте (nth-derivative n f), пресмятаща n-тата производна на f.

(define plus-10 (iterate 10 inc))
(plus-10 1) ; => 11
(plus-10 25) ; => 35

(define pow-8 (iterate 3 square))
(pow-8 1) ; => 1
(pow-8 2) ; => 256


Задача 15: Имплементирайте cons, car и cdr като функции от по-висок ред.

(define (cons' a b)
  (lambda (z)
    (z a b)))
(define (car' pair)
  <??>)
(define (cdr' pair)
  <??>)

(define p (cons' 2 3))
(car' p) ; => 2
(cdr' p) ; => 3


Последно модифициране: понеделник, 24 октомври 2016, 17:45