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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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ą (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 
     // Niech  oznacza reprezentację bitową liczby n
     w := 1
     for i := 0 to k – 1 do {
       if  = 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:

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:

Zadanie 8

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

Wskazówka: