Haskell Hero

map je binární funkce, která si jako argumenty bere:

• unární funkci f, která z a dělá b
• seznam s typu [a], na jehož prvky se dá aplikovat funkce f

Výraz map f s se vyhodnotí na seznam s, na jehož každý prvek je aplikována funkce f, typu [b].

Definice

map         ::  (a -> b) -> [a] -> [b]
map _ []     =  []
map f (x:s)  =  f x : map f s

Příklady

map (+1) [1,2,3]  ~>* [2,3,4]
map even [1,2,3]  ~>* [False, True, False]
map (*8) []       ~>* []

Příklad vyhodnocení

Teď nastává ten okamžik, kdy využijeme přirovnání seznamu k vláčku. Pokud si seznam představíme jako vláček, pak funkce map je tunel.

Vláčkový model	Haskell
Mějme funkci naloz, která dělá to, že na prázdný vagónek naloží uhlí a plný vagónek nechá plný.	Mějme funkci naloz, která je definována následovně: naloz :: Bool -> Bool naloz False = True naloz True = True
Tunel se chová následovně: Pokud je v něm vagónek, naloží na něj uhlí a posune vláček. Pokud je v něm mašinka, nechá ji projet a ukončí svou činnost.	Funkce map se chová následovně: Pokud je aplikována na funkci f a neprázdný seznam x:s, na první prvek seznamu, čili na x, aplikuje funkci f, výsledek připojí na začátek výsledného seznamu a pokračuje aplikací funkce map na zbytek seznamu s. Pokud je aplikována na libovolnou funkci a prázdný seznam, vyhodnotí se na prázdný seznam.
Pošleme tedy do tunelu, který nakládá uhlí, vláček, který má tři prázdné vagónky.	Aplikujme tedy funkci map na funkci naloz a na seznam [False,False,False].
V tunelu je prázdný vagónek, takže se na něj naloží uhlí a vláček se posune.	Jelikož je druhým argumentem neprázdný seznam, vyhodnocujeme podle druhé klauzule funkce map. Aplikujeme funkci naloz na první prvek seznamu, což je False. Tím nám vznikne True, které připojíme na začátek a pokračujeme vyhodnocováním map naloz [False,False].
V tunelu je prázdný vagónek, takže se na něj naloží uhlí a vláček se posune.	Opět vyhodnocujeme podle druhé klauzule. Za x se dosadí False, za s se dosadí [False]. Na začátek se tedy připojí naloz False, což se vyhodnotí na True, a pokračuje se vyhodnocováním map naloz [False].
Stejná situace, naloží se uhlí a posune se vláček.	Opět podle druhé klauzule: Za x se dosadí False, za s se dosadí [], čili vyhodnocení vypadá následovně: map naloz (False : []) ~> (naloz False) : map naloz []
V tunelu je mašinka, která jen projede, a jsme hotovi.	Výraz map naloz [] se vyhodnotí podle první klauzule na prázdný seznam.
Výsledkem je vláček se třemi naloženými vagónky.	Výsledkem je tříprvkový seznam [True,True,True].

filter je binární funkce. Jejími argumenty jsou:

• podmínka p, což je funkce, která z čehokoli udělá pravdivostní hodnotu, její typ je tedy a -> Bool
• seznam s, jehož prvky se dají vložit do funkce p, typ tohoto seznamu je [a]

Výraz filter p s se vyhodnotí na seznam, jehož prvky budou prvky seznamu s, které vyhovují podmínce p.

Definice

filter         ::  (a -> Bool) -> [a] -> [a]
filter _ []     =  []
filter p (x:s)  =  if p x then x : filter p s
                          else     filter p s

Příklady

filter (>5) [1,6,2,8,5,7]       ~>*  [6,8,7]
filter even [1,6,2,8,5,7]       ~>*  [6,2,8]
filter not  [False,True,False]  ~>*  [False,False]

Příklad vyhodnocení

Funkci filter můžeme, jako funkci map, znázornit tunelem. Bude se ale chovat trochu jinak.

Vláčkový model	Haskell
Mějme funkci jePlny, která zjišťuje, zda je vagónek do ní vložený naložený uhlím.	Mějme funkci jePlny, která je definována následovně: jePlny :: Bool -> Bool jePlny True = True jePlny False = False nebo zkráceně jePlny :: Bool -> Bool jePlny x = x nebo ještě kratčeji jePlny :: Bool -> Bool jePlny = id
Tunel se chová následovně: Pokud funkce jePlny zjistí, že vagónek v tunelu je naložen uhlím, pustí jej z tunelu a posune vláček. Pokud funkce jePlny zjistí, že vagónek v tunelu je prázdný, vagónek zahodí a posune vláček.	Funkce filter se chová následovně: Pokud je aplikována na funkci p a neprázdný seznam x:s, postupuje se následovně: Pokud se aplikace p x vyhodnotí na True, připojí se prvek x na začátek výsledného seznamu a dále se vyhodnocuje výraz filter p s. Pokud se aplikace p x vyhodnotí na False, prvek x se zahodí a rovnou se vyhodnocuje filter p s. Pokud je aplikována na jakoukoli funkci a prázdný seznam, vyhodnotí se na prázdný seznam.
Do tunelu, který vybírá pouze naložené vagónky, tedy pošleme třívagónkový vláček s vagónky: naložený, prázdný, naložený.	Aplikujme tedy funkci filter na funkci jePlny a seznam [True,False,True].
V tunelu je naložený vagónek, který tím pádem chceme ponechat i ve výsledném vláčku. Takže se tento vagónek dostane z tunelu a posune se vláček.	Druhým argumentem je neprázdný seznam, vyhodnocuje se podle druhé klauzule. Aplikace funkce p na x, po dosazení jePlny True, se vyhodnotí na True. if-výraz se tedy vyhodnotí na then-větev, což je x : filter p s. Po dosazení True : filter jePlny [False,True].
Nyní je v tunelu prázdný vagónek, který ve výsledném vláčku nechceme. Takže jej zahodíme a posuneme vláček.	Opět je druhým argumentem neprázdný seznam, vyhodnocuje se podle druhé klauzule. Protože se výraz jePlny False vyhodnotí na False, if-výraz se vyhodnotí na else-větev, čili na výraz filter jePlny [True].
V tunelu je naložený vagónek, takže jej pošleme dál a posuneme vláček.	Opět se vyhodnocuje podle druhé klauzule. Tentokrát je podmínka p splněna, takže se if-výraz vyhodnotí na then-větev, čili na výraz True : filter jePlny [].
V tunelu je mašinka, kterou necháme projet a jsme hotovi.	Druhým argumentem je prázdný seznam, takže vyhodnocujeme podle první klauzule na prázdný seznam.
Výsledkem je vláček se dvěma naloženými vagónky.	Výsledkem je dvojprvkový seznam [True,True].

Popis

Funkce take x s vrátí seznam prvních x prvků ze seznamu s.

Definice

Poznámka: Zde uvedená definice je zjednodušená. Ve skutečnosti může take jako první argument přijmout i záporné číslo. V takovém případě se vyhodnotí na prázdný seznam.

take 0 _     =  []
take _ []    =  []
take n (x:s) =  x : take (n-1) s

Příklady

take 3 [1,2,3,4,5]     ~>*  [1,2,3]
take 4 "Ahoj ty tam!"  ~>*  "Ahoj"
take 0 [True, True]    ~>*  []
take 5 []              ~>*  []

Výraz drop n s se vyhodnotí na seznam s bez prvních n prvků.

Definice

drop 0 s      =  s
drop _ []     =  []
drop n (_:s)  =  drop (n-1) s

Příklady

drop 2 [1,2,3,4,5]    ~>*  [3,4,5]
drop 0 [1,2,3,4,5]    ~>*  [1,2,3,4,5]
drop 8 [True, False]  ~>*  []

Funkce repeat x vytvoří nekonečný seznam x.

[x,x,x,x,x,x,x, ... ]

Definice

repeat   ::  a -> [a]
repeat x  =  x : repeat x

Příklady

repeat 1              ~>*  [1,1,1,1,1, ... ]
repeat 'c'            ~>*  "ccccccccc ... "
repeat [True, False]  ~>*  [[True, False],[True, False], ... ]

Poznámka

Pokud si necháme vyhodnotit například výraz repeat 1, Hugs začne do nekonečna vypisovat seznam jedniček, dokud jej nezastavíme kombinací kláves Ctrl+C.

replicate n x vytvoří n-prvkový seznam x-ů.

Definice

replicate     ::  Int -> a -> [a]
replicate n x  =  take n (repeat x)

Příklady

replicate 4  1          ~>*  [1,1,1,1]
replicate 3  "Haskell"  ~>*  ["Haskell","Haskell","Haskell"]
replicate 10 'c'        ~>*  "cccccccccc"