Programowanie funkcyjne/Procedury wyższych rzędów

Wstęp

Jak wcześniej zaznaczyliśmy, procedury są równie dobrymi wartościami jak wszystkie inne. W szczególności procedury mogą być argumentami procedur lub ich wynikami. Dzisiaj zajmiemy się procedurami wyższych rzędów, tzn. procedurami przetwarzającymi procedury.

Kilka prostych przykładów

Podniesienie funkcji do kwadratu

let twice f = function x -> f (f x);;
val twice : ('a -> 'a) -> 'a -> 'a = <fun>
twice (function x -> x * (x+1)) 2;;
- : int = 42          

Zwróćmy (pobieżnie) uwagę na typ procedury twice. (Krotka zapowiedź typów proceduralnych. Bez zagłębiania się w polimorfizm.) Jest to procedura, której parametrem jest procedura, a wynikiem jest procedura takiego samego typu, jak argument.

Składanie funkcji

let compose f g = function x -> f (g x);;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
let twice f = compose f f;;

Iterowanie funkcji:

let id x = x;;
let rec iterate n f =
  if n = 0 then id else compose (iterate (n-1) f) f;;
          

Czy istnieją procedury wieloargumentowe?

Typy proceduralne to typy postaci $\text{argument}\to \text{wynik}$. Ponieważ zarówno argument, jak i wynik może być typu proceduralnego, więc typ może zawierać więcej "strzałek". Zastanówmy się co z procedurami wieloargumentowymi. Rozważmy następujące dwie definicje:

let plus (x, y) = x + y;;
val plus : int * int -> int = <fun>
let plus x y = x + y;;
val plus : int -> int -> int = <fun>      

Pierwsza procedura bierze parę wartości i oblicza wynik. Druga procedura bierze pierwszy argument i jej wynikiem jest procedura, która gdy dostanie drugi argument, to obliczy sumę. Inaczej mówiąc, bierze argumenty na raty.

Ta druga postać jest wygodniejsza, ze względu na możliwość podania tylko części argumentów.

let plus x y = x + y;;
let inc = plus 1;;
     

Obie postacie, są równoważne. Dowodem na to są poniższe dwie procedury przekształcające jedną w postać w drugą i odwrotnie. Jakiego typu są te procedury?

let curry f = function x -> function y -> f (x, y);;
let uncurry f = function (x, y) -> f x y;;
     

Standardowa postać podawania argumentów procedury jest curry. Tak więc przedstawione przykłady można zdefiniować i tak:

let twice f x = f (f x);;
let compose f g x = f (g x);;
let curry f x y = f (x, y);;
let uncurry f (x, y) = f x y;;

Przykład: Sumy częściowe szeregów

Przykład - szereg (kolejnych liczb naturalnych, kwadratów, $\frac{1}{(4i-3)(4i-1)}$ zbieżny do $\frac{\pi }{8}$. Istota szeregu jako funkcja wyższego rzędu, sumowane elementy jako funkcje liczb całkowitych. Procedura sumująca $n$ pierwszych elementów danego szeregu (podać specyfikację sum):

let rec szereg f n = 
  if n = 0 then 0.0 else f n + szereg f (n-1);;
  
let szereg_pi_8 n = 
  szereg 
    (function i ->
      1. /. ((4. *. float i -. 3.) *. (4. *. float i -. 1.)))
    n;;
  
let pi = 8. *. szereg_pi_8 1000;;
     

Procedura szereg może służyć do obliczania sumczęściowych dowolnych szeregów.

Przykład: Różniczkowanie funkcji

Zdefiniujmy najpierw różniczkę:

let rozniczka f x dx = (f (x +. dx) -. f x) /. dx;;
     

Wówczas pochodną możemy przybliżyć następująco:

let pochodna f x = rozniczka f x epsilon;;
     

Zwróćmy uwagę, że pochodna jest procedurą jednoargumentową i wynikiem (pochodna f) jest funkcja będąca pochodną f.

Metoda Newtona

Zakładamy, że dana funkcja jest różniczkowalna. Pomijamy kwestie stopu i dzielenia przez 0. Metoda Newtona, nazywana też metodą stycznych, polega na przybliżaniu zera funkcji w następujący sposób: w punkcie będącym aktualnym przybliżeniem rysujemy styczną do wykresu funkcji i kolejnym przybliżeniem jest punkt przecięcia stycznej z osią X.

Zauważmy, że jeżeli naszym przybliżeniem zera jest $x$, to styczna do wykresu funkcji przecina oś X w punkcie $x-\frac{(fx)}{(f^{\prime }x)}$.

Jest to przykład algorytmu polegającego na iteracyjnym przybliżaniu wyniku. Spróbujmy sformułować najpierw ogólny schemat takiego postępowania iteracyjnego:

let rec iteruj poczatek popraw czy_dobre wynik =
  if czy_dobre poczatek then 
    wynik poczatek
  else
    iteruj (popraw poczatek) popraw czy_dobre wynik;;
     

Zastosujmy teraz ten schemat do zaimplementowania metody stycznych Newtona. Zauważmy, że jeżeli naszym przybliżeniem zera jest $x$, to styczna do wykresu funkcji przecina oś X w punkcie $x-\frac{(fx)}{(f^{\prime }x)}$.

let id x = x;;
let newton f x = 
  let p = pochodna f
  in 
    let czy_dobre x = abs (f x) < epsilon
    and popraw x = x -. (f x) /. (p x)
    in
      iteruj x popraw czy_dobre id;;
     

Zwróćmy uwagę na to, że procedura popraw-newton jest lokalna i ma dostęp do funkcji f. Pozostało nam jeszcze napisanie procedury pochodna. Metoda Newtona liczenia pierwiastków kwadratowych to szczególny przypadek metody Newtona znajdowania zer, dla funkcji $f(x)=x^2-a$. Funkcja ta ma zera w punktach $\pm \sqrt{a}$. Ponadto $f^{\prime }(x)=2x$, czyli nasz algorytm przekształca przybliżenie $x$ w

$x-\frac{f(x)}{f^{\prime }(x)}=x-\frac{x^2-a}{2x}=\frac{2x^2-x^2+a}{2x}=\frac{x^2+a}{2x}=\frac{x+\frac{a}{x}}{2}$

Zaczynając w punkcie 1 przybliżamy $\sqrt{a}$.

let sqrt a = 
  let f x = a -. square x
  in newton f 1.;;

Punkty stałe funkcji

Punkt stały funkcji $f$, to taki $x$, że $f(x)=x$. W przypadku niektórych funkcji (i określonych $x$-ów) ciąg $x,f(x),f^2(x),f^3(x),\dots$ jest zbieżny do pewnego punktu stałego $f$. Możemy zaimplementować tę metodę:

let punkt_staly f x = 
  let blisko x = abs (x -. f x) < epsilon
  in
    iteruj x f blisko f;;
     

Przykładową funkcją, której punkt stały można znaleźć tą metodą jest $\cos (x)$.

punkt_staly cos 1.0;;
0.73908\dots      

Proszę to sprawdzić na jakimś nudnym wykładzie --- wystarczy ciągle stukać w klawisz $\cos$.

Obliczanie punktów stałych moglibyśmy zastosować do obliczania pierwiastków --- punkt stały funkcji $y\to \frac{x}{y}$ to $\sqrt{x}$. Jednak obliczenie:

punkt_staly (function y ->  x /. y) 1.0;;
     

nie jest zbieżne: $1\to \frac{x}{1}=x\to \frac{x}{x}=1\to \dots$

W takich przypadkach czasami pomaga "wytłumienie" oscylacji takiego ciągu przez jego uśrednienie.

let usrednienie f = 
  function x -> average x (f x);;
  
let sqrt x = 
  punkt_staly (usrednienie (function y -> x /. y)) 1.0;;
     

W ten sposób uzyskujemy po raz kolejny metodę pierwiastkowania Newtona.

Zastosowania procedur wyższych rzędów

Procedury wyższych rzędów to jeden z tych elementów języka, który jest czysto funkcyjny. W językach imperatywnych procedury mogą być parametrami procedur, lecz nie wynikami. W przypadku języków funkcyjnych mamy pełną swobodę.

Zastosowania procedur wyższych rzędów można podzielić na dwie grupy:

• Pewne pojęcia matematyczne, zwłaszcza te dotyczące funkcji, w naturalny sposób przekładają się na procedury wyższych rzędów, np.: sumy częściowe szeregów, składanie funkcji, różniczkowanie funkcji itp.
• Procedury są jeszcze jednym typem danych. Przyjmując takie podejście, procedury przetwarzające takie dane będą procedurami wyższych rzędów.
• Procedury wyższych rzędów są również narzędziem abstrakcji. Jeżeli ten sam fragment kodu pojawia się w kilku miejscach, to naturalnym jest wyłonienie go w postaci (zwykłej) procedury.
• Jeżeli ten sam schemat kodu pojawia się w wielu miejscach, ale różni się wypełniającymi go fragmentami, to schemat ten możemy ująć w postaci procedury wyższego rzędu, a fragmenty do wypełnienia staną się parametrami proceduralnymi. Przykładem może być tu procedura iteruj.

Procedury wyższych rzędów i listy

Funkcje przetwarzające listy często mają ten sam schemat. Spróbujmy ująć ten schemat w postaci procedur wyższych rzędów. Najczęściej przeglądamy kolejne elementy listy i obliczamy na ich podstawie pewien wynik. W schemacie tym mamy następujące elementy zmienne:

• elementy listy przetwarzamy od lewej do prawej, lub odwrotnie,
• wynik dla pustej listy,
• wynik dla nie pustej listy, jako funkcja głowy i wyniku obliczonego dla ogona.

W zależności od kierunku przetwarzania listy, schemat ten możemy ująć w postaci następujących dwóch procedur:

let rec foldr f l a = 
  match l with
    []   -> a |
    h::t -> f h (foldr f t a);;
  
let rec foldl f a l = 
  match l with 
    []   -> a |
    h::t -> foldl f (f a h) t;;
  
let fold = foldl;;        
     

Oto kilka prostych zastosowań:

let sum l = fold (+) 0 l;;
let prod l = fold ( * ) 1 l;;
     

Inny schemat, to przetwarzanie wszystkich elementów listy, element po elemencie.

let map f l = 
  foldr 
    (fun h t -> (f h)::t) 
    l 
    [];;
     

Kolejny częsty schemat, to selekcja elementów listy --- sprawdzamy pewien warunek i zostawiamy tylko elementy spełniające go.

let filter p l = 
  foldr (fun h t -> if p h then h::t else t) l [];;

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu