Բարձր կարգի ֆունկցիաներ և անանուն ֆունկցիաներ

Երկու սերտ հասկացություններ՝ բարձր կարգի ֆունկցիա և անանուն ֆունկցիա, որոնք լայնորեն կիրառվում են ֆունկցիոնալ ծրագրավորման մեջ, որոնց տրամադրած մեխանիզմները հնարավորություն են տալիս կազմակերպել ավելի բնական, ավելի գեղեցիկ, ավելի ընթեռնելի ծրագրեր։

Ֆունկցիան կոչվում է բարձր կարգի, եթե նրա արգումենտներից գոնե մեկը ֆունկցիա է, կամ նրա վերադարձրած արժեքն է ֆունկցիա։

Ես ուզում եմ բարձր կարգի ֆունկցիաները ցուցադրել տրված ֆունկցիայի որոշյալ ինտեգրալի թվային հաշվման օրինակով։ Ենթադրենք պետք է իրականացնել integral ֆունկցիան, որն արգումենտում ստանում է \(f(x)\) ինտեգրվող ֆունկցիան և \([a;b]\) ինտեգրման միջակայքը։ $$ \mathrm{integral}(f, a, b)=\int\limits_a^b f(x)dx $$ Այս integral ֆունկցիան երկրորդ կարգի է, որովհետև նրա f արգումենտը առաջին կարգի ֆունկցիա է։

Ինտեգրալի թվային հաշվման համար ընտրենք սեղանների մեթոդը, որի դեպքում ինտեգրման միջակայում \(f\) ֆունկցիայի գրաֆիկը մոտարկվում է ուղիղ գծով, իսկ ինտեգրալի արժեքը ընդունվում է \((a,0)\), \((a,f(a))\), \((b,f(b))\) և \((0,b)\) գագաթներով սեղանի մակերեսին հավասար։ \[ \mathrm{trapezoid}(f, a, b)=(b-a)\frac{f(a)+f(b)}{2} \] Common Lisp լեզվով այս բանաձևը ծրագրավորվում է հետևյալ կերպ.

(defun trapezoid (f a b)
  (* (- b a) (/ (+ (funcall f a) (funcall f b)) 2.0)))

integral ֆունկցիայի արգումենտում տրված f ֆունկցիա-արգումենտը ֆունկցիայի մարմնում օգտագործված է funcall ֆունկցիայի միջոցով, որը տրված ֆունկկցիա-օբյեկտը կիրառում է տրված արգումենտների նկատմամբ։

C++11 լեզվով նույն integral ֆունկցիան կարելի է գրել հետևյալ կերպ.

double trapezoid( std::function<double(double)> f, double a, double b )
{
  return (b - a) * ((f(a) + f(b)) / 2);
}

Եթե այս ֆունկցիայով հաշվենք, օրինակ \(f(x)=x^2\) ֆունկցիայի ինտեգրալը \([-1;1]\) միջակայքում, ապա կստանանք \(2\) արժեքը՝ իրական \(2/3\)-ի փոխարեն։

Պարզ է, որ սեղանների մեթոդը կարող է բավարար ճշտություն ապահովել միայն այն դեպքում, երբ ինտեգրման միջակայքը շատ փոքր է։ Օգտագործելով այդ փաստը, սահմանեմ integral ֆունկցիան, որի \(\varepsilon\) արգումենտը ցույց է տալիս ինտեգրման միջակայքի ամենամեծ թույլատրելի չափը։ Այն դեպքում, երբ \(b-a\gt\varepsilon\), միջակայքը կկիսեմ երկու հավասար մասերի և իրար կգումարեմ այդ երկու մասերում հաշված ինտեգրալների արժեքները։ Այլ կերպ ասած, ինտեգրալի հաշվման նոր բանաձևն է հետևյալը. \[ \mathrm{integral}(f, a, b, \varepsilon)= \left\{ \begin{array}{ll} \mathrm{trapezoid}(f, a, b), & |b - a|\le\varepsilon, \\ \mathrm{integral}(f, a, \frac{a+b}{2}, \varepsilon) + \mathrm{integral}(f, \frac{a+b}{2}, b, \varepsilon), & |b - a|\gt\varepsilon.\\ \end{array} \right. \] Այս integral ֆունկցիան նույնպես երկրորդ կարգի է, քանի որ նրա արգումենտներում ամենաբարձր կարգը առաջինն է։ integral ֆունկցիայի սահմանումը Common Lisp լեզվով ունի այսպիսի տեսք.

(defun integral (f a b &optional (eps 0.001))
  (if (<= (- b a) eps)
      (trapezoid f a b)
      (let ((m (/ (+ a b) 2)))
        (+ (integral f a m eps) (integral f m b eps)))))

Նույն ֆունկցիան C++11 լեզվով կունենա հետևյալ տեսքը։

using mathfunc = std::function<double(double)>;

double integral( mathfunc f, double a, double b, double eps = 0.001 )
{
  if( b - a <= eps)
    return (b - a) * ((f(a) + f(b)) / 2);

  auto m((a + b) / 2);
  return integral(f, a, m, eps) + integral(f, m, b, eps);
}

Հիմա, ենթադրենք, ուզում եմ հաշվել \(f(x)=x^3\) ֆունկցիայի ինտեգրալը \([0;2]\) միջակայքում: Նախ սահմանեմ այդ ֆունկցիան Lisp լեզվով.

(defun f (x) (* x x x))

Ապա integral ֆունկցիայի օգնությամբ հաշվեմ սրա ինտեգրալը տրված միջակայքում.

(integral #'qub 0 2.0)   ; => 4.0

Եթե պետք լինի հաշվել, օրինակ, \(f(x)=x^2-3x\) ֆունկցիայի ինտեգրալը, ապա սա նույնպես պետք է սահմանել

(defun f (x) (- (* x x) (* x 3)))

ապա integral ֆունկցիան կիրառել այս f ֆունկցիայի նկատմամբ։ Բայց անանուն ֆունկցիաների մեխանիզմը հնարավորություն է տալիս խուսափել ինտեգրվող ֆունկցիայի առանձին սահմանումից։ Օրինակ, այս վեջին ֆունկցիան \([-2;1]\) միջակայքում ինտեգրելու համար կարելի է գրել.

(integral #'(lambda (x) (- (* x x) (* x 3))) -2 1)

Այստեղ integral ֆունկցիայի կանչի մեջ lambda մակրոսով ստեղծվել է ինտեգրվող ֆունկցիային համապատասխան անանուն ֆունկցիա։
C++11 լեզվում նույնպես կարելի է գրել համարժեք արտահայտություն.

integral([](double x)->double{ return x*x-3*x;}, -2, 1);

որտեղ անանուն ֆունկցիան սահմանված C++11 լեզվի []()->{} կառուցվածքով։

Բայց սեղանների մեթոդը ինտեգրալի հաշվման միակ մեթոդը չէ։ Օրինակ, \(f\) ֆունկցիան \([a;b]\) հատվածի վրա կարելի է մոտարկել ոչ թե ուղիղ գծով, այլ պարաբոլով։ Այս մեթոդը կոչվում է Սիմպսոնի մեթոդ և ներկայանում է հետևյալ բանաձևով. \[ \mathrm{simpson}(f, a, b)=\frac{b-a}{6}\left(f(a)+4f\Big(\frac{a+b}{2}\Big)+f(b)\right) \] Եվ ինտեգրալի հաշվման թվային մեթոդը նույնպես կարելի է տալ integral ֆունկցիային որպես արգումենտ։ Այդ դեպքում կստանանք մի նոր, երրորդ կարգի ֆունկցիա. \[ \mathrm{integral}(method, f, a, b, \varepsilon)= \left\{ \begin{array}{ll} method(f, a, b), & |b - a|\le\varepsilon, \\ \mathrm{integral}(f, a, \frac{a+b}{2}, \varepsilon) + \mathrm{integral}(f, \frac{a+b}{2}, b, \varepsilon), & |b - a|\gt\varepsilon.\\ \end{array} \right. \] Ծրագրավորենք այս ֆունկցիան Common Lisp լեզվով.

(defun integral (method f a b &optional (eps 0.001))
  (if (< (- b a) eps)
      (funcall method f a b)
      (let ((m (/ (+ a b) 2)))
        (+ (integral method f a m eps) 
           (integral method f m b eps)))))

Եվ C++11 լեզվով։

using method = std::function<double(mathfunc,double,double)>>;

double integral( method r, mathfunc f, double a, double b, double delta = 0.001 )
{
  if( b - a < delta )
    return r(f, a, b);

  auto m((a + b) / 2);
  return integral(r, f, a, m, delta) + integral(r, f, m, b, delta);
}