Генератори на функции, Подаване на функция като аргумент

Лесна задача, лесно решение

Да кажем, че е нужно да се направи функция на Scheme/Lisp, която изчислява сумата на първите N числа.

(1)
\begin{align} f(x) = \sum^n_{i=1} i \end{align}

Ако сме глупави и не знаем, че има формула за тази работа, най-вероято кодът ще изглежда така:

(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-ове за нула време.
Не е за изпускане и фактът, че така програмистът не трябва да си губи времето с писане на двадесет и осем малки, лесни, еднообразни и досадни функции. Ще ми благодариш после :)

Забележи, че това не е всичко, което има да се каже за генераторите на функции. Всъщност, в момента даже не правим точно генератори на функции - след две-три лекции темата ще достигне своят апотеоз.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License