Първо контролно

Контролно тайм

На тази страница са задачите от първото контролно по функционално програмиране. Това е, не ми идва нищо остроумно да кажа по темата. Естествено, контролното вече мина, така че целта на тази страница ще е да служи за упражнение на всички, които смятат да ходят на поправка по ФП. Както и за източник на мъдрост и вдъхновение на бъдещите поколения(това само в случай, че механата зад факултета затвори преждевременно, нали).
Задачите бяха седем, задължително е да бъдат решени първите пет, както и една от последните две. И като казвам задължително - само ако искаш да не те скъсат е задължително. Иначе, ако смяташ да преследваш кариера като морско свинче за експериментални лекарства - заповядай, не решавай нищо.

Силно се надявам да не си мислиш, че ако просто запомниш наизуст решенията на тези задачи, ще си вземеш изпита. Тоест, шансът е, че ако искаш да зубриш, ще го вземеш, но няма да си научиш материала и тогава даже всичките шестици на света няма да ти повишат интелектуалното ниво. Моля, първо пробвай да ги решиш без да гледаш отговорите.

Задача 1

Тази е гадна, ще я напиша после. Т.е. тя не е гадна, ама трябва да рисувам, а ме мързи.

Задача 2

Да се дефинира процедура, която без да използва процедури от по-висок ред намира сумата

(1)

\begin{align} \sum_{i=1}^n (-1)^{i-1} \cfrac{i!}{(a+1)(a+2) \cdots (a+i)} \end{align}

Където a и n са дадени естествени числа.

Решение

Защо без процедури от по-висок ред остава мистерия. Явно авторите са решили, че не се мъчим достатъчно във ФМИ.
Така де, това е кратко и ясно, решението много прилича на всеизвестната вече accumulate. Просто си пишем функция, която да намира едно от събираемите (изразът е сума) и после това се вика N пъти. Естествено, на контролното я обърках тази задача. При това беше нещо адски дребно, стана ми ясно в момента, в който я написах на компютър. Oh well, аз нямам амбиция да ставам човек-компилатор, щом мога да си хващам бъговете по нормалния начин, не ми трябва да ги хващам на лист хартия. Ако имаш повече боен дух от мен, не гледай напред, а пробвай да го напишеш на ръка :)

(define (zad2_one_term a n)
    (if (= n 0)
        -1
        (*
            (/ (- n) (+ a n))
            (zad2_one_term a (- n 1))
        )
    )
)

(define (zad2 a n)
    (if (= n 0)
        0
        (+
            (zad2_one_term a n)
            (zad2 a (- n 1))
        )
    )
)

Защо началната стойност в първата процедура е -1, а не 1 ще стане ясно в момента, в който си пуснеш програмата. Просто малко по-елегантно става.

Задача 3

Да се дефинира процедура от по-висок ред (accumulate combinator null-value term start next end) и като се използва, да се дефинира процедура, която по дадени естествено число n и реално число x(x е различно от 0) намира стойността на израза:

(2)

\begin{align} (\sqrt{2} - \cfrac{1}{x} + \cfrac{1}{x^2})(\sqrt{4} - \cfrac{1}{x} + \cfrac{1}{x^2} - \cfrac{1}{x^4}) \cdots (\sqrt{2n} - \cfrac{1}{x} + \cfrac{1}{x^2} - \cfrac{1}{x^4} + \cdots + (-1)^{n+1}\cfrac{1}{x^{2n}}) \end{align}

Тази задача е тъпа, затова преди решението първо ще я наредя:

Аз нареждам задачата

Защо задачите от контролни са толкова безнадеждно повтарящи се и скучни? Защо всичките такива задачи стават само за губене на време? Защо очевидно ненужно се усложняват едни и същи неща, чрез които просто няма как да се провери кой може да програмира и кой - не? Не, тази задача все пак не я обърках, просто ме дразни, защото е тъпа.
Такива задачи препъват основно грешните хора. Некадърниците така и така няма да я решат, а зубърите ще се хванат за всяка завъртулка на условието и ще го уцелят накрая. Нормалният човек ще си напише програмата, ще изгуби 5 секунди в дебъг(вместо 10 минути в четене на скоби, написани с химикал), ще види дали има грешка и евентуално за още 30 секунди ще я оправи. Ама тук няма дебъг, нали? Така че нормалният пич губи. Животът е гаден, свиквай. Освен това, по последни проучвания, повече момичета си падат по Mercedez, отколкото по законите на Кеплер. Да не говорим за китайската теорема за остатъците - тази даже и математичките не ги кефи. Ако това е някакво успокоение, в общия план на вселената, това контролно няма абсолютно никакво значение. За още по-голямо успокоение, даже в общия план на твоя живот, плана на ФМИ, на семестъра или даже само на този предмет, контролното продължава да няма никакво значение :). Така де, аз седя и пиша тук, защото трябва да откарам още един час на работа, ама ти - като една свободна и прекрасна душа под синьото небе - най-добре се качи на покрива на блока си и си представи, че виждаш звездите. Представи си, че един ден всичко ще е Наред и ще можеш да прекарваш нощите си, измисляйки нови съзвездия и мечтаейки всички да са щастливи колкото теб. Иска ми се да живея в свят, в който не ми губят времето с глупости. В свят, в който не ме е страх да си оставям входната врата отключена. И да мога да вярвам на хората. Мдам. Това би било хубаво.

Решение

В моята реализация next не е число, а функция. По-удобно е, според мен, защото така може да се работи с неравномерно променящи се величини. Ако искаш, сложи си го да е число. Отново има отделна функция за намиране на един елемент на произведението. Всъщност, това е същото като задача 2. zad2_one_term има специфична null-value стойност, впрочем.

(define (accumulate combinator null-value term start next end)
    (if (>= start end)
        null-value
        (combinator
            (term end)
            (accumulate combinator null-value term start next (next end))
        )
    )
)

(define (zad3_one_term x n)
    (accumulate 
        +
        (- (sqrt (* 2 n)) (/ 1 x))
        (lambda (i) (* (expt (- 1) (+ i 1)) (/ 1 (expt x (* 2 i)))))
        0
        (lambda (y) (- y 2))
        n
        )
)

(define (zad3 x n)
  (accumulate * 1 (lambda (i) (zad3_one_term x i)) 0 (lambda (y) (- y 1)) n)
)

Функцията expt повдига реално число на реална степен. В zad3_one_term стъпката е -2, а в zad3 стъпката е -1.

Задача 4

Даден е списък от точкови двойки от естествени числа $l = ((a_1 . b_1) (a_2 . b_2) \cdots (a_n . b_n))$, за който е известно, че всяко $b_i$ е различно от $b_j$ за $i \ne j$. Да се дефинира функция, построяваща частичната функция f върху естествените числа, дефинирана по следния начин: $f(b_i) = a_i$ за всяко i $(1 \le i le k)$.

Решение

Това е сравнително лесно, просто генерираме фунцкия, която приема един аргумент. Проверява дали този аргумент го има в списъка и ако да - връща каквото трябва. Иначе връща nil. Естествено, пак го има проблемът с писането на хартия - внимавай за бъгове, които иначе не биха се появили.

(define (zad4 l)
    (define (checker num lst)
        (cond
            ((null? lst) nil)
            ((= (cadar lst) num) (caar lst))
            (else (checker num (cdr lst)))
        )
    )
    (lambda (x)
        (checker x l)
    )
)

Впрочем, вярно или не? В момента, в който скъсаш с едно момиче, тя сваля 10 кила, купува си секси дрехи и започва да чете поезия? (Не се смей, това беше бонус въпрос на контролното. На първа група въпросът беше за момче, ама там нямам сведения как е.)

Задача 5

Deep list се нарича празният списък () и ако x е число или deep list, а l е deep list, то (cons x l) е deep list. Например (1 (2 (3 4)) (5 6) (7 (8))) e deep list. Нека L1 и L2 са дадени дълбоки списъци. Да се дефинира функция, която намира сечението на множеството от числата в L1 с множеството от числата в L2.

Решение

Ето нещо по-сложно. Не казвам по-интересно, но поне по-сложно. Според мен се прави с две прилагания на функцията
symm-diff, която приема два списъка L1 и L2 и намира всички елементи от L1, които принадлежат на L2. Теория на множествата, симетрични разлики… да ти говорят нещо? :)

(define (in-deep-list? num lst)
    (cond
        ((null? lst) #f)
        ((number? (car lst)) (if (= num (car lst))
                            #t
                            (in-deep-list? num (cdr lst))
                        )
                )
        (else (if (in-deep-list? num (car lst))
                #t
                (in-deep-list? num (cdr lst))
            )
        )
    )
)

(define (symm-diff l1 l2)
    (cond
        ((null? l1) '())
        ((number? (car l1))
            (if (in-deep-list? (car l1) l2)
                (cons (car l1) (symm-diff (cdr l1) l2))
                (symm-diff (cdr l1) l2)
            )
                )
        (else (cons (symm-diff (car l1) l2) (symm-diff (cdr l1) l2)))
    )
)

(define (zad5 l1 l2)
    (symm-diff l2 (symm-diff l1 l2))
)

symm-diff връща дълбок списък. Това е хубаво, защото може да го приложим 2 пъти както в zad5. Аз като го тествах - работеше. При теб как е?

Задача 6

Като се използват функции от по-висок ред за списъци, да се дефинира предикат (fixed? f l), който по дадена функция $f: R \to R$ и списък от списъци от реални числа l проверява дали във всеки от подсписъците на l съществува поне една неподвижна точка за f (x е неподвижна точка за f, ако f(x) = x).
Пример:

(fixed? (lambda (x) (+ (* x x) (- x 1))) '((0 1 -1) (1 -1) (0 -1)))
#t

Решение

Използваме добре познатите функции от преди. Няма да ги пиша пак. Иронията е, че уж "най-трудната" задача се оказва една от най-лесните просто защото не е изморителна рутина.

(define (has-fixed-point? f lst)
  (cond ((null? lst) #f)
        ((= (f (car lst)) (car lst)) #t)
        (else (has-fixed-point? f (cdr lst)))
  )
)

(define (fixed? f l)
  (all? (lambda (item) has-fixed-point? f (item)) l)
)

Хайде сега сравни размера на решението за "трудната" задача с размера на някоя от "лесните". Сериозно, понякога почти успяват да ме откажат тези хора. Искам отново да повторя - Програмирането не е за глупави хора, които просто могат да напишат 1000 реда код на ден. Програмирането е за умни хора, които могат да свършат същата работа със 100 реда. Писането на дълги, трудоемки и скучни програми е работа на чираците. Повтарям, това е работа за другите хора. Тези, които не прекарват четири години от живота си специално учейки как да не правят точно така. Ако след тези редове решиш да пропуснеш контролното и направо да отидеш на изпит - браво на теб, аз аплодирам твоята смелост :)

---

Е, надявам се, че тази статия ти е била забавна, или поне полезна. Успех на следващото контролно.