Lab: Funkcje i listy

Tematyka:

• definiowanie prostych funkcji
• ćwiczenie operacji na listach

• Pamiętasz z pierwszego laboratorium jak się sprawdza typy wyrażeń?
• Zapoznaj się z 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 rozwijanie funkcji (currying) (więcej na ten temat będzie w laboratorium 3):

      sum2c :: Int -> Int -> Int
      sum2c m n = m + n

1. Uruchom i przeanalizuj wszystkie przykłady z Wprowadzenia.
2. 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')]

3. 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.
   1. 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.
   2. 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)]

   3. 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.
4. 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
5. 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"

6. 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 = []