Лесна задача, лесно решение
Да кажем, че е нужно да се направи функция на Scheme/Lisp, която изчислява сумата на първите N числа.
(1)Ако сме глупави и не знаем, че има формула за тази работа, най-вероято кодът ще изглежда така:
(define (f n)
(if (= n 1)
1
(+ n (f (- n 1)) )
)
)
Втора подобна задача - работата се заплита
Добре де, но ако след това се наложи да търсим произведение на първите N числа(това е N! - "N факториел")?
(define (f n)
(if (= n 1)
1
(* n (f (- n 1)) )
)
)
Да де, ама двете функции се различават буквално по един символ! Голяма загуба на време и усилия ще е да се създава нова функция, която прави кажи-речи същото като предишната. Да не говорим, че ако искаме да сменим и двете функции да работят и с нула, или да вземат числата през две, ще трябва да се променя кодът и на двете. Ами ако бяха не две функции, а десет?
Генератори на функции
Ето тук идват на помощ генераторите на функции.
Това са функции, които връщат други функции.
Например, в нашия случай би ни бил полезен генератор, който приема число N и операция oper и създава израз от вида:
$1-oper-2-oper-3 ... N$
(това са тирета, не са минуси)
Код:
(define (f oper n)
(if (= n 1)
1
(oper n (f oper (- n 1)) )
)
)
Сега, ако извикаме (f + n) - събираме числата от 1 до N. (f * n) - умножаваме ги. Ако си измислим нова, идиотска операция, която приема два аргумента - числа, и връща число, можем да си я прилагаме на 1…N колкото си искаме.
Това не работи на Dr Scheme - Beginning Student. Ако сте на това, от Language сменете на Pretty Big.
Добре, ами ако след това шефът ни(този гад) реши да се изгаври с нас.
"Намери сумата на петите степени на първите 3N числа, вземайки само тези, които са кратни на 3. На Scheme, никакви такива C++ лигавщини. И след това намери сумата на седмите степени на тия числа."
Как става това?
Бъдете с нас и следващия път, драги зрители, и ще разберете.
А сега, кратко прекъсване за съобщения от нашите спонсори.
По-сложни генератори
И така, отново сте с нашето супер шоу (Невада), днес ще имате уникалния шанс да спечелите -1000 лева, опитавайки се да напишете програма на Scheme.
Как да направим програма, която събира числа, но не тези от 1 до N, а например петите им степени?
Ако цялата тема не беше кръстена "Генератори на функции", това щеше да е наистина интересен въпрос. Оттук нататък в общи линии ще правим още от същото, но ще става все по-сложно. Ясно е, че можем да намираме степените на числата като просто в (oper n (f (- n 1)) ) заменим N с (power n 5), което е функция, която вдига на пета степен. Но няма ли да е по-хубаво да направим място в кода за функция, която приема число от 1 до N и на него съпоставя друго число (в частност - петата му степен?). Тази функция наричаме term(защото дава N-тия член, на английски "N-th term" на редицата, с която работим).
(define (aggregate oper term n)
(if (= n 1)
1
(oper (term n) (aggregate oper term (- n 1)) )
)
)
Кръщаваме функцията aggregate(което означава "събирам на едно място", защото тя това прави - от N стойности прави 1).
След това работата се улеснява доста:
(define (power n x)
(if (= x 0)
1
(* n (power n (- x 1)))
)
)
(define (power5 n)
(power n 5)
)
(aggregate + power5 5)
(Намира сумата на петите степени на първите 5 естествени числа)
С така направения код вече е много по-лесно да правим магии. Например, седми степени:
(define (power7 n)
(power n 7)
)
(aggregate + power7 5)
Ама нали трябваше да са всъщност не 1,2,3 ами 3,6,9 числата? Това лесно може да се направи с кадърно написана term функция, но ние ще направим друго. Ще си дефинираме стъпка, през която да вършим изчисленията. Започваме от N, след това отиваме в N-step, после в N-2*step и т.н.
Освен това, за да стигнем докрай с гадорията, дефинираме си минимална стойност. Такава, че когато N стане по-малко или равно на нея, рекурсията да спира. И да връща нещо(най-често това ще е 1, но може и да е 0, кой знае…)
(define (aggregate oper term n step min_n null_value)
(if (<= n min_n)
null_value
(oper
(term n)
(aggregate oper term (- n step) step min_n null_value)
)
)
)
Сега, пети степени на числата, кратни на 3. Вървим от 9, намалявайки с по 3 всеки път, докато стигнем 0. Стойността в 0 е 0.
(aggregate + power5 9 3 0 0)
Тази функция е еквивалент на for и foreach в други езици.
Вече става малко претрупано и може да ни се наложи да си дефинираме функции за по-обикновените случаи. Такива, които приемат по-малко параметри и просто решават, че останалите са винаги едни и същи - например за step=1, min_n=1, null_value=11.
(define (simple_for oper term n)
(aggregate oper term n 1 1 1)
)
Защо и къде са полезни
Току-що се занимавахме доста време, за да постигнем резултата, който беше готов още в началото на статията.
Това на пръв поглед може да изглежда глупаво, прахосническо и неоптимално. Но всъщност не е така, спокойно.
Защо тази имплементация е по-добра от предишната? Защото цялата логика на програмата е на едно място. Ако се окаже, че има нещо грешно в начина, по който смятаме нещата, трябва само да се промени aggregate и всичко, което зависи от него - например simple_for също ще бъде оправено. И можем да си направим други complex_for-ове за нула време.
Не е за изпускане и фактът, че така програмистът не трябва да си губи времето с писане на двадесет и осем малки, лесни, еднообразни и досадни функции. Ще ми благодариш после :)
Забележи, че това не е всичко, което има да се каже за генераторите на функции. Всъщност, в момента даже не правим точно генератори на функции - след две-три лекции темата ще достигне своят апотеоз.