06

Упражнение 6

Процедури с произволен брой аргументи

1. Дефинирайте процедура (compose . fns), която връща композицията на подадените едноаргументни процедури fns.

   (define (double x) (* 2 x))
   (define (square x) (* x x))
   (define (inc x) (+ x 1))
   
   (define f (compose double square inc)) ; 2 * (x + 1)^2
   (f 3) ; -> 32
   (f 4) ; -> 50

2. Дефинирайте процедура (flip fn), която обръща реда на аргументите на процедурата fn независимо от броя им.

   (define list^ (flip list))
   (list^ 1 2 3) ; -> (3 2 1)

3. Дефинирайте процедура (zip x y), която връща списък от наредени двойки ((x₁ y₁) (x₂ y₂) ... (x_n y_n)), където x_i и y_i са съответно i-тият елемент на списъка x и i-тият елемент на списъка y, а n е дължината на по-късия списък от x и y.

   (zip '(1 3 5) '(2 4 6)) ; -> ((1 2) (3 4) (5 6))
   (zip '(1 3 5) '(2 4 6 8)) ; -> ((1 2) (3 4) (5 6))

   Дефинирайте процедура (zip-with fn x y), която връща списъка (fn(x₁, y₁) fn(x₂, y₂) ... fn(x_n, y_n)), където x_i и y_i са съответно i-тият елемент на списъка x и i-тият елемент на списъка y, а n е дължината на по-късия списък от x и y.

   (zip-with + '(1 3 5) '(2 4 6)) ; -> (3 7 11)
   (zip-with + '(1 3 5) '(2 4 6 8)) ; -> (3 7 11)

   Дефинирайте по-общ вариант на процедурата zip-with - (zip-with* fn . ls), която прилага fn с аргументи поредните елементи на списъците ls, докато някой от тях не се изчерпа.

   (zip-with* + '(1 2 3) '(4 5 6) '(7 8 9)) ; -> (12 15 18)
   (zip-with* cons '(1 3 5) '(2 4 6 8 10)) ; -> ((1 . 2) (3 . 4) (5 . 6))

4. Дефинирайте процедура (juxt . fns) (от англ. juxtaposition - съпоставяне). Резултатът от (juxt f g h ...) e процедура с променлив брой аргументи, която връща списък с резултатите от прилагането на всяка една от процедурите f, g, h, ... върху тези аргументи.

   (define (inc x) (+ x 1))
   (define (dec x) (- x 1))
   (define (square x) (* x x))
   (define (double x) (* 2 x))
   
   (define f (juxt inc dec square double)) ; (f x) = (list (inc x) (dec x) (square x) (double x))
   (f 5) ; -> (6 4 25 10)
   
   (define g (juxt + *))
   (g 3 4 5) ; -> (12 60)

Матрици

1. Дефинирайте процедура (dimensions matrix), която връща наредена двойка с броя редове и броя колони на матрицата matrix.

   (dimensions '((1 2 3) (4 5 6))) ; -> (2 . 3)

2. Дефинирайте процедура (reverse-columns matrix), която обръща реда на колоните в матрицата matrix.

   (reverse-columns '((1 2 3) (4 5 6) (7 8 9))) ; -> ((3 2 1) (6 5 4) (9 8 7))

3. Дефинирайте процедура (nth-column matrix n), която връща списък с елементите на n-тата поред колона от матрицата matrix.

   (nth-column '((1 2 3) (4 5 6) (7 8 9)) 1) ; -> (2 5 8)

4. Дефинирайте процедура (main-diagonal matrix), която връща списък с елементите в главния диагонал на матрицата matrix.

   (main-diagonal '((1 2 3) (4 5 6) (7 8 9))) ; -> (1 5 9)

5. Дефинирайте процедура (transpose matrix), която връща транспонираната матрица на матрицата matrix.

   (transpose '((1 2 3) (4 5 6))) ; -> ((1 4) (2 5) (3 6))

6. Дефинирайте процедура (for-all-columns? p matrix), която проверява дали за всяка колона в матрицата matrix е изпълнен предикатът p.

7. Дефинирайте процедура (prime-in-each-column? matrix), която проверява дали във всяка колона в матрицата matrix има просто число.

   (prime-in-each-column? '((1 2 3) (4 5 6) (42 8 9))) ; -> #f
   (prime-in-each-column? '((17 2 16) (4 5 3))) ; -> #t

8. Дефинирайте процедура (multiply a b), която връща произведението на двете матрици a и b.

9. Дефинирайте процедура (count-columns matrix), която намира броя на колоните на матрицата matrix, за които е вярно, че всичките им елементи се срещат в някой от редовете на матрицата matrix.

   Например (count-columns '((1 4 3) (4 5 6) (7 4 9))) връща 1, защото 4, 5 и 4 от втората колона се срещат във втория ред.

Дървета

За решаването на задачите използвайте основните процедури за работа с двоични дървета, дефинирани в binary-tree.scm.

1. Дефинирайте процедури (pre-order tree), (in-order tree) и (post-order tree), които правят съответно корен-ляво-дясно, ляво-корен-дясно и ляво-дясно-корен обхождане на двоичното дървото tree. Процедурите да връщат списък от върховете на tree в реда на тяхното обхождане.

2. Ниво n в двоично дърво наричаме списък от всички върхове на двоичното дърво, които са на разстояние n от корена. Ниво 0 съдържа само корена на дървото. Дефинирайте процедура (level n tree), която връща n-тото ниво в двоичното дърво tree.

3. Дефинирайте процедура (count-leaves tree), която намира броя на листата в двоичното дърво tree.

4. Дефинирайте процедура (map-tree fn tree), която прилага процедурата fn върху всеки връх на двоичното дърво tree.

5. Двоична пирамида е:

   1. празното двоично дърво или
   2. двоично дърво, в което всеки връх е по-малък от децата си.

   Да се напише процедура (binary-heap? tree), която проверява дали двоичното дърво tree е двоична пирамида.

6. Двоично дърво е балансирано, ако:

   1. е празното двоично дърво или
   2. височините на лявото и дясното поддърво се различават най-много с 1 и лявото и дясното поддървета са балансирани.

   Да се напише процедура (balanced? tree), която проверява дали двоичното дърво tree е балансирано.