Datové struktury

Z jednodušších typů můžeme v Haskellu vybudovat další datové struktury, které často bývají označovány jako abstraktní datové typy (ADT). Na minulém cvičení jsme si již ukázali množiny (Data.Set), napsali si vlastní modul pro frontu a zásobník, a nyní si představíme další.

Asociační seznamy (mapy)

V modulu Data.Map jsou definovány mapy. Mapa je vlastně asociační seznam, skládající se z klíče a hodnoty. Pomocí klíče se dostaneme k hodnotě, podobně jako pomocí indexu k prvku v seznamu. Klíčem ale bývá i jiná hodnota než číselného typu. Podobá se tak datovému typu hash z Perlu či slovníku z Pythonu. Vnitřně jsou implementovány pomocí stromu, takže přístup k jednotlivým položkám probíhá v čase O(log n). Popis nejdůležitějších funkcí pro práci se mapami lze nalézt v tutoriálu Naučte se Haskell!.

Pole

Pole se v mnohém podobá seznamu, ale má mnohem rychlejší přístup k jednotlivým položkám. Seznam (často také nazývaný jako lineární seznam) je implementován spojově, čas přístupu k prvku je tedy O(n), u pole se přistupuje k položkám v čase O(1). Nevýhodou pole oproti seznamu je velmi pomalé odebírání a přidávání prvků. Pole je tedy vhodné pro případy, kdy naše data velmi často čteme a zřídkakdy je modifikujeme. Haskell poskytuje více druhů polí, v dokumentaci modulu Data.Array jsou popsány všechny.

Implementace vlastních datových struktur

Datové struktury se vytvářejí pomocí klíčového slova data. Za klíčovým slovem se nachází název datového typu a případné typové proměnné. Poté následuje rovnítko a za ním typové konstruktory, které mohou využívat typové proměnné. Konstruktory se oddělují pomocí svislítka a pomocí nich můžeme vkládat data do struktury. Dekonstruovat strukturu na jednotlivé složky lze pomocí vzorů nebo výrazu case. Datová struktura může odkazovat sama na sebe, tedy být rekurzivní.

Příklady

-- přirozená čísla definovaná pomocí následníka
data Nat = Zero | Succ Nat

-- seznam
data List a = Nil | Cons a (List a)

-- binární strom
data Tree a = Empty | Node a (Tree a) (Tree a)

-- n-ární strom
data NTree a = NNode a [NTree a]

-- výčet (dny v týdnu)
data Days = Mon | Tue | Wed | Thu | Fri | Sat | Sun

Typová synonymyma

Typy si můžeme pojmenovat a vytvořit si tak tzv. typové synonymum pomocí klíčového slova type. Příkladem takového synonyma je type String = [Char], což je definuje, že řetězec je pouhý seznam znaků. Synonyma lze použít i ke tvorbě sofistikovanějšího pojmenování (např. s n-ticemi) a značně zpřehledňují zapisování námi definovaných struktur.

Zavádění nového typu

Klíčové slovo newtype je hybridem mezi předcházejícími dvěma. Umožní nám vytvořit nové typy, jejichž hodnoty se vytváří pomocí datových konstruktorů. Syntakticky se podobá klíčovému slovu data, ale z hlediska použití je to vlastně náhrada type. Podrobnější popis naleznete HaskellWiki a v knížce Real World Haskell.

Záznamy

Záznamy jsou vlastně jenom syntaktickým konstruktem pro zjednodušení práce se složkami datových struktur. Při použití záznamů se jednotlivé složky stanou pojmenovanými položkami a automaticky se vygenerují funkce, pomocí kterých se k nim dá lehce přistupovat. Také pak máme možnost jednodušeji modifikovat jednotlivé složky datové struktury.

Příklad

Datová struktura znázorňující studenta MU a sestávající se z položek: UČO, jméno a příjmení.

data Student = Student Int String String
    deriving (Show)

Tato struktura po přepsání do záznamu vypadá takto:

data Student = Student { sid :: Int
                       , firstName :: String
                       , lastName :: String
                       } deriving (Show)

Příklad použití tohoto záznamu:

> Student 172770 "Pavel" "Dvořák" -- stejná syntaxe jako u datových struktur
Student {sid = 172770, firstName = "Pavel", lastName = "Dvořák"}
> let student = Student {sid=172770, firstName="Pavel", lastName="Dvořák"}
> sid student
172770
> firstName student
"Pavel"
> student {firstName="Jan", lastName="Novák"} -- modifikace položek
Student {sid = 172770, firstName = "Jan", lastName = "Novák"}
> let name s = firstName s ++ [' '] ++ lastName s in name student
"Pavel Dvořák"

← IB016