Monady i 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:

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  

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

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

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, 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.

{-# 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]

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:

data NamedPoint = NamedPoint
    { pointName :: String
    , pointX    :: Int
    , pointY    :: Int
    } 

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.

data NamedPoint = NamedPoint
    { pointName :: String
    , pointX    :: Int
    , pointY    :: Int
    } deriving (Show)

Monady

Monady w Haskellu to konstruktory polimorficznych typów. Typy takie mogą przechowywać wartości wielu różnych typów.

Najczęściej używana monadą jest Maybe, definiowana jako

data Maybe a = Nothing | Just a

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.

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

Zadania

  1. 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:
    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
  2. 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:
    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
  3. Zaimplementuj funkcję, która będzie wykonywać pewien predykat na elementach listy i w przypadku gdy predykat zwróci True, funkcja zwróci dany element listy, lub Nothing jeśli predykat nie zakończy się True na żadnym z elementów listy. Np. możesz użyć predykatu porównującego osoby po peselu co umożliwi wyszukiwanie pierwszej osoby w liście o danym peselu.
  4. Zaimplementuj drzewo binarne umożliwiające przechowywanie dowolnych typów, tak aby dało sie stworzyć je w następujący sposób:
    myTree :: Tree Int
    myTree = Node 3 (Node 1 Empty (Node 2 Empty Empty)) (Node 4 Empty Empty)
    1. insert (wstawienie elementu)
    2. empty (sprawdzanie czy drzewo jest puste)
    3. search (sprawdzanie czy element jest w drzewie)
    4. toString (wypisującą drzewo w postaci „a(b(d,e),c(,f(g,)))” )
    5. leaves ( zwracającą listę liści )
    6. nnodes (podającą ilość węzłów)
    7. nsum (zliczającą sumę wartości w węzłach)
    8. remove (usuwanie elementu)*
pl/dydaktyka/pp/haskell/lab-monads-types.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0