====== Typy ======
===== Wprowadzenie =====


W Haskellu mamy do czynienia z typowaniem statycznym. Oznacza to, ze już podczas kompilacji typ każdego z wyrażeń jest znany.

W odróżnieniu jednak od standardowych języków programowania (np. Java), Haskell posiada mechanizm inferencji typów, co pozwala kompilatorowi wywnioskować typy wyrażeń, np:

<code haskel>
ghci> :t 'a'  
'a' :: Char  
ghci> :t True  
True :: Bool  
ghci> :t "HELLO!"  
"HELLO!" :: [Char]  
ghci> :t (True, 'a')  
(True, 'a') :: (Bool, Char)  
ghci> :t 4 == 5  
4 == 5 :: Bool  
</code>

Podobnie w przypadku funkcji, chociaż tutaj zaleca się stosowanie deklaracji explicite, chyba że tworzymy bardzo proste funkcje, np:

<code haskell>
mycomp  a b = a < b
ghci> :t mycomp
ghci> Ord a => a -> a -> Bool
</code>


Widzimy tutaj ciekawą rzecz. Sygnatura funkcji została poprawnie rozwinięta, ale nie mamy tutaj żadnego konkretnego typu, znanego z innych języków programowania (Int, Float, Double). Zamiast tego mamy ''%%a -> a -> Bool%%''. Jedynie typ wynikowy wygląda znajomo.
Po lewej stronie tego wyrażenia, tuż przed ''%%=>%%'' pojawia się tzw. ograniczenie klasy ''Ord a'' wymuszające, że typ wejścia dla tej funkcji musi implementować //interfejs// ''Ord''. Do poczytanie o ograniczeniach było na Lab 2 (dla przypomnienia, [[http://learnyouahaskell.com/types-and-typeclasses|tutaj jest ten link do podręcznika]]).

Pozwala to na pewnego rodzaju metaprogramowanie na poziomie typów.

==== Definiowanie własnych type-classes ====

Możemy oczywiście definiować własne //interfejsy// dla typów, czyli type-classy i dziedziczyć istniejące.
Co więcej, mozna je aplikować do istniejących typów.

<code haskell>
{-# LANGUAGE FlexibleInstances #-}

class Listable a where
  toList :: a -> [Int]
  
instance Listable Int where
  toList x = [x]

instance Listable Bool where
  toList True  = [1]
  toList False = [0]
</code>


==== Definiowanie własnych typów ====
W Haskellu robimy to za pomocą słowa kluczowego data.
Na przykład, aby zdefiniować typ opisujący punkt w przestrzeni 2D:

<code haskell>
data NamedPoint = NamedPoint
    { pointName :: String
    , pointX    :: Int
    , pointY    :: Int
    } 
</code>

Z takim type niewiele da sie zrobić. Nie da sie go nawet wyświetlić, ponieważ aby być wyświetlanym typ musi //implementować interfejs// Show, czyli dziedziczyć go.

Na szczęście możliwe jest dziedziczenie typów.

<code haskell>
data NamedPoint = NamedPoint
    { pointName :: String
    , pointX    :: Int
    , pointY    :: Int
    } deriving (Show)
</code>

==== Parametryzowane Typy Danych ====
Parametryzowane typy danych w Haskellu to konstruktory polimorficznych typów.
Typy takie mogą przechowywać wartości wielu różnych typów.
Przykładem takiego typu jest typ Maybe, definiowany jako

<code haskell>
data Maybe a = Nothing | Just a
</code>

Pozwala tworzyć pewnego rodzaju wrapper wokół typu, który w zależności od tego jak pójdą obliczenia, //wyrzuci// ten typ, albo Nothing, ale nadal interpretowany jako Maybe.

<code haskell>
maybe_sqrt :: Float -> Maybe Float
maybe_sqrt x
        | x >= 0 = Just (sqrt x)
        | otherwise = Nothing

</code>

===== Zadania =====
  -  Wykorzystując wiedzę o tym jak tworzyć typeclassy, stwórz jedną o nazwie Intable, która pozwoli na konwersję [Char] to Int poprzez funkcję toInt. Użyj jej jako ograniczenie w funkcji mySuperAdd:<code haskell>
mySuperAdd :: (Intable a, Intable b) => a -> b -> Int
mySuperAdd x y = toInt x + toInt y
ghci> mySuperAdd "123" "12"
135
ghci> mySuperAdd "123" (12::Int)
135
</code>
  - Zbuduj nowy typ Osoba, zawierający imię, nazwisko, pesel. Napisz typeclase umożliwiającą porównywanie osób (po peselu) i sortowanie po nazwisku. Czy da się wyświetlić osobę? Co gdyby dziedziczyć po Eq i Ord? Jak zachowywałoby się porównywanie ''%%==,<=%%''? Poniższe powinny działać poprawnie:<code haskell>
let szymon = Osoba "Szymon" "Bobek" "12345678901"
let bobek = Osoba "S" "Bobek"  "12345678901"
let zenon = Osoba "Zenon" "Adamczyk" "111111111"
ghci> szymon == bobek
True
ghci> szymon > zenon
True</code>
  - Zaimplementuj dwuargumentową funkcję ''find'', która jako argumenty przyjmuje listę oraz predykat. Funkcja ma zwrócić pierwszy element opakowany typem ''Maybe'', który spełnia dany predykat (predykat = funkcja zwracająca wynik typu ''bool''). Jeżeli takiego elementu nie ma, zwracane jest ''Nothing''
  - Zaimplementuj drzewo binarne umożliwiające przechowywanie dowolnych typów, tak aby dało sie stworzyć je w następujący sposób:<code haskell>
myTree :: Tree Int
myTree = Node 3 (Node 1 Empty (Node 2 Empty Empty)) (Node 4 Empty Empty)
</code>
    - insert (wstawienie elementu)
    - empty (sprawdzanie czy drzewo jest puste)
    - search (sprawdzanie czy element jest w drzewie) 
    - toString (wypisującą drzewo w postaci „a(b(d,e),c(,f(g,)))” )
    - leaves ( zwracającą listę liści )
    - nnodes (podającą ilość węzłów)
    - nsum (zliczającą sumę wartości w węzłach)
    - remove (usuwanie elementu)