Funkcionální programování - Typy

Ve třetí části seriálu o funkcionálním programování si řekneme o typech výrazů, jak lze z jednodušších typů skládat typy složitější a také něco o polymorfismu.

Celá čísla mají typ Int nebo Integer, desetinná čísla mají typ Float nebo Double, znaky mají typ Char.

Typ můžeme (trochu zjednodušeně) chápat jako množinu hodnot. Skutečnost, že výraz M má typ σ, zapisujeme M::σ. Má-li více výrazů, M₁,…,M_k, stejný typ σ, lze psát M1,…,Mk::σ.

Například:

False, True :: Bool
'a', 'b' :: Char
1 :: Int

pi :: Float
pi  = 3.14159265

prompt :: Char
prompt  = '?'

Typové anotace nejsou v Haskellu povinné. Předchozí definice mohly být zapsány bez nich, interpret nebo kompilátor si umí typy odvodit sám. Existuje však několik důvodů, proč typové anotace uvádět.

• zdrojový text programu je čitelnější
• v typově anotovaném programu se odhalí více typových chyb (typová chyba ve výrazu může být taková, že se pozná, až když je odvozený typ srovnán s typem deklarovaným, a zjistí se rozdíl)
• v některých případech je výpočet podle programu s typovými anotacemi rychlejší, protože automaticky odvozený typ může být příliš obecný a přeložený program by předpokládal výpočet i s hodnotami, které se pak nikdy nevyskytnou<>

Kromě základních typů (Bool, Float,…) můžeme vytvářet typy složené pomocí tzv. typových konstruktorů. Nejdůležitějším typovým konstruktorem ve funkcionálním programování je typový konstruktor –> (šipka). Jsou-li σ, τ dva typy, pak σ–>τ je typ všech (unárních) funkcí, jejichž argument je typu σ a funkční hodnota (výsledek) je typu τ.

Jsou-li ρ, σ, τ tři typy, pak typ ρ–>σ–>τ je typem všech binárních funkcí (tj. funkcí dvou proměnných), jejichž první argument je typu ρ, druhý argument je typu σ a výsledek je typu τ.

Jsou-li σ₁,σ₂,…,σ_n,τ nějaké typy, pak σ1–>σ2–> ... –>σn–>τ je typ všech n-árních funkcí, jejichž argumenty mají po řadě typy σ₁,…,σ_n a jejich funkční hodnota je typu τ.

Například typové anotace některých operací v Haskellu vypadají takto:

toUpper :: Char -> Char
isDigit :: Char -> Bool
not :: Bool -> Bool
(&&), (||) :: Bool -> Bool -> Bool
odd, even :: Int -> Bool

V následujících kapitolách poznáme další typové konstruktory, různé rarity, pomocí nichž se tvoří typy seznamů nebo typy uspořádaných n-tic. Nyní si však můžeme všimnout, že i základní typy jako Bool nebo Int jsou zvláštními případy typových konstruktorů – jsou to tzv. nulární typové konstruktory: abychom pomocí nich vyjádřili typ, stačí je napsat samy o sobě. Neaplikují se na žádný další typ (na rozdíl třeba od šipky, kterou musíme aplikovat na dva typy), proto jsou nulární.

Polymorfní typy

Zatím jsme se setkali jen s typy, které se nazývají monomorfní. Lze je použít vždy jen v kontextu jediného typu. Například monomorfní funkci (tj. funkci monomorfního typu) lze aplikovat vždy jen na argument jediného typu a typ jejího výsledku může být také jen jediný. Takovou monomorfní funkcí je třeba funkce toUpper. Její typ je Char–>Char. Jiným příkladem monomorfní funkce je logická spojka not. Její typ je Bool–>Bool.

Funkce id je tzv. identita. Je definovaná

id x = x

Jaký typ má tato funkce? Kdybychom identitu aplikovali jen na celá čísla, měla by typ Int–>Int. Kdybychom ji aplikovali jen na znaky, měla by typ Char–>Char, kdyby byla aplikována na funkce typu Float–>Bool, měla by sama typ (Float–>Bool) –> (Float–>Bool) atd. Chceme však, aby identita byla univerzálně aplikovatelná na jakoukoliv hodnotu jakéhokoliv typu. Jinými slovy, aby jednou byla typu Int–>Int, podruhé typu Char–>Char, potřetí (Float–>Bool) –> (Float–>Bool) a jindy jakéhokoliv jiného typu a–>a, kde a zastupuje libovolný typ.

Jazyky s parametricky polymorfními typovými systémy (a Haskell mezi ně patří) umožňují zavést tzv. polymorfní typy, v jejichž zápisu kromě typových konstruktorů vystupují i tzv. typové proměnné. Například zmíněná identita má typ

id :: a -> a

V typu a–>a je a typová proměnná zastupující libovolný typ. To znamená, že např. ve výrazu id 3 se typová proměnná a specializuje na typ Int (a celý výraz id 3 má typ Int), ve výrazu id '*' se specializuje na Char (a celý výraz má typ Char) atd.

Podobně jako id existují v Haskellu polymorfní funkce const, flip definované následovně:

const x y = x
flip f x y = f y x

Funkce const vrátí první ze svých dvou argumentů. Tyto dva argumenty však mohou být libovolného typu. Jediným omezením na typ funkce const tedy je, že výsledek musí být stejného typu jako první argument. Je tedy

const :: a -> b -> a

Všimněme si, že kdybychom místo a–>b–>a napsali a–>a–>a, řekli bychom tím, že oba argumenty funkce const musejí mít stejný typ. Tím bychom však typ funkce const zbytečně omezili, protože bychom vyloučili výrazy const toUpper 5 apod.

Funkce flip vyžaduje, aby jejím prvním argumentem byla binární funkce, a této funkci obrací pořadí argumentů. Například flip const True 8 → const 8 True → 8 nebo flip (-) 3 8 → (-) 8 3=8-3 → 5. Její typová anotace (přidělující funkci flip nejobecnější typ) je tedy

flip :: (a -> b -> c) -> (b -> a -> c)

Už dříve jsme se setkali s operátorem skládání funkcí (.)

(f . g) x = f (g x)

Jeho (nejobecnější) typ je

(.) :: (b -> c) -> (a -> b) -> (a -> c)

Tento polymorfní typ říká, že první dva argumenty operátoru (.) jsou funkce, ale typ b argumentu prvé funkce musí být stejný jako typ výsledku druhé funkce. Například ve výrazu (not . odd) 4 má operátor (.) monomorfní typ (specializovaný z polymorfního) (Bool–>Bool)–>(Int–>Bool)–>Int–>Bool, neboť typová proměnná a se specializuje na typ Int, typové proměnné b, c se obě specializují na typ Bool.

V zápisech typů v Haskellu rozeznáme typové proměnné od typových konstruktorů podle toho, že jejich jména vždy začínají malým písmenem. Jména typových konstruktorů jsou buď tvořena speciálními symboly (např. (–>)), anebo začínají velkým písmenem (např. Bool, Char).

V programu Hugs, interpretu Haskellu, si můžeme nechat vypsat typ libovolného výrazu (pokud je tento výraz správně utvořen). Povelem :t (vypiš typ) zjistíme například:

not . not :: Bool -> Bool
const :: a -> b -> a
flip const :: a -> b -> b

Poznamenejme ještě, že s pojmy polymorfismus a polymorfní typ se setkáváme i v objektových jazycích. Tam však nejde o polymorfismus parametrický, ale o tzv. polymorfismus inklusní, mající původ v tom, že jeden typ může být podtypem jiného typu, anebo jedna třída podtřídou jiné třídy. Naproti tomu parametrický polymorfismus ve funkcionálních jazycích spočívá v nahrazení parametru – typové proměnné – libovolným typem.

Kvalifikované typy

Takzvané kvalifikované typy jsou jistým zobecněním parametricky polymorfních typů: Parametricky (plně) polymorfní typ říká, že za typovou proměnnou lze dosadit zcela libovolný typ. Někdy je však vhodné polymorfismus omezit a za typovou proměnnou dovolit dosadit jen typy z určité množiny typů, neboli z typové třídy.

Nechme si vypsat třeba typ operace sčítání (+).

(+) :: Num a => a -> a -> a

Tento zápis typu říká, že (+) je typu a–>a–>a , v němž za typovou proměnnou a lze dosadit každý takový typ, který náleží do typové třídy Num. V té jsou číselné typy Int, Integer, Float, Double, Rational a další (uživatelsky definované) typy do ní lze přidávat.

Podobně typ operace (<)  (menší než) je

(<) :: Ord a => a -> a -> Bool

V typové třídě Ord jsou takové typy, jejichž hodnoty můžeme lineárně uspořádat, např. většina číselných typů (ale už ne třeba typ komplexních čísel), nebo typ Char – znaky lze seřadit podle abecedy, ale také uspořádané dvojice či posloupnosti – ty lze řadit lexikograficky.

Řekli jsme, že kvalifikované typy jsou zobecněním polymorfních typů. Podle toho, kolik typů je v typové třídě, která typ kvalifikuje, můžeme vyjádřit „míru polymorfismu“ – celou škálu od monomorfních až k plně polymorfním typům. Když budeme mít typovou proměnnou b, která bude kvalifikovaná typovou třídou ClassBool a tato třída bude obsahovat jediný typ Bool, pak typ ClassBool b => b popisuje tentýž typ jako Bool. Naopak, když zavedeme typovou třídu All a řekneme, že má obsahovat všechny typy, pak třeba kvalifikovaný typ All c => c->c popisuje stejnou množinu typů, jakou popisuje plně parametricky polymorfní typ c->c. Toto je ovšem spíše jen teoretická úvaha – v obou případech použijeme raději monomorfní resp. plně polymorfní typ, než bychom zaváděli jednoprvkovou resp. univerzální typovou třídu; chceme jen ukázat, že kvalifikované typy jsou silným prostředkem schopným popsat jak monomorfní, tak polymorfní typy a navíc i cokoliv mezi tím.

Definice nových typů

V Haskellu lze také vytvářet nové uživatelské typy, anebo dávat nová jména existujícím typům. Nově pojmenovat typ lze pomocí deklarace type. Můžeme dát třeba nové jméno typu Bool nebo pojmenovat typ uspořádaných dvojic reálných čísel:

type  PravdivostniHodnoty  =  Bool
type  Complex  =  (Double,Double)

Takto lze zavádět i nové typové konstruktory:

type  BinarniOperace a  =  a -> a -> a

(.+.)  :: BinarniOperace Int
m .+. n  =  (m + n) `mod` 10

implikace  ::  BinarniOperace PravdivostniHodnoty
implikace p q  =  not p || q

Deklarací type pouze dáváme nové jméno existujícímu typu nebo typovému konstruktoru. Je však také možné zavést nový tzv. datový typ se vším všudy, zejména se všemi hodnotami tohoto typu. K tomu se však potřebujeme seznámit s datovými strukturami, jako jsou n-tice, seznamy, stromy… Proto si definice nových datových typů a datových struktur necháme na některou z dalších částí.

Shrnutí

• Každá hodnota v Haskellu má svůj typ. Typy hodnot vyjadřujeme typovými anotacemi.
• Nejjednodušší typy jsou vyjádřeny nulárními typovými konstruktory.
• Složitější typy se tvoří ze základních pomocí dalších typových konstruktorů. Ve funkcionálním programování hraje klíčovou roli binární typový konstruktor (->).
• Typy mohou být parametricky polymorfní, v jejich zápisu vystupují typové proměnné.
• Polymorfismus může být ohraničen – kvalifikované typy zužují výběr typů, které lze dosadit za typové proměnné v zápisu typu.
• Složitější typy nebo typové konstruktory si můžeme označit jménem pomocí deklarace type.