Haskell

03.09.2003 17:56 | blackhole

Haskell je striktně funkcionální programovací jazyk. Toto znamená, že vše veškeré programování se v něm děje funkcionálně (snad kromě monádů). Sám o sobě by se jazyk dal definovat jako polymorfní funkcionální jazyk s lazy vyhodnocováním a nutným explicitním sekvencováním \"side effects\" (pro srozumitelnost to uvedu v angličtině: Haskell is polymorphic functional language with lazy evaluation which demands explicit sequencing of side effects

Tyto vlastnosti z něj tvoří jednak velmi zajímavý jednak nadmíru užitečný jazyk. Dovolte mi vám ho představit...

Na začátek uvedu, že veškeré funkcionální jazyky jsou založeny na matematické teorie tzv. Lamda kalkulu. Toto odvětví matematiky založil Alfonso Church a snažil se v něm podchytit funkce z hlediska jich samotných. Tj. ne jako relaci mezi vstupem a výstupem, ale jako jakousi posloupnost pravidel, resp. dalších funkcí. Tato teorie je docela složitá a není lehké ji pochopit (minimálně tedy pro mne), ale pro dnešní moderní funkcionální jazyky (jako Haskell bezesporu je) to ani není nutné. Ale rozhodně to neuškodí.

Řekl jsem, že Haskell je funkcionální - to znamená, že všechno jsou v něm funkce a výpočet probíhá deterministicky. Základní atomické datové typy jsou stejné jako všude jinde - Int, Char, Bool. Dalším velmi silně podporovaným typem je seznam. Není to nutné (jako např. v Lispu) ale je velmi dobré chápat všechno jako seznam. Základní denotace seznamu je takováto:
konstruktory: [] a :
prázdný seznam: []
neprázdný: 1:2:3:[] = [1,2,3] = 1:[2,3]
operátor : má funkci spojovatele prvku a seznamu (cons v lispu)
dalším typem jsou takzvané n-tice:
konstruktor: ,
(a,b,c)
slouží pro takzvanné \"curried\" funkce (funkce u kterých potřebujete předat
všechny parametry zaráz)
ovšem hlavní jsou v Haskellu funkce:
f a1 a2 ... an
je důležité upozornit, že Haskell zná pouze funkce jedné proměnné, funkci více proměnných, ale lze získat kompozicí n funkcí jedne proměnné. (Haskell to umí automaticky) - toto má tu výhodu, že můžete specifikovat funkceparciálně.

Typ funkce:
Haskell je polymorfní jazyk se specifickým přístupek k typům. Přestože je možné specifikovat typ \"natvrdo\", jelepší specifikovat v signatuře funkce pouze polymorfní typy (např. s udáním třídy typu).
příklad - spojení seznamů
merge :: [a] -> [a] -> [a]
merge l1 [] = l1
merge [] l2 = l2
merge l1 l2 = merge (tail l1) (head l1):l2
jak vidět specifikoval jsem funci merge jako polymorfní (typ \"a\" je polymorfní a lze za něj \"dosadit\" cokoliv). Signatura lze číst takto: funkce merge je funkcí dvou proměných stejného typu (seznam prvků typu a) a jejím výsledkem je opět ten samý typ. Na daném příkladu si lze všimnou i jiné věci - pattern matchingu - pro daný
stav výpočtu se použije ta deklarace funkce, kterou lze unifikovat se stavem parametrů (postupuje se zhora dolů). Také stojí za pošimnutí deklarativní povaha programu.

Tímto se dostáváme k základním programovým konstrukcím Haskellu. Mohli jste si všimnout, že pro iteraci se používá rekurze. Pro větvení lze použít buď pattern matching (pozor! není vždy vhodné - viz. ADT), nebo takzvané \"strážené rovnice\" na našem příkladu funkce merge by to vypadalo takto:

merge :: [a] -> [a] -> [a]
merge l1 l2 | l1 == [] = l2
| l2 == [] = l1
| otherwise = merge (tail l1) (head l1):l2

syntaxe i sémnatika jsou myslím samovysvětlující. Též stojí za zmínku použití tzv. anonymních proměných - to jsou proměnné, jež jsou nutné syntakticky, nicméně v dané chvíli význam nemají a jejich obsah nás nezajímá. např. kdo_je_lepsi neologism _ = neologism (protože já jsem lepší než kdokoliv a proto není podstatné s kým jsem srovnávánení podstatné s kým jsem srovnáván) Další věcí jsou operátory - ty jsou jak známo infixové. Infixový zápis je dost špatná věc se kterou se většina funkcionálních jazyků vypořádává tak, že je prostě nemá. Haskellinfixové operátory má. Zavádí je prostým uvozením jména funkce o uvozovek. aka:

mod a b = a `mod` b

To by k syntaxi zhruba stačilo (protože mne nebaví to psát a protože se to dá lépe nastudovat jinde). Teď uvedu několik věcí které činí funkcionální programování (zde v podání Haskellu) nekonečně nadřazené imperativnímu.

Za prvé jsou to HOFs - higher order functions - funkce vyšších řádů. Tyto by se daly popsat asi jako funkce, jejichž některý parametr(y) jsou zase funkce. jedna taková funkce je např. map. Map je funkce definovaná takto:

map f [] = []
map f (x:xs) = f x ++ map f xs

tj. aplikuje funkci f na každý prvek seznamu. Její sílu vám ukážu na následujícím příkladu - součet prvků matice.

sumMatrix :: [[a]] -> Int
sumMatrix = sum . map sum

tady platí, že matice je seznam seznamů. funkce sum je předdefinovaná a sečte seznam. Operator . (tečka) je operátor kompozice funkcí.
Další hezkou HOF je foldl:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

tato funkce bere prvky seznamu zleva a aplikuje na tento prvek a parametr funkci f. tímto se dají definovat velmi zajímavé věci. max = foldl maximum lowest_num kde maximum je funkce, která ze dvou čísel vrátí to větší a lowest_num je nulární funkce (konstanta) značící nejnižší číslo.

fact n = foldl (*) 1 [1..n] -- faktorial
sum = foldl (+) 0 -- součet řady

složitější příklad:
type Vector = [Integer]
type Matrix = [Vector]

columns :: Matrix -> Matrix
columns y = [ [ z!!j | z <- y ] | j <- [0..s] ]
where s = length (head y) - 1

vecProd :: Vector -> Vector -> Int
vecProd x y = sum (map ((x,y) -> x*y) (zip x y

matProd :: Matrix -> Matrix -> Matrix
matProd x y = columns [ [vecProd (x!!i) (yT!!j) | i <- [0..s]] | j <- [0..s]]
where s = length (head x) - 1
yT = columns y

tento program násobí matice... je to docela hezká ukázka, mimojine proto, že jsem vlastně jen opsal nasobení matic ze skript... myslím, že je to až průzračně jasné a snadno pochopitelné (součin matice A a matice B definujeme jako matici C(cij) kde prvek cij je definován jako skalární součin řádku i matic A a sloupce j matice B)
dále si program rozšíříme tak aby toho uměl víc... funkce vecProd je škaredá pač není obecná, zavedemy tedy:

vecOp f x y = map ((x,y) -> (f x y)) (zip x y

a vecProd změníme na: vecProd = vecOp (*

toto sice v našem programu nebude mít zhola žádné výhody, ale je to dobré z hlediska čistoty, navíc by se to mohlo hodit v budoucnosti (např. k různým heuristikám urychlujícím výpočet

funkce na výpočet submatice:
dropNth n x = (take n x) ++ drop (n+1) x
subDet x (i,j) = dropNth i (map (dropNth j) x)
samotný determinant:
det x | length x == 1 = head (head x)
| otherwise = sum (vecOp (*) (x!!0) complements)
where complements = [ algCmpl x (0,i) | i <- [0..(length x )]]
algCmpl x (m,n) = (-1)^(m+n)*(det (subDet x (m,n

jde o výpočet determinantu pomocí Laplaceova rozvoje, kde algCmpl je
algebraický doplňek... nyní ještě doplníme funkci na výpočet inverzní matice
invMat x = columns [[(algCmpl x (i,j))/(det x) | j <- [0..s]] | i <- [0..s]]
where s = length x - 1
(celý program je ke stažení na hysteria.sk/~neologism/matrix.hs) kdybychom, teď chtěli například zadefinovat dělení matic, pak to uděláme velmi
jednoduše:
matDiv x y = matProd x (invMat y)
no, nakonec neodolám a ukážu vám k proč bylo dobré předefinovat vecProd na
vecOp...
řekněme, že chceme funkci na sčítání matic... není nic jednoduššího:
matPlus = vecOp (vecOp (+)) - začínáte vidět výhody?
(podotýkám, že funkce vecOp je v Haskellu standardně definována pod jménem zipWith... ovšem mně se zdá můj zápis hezčí, ie. složitější) Podotýkám, že celý program jsem v podstatě opsal z matematických skript, pouze jsem ho přeložil z češtiny do Haskellu. Jistě si všimnete toho, že zápis programu je v podstatě normální matematický zápis - velmi výhodná věc. Další věcí, která stojí za zmínku (i když spíš z obecného hlediska, než že by to bylo něco Haskellovského) je docela zajímavá nepřímá rekurze ve funkci det.

Doufám, že aspoň některé z vás jsem Haskellem zaujmul a začnou jej zkoumat samy. Ona zde presentovaná úkazka (hraní si s maticemi) má pouze demonstrovat některé nástroje jimiž haskell disponuje... nemá demonstrovat jejich ideální použití. Chtěl jsem pouze ukázat trošku z flexibility a expresivnosti, která se jinde nevidí

P.S. check www.haskell.org to learn more
P.S2. mimochodem, zde presentovana abstraktnost je jeden z duvodu proc se budu do krve hadat ze asm a podobne low-level kravoviny jsou nahovno...neologism