Václav Končický

Modulový systém

Většina programovacích jazyků má koncept knihoven nebo modulů, aby se mohl program rozdělit do více ucelených části, které se mohou dále využívat mezi programy. Haskell je jeden z nich.

Moduly v Haskellu se skládají z definic funkcí a datových typů. Jeden modul pak typicky odpovídá určité datové struktuře včetně rozhraní k ní, nebo ke skupině funkcí řešící určitý problém. Každý modul pak může pro své potřeby odkázat na další moduly.

Standardní knihovna Haskellu je ve skutečnosti poměrně rozsáhlá a rozdělená na moduly. Modul Prelude obsahuje právě ty nejzákladnější funkce, které se načítají u každého programu automaticky. Funkce, které nejsou úplně základní, ale stále se velmi často využijí, jsou pak schované do specializovanějších modulů.

Název modulu se skládá z několika slov začínající velkými písmeny, která jsou oddělená tečkou. Tyto tečky pak indukují stromovou hiearchii na modulech. Pokud máme třeba modul Data.List pracující se seznamy, tak Data.List.NonEmpty pak přidává rozhraní pro práci s neprázdným seznamem.

Způsob, jakým si můžeme libovolný modul načíst, je jednoduchý. Pokud chceme načíst všechny funkce modulu do aktuálního jmenného prostoru, použijeme prostě import Module.

import Data.List -- Importujeme vše ze seznamů

-- nub :: Eq a => [a] -> [a]; deduplikuje obecný seznam

uniqueCount :: Eq a => [a] -> Int
uniqueCount = length . nub

> uniqueCount [1,2,3,1,3]
3

> tails "abc"
["abc","bc","c",""]

Pokud se ale obáváme kolizí názvů funkcí, můžeme zařídit, aby všechny funkce musely být prefixnuté názvem modulu. Toho můžeme dosáhnout přidáním slova qualified. Jestliže nás zajímá jen určitá podmnožina funkcí, můžeme je vyjmenovat v závorce.

V případě kvalifikovaného importu modulu můžeme navíc tento modul lokálně přejmenovat na kratší název.

import qualified Data.List as List
import Data.Maybe (maybeToList)

> nub [1,2,3,1,3]
error:
    • Variable not in scope: nub
    • Perhaps you meant ‘List.nub’ (imported from Data.List)

> List.nub [1,2,3,1,3]
[1,2,3]

> maybeToList $ Just 3
[3]

> listToMaybe [1]
error: Variable not in scope: listToMaybe

Pokud se stane, že nahrajeme modul, který obsahuje definici funkce, jejíž název se koliduje s jinou funkcí, musíme při jejím zavolání použít název modulu, abychom situaci zjednoznačnili.

Moduly standardní knihovny

Mnoho funkcí, které jsme zatím používaly, byly definované v modulu Prelude, rozhodně ne však všechny. Nyní si projdeme některé z užitečných modulů.

Pro prohledávání (nejen) standardních knihoven můžeme využít službu Hoogle. Ta nám umožňuje vyhledávat moduly, funkce i datové typy a to podle názvu nebo i podle typové signatury.

Standardní knihovna se dělí na více částí. Ta obsahuje balíček Prelude odpovídající vždy importovaným základním funkcím. Dále pak obsahuje (nejen) moduly pod Data, obsahující datové struktury a speciální typy, a moduly pod Control, které nám přidávají ovládací prvky. Kromě toho můžeme chtít využít moduly pod System, které propojují program se systémem.

Pojďme se teď podívat na výčet užitečných modulů pro datové struktury.

Cvičení: Rozmyslete si, jakou signaturu bude mít funkce beroucí seznam, prvek a vrátí seznam proložený tímto prvkem. Potom tuto funkci najděte pomocí Hoogle.

Dále pak máme velmi důležité moduly Control.Applicative a Control.Monad, které nejen definují aplikativní struktury a monády, ale kromě Prelude instanciují mnoho dalších datových struktur jako aplikativní struktury nebo monády. Taktéž tyto moduly obsahují užitečné funkce pro práci s takovými strukturami.

Tvorba vlastního modulu

Už umíme existující moduly nahrávat. Musíme si ještě ukázat, jak takový modul vytvořit.

Hiearchický název modulu musí odpovídat adresářové struktuře a názvu souboru obsahující tento modul. Moduly se hledají v aktuálním podasresáři nebo v adresáři obsahujícím standardní knihovny.

Pokud tohle splníme, tak samotné vytvoření modulu je velmi jednoduché. Na začátek zdrojáku přidáme kouzelnou formuli module Name where. Tento řádek nevyžaduje žádné další odsazení kódu pod ním.

Protože se často může stát, že si pořídíme malé pomocné funkce, které nechceme ukazovat zvenku, můžeme navíc při vytvoření modulu specifikovat, které z funkcí chceme zviditelnit. To provedeme jejich výčtem v závorce.

Pokud chceme zviditelnit ADT, který se skládá z více konstruktorů, můžeme jej zviditelnit celý najednou pomocí užití konstrukce Type(..).

-- MyModule.hs
module MyModule (
    helloWorld,
    MyWorld(..)) where

data MyWorld = Planet | World | Universe

helloMTString Planet = "Hello, Planet!"
helloMTString World = "Hello, World!"
helloMTString Universe = "Hello, Universe!"

helloWorld :: MyWorld -> IO ()
helloWorld = putStrLn . helloMTString

-- main.hs
import MyModule

main = HelloWorld World

U typů se můžeme rozhodnout, že sice zviditelníme typ, ale jeho konstruktory necháme skryté. Pak místo toho dodáme vlastní konstruktory, které třeba zkontrolují určité vlastnosti parametru nebo na jeho základě připraví rovnou složitější strukturu.

module Password (
    PassHash,
    getHash) where

type Hash = Integer
data PassHash = PassHash Hash

hash :: String -> Integer
hash = undefined -- Zahešujeme řetězec

getHash :: String -> PassHash
getHash str = PassHash $ hash str

Trocha algebry: Pologrupy a monoidy

Překvapivě pro mnoho datových struktur se nám stává, že na nich používáme asociativní operaci. Pro čísla máme třeba sčítání a násobení, pro seznamy máme třeba jejich spojování. Této struktury můžeme využít v programování a pořídit si třeba funkci, která všechny prvky spojí asociativní operací.

Pro asociativní operaci platí, že pro spočítání výsledku je jedno, jakým způsobem uzávorkujeme výraz. Všechny výrazy jsou ekvivalentní:

((a <> b) <> c) <> d
(a <> b) <> (c <> d)
a <> (b <> (c <> d))

V algebře máme definici pologrupy (semigroup), což je libovolná struktura, která podporuje asociativní binární operaci. Monoid je pak pologrupa, která navíc definuje neutrální prvek vzhledem k této operaci, tedy takový prvek, který při použití v operaci nezmění druhý člen.

Pokud označíme neutrální prvek písmenem e, pro monoid platí:

a <> (b <> c) = (a <> b) <> c
a <> e = a
e <> a = a

Tyto algebraické struktury můžeme popsat typovými třídami.

class Semigroup a where
    (<>) :: a -> a -> a

class Semigroup a => Monoid a where
    mempty :: a
    mappend :: a -> a -> a
    mappend = (<>)

Cvičení: Definujte seznamy jako instanci monoidu vzhledem ke spojování seznamů. Uvědomte si, že tato operace je asociativní a najděte neutrální prvek.

Co když ale máme typ, který má mnoho monoidových operací? Na číslech třeba máme dva monoidy, a to sčítání a násobení. Zde nás zachrání kouzelné slůvko newtype. Vytvoříme tedy obálkový typ, který obsahuje náš původní typ a kóduje v sobě informaci, kterou operaci chceme.

Nadefinujeme si tedy dva obálkové typy Sum a Product, které popisují sčítání a násobení jako monoidovou operaci.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
-- Aby šlo derivovat Num

newtype Sum a = Sum { getSum :: a }
    deriving (Show, Read, Eq, Ord, Bounded, Num)

newtype Product a = Product { getProduct :: a }
    deriving (Show, Read, Eq, Ord, Bounded, Num)

instance Num a => Semigroup (Sum a) where
    (<>) = (+) -- Sčítání
instance Num a => Monoid (Sum a) where
    mempty = Sum 0 -- 0 + x = x

> getSum $ Sum 4 <> Sum 7 <> mempty
11

Cvičení: Definujte monoid Product nad operací násobení.

Když máme v ruce monoid, můžeme jej použít v libovolné funkci, která monoidicky skládá více prvků. My si pro účely zobrazení, jak se naše asociativní operace bude aplikovat, sestavíme jednoduchý typ popisující strukturu provádění operace. Porušíme tím sice asociativitu operace, ale nás zajímá hlavně to uzávorkování.

data Assoc = Neut | Assoc Assoc Assoc

instance Show Assoc where
    show Neut = "."
    show (Assoc a b) = "(" ++ a ++ " <> " ++ b ++ ")"

instance Semigroup Assoc where
    a <> b = Assoc a b
instance Monoid Assoc where
    mempty = Neut

Ukažme si třeba takové jednoduché složení všech prvků asociativní operací v seznamu. Můžeme uvést možnost pologrupy i monoidu. V případě pologrupy budeme chtít, aby byl seznam neprázdný.

sconcat :: Semigroup a => [a] -> a
sconcat = foldr1 (<>)

mconcat :: Monoid a => [a] -> a
mconcat = foldr (<>) mempty

> mconcat $ map Sum [1..5]
Sum 15

> mconcat $ map (const Neut) [1..3]
(. <> (. <> (. <> .)))

Co je ale zajímavější, můžeme přidat mocnění operací, které využívá toho, že operace je asociativní. Určitě znáte trik binárního mocnění, kde můžeme mocnit v logaritmickém čase?

stimes :: (Integral n, Semigroup s) => n -> s -> s
stimes 0 _ = error "a^0 undefined for semigroups"
stimes 1 x = x
stimes k x
    | even k = stimes (k `div` 2) (x <> x)
    | odd k = x <> stimes ((k - 1) `div` 2) (x <> x)

> stimes 5 (Sum 8)
Sum {getSum = 40}

> stimes 8 Neut
(((. <> .) <> (. <> .)) <> ((. <> .) <> (. <> .)))

Cvičení: Nadefinujte typ pro matice velikosti 2x2 s asociativní operací maticového násobení. Pak využijte stimes k tomu, abyste uměli takovou matici rychle umocnit.

Cvičení: Využijte triku, že n-té Fibonacciho číslo lze spočítat umocněním určité matice na n-tou k tomu, abyste toto číslo spočítali v čase O(log n).

Na závěr si ukažme zajímavou funkci foldMap, která vezme redukovatelnou strukturu, každý prvek převede na prvek monoidu a nakonec tuto strukturu zredukuje do složení všech prvků monoidu.

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty

> foldMap Sum [1..5]
Sum {getSum = 15}

> foldMap (const Neut) [1..5]
(. <> (. <> (. <> (. <> (. <> .)))))

Cvičení: Ukažte, že lze foldr odvodit z foldMap.

Pro redukovatelné struktury platí, že abychom ji instanciovali jako Foldable, stačí naimplementovat foldMap nebo foldr. Ta druhá funkce se pak doimplementuje sama. To se nám může hodit, protože foldMap se často bude implemetovat snadněji. Ukažme si to třeba na stromech.

data Tree a = Ext | Node (Tree a) a (Tree a)

instance Foldable Tree where
    foldMap f Ext = mempty
    foldMap f (Node l x r) = foldMap f l <> f x <> foldMap f r

insert :: Ord a => a -> Tree a -> Tree a
-- Vkládáme prvek do BVS

> foldr insert Ext [1,3,5,7,2,6,4]
Node (Node (Node Ext 1 Ext) 2 (Node Ext 3 Ext)) 4 (Node (Node Ext 5 Ext) 6 (Node Ext 7 Ext))

> foldMap (const Neut) $ foldr insert Ext [1,3,5,7,2,6,4]
(((. <> (. <> .)) <> (. <> (. <> (. <> .)))) <> (. <> ((. <> (. <> .)) <> (. <> (. <> (. <> .))))))

Cvičení: Definujte foldMap na obecných stromech, kde potomci jsou reprezentovaní seznamem.

Sledujeme jezdec na zipu

Seznamy v Haskellu mají tu velkou nevýhodu, že kromě hlavy seznamu se musíme k ostatním prvkům dopracovat nepřímo. To je jistě částečně dáno tím, že seznamy jsou spojové.

Druhý zásadní problém je, že si sice můžeme pořídit ukazatel na libovolný vnitřní prvek seznamu, ale tím ztratíme veškerou informaci o jeho začátku. Navíc, narozdíl od procedurálních jazyků nemůžeme jen tak přepsat vnitřní prvek seznamu, protože kvůli persistenci nám vznikne nový seznam, kterému chybí celý počáteční kus.

Naštěstí, obě nevýhody můžeme obejít. Podívejme se na seznam a vyberme si nějaký jeho prvek x. Představme si, že máme dva seznamy, řekněme jim levé a pravé. Prvky levého seznamu jsou prvky nalevo od x, prvky pravého analogicky včetně x. Navíc, tyto seznamy uspořádáme podle vzdáleností jejich prvků od x. Všimněme si, že tato struktura je analogická zipu s jezdcem. Z toho důvodu ji budeme říkat Zipper.

-- Původní seznam
[1,2,3,4,｢5｣,6,7,8,9]

-- Rozložený seznam
[4,3,2,1]
5:[6,7,8,9]

Zipper je obecný koncept, jak pointerovou datovou strukturu převést na strukturu, ve které si držíme ukazatele na aktuální prvek. Pro seznamy to znamená, že si udržíme levou část seznamu zvlášť, a navíc prvky obrátíme, abychom mohli v konstantním čase vytáhnout nebo zasunout poslední prvek nalevo od aktuálního.

Zipper se v mnoha ohledech chová jako obyčejný seznam, a dá se i na seznam snadno převést tím, že obrácený levý seznam spojíme s hlavou a pravým seznamem. Tudíž mu můžeme snadno přidat instance pro Foldable, Functor a další strukturální třídy.

data Zipper a = Zipper { leftZ :: [a], rightZ :: [a] }

instance (Show a) => Show (Zipper a) where
    show (Zipper l r) = show (reverse l) ++ show (head r) ++ show (tail r)

headZ :: Zipper a -> a
headZ = head . rightZ

fromList :: [a] -> Zipper a
fromList = Zipper []

toList :: Zipper a -> [a]
toList z = (reverse . leftZ) z ++ rightZ z

instance Foldable Zipper where
    foldr f s = (Prelude.foldr f s) . toList

instance Functor Zipper where
    fmap f (Zipper l r) = Zipper (map f l) (map f r)

> fromList [1,4,9]
[]1[4,9]

> toList $ Zipper [1,3] [4,1,5]
[3,1,4,1,5]

Cvičení: Naprogramujte funkci headDefaultZ, která buďto vrátí aktuální prvek nebo, pokud je seznam prázdný, vychozí prvek.

V takové reprezentaci seznamu je nyní velmi snadné se přesunout na sousední prvek oběma směry. Aktuální prvek přesuneme do levého nebo pravého seznamu a z toho opačného si vezmeme hlavu. Dokonce můžeme zipperem simulovat nekonečný seznam, kde posun vlevo nebo vpravo vytáhne "neexistující" předem specifikovaný prvek.

headDefault :: a -> [a] -> a
headDefault x [] = x
headDefault _ l = head l

moveLeft :: Zipper a -> Zipper a
moveLeft (Zipper l r) = Zipper (tail l) (head l:r)

moveLeftInf :: a -> Zipper a -> Zipper a
moveLeftInf def (Zipper l r) = Zipper (drop 1 l) (headDefault def l):r

-- Přepsání prvku, pokud existuje
overwrite :: a -> Zipper a -> Zipper a
overwrite x (Zipper l r) = Zipper l (x:drop 1 r)

> moveLeft $ Zipper [1,3] [4,1,5]
[3]1[4,1,5]

> moveRight $ moveLeftInf 3 $ moveLeftInf 1 $ fromList [4,1,5]
[3]1[4,1,5]

Cvičení: Naprogramujte funkce moveRight a moveRightInf.

Samozřejmě, celý Zipper si můžeme uložit do modulu.

-- Data/Zipper.hs
module Data.Zipper (
    Zipper(..),
    headZ,
    headDefaultZ,
    fromList,
    toList,
    moveLeft,
    moveRight,
    moveLeftInf,
    moveRightInf,
    overwrite
    ) where

[..]

Máme i zip na stromech

Obdobným způsobem můžeme vytvořit Zipper pro stromy. Zde je situace trochu komplikovanější. Aktuálně ukázaný vrchol si můžeme pamatovat přímo jako celý podstrom, z něj též vyčteme jeho levého a pravého syna.

Pokud se však chceme posunout směrem ke kořeni, už potřebujeme další informace. Musíme vědět, jestli je aktuální vrchol levý nebo pravý syn jeho předchůdce (nebo kořen). Dále pak, abychom mohli zrekonstruovat celý strom, musíme si ještě pamatovat obsah rodičovského vrcholu a celý podstrom svého bratra. Stromový Zipper tedy funguje ve výsledku tak, že si kromě aktuálního podstromu pamatuje páteř, kde obratle reprezentují cestu z kořene jako obsahy vrcholů, směry pohybu a podstromy mimo cestu.

Posun vlevo a vpravo je pak jednoduchý. Z aktuálního vrcholu vytvoříme obratel. Posun směrem nahoru pak vezme z páteře spodní obratel a z něj zpětně rekonstruuje vrchol.

data Tree a = Ext | Node (Tree a) a (Tree a) deriving (Show)

data TreeSpine a = LeftParent a (Tree a) | RightParent a (Tree a)

data TreeZipper a = TreeZipper (Tree a) [TreeSpine a]

root :: TreeZipper a -> Bool
root (TreeZipper _ spine) = null spine

moveLeft :: TreeZipper a -> TreeZipper a
-- Vlevo se už nedá posunout
moveLeft t@(TreeZipper Ext _) = t
moveLeft (TreeZipper (Node l x r) up) = treeZipper l (LeftParent x r:up)

-- Nahoru už se nedá posunout
moveUp t@(TreeZipper _ []) = t
moveUp (TreeZipper n (p:up)) = case p of
    LeftParent  x r -> TreeZipper (Node n x r) up
    RightParent x l -> TreeZipper (Node l x n) up

Cvičení: Naprogramujte funkci fromTree, která převede strom na stromový Zipper.

Cvičení: Naprogramujte funkci toTree, která převede stromový Zipper na strom.

Cvičení: Naprogramujte funkci moveRight.

Nyní můžeme mnohem snáze pracovat se stromem, jelikož jej můžeme procházet v libovolných směrech. Ukažme si třeba takovou jednoduchou funkci, která zrotuje aktuální vrchol směrem nahoru. To se může hodit pro vyvažované stromy.

rotateUp :: TreeZipper a -> TreeZipper a

rotateUp t@(TreeZipper _ []) = t
rotateUp (TreeZipper (Node l x r) (p:up)) = case p of
    LeftParent  y rp -> TreeZipper (Node (Node l y rp) x r) up
    RightParent y lp -> TreeZipper (Node l x (Node lp y r)) up

Cvičení: Naprogramujte funkci succ, která pro aktuální vrchol stromového Zipperu najde jeho následníka.

Cvičení: Zkuste si naprogramovat nějakou variantu vyvažovaných stromů s pomocí stromových Zipperů.

Cvičení: Definujte Zipper na obecných stromech, kde potomci jsou reprezentovaní seznamem.