Paradygmaty programowania/Ćwiczenia 6: Programowanie funkcyjne — przegląd

Zadanie 1

Napisać funkcję w Schemie, która zlicza zera w podanej liście liczb. Lista może zawierać zagnieżdżone podlisty itd. — zliczyć należy wszystkie zera.

Zadanie 2

Napisać funkcję w Schemie, która usuwa z podanej listy wszystkie niezagnieżdżone wystąpienia podanego atomu.

Zadanie 3

Rozważmy następującą funkcję w ML-u:

     fun f(ys, 0)    = []
       | f(x::ys, z) = if z < x
           then f(ys, z)
           else (z mod x) :: f(x::ys, z mod x);

Jaki będzie wynik przy wywołaniu f ([9, 2, 1], 57)?

Zadanie 4

Rozważmy następującą funkcję w Haskellu:

     fx []      = 3
     fx (x : y) = x + fx y

Jaki będzie wynik aplikacji fx do listy [1, 4..10]?

Zadanie 5

Napisać w dowolnym języku funkcyjnym funkcję obliczającą $x^n$ (a) za pomocą algorytmu „naiwnego”, tzn. przez n – 1 mnożeń, (b) za pomocą algorytmu „bitowego”. Idea tego algorytmu jest następująca:

     // Algorytm oblicza $x^n$
     // Niech $n_{k-1}\dots n_1{n}_0$ oznacza reprezentację bitową liczby n
     w := 1
     for i := 0 to k – 1 do {
       if $n_i$ = 1 then w := w*x
       x := x*x
     }
     return w

Zadanie 6*

Przyjrzyj się poniższej funkcji w Haskellu, obliczającej n-ty wyraz ciągu Fibonacciego. Czy to jest rozsądnie napisana funkcja, czy też można to zrobić (znacznie) lepiej. Jeśli tak, zrób to. Czy odpowiedź na to pytanie zależy od tego, czy piszemy w języku funkcyjnym?

     fib 0 = 0
     fib 1 = 1
     fib n = fib (n–1) + fib (n-2)

Wskazówka:

Wyliczanie elementów ciągu Fibonacciego za pomocą takiej rekurencji to generalnie zły pomysł, prowadzący do fatalnej złożoności obliczeń — liczba operacji potrzebnych do wyliczenia n-tego wyrazu jest rzędu 2n. Co prawda można sobie wyobrazić bardzo sprytny kompilator, który przearanżuje te obliczenia tak, by uzyskać mniejszą złożoność, ale w ogólności nie należy raczej na to liczyć... Choć trzeba przyznać, że w języku funkcyjnym kompilator jest w nieco lepszej sytuacji, gdyż nie musi się obawiać efektów ubocznych funkcji.

W języku niefunkcyjnym lepiej zastosować prosty algorytm iteracyjny, który będzie wyliczał kolejne wyrazy ciągu korzystając z dwóch poprzednich zapisanych w zmiennych roboczych. W Haskellu trzeba zastosować strategię „łączenia w n-tki” — tutaj w pary — a z par brać pierwszy element. O łączeniu w n-tki będzie mowa w wykładzie poświęconym Haskellowi:

     fibS 0     = (0, 1)
     fibS (n+1) = (x, y), where (x, y) = fibS n
     fib n      = fst (fibS n)

Zadanie 7

Napisz jak najprostszą funkcję w Haskellu odwracającą podaną listę. Ile operacji ona potrzebuje, by odwrócić listę o długości n?

Wskazówka:

Można tak...

     odwr []       = []
     odwr (x : xs) = odwr xs ++ [x]

Zadanie 8

Funkcja z poprzedniego zadania zapewne potrzebuje O($n^2$) operacji, by odwrócić n-elementową listę. Napisz funkcję, która potrzebuje tylko $O(n)$ operacji.

Wskazówka:

Wskazówki szukaj w wykładzie poświęconym Haskellowi.