Programowanie Funkcyjne

Prowadzący: Radosław Rowicki

Zadania kwalifikacyjne
Kategorie: informatyka

W ZADANIU 4 JEST MAŁA POPRAWKA (30.05.2019 22:30), PRZEPRASZAM ZA NIEDOGODNOŚĆ

>λ=

Większość programistów zaczynała swoją informatyczną przygodę od języków imperatywnych, zazwyczaj były to C, C++, Java, Python, czasem PHP czy inne. Pierwsze podstawowe (i mogło by się wydawać niezbędne) pojęcia, z jakimi się spotkaliśmy, to "zmienna", "pętla", "polecenie/instrukcja" i pewnie do dziś nie wyobrażamy sobie życia bez nich. Pytanie czy aby słusznie? A może da się tworzyć aplikacje i implementować algorytmy bez konieczności zmieniania stanu programu co krok? Może nawet da się programować bez wykonywania "kroków"?

inititle:"index of" WNCRYNa tych warsztatach poznacie zupełnie inny sposób patrzenia na program. Nie będzie to już tyrańskie wydawanie rozkazów i mówienie komputerowi co ma robić, lecz wręcz artystyczne tworzenie nowych obiektów, łączenie ich ze sobą w większe głosząc "niechaj się stanie <x>" (a programista widział że kod się skompilował, więc prawdopodobnie był dobry...). Dowiecie się, jak pisać sprawny, czytelny i wolny od błędów(!) kod bez użycia pętelek, zmiennych i obiektów zastępując je... oczywiście funkcjami! Będziemy dzielnie zmagać się z ograniczeniami, jakie narzuca nam deklaratywność, ale poznamy również niebywałe korzyści, jakie w zamian otrzymujemy.

Paradygmat poznamy na przykładzie czysto funkcyjnego języka jakim jest Haskell. Posiada on niezwykle przejrzystą składnię, pattern matching i bardzo rozbudowany, silny i statyczny system typów. Mimo to nie wymaga on od nas jawnego typowania, dzięki czemu kod wygląda tak przejrzyście jak np. w Pythonie. Dodatkowym atutem jest jego własny REPL - interaktywny shell, który pozwala nam sprawnie i dynamicznie testować kod (choć sam język domyślnie jest kompilowany).

Program

  • Króciutki wstęp do rachunku lambda
  • Podstawy składni Haskella
  • Funkcje wyższych rzędów
  • Duuuużo rekurencji
  • Jak zamienić każdą pętlę na rekurencję?
  • Struktury danych - listy, krotki, drzewa
  • Typy rekurencyjne
  • Leniwość / gorliwość
  • (Jeśli zdążymy) Czym jest monada i jak wykonywać akcje wyjścia i wejścia w czysto deklaratywnym kodzie
  • Jak wyglądają inne języki funkcyjne i jak działa funkcyjność w językach niefunkcyjnych (o ile istnieje)

    #define true false

Wymagania

  1. Znajomość pojęcia funkcji, dziedziny, przeciwdziedziny, zbioru itp.
  2. Zdolność posługiwania się funkcjami (przekształcenia wykresu, badanie różnowartościowości, rekurencja itp.)
  3. Świadomość, że funkcje nie muszą działać wyłącznie na liczbach...
  4. Umiejętność abstrakcyjnego myślenia
  5. Znajomość indukcji matematycznej

Przyda się oczywiście laptop z zainstalowanym GHC (kompilator Haskella).

Przydatne rzeczy

Małe powtórzenie, definicje, fakty:

  • Funkcją nazywamy każde jednoznaczne przypisanie każdemu elementowi zbioru A jakiegoś elementu zbioru B. Zbiór takich funkcji oznaczamy A → B, lub BA.
  • W powyższym przykładzie zbiór A nazywa się dziedziną funkcji, B przeciwdziedziną, a zbiór {f(x), gdzie x należy do A} zbiorem wartości funkcji f.
  • Jeśli dla dowolnych różnych x, y z dziedziny funkcji f(x) ≠ f(y) to funkcja jest różnowartościowa (f jest iniekcją).
  • Jeśli dla dowolnego y z przeciwdziedziny funkcji f istnieje takie x, że f(x) = y (lub po prostu zbiór wartości jest równy przeciwdziedzinie), to f jest "na" (f jest suriekcją).
  • Jeśli funkcja jest zarówno iniekcją jak i suriekcją, to jest bijekcją.
  • Między zbiorami istnieje bijekcja wtedy i tylko wtedy, gdy mają tyle samo elementów. Jeśli bijekcji nie ma, a istnieje suriekcja z A do B, to elementów w A jest ściśle więcej niż w B (i vice versa). To działa również dla zbiorów o nieskończonej liczbie elementów!
  • Jeśli istnieje funkcja iniekcja z A do B oraz z B do A, to istnieje bijekcja między A i B.
  • Każdą funkcję można zapisać "anonimowo", tj. bez podawania jej nazwy. Używa się do tego tzw. zapisu lambda, np f(x) = x2 można przedstawić równoważnie jako f = (λx.x2) lub f = (λx→x2).
  • Kolejność łączenia: A → B → C = A → (B → C), λa.λ.b.c = λa.(λb.c)

W razie problemów z zadaniami można śmiało podpierać się wiedzą z internetu (Wikipedia jest zazwyczaj wystarczająco legitnym źródłem). Proszę tylko nie szukać pomocy w internecie do zadania nr 6, gdyż łatwo trafić na gotowe rozwiązania... Liczę na waszą uczciwość.