====== Lab: Funkcje i listy ======
Tematyka:
* definiowanie prostych funkcji
* ćwiczenie operacji na listach
===== Wprowadzenie =====
* Pamiętasz z pierwszego laboratorium jak się sprawdza typy wyrażeń?
* Zapoznaj się z [[http://learnyouahaskell.com/types-and-typeclasses|rozdziałem z podręcznika dotyczącym typów]], w szczególności z sekcją "Typeclasses 101", aby dowiedzieć się w jaki sposób można definiować "interfejsy" (typy funkcji). Od teraz chcemy do każdej funkcji (poza małymi pomocniczymi) definiować typy.
* 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
ostatni warunek możemy też zapisać z wykorzystaniem słowa kluczowego `otherwise` (else z Javy): sign :: Double -> Double
sign x | x > 0 = 1
| x == 0 = 0
| otherwise = -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
* Wykorzystując [[https://wiki.haskell.org/Currying|rozwijanie funkcji (currying)]] (więcej na ten temat będzie w laboratorium 3):sum2c :: Int -> Int -> Int
sum2c 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:
* supercyfra 8 = 8
* supercyfra 77 = supercyfra (7+7) = supercyfra 14 = supercyfra (1+4) = supercyfra 5 = 5
* supercyfra 1234 = 1
* supercyfra 3912 = 6
- 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 = []