Mariusz Prowaźnik

o programowaniu w Javie, Scali i Clojure.


Aproksymacja liczby e w Clojure

W tym poście pokażę jedną z różnic pomiędzy programowaniem funkcyjnym a imperatywnym, na przykładzie szacowania wartości liczby e.

Odrobina teorii

Do szacowania liczby e wykorzystam jej rozwinięcie w szereg:

Pomiędzy elementami takiego szeregu istnieje zależność, dzięki której można zmniejszyć ilość obliczeń. Wzór rekurencyjny:

Szacowanie będzie polegać na zsumowanie pierwszych n elementów szeregu - im wyższe n, tym lepsze oszacowanie.

Jak to zaimplementować w Javie?


Jest tu kilka zmiennych, pętla for. W każdej iteracji obliczamy kolejny wyraz ciągu, nowe przybliżenie liczby e. Krótki, imperatywny kod.

A jak w Clojure?


W tym kodzie nie ma żadnej pętli, nie ma zmiennych. Są "wiązania" (naturals, e-taylor-serie, first-n-elems), ale bez nich też dałoby się ten kod napisać - wprowadziłem je dla lepszej czytelności, bo dzięki ich nazwom, nawet nie znając clojure, można się domyślić, że są tu 4 kroki: zdefiniowanie liczb naturalnych, kolejnych elementów szeregu, wybranie n pierwszych elementów i zsumowanie ich.

Nasuwać się może pytanie, co to za struktura danych, co przechowuje wszystkie liczby naturalne? Jest to leniwa sekwencja. Jej elementy elementy obliczane są dopiero w momencie użycia. Oznacza to, że może być ona nieskończonej długości, czyli na przykład być ciągiem liczb naturalnych.

Funkcja iterate przyjmuje dwa parametry: jednoargumentową funkcję f i wartość początkową. Generuje ona nieskończoną, leniwą sekwencję o elementach równych:

Czyli (iterate inc 1) wygeneruje nieskończoną leniwą sekwencję liczb naturalnych (inc to f(x)=x+1).

Funkcja reductions przyjmuje dwuargumentową funkcję f, wartość początkową x i sekwencję a. Rezultatem jest leniwa sekwencja. Pierwszy element tej sekwencji to f(x , a0), a kolejne to rezultat zastosowania funkcji f na poprzednim wyniku i kolejnym elemencie sekwencji a. Przykład:

(reductions / 1.0 natural) zwróci sekwencję z kolejnymi elementami rozwinięcia e.

Funkcja take jest najprostsza do zrozumienia ze wszystkich tu wymienionych. (take n s) bierze n elementów z sekwencji s. Jeśli sekwencja s jest leniwa, to te n elementów zostanie w tym momencie obliczone.

Pisałem wcześniej, że można napisać podobny kod, ale bez użycia wiązań. Przykład:

Wnioski

W programowaniu funkcyjnym operuje się na nieco innych abstrakcjach niż w imperatywnym. Implementacja w Javie opierała się modyfikowaniu stanu kilku zmiennych, wykonywanym interacyjnie. W kodzie Clojure zostało zdefiniowanych kilka przekształceń danych w ogólnej postaci (np. jak z liczb naturalnych zrobić rozwinięcie liczby e w szereg), a dopiero później zostały wykonane obliczenia. Moje subiektywne odczucie jest takie, że programując w języku funkcyjnym łatwiej odzwierciedlić w kodzie różne matematyczne zależności.

2 komentarze :

  1. Bardzo ciekawy artykuł i eleganckie rozwiązanie. Z ciekawości napisałem to samo w Scali, może komuś się przyda (scanLeft zastępuje tutaj reducations):

    def approxE(n: Int) =
    Stream.iterate(1.0)(1+).scanLeft(1.0){_ / _}.take(n).sum

    OdpowiedzUsuń
  2. Przyznam, że całkiem zwięźle wygląda ta implementacja w Scali. Znasz może odpowiednik scanLeft/reductions w javie8? Szukałem, ale nie znalazłem.

    OdpowiedzUsuń