To jest stara wersja strony!
Lab: Funkcje i listy
Wprowadzenie
W Haskellu wszystko opisujemy za pomocą funkcji (rozumianych jako funkcje matematyczne), więc w szczególności możemy definiować funkcje rekurencyjne, funkcje określone kilkoma wzorami czy funkcje przyjmujące więcej niż jeden argument:
Ciąg Fibonacciego możemy zdefiniować jako następującą funkcję matematyczną działającą na zbiorze liczb całkowitych (Z):
fib : Z --> Z
fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
W bardzo podobny sposób możemy tę funkcję zapisać w Haskellu:
fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Funkcja signum zdefiniowana jest jako funkcja składająca się z trzech wzorów:
sign : R --> R
sign(x) = 1, dla x > 0
sign(x) = 0, dla x = 0
sign(x) = -1, dla x < 0
Zapisanie jej w Haskellu jest bardzo proste:
sign :: Double -> Double
sign x | x > 0 = 1
| x == 0 = 0
| x < 0 = -1
Najprostsza funkcja dodająca dwie liczby całkowite może być zdefiniowana jako:
sum : Z x Z --> Z : sum(m, n) = m + n
W Haskellu możemy ją zrealizować na co najmniej trzy podstawowe sposoby:
Wykorzystując krotki:
sum2a :: (Int, Int) -> Int
sum2a (m, n) = m + n
Wykorzystując listy:
sum2b :: [Int] -> Int
sum2b (m:n:_) = m + n
-
Zadania
Uruchom i przeanalizuj wszystkie przykłady z Wprowadzenia.
Na rozgrzewkę: napisz własną implementację funkcji
zip - znasz ją już zapewne z Pythona, tak samo działa w Haskellu
jako argument przyjmuje dwie listy, w wyniku zwraca listę dwuelementowych krotek: w pierwszej krotce znajdują się pierwsze elementy z obydwu list, w drugiej znajdują się drugie elementy, itd.
Przykłady:
zip [1,2,3] [4,5,6] = [(1,4),(2,5),(3,6)]
zip [1,2,3] "abc" = [(1,'a'),(2,'b'),(3,'c')]
Wyobraźmy sobie eksperyment biologiczny, w którym wykorzystuje się dwa rodzaje bakterii. Co sekundę bakteria typu A dzieli się na dwie bakterie typu B, a bakteria typu B dzieli się na jedną typu A i jedną typu B. Załóżmy, że bakterie nie umierają podczas eksperymentu.
Na początku eksperymentu (w momencie 0) mamy dokładnie dokładnie dwie bakterie: jedną typu A i jedną typu B. Napisz funkcję, która wyliczy liczbę bakterii obydwu typów w czasie s sekund od rozpoczęcia eksperymentu.
Obejrzyj wartości funkcji dla n ∈ {5, 7}
spodziewany wynik:
map bakteria [0..7] = [(1,1),(1,3),(3,5),(5,11),(11,21),(21,43),(43,85),(85,171)]
W jaki sposób zmienią się wyniki, jeżeli eksperyment rozpoczniemy posiadając dokładnie dwie bakterie typu A? Napisz drugą funkcję, która to zamodeluje.
Napisz funkcję liczącą wartość supercyfry dla zadanego argumentu. Supercyfrę dla danej liczby całkowitej x definiujemy jako:
- x, jeżeli x jest jednocyfrową liczbą
- supercyfrę od xx, gdzie xx to suma cyfr liczby x (dla x mających co najmniej dwie cyfry)
Przykłady:
Napisz funkcję, która usuwa powtarzające się elementy z danego stringa (zostawia tylko pierwsze wystąpienie elementu)
Przykłady:
usunduplikaty "accabb" = "acb"
usunduplikaty "abc" = "abc"
Napisz funkcję, która zwraca elementy, które na liście wejściowej pojawiły się co najmniej n razy. Funkcja powinna zwracać pustą listę, gdy nie ma takich elementów.
Przykłady:
conajmniejn [4,5,2,5,4,3,1,3,4] 2 = [4,5,3]
conajmniejn [4,5,2,5,4,3,1,3,4] 4 = []