2. Darbs ar sarakstiem

1. Teorētiskais minimums

Ievads

Šī apmācība, pirmkārt, ir domāta tiem, kas jau māk programmēt citās valodās. Bet, ja Jums nav pieredzes programmēšanā vai kaut kāds termins nav saprotams, tad Jūs varat uzbraukt ar peli uz pasvītrotajiem terminiem un izlasīt definīciju. Savukārt atbildes uzdevumiem tiks parādītas, uzklikšķinot uz tām.

Apmacībā sastāv no vairākām daļām. Pirmajā daļā ir saspiests viss teorētiskais minimums, kas ir vajadzīgs pilnvērtīgai programmēšanai, izmantojot Haskell valodu. Nākamās daļas vairāk veltītas praktiskiem darbiem un dažādu problemu risināšanai.

Kas ir Haskell

Haskell ir funkcionāla valoda, kurai piemīt vairākas īpašības, kas izceļ to citu programmēšanas valodu starpā. Tā ir tīri funkcionāla, bet tajā pašā laikā ļauj viegli rakstīt imperatīvu kodu. Tai ir ļoti attīstīta tipu sistēma, kas ļauj izvairīties no daudzām kļūdām. Ir pat pieņemts uzskatīt, ja Haskell programma kompilējas, tad tā gandrīz nesatur kļūdas.

Haskell valodai ir diezgan daudz sintakses iespēju (pattern matching, kompozīcijas, eta-conversion), kas ļauj rakstīt lakonisku un saprotamu kodu. Haskell valodā praktiski nav boilerplate elementu (atslēgvārdi function vai return, funkciju vai argumentu delimiteri). Haskell valodā ir ļoti maz dažādu elementu, no kuriem sastāv programma, atšķirībā no OOP valodām.

Daži koda piemēri

a = 2 + 3

a saturēs 5.

list = [1,2,3,4,5]

anotherList = [1..10]

Tiek izveidoti 2 saraksti, viens ar skaitļiem no 1 līdz 5, otrs - no 1 līdz 10.

toUpper 'a'

Atgriež 'A'.

Funkcijas

Haskell valodas galvenais elements ir funkcijas. Funkciju definīcija arī ir īsa un lakoniska:

cube x = x ^ 3

Kā var redzēt, Haskell neprasa nekādu funkcijas atslēgvārdu, piemēram, function vai def. Tas tiek panākts ar to, ka funkcijas ir valodas pamatelements.

Funkcijas argumenti tiek padoti pēc funkcijas nosaukuma ar atstarpi, piemēram:

triangleArea a h = a * h / 2

Būtīska starpība ir tajā, ka, atšķirībā no citām valodām, Haskell valodā netiek izmantots return atslēgvārds. Tas skaidrojams ar to, ka Haskell valodā katrai funkcijai ir viena darbība (kas var sastāvēt no vairākām darbībām ķēdē), un tās darbības rezultāts arī ir tas, ko atgriež funkcija. Haskell valodā ir funkcija, kas saucās return, kas tiks izpētīta vēlāk, bet tā dara pavisam kaut ko citu.

Programmas

Haskell programmas ir ļoti lakoniskas un satur ļoti maz boilerplate:

cube x = x ^ 3

main = print (cube 4)

Un pat šo programmu var padarīt īsāku. Ja mēs skatāmies uz funkciju cube, tad viss, ko tā dara - kāpina argumentu trešajā pakāpē. Mums šajā situācijā ir vienalga, kāds ir arguments, mums ir svarīgi, ko funkcija dara. Tāpēc pierakstīsim to citādāk:

cube = (^3)

main = print (cube 4)

Izmantojot šo pieeju (kas saucās eta-conversion un smalkāk tiks izpētīta apmācības trešajā daļā), kods var sanākt ļoti tīrs un daudz lasāmāks.

Kā iesākt

Iesācējiem ir rekomendēts uzinstalēt haskell-platform, piemēram

sudo apt-get install haskell-platform

Tas iekļauj sevī GHC kompilātoru, Cabal paku menedžeri un dažas izplatītākās pakas.

Programmētāji ar lielāku pieredzi var uzinstalēt tikai ghc.

Lai instalētu vajadzīgās pakas, var izmantot komandu

cabal install package_name

Ir noderīgi apgūt arī interaktīvo interpretatoru, ghci.

Pirmā programma

Izveidojiet failu hello.hs un ierakstiet šo kodu:

main = print "Hello world!"

Sakompilējiet to ar

ghc hello.hs

Jūs redzēsiet paziņojumus:


[1 of 1] Compiling Main             ( hello.hs, hello.o )
Linking hello ...

Sakompilēto programmu var palaist ar

./hello

Ērtībai ir vērts piesaistīt kādu pogu kombināciju programmas kompilācijai. Piemēram, ja Jūs izmantojat vim redaktoru, var izveidot komandu, kas saglabā, sakompilē un palaiž kodu, piemēram, es izmantoju binding uz pogas F7:

au BufNewFile,BufRead *.hs set filetype=haskell

au FileType haskell nnoremap <F7> :w<CR>:!ghc % && ./%:t:r<CR>

Darbs ar interpretatoru

Kopā ar GHC instalāciju nāk arī interaktīvais interpretators GHCi, kurš ļauj izpildīt Haskell izteiksmes un redzēt rezultātu. Tāpat GHCi ļauj analizēt un labot kļūdas jau gataviem moduļiem vai programmām.

Lai palaistu interpretatoru, vajag izpildīt komandu "ghci" komandrindā. Jūs redzēsiet rindu "Prelude> ", tajā momentā ghci ir gatavs darbam.

ghci ļauj izpildīt jebkuru Haskell kodu. Piemēram, ierakstot map (^2) [1..5], Jūs uzreiz redzēsiet rezultātu.

Haskell programmētāji izmanto ghci diezgan bieži, tāpēc ir vērts to konfigurēt. Lai to izdarītu, ir jāizveido fails $HOME/.ghci. Kā piemērs, var nomainīt prefiksu:

:set prompt "λ> "

Palaižot ghci nākamreiz, jūs redzēsiet "λ> " "Prelude> " vietā.

Starpība starp kompilatoru un interpretatoru

Viss Haskell kods, kas tiek padots interpretatoram, tiek uztverts kā izteikums. Ja Jūs gribēsiet GHCi definēt kādu funkciju, piemēram

foo a b = a + b

Jūs redzēsiet kļūdu. Tas skaidrojas ar to, ka visas Haskell funkciju definīcijas ir deklaratīvas, tie nav izteikumi. Atslēgvārds let un konstrukcija let .. in .. ļauj veidot definīcijas izteikumos. Piemēri:

λ> let foo a b = a + b
λ> foo 2 3
5

λ> let foo a b = a + b in foo 2 3
5

Atšķirība starp abiem piemēriem ir tajā, ka pirmais nodefinē funkciju foo, kas eksistēs, kamēr GHCi ir atvērts. Savukārt otrajā foo eksistēs tikai izteikuma robežās - ja mēģināsiet pēc tam izsaukt foo 2 3, jūs redzēsiet kļūdu (ja pirms tam neesat nodefinējuši foo ar let).

Tipi

Haskell tipu sistēma ir ļoti advancēta un dara ļoti daudz darba, lai nodrošinātu programmas stabilitāti. Bet sākumā ir nepieciešams saprast, kā Haskell funkcijām tiek aprakstīti tipi. Paņemsim elementāru funkciju ar diviem argumentiem:

add a b = a + b

Lai aprakstītu šīs funkcijas tipu, tiek izmantots šāds pieraksts:

add :: Int -> Int -> Int

Šo pierakstu jālasa tā: funkcija add saņem divus argumentus ar tipu Int un atgriež rezultātu ar tipu Int.

Sākumā šāds pieraksts liekas neloģisks, jo argumenti ir samesti kopā ar rezultātu. Ar laiku Jūs sapratīsiet, ka pieraksts ir tieši šāds pateicoties procesam, kas saucās karings.

Pierakstīt funkcijas tipu lielākoties nav obligāti. Šāda vajadzība parādās diezgan reti. Bet tos ir jāprot lasīt, lai varētu viegli orientēties gatavajās funkcijās.

Primitīvie tipi

Var nošķirt 5 primitīvus tipus: Int, Integer, Float, Char, Bool.

Int ir veselie skaitļi, kuru diapazons tiek ierobežots ar datora arhitektūru. Piemēram, 32 bitu arhitektūrā Int skaitļi ir no -2147483648 līdz 2147483647.

Integer ir neierobežoti veselie skaitļi.

Float ir skaitļi ar peldošo punktu, jeb reālie skaitļi, piemēram 1.23.

Char ir simbolu tips: viens simbols ir ierobežots ar parastajām pēdiņām - 'a'.

Bool ir būla mainīgie, kas var būt True vai False.

Saraksti

Tāpat kā citās valodās, Haskell ļauj izveidot sarakstu ar noteikta tipa elementiem. Piemēram, [1, 2, 3, 4, 5] ir saraksts ar skaitļiem.

Saraksta elementiem ir jābūt viena tipa. Izveidojot sarakstu ar jauktiem tipiem, piemēram, [1, 'a'] izsauks kompilācijas kļūdu.

Simbolu saraksts atzīmējas kā saraksts [Char] vai ar tā sinonīmu, String. Lai izveidotu String tipa mainīgo, vajag izmantot dubultpēdiņas - "abcd". Tas pieraksts ir sintaktiskais atvieglojums simbolu sarakstam - ['a', 'b', 'c', 'd'].

Atšķirībā no tādām valodām kā PHP vai JavaScript, Haskell piespiež programmētāju izmantot vajadzīgā veida pēdiņas. Tas nozīmē, ka konstrukcija 'abcd' izsauks kompilācijas kļūdu - Haskell gaida, ka ar '' ir definēts Char tipa mainīgais, nevis [Char]. Savukārt konstrukcija "a" neizsauks kļūdu, bet izveidos [Char] tipa mainīgo.

Haskell valodā visbiežāk tiek izmantota funkcija : - pievienot elementu pie saraksta sākuma. Piemēram, 1 : [2, 3] atgriež [1, 2, 3], 'a' : "bc" atgriež "abc".

Pāri

Pāris ir konstrukcija, kas var būt pazīstama Python programmētājiem. Pāris satur divus elementus, kuriem var būt dažādi tipi, piemēram, (1, "abcd").

Pāris var sastāvēt no vairākiem elementiem, piemēram, (1, "Jānis Bērziņš", 1987). Bet funkcijas, kas ir domātas pāriem no diviem elementiem, nestrādās ar pāriem no vairākiem elementiem, piemēram:

foo (a, b) = a

main = print (foo (1, "Jānis Bērziņš", 1987))

Šis kods izsauks kompilācijas kļūdu.

Visbiežāk tiek izmantots pāris no 2 elementiem, un tam ir definētas funkcijas, kas ir pieejamas ar bāzes paku Prelude - fst un snd, kuras atgriež attiecīgi pirmo un otro pāra elementu.

Jūs varat pamanīt, ka pieraksts foo (a, b) ir līdzīgs tam, kā citās valodās, piemēram, JavaScript, tiek aprakstīti argumenti funkcijām. Sākumā tos var jaukt, tāpēc ir svarīgi saprast, ka (a, b) ir viens arguments, kas ir pāris no 2 elementiem.

Funkcijas kā argumenti

Haskell valoda ļauj veidot augstākas kārtas funkcijas, tās ir funkcijas, kas pieņem citas funkcijas kā argumentus. Piemēram, mums ir funkcija foo a = a + 2, tās tips var būt foo :: Int -> Int. Tagad mēs gribam izpildīt šo funkciju uz diviem argumentiem un atgriezt sarakstu ar divām vērtībām. Tātad, mums ir funkcija ar trīs argumentiem - pirmais ir mūsu funkcija foo, bet otrais un trešais ir kaut kādi skaitļi:

foo a = a + 2

bar f x y = [f x, f y]

main = print $ bar foo 3 4

Rezultāts būs [5, 6], bet mums ir svarīgi, kāds ir tipa pieraksts šai funkcijai. Ja funkcijas arguments ir cita funkcija, tad mēs aprakstām tās funkcijas tipu iekavās. Konkrētajā gadījumā funkcijas bar tips varētu izskatīties šādi:

bar :: (Int -> Int) -> Int -> Int -> Int

Šo var izlasīt šādi: pirmais arguments ir funkcija ar tipu (Int -> Int), otrais arguments ir Int, trešais arguments ir Int, rezultāts ir Int.

Uzdevumi

Šeit būs nelieli uzdevumi, kuru atbildes ir paslēptas zemāk (uzklikšķiniet uz tumšiem laukiem, lai redzētu atbildes).

Izdomājiet galvā tipu funkcijai foo a b = toUpper a : b.

foo :: Char -> [Char] -> [Char]

Uzrkastiet funkciju, kas maina vietām pāra elementus.

foo pair = (snd pair, fst pair)
vai
foo (a, b) = (b, a)

Uzrakstiet funkciju, kas saņem trīs argumentus un saliek tos sarakstā pretējā secībā.

foo a b c = [c, b, a]

Argumentu pierakstīšanas iespējas

Haskell valodā ir dažas iespējas, kuras var atvieglot funkciju veidošanu. Viena no tām ir tā saucamais pattern matching. Tā pamatdoma ir definēt funkcijas versiju noteiktiem argumentiem vai argumentu šablonam. Izveidosim rekursīvu faktoriāļa funkciju:

fact n = if n == 0
        then 1
        else n * fact (n - 1)

main = print (fact 5)

Mēs varam padarīt to nedaudz lasāmāku ar guard simboliem:

fact n
    | n == 0    = 1
    | otherwise = n * fact (n - 1)

main = print (fact 5)

Bet pattern matching ļauj definēt funkcijas versijas noteiktajām vērtībām:

fact 0 = 1
fact n = n * fact (n - 1)

main = print (fact 5)

Ar šo kodu mēs nodefinējam divas fact funkcijas versijas - viena izpildas kad arguments ir vienāds ar 0, bet otra - visos pārējos gadījumos.

Pattern matching sarakstiem

Haskell atbalsta pattern matching iespējas, kas ir domātas sarakstiem. Piemēram, var definēt funkcijas versiju tukšam sarakstam vai izdalot saraksta elementus.

Izveidosim funkciju, kas pārveido vārda pirmo burtu augšējā reģistrā (atceramies, ka rinda ir simbolu saraksts):

import Data.Char

cap [] = ""
cap (x:xs) = toUpper x : xs

main = print (cap "hello")

Pirmā rinda pievieno bibliotēku Data.Char, kas satur funkciju toUpper.

Nākamajā rindā mēs izmantojam šablonu [], kas definē funkcijas cap versiju gadījumam, ja tiek padots tukšs saraksts - tajā gadījumā mēs atgriežam tukšu sarakstu.

Nākamajā rindā mēs ar šablonu (x:xs) atdalam pirmo elementu x no pārējas listes xs. Tas pieraksts nozīmē, ka šajā funkcijas versijā ir pieejami 2 argumenti - x, kas ir pirmais saraksta elements, un xs, kas ir atlikušais saraksts. Mūsu gadījumā x ir rindas pirmais simbols. Mēs ieceļam to simbolu augšējā reģistrā ar toUpper un tad pievienojam pie pārējā saraksta ar : operatoru.

Šablons (x:xs) tiek izmantots ļoti bieži. Tāpēc ir jāņem vērā nosacījums: tas pieprasa, lai sarakstā būtu vismaz viens elements. Ar šo šablonu var izdalīt arī vairākus elementus, piemēram, (x1:x2:x3:xs) - šeit, ja padot sarakstu [1, 2, 3, 4, 5], x1 būs 1, x2 būs 2, x3 būs 3, bet xs būs [4, 5]. Ir iespēja veidot funkcijas versiju sarakstam ar vienu elementu - (x:[]), bet ērtāk dabūt to pašu ar šablonu [x].

Citas pattern matching iespējas

Ir iespēja veidot funkciju, kurā ir definēts gan arguments, gan tā šablons. Piemēram:

foo n@123 = n*2
foo _ = 456

main = do
    print (foo 123)
    print (foo 111)

Pirmā rinda definē funkciju foo gadījumam, ja arguments n ir vienāds ar 123. Otrā rindā šablons _ tiek izmantots, lai pilnībā ignorētu argumentu.

Cits piemērs ar sarakstiem. Teiksim, mums vajag paņemt sarakstu un tam klāt pielikt vēlreiz to pašu sarakstu, bet bez pirma elementa:

foo list@(x:xs) = list ++ xs

main = print (foo [1, 2, 3])

Rezultāts būs [1, 2, 3, 2, 3].

Var definēt šablonus pāriem:

first  (a, b) = a
second (a, b) = b

Noderīgas funkcijas

Šeit apkoposim funkcijas, kuras ir noderīgas darbam ar sarakstiem vai pāriem.

: - pievienot elementu sarakstam. 1 : [2, 3] atgriezīs [1, 2, 3]

++ - salīmēt divus sarakstus. [1, 2] ++ [3, 4, 5] atgriezīs [1, 2, 3, 4, 5]

fst, snd - atgiež divu elementu pāra pirmo un otro elementu respektīvi. fst (1, 2) atgriezis 1.

head, last - atgriež saraksta pirmo vai pēdējo elementu respektīvi. head [1, 2, 3] atgriezīs 1

init, tail - atgriež sarakstu bez pēdējā vai pirmā elementa respektīvi. tail [1, 2, 3] atgriezīs [2, 3]

filter - filtrēt sarakstu, izmantojot funkciju. filter odd [1..10] atgriezīs [1, 3, 5, 7, 9]

all - pārbaudīt, vai visi elementi atbilst nosacījumam. all odd [1, 3, 4, 5, 7] atgriezīs False

any - pārbaudīt, vai kaut viens elements atbilst nosacījumam. any odd [2, 4 .. 10] atgriezīs False

elem - pārbaidīt, vai elements ir sarakstā. elem 3 [1 .. 10] atgriezīs True

not - pieņem Boolean tipa argumentu, atgriež True, ja arguments ir False, vai False, ja arguments ir True.

!! - atgriezt saraksta n-to elementu. ['a'..'z'] !! 3 atgriezīs 'd' (elementus sāk skaitīt no 0)

Uzdevumi

Uzrakstiet funkcijas first, second un third, kas ir domātas pāriem ar trijiem elementiem.

first  (a, b, c) = a
second (a, b, c) = b
third  (a, b, c) = c

Uzrakstiet rekursīvo funkciju, kas aprēķina n-to Fibonacci skaitli.

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Uzrakstiet rekursīvo funkciju, kas apgriež rindu otrādi.

foo [] = []
foo line = last line : foo (init line)

Map & Fold

Sarakstiem ir ļoti nopietna loma Haskell valodā. Ir vērts izcelt divas galvenās funkcijas darbam ar sarakstiem: map un fold. Citās valodās fold tiek saukts par reduce, bet fold nosaukums ir nedaudz loģiskāks, jo rezultātā saraksts tiek "salikts" vienā vērtībā.

Map

Funkcija map pieņem divus argumentus - funkciju un sarakstu. Map funkcija iziet cauri sarakstam un izpilda padoto funkciju ar katru saraksta elementu. Piemēram, mums ir saraksts un mums vajag atrast kvadrātu no katra elementa:

sqr n = n ^ 2

main = print (map sqr [1,2,3,4,5])

Rezultātā redzēsim [1, 4, 9, 16, 25].

Funkcijas map tips ir map :: (a -> b) -> [a] -> [b]. Šo var izlasīt: pirmais arguments ir tipa a -> b funkcija, tas ir funkcija, kas pieņem argumentu ar tipu a un atgriež rezultātu ar tipu b. Otrais ir saraksts ar tipa a vērtībām. Rezultāts ir saraksts ar tipa b vērtībam. a un b šajā pierakstā ir simboliski aizvietojumi, kas demonstrē, ka tur var būt jebkādi tipi.

Fold

Funkcija fold ir nedaudz sarežģītāka. Tā uzkrāj rezultātu vienā mainīgajā, ko sauc par akumulatoru. Tā izmanto funkciju ar diviem mainīgajiem. Kā pirmā tai tiek padota akumulatora vērtība, otrais arguments tiek paņemts no saraksta. Rezultāts atjauno akumulatora vērtību.

Piemēram, mēs izmantojam akumulatora vērtību 1, sarakstu [2, 3, 4] un funkciju foo a b = 2 * a + b. Izmantosim fold versiju, kas sāk no saraksta kreisās puses - foldl:

foo a b = 2 * a + b

main = print (foldl foo 1 [2,3,4])

Ja attēlo, ko dara foldl, sanāk 4 soļi:

1. Funkcija foo saņem argumentus 1 un 2, rezultāts 1 * 2 + 2 = 4 tiek ierakstīts akumulatorā, sarakstā paliek [3, 4]
2. Funkcija foo saņem argumentus 4 un 3, rezultāts 4 * 2 + 3 = 11 tiek ierakstīts akumulatorā, sarakstā paliek [4]
3. Funkcija foo saņem argumentus 11 un 4, rezultāts 11 * 2 + 4 = 26 tiek ierakstīts akumulatorā, saraksts ir tukšs
4. Šis solis notiek, kad saraksts kļuvis tukšs. Šajā gadījumā tiek vienkārši atgriezta akumulatora vērtība, un rekursija apstājas.

Map & Fold kodi

Patreiz jums ir jābūt pietiekami daudz zināšanām, lai paši saprastu, kā darbojas funkcijas map un foldl, izlasot šo funkciju kodu. Pamēģiniet to izdarīt, pirms turpināsiet lasīt:

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

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

Uzdevumi

Uzrakstiet funkciju, kas izmanto map un pārverš rindu uz augšējo reģistru.

foo line = map toUpper line

Uzrakstiet funkciju, kas izmanto foldl un apgriež rindu otrādi.

foo acc char = char : acc
bar line = foldl foo "" line

Funkciju definēšanas iespējas

Prefix un infix pieraksti

Visbiežāk ir sastopams prefix pieraksts funkcijām - kad funkcijas nosaukums ir pirms argumentiem. Funkcijām ar 2 argumentiem pastāv iespēja izmantot infix pierakstu. Lai izmantotu infix pierakstu funkcijai, kuras nosaukums sastāv no burtiem, mēs varam izmantot backquote simbolus - ``. Izveidosim funkciju, kas aprēķina procentus no skaitļa:

percent a b = a / b * 100

main = do
    print (percent 20 160)
    print (20 `percent` 160)

Savukārt, ja funkcijas nosaukums sastāv no simboliem (tā saucāmas operatoru funkcijas), tad backquotes izmantot ar infix pierakstu nevajag, bet ar prefix pierakstu vajag izmantot iekavas:

a % b = a / b * 100

main = do
    print (20 % 160)
    print ((%) 20 160)

Infix pieraksts ļauj definēt funkcijas ar vairāk ka 2 argumentiem:

(a &&& b) c = [a, b, c]

main = print ((1 &&& 2) 3)

Rezultāts būs [1, 2, 3].

Anonīmās funkcijas

Anonīmās vai lambda funkcijas ir funkcijas, kurām nav nosaukuma. Tās bieži tiek izmantotas augstākas kārtas funkcijās (funkcijās, kuras izmanto citas funkcijas kā argumentus). Haskell valoda izmanto šādu pierakstu lambda funkcijām: (\a -> doSomething a). Simbols "\" pirms argumenta simbolizē grieķu simbolu lambda. Pati lambda funkciju sintakse ir mantota no lambda calculus.

Piemēram, funkcija, kas kāpina skaitli kvadrātā, izskatīsies šādi: (\a -> a^2)

Lambda funkcijas var izmantot kā patstāvīgas funkcijas:

main = print ((\a -> a^2) 3)

vai kā argumentus augstākas kārtas funkcijām, piemēram, map:

map (\a -> a^2) [1, 2, 3, 4, 5]

Līdzīgi kā mēs vienkāršojām cube funkciju, lambda funkcijas arī var vienkāršot (process saucas eta reduction):

map (^2) [1, 2, 3, 4, 5]

Lambda funkcijas ar vairākiem argumentiem veidojas līdzīgi: (\a b -> a + b)

Uzdevumi

Izveidojiet funkciju, kas izmanto foldl un apgriež rindu otrādi, bet šoreiz kā pirmo argumentu foldl izmantojiet lambda funkciju.

foo line = foldl (\x y -> y : x) "" line

Izveidojiet funkciju, kas izfiltrē visus patskaņus (a, e, i, o, u) no rindas, izmantojot anonīmo funkciju.

foo line = filter (\x -> not (elem x "aeiouAEIOU")) line

Karings, Kompozīcijas un aplikācijas

Karings

Karings ir process, kas pārveido funkciju ar vairākiem argumentiem par virkni funkciju ar vienu argumentu. Matemātiskās funkcijas var izmantot tikai vienu argumentu, un tīri funkcionālās valodās funkcijām ir jāatbilst šim noteikumam. Bet, lai atvieglotu programmētāja darbu, tika izveidots mehānisms, kas ļauj veidot funkcijas ar vairākiem argumentiem, nepārkāpjot tīri funkcionālo principu.

Piemēram, mēs gribam uztaisīt funkciju foo a b = a + b. Pirmkārt, pierakstīsim šo funkciju prefix pierakstā - foo a b = (+) a b. Tālāk izdomāsim funkciju (x -> x + a). Mēs redzam, ka šo funkciju mēs varam ievietot mūsu galvenajā funkcijā: foo a b = (x -> x + a) b. Un, līdzīgi kā iepriekš, ar eta reduction vienkāršosim to funkciju: foo a b = (+a) b

Šis process saucās karings (currying, no matemātiķa Haskell Curry uzvārda). To dara Haskell kompilators katru reizi, kad tiek izveidota funkcija ar vairākiem parametriem.

Tieši tāpēc Haskell izmanto tādus tipu pierakstus - tie demonstrē, kā funkcijas reducējas līdz vienam mainīgajam. Ja mums ir funkcija foo a b = a + b, mēs varam to izmantot kā foo 2 3, vai (foo 2) 3, pieeja, kas saucās partial application. Šeit (foo 2) ir eta-reducēts pieraksts lambda funkcijai (\x -> foo 2 x). Kā redzat, ar karingu mēs viegli izveidojam jaunu funkciju. Karings ļauj viegli modificēt kodu, veidojot jaunās funkcijas, vai apvienojot esošās, padarot kodu lasamāku un vieglāk modificējamu.

Kompozīcijas

Kompozīcija ir process, ar kura palīdzību divas funkcijas tiek salīmētas vienā. Kompozīciju operators ir (.), piemēram, foo . bar. Piemērs:

import Data.Char

cap []     = ""
cap (x:xs) = toUpper x : xs

capWords = map cap . words

processString = unwords . capWords

main = print (processString "hello world")

Šeit mēs izmantojam kompozīciju divās vietās: funkcija processString apvieno funkcijas unwords un capWords, bet funkcija capWords apvieno izteikumu map cap un funkciju words.

Kompozīcijas noder, lai savienotu funkcijas, kas bieži atkārtojas. Kā arī ar kompozīcijām var uzrakstīt lasāmāku kodu.

Aplikācijas

Aplikācija ir vienkāršs process, kad par vienas funkcijas argumentu tiek izmantots citas funkcijas rezultāts. Piemēram, foo(bar 1).

Haskell valodā ir izveidots speciāls operators aplikācijām, ($). Piemēru augstāk var pierakstīt šādi: foo $ bar 1. Viss, kas no labās puses, tiek padots kā arguments funkcijai no kreisās puses.

Visas iepriekš attēlotās programmas var vienkāršot, izmantojot aplikācijas operatoru, piemēram:

a % b = a / b * 100

main = do
    print $ 20 % 160
    print $ (%) 20 160

Kompozīcijas un aplikācijas operatori

Lai saprastu līdz galam, kā darbojas šie operatori, varat izpētīt to kodus.

Aplikācijas operators:

($) :: (a -> b) -> a -> b
f $ x = f x

Kompozīcijas operators:

(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)

Uzdevumi

Izveidojiet funkciju, kas ceļ kvadrātā katru saraksta elementu, pirms tam izfiltrējot no tā visus nepāra skaitļus (funkcija even ir pretēja funkcijai odd). Izveidojiet divas versijas funkcijai - vienu ar aplikācijas operatoru, otru ar kompozīcijas operatoru. Izmantojiet funkcijas map un filter.

foo list = map (^2) $ filter even list

foo = map (^2) . filter even

Lazy

Lazy ir programmēšanas princips, kas atliek funkcijas izpildi līdz brīdim, kad tas ir vajadzīgs. Apskatīsim piemēru ar pāri, kura pirmais elements ir bezgalīgs saraksts, bet otrais ir nulle:

main = print $ fst ([1 ..], 0)

Jūs redzēsiet, ka tas tiešām ģenerē bezgalīgu sarakstu. Tagad ņemsim otro pāra elementu:

main = print $ snd ([1 ..], 0)

Tiks izvadīta nulle un programma beigs savu darbu. Saraksts nav sācis ģenerēties, jo tas nav vajadzīgs.

Lazy piemēri

Cits, nedaudz noderīgāks lazy pielietojums:

main = print $ take 5 [1 ..]

Mēs atkal izmantojam bezgalīgu sarakstu un pat sākam to ģenerēt. Bet augstākas kārtas funkcija take (paņemt n elementus no saraksta) kontrolē saraksta ģenerāciju. Kods saprot, ka vajag ģenerēt tikai 5 elementus, jo vairāk elementi programmā netiks izmantoti.

Vēl viens piemērs:

mapOdds f = map f [1,3 ..]

main = print $ take 10 $ mapOdds (^2)

Tiks aprēķināti kvadrāti pirmajiem 10 nepāra skaitļiem.

Lazy un rekursīvie dati

Haskell definē datus līdzīgi kā funkcijas:

ones :: [Integer]
ones = [1, 1 ..]

Šis ir bezgalīgs saraksts ar vieniniekiem, kuru, pateicoties lazy izpildei, mēs varam kontrolēt ar augstākas kārtas funkcijām. Bet šo pašu sarakstu var nodefinēt rekursīvi:

ones = 1 : ones

Pateicoties karingam, Haskell ļauj izveidot rekursīvus datus, jo šo var uzskatīt par funkciju ar 0 argumentiem (ones tipa aprakstā nav neviens "->" simbols jeb karinga operators).

Cits piemērs:

odds = 1 : map (+2) odds

Šis kods ģenerēs bezgalīgu sarakstu ar nepāra skaitļiem.

Savstarpējas rekursijas

Haskell ļauj izveidot savstarpēji rekursīvas funkcijas vai datus. Piemērs:

odds, evens :: [Integer]
odds  = map succ evens
evens = 0 : map succ odds

main = print $ take 10 odds

Funkcija succ palielina argumentu par 1.

Šeit mēs redzam, ka abi sarakstu ģeneratori izmanto viens otru. Nulle evens ģeneratoram kalpo kā atskaites punkts.

Nākamajā piemērā izveidosim bezgalīga pirmskaitļu saraksta ģeneratoru, kas ģenerēšanai izmantos funkciju, bet tā funkcija savukārt izmantos šo ģeneratoru:

primes = 2 : filter isPrime [3, 5 ..]

isPrime n = all checkRem $ takeWhile checkSquare primes
    where
        checkRem    x = n `rem` x /= 0
        checkSquare x = x ^ 2 <= n

main = do
    print $ isPrime 37
    print $ take 10 primes

Konstrukcija all checkRem pārbauda, vai visi saraksta elementi nedalās ar skaitli n. Savukārt takeWhile checkSquare atlasa elementus no saraksta, kamēr tie ir mazāki vai vienādi ar kvadrātsākni no n (kas ir pietiekami, lai pārbaudītu pirmskaitli).

Funkcija rem atrod atlikumu no dalīšanas. Operators /= atgriež True, ja argumenti nav vienādi (!= citās valodās). Ar where var definēt lokālas funkcijas, kurām ir pieejami parent funkcijas argumenti.

List comprehension

List comprehension (LC) ir mehanisms, kas ļauj ģenerēt sarakstus, izmantojot kādu citu sarakstu, funkciju un noteikumus. Vienkāršs piemērs:

odds = [ x | x <- [1, 3 ..]]

Šajā sarakstā būs visi nepāra skaitļi. LC ļauj izpildīt arī funkciju uz katra elementa, kā arī var būt definēti lokālie mainīgie, piemēram:

list = [ y ^ 2 | x <- [1 .. 20], let y = x * 2]

Šis saraksts saturēs kvadrātus skaitļiem no 1 līdz 20, reizinātiem ar 2.

LC var arī saturēt pārbaudes funkciju. Izmainīsim pēdējo piemēru, ņēmot tikai skaitļus, kuri dalās ar 3:

list = [ y ^ 2 | x <- [1 .. 20], let y = x * 2, x `rem` 3 == 0]

Tipu sistēma

Tipu sistēma Haskell valodā ir laikam svarīgākais un sarežģītākais temats. Pie Haskell tipu sistēmas ir grūti pierast un dažiem ir grūti to saprast. Bet, ja programmētājs to ir apguvis, ir iemācījies lasīt funkciju tipus, meklēt funkcijas pēc tipa apraksta un kombinēt funkcijas, tas nozīmēs, ka viņš ir spējīgs uzrakstīt jebkuru programmu, izmantojot Haskell valodu. Ir ļoti svarīgi apgūt Haskell tipu sistēmas pamatus, pirms apgūt tādas lietas kā monādes vai funktorus. Tāpēc šo sadaļu nav vēlams izlaist un ir jāapgūst visu materiālu.

Izteiksmju tipi

Pirms laika mēs iemācījāmies, kā Haskell valodā tiek pierakstīti tipi funkcijām un datiem. Piemēram, funkcijai foo, kas saņem divus argumentus ar tipu Int un atgriež rezultātu ar tipu Int, apraksts būs sekojošs: foo :: Int -> Int -> Int. Šeit -> var saukt par karinga operatoru.

Ir jāsaprot, ka Haskell valodā tips ir ne tikai funkcijām un datiem, bet jebkurai izteiksmei. Haskell programmētājam ir svarīgi būt spējīgam izprast, uz kādu tipu reducējas izteikums. Sākumā to ir grūti darīt galvā, tāpēc ir svarīgi apgūt GHCi.

Jebkuras izteiksmes tipu var pārbaudīt ar :t komandu. Kā piemēru izskatīsim funkciju, kas sasummē divus argumentus. Palaidiet GHCi un uzrakstiet:

λ> let add a b = a + b

λ> :t add

Šeit un turpmāk komandas un izteiksmes, kuras ir jāizpilda GHCi, tiks atzīmētas ar λ> prefiksu.

Jūs redzēsiet atbildi add :: Num a => a -> a -> a. Tagad, ja izpildīsiet:

λ> :t add 1

atbilde būs add 1 :: Num a => a -> a. Mēģināsim analizēt abus rezultātus, lai saprastu, kāpēc tie atšķiras.

Pirmkārt, mēs pagaidām ignorējam visu, kas ir pirms => zīmes. Šajā gadījumā a ir tipu mainīgais. Tipu mainīgie tiek izmantoti, lai atvieglotu tipa pierakstu. Tipu mainīgie ir aprakstīti pirms => zīmes. Piemēram, ja funkcijas tips ir a -> b -> a, tad to ir jāsaprot šādi: pirmais arguments ir jebkāda tipa, otrais arguments var būt jebkāda cita tipa, bet rezultāts ir tāda paša tipa kā pirmais arguments, jo abiem mēs izmantojam vienādu tipu mainīgo a.

Mums pašreiz ir svarīga konstrukcija pēc => zīmes, un funkcijai add bez argumentiem tā ir a -> a -> a. Tas nozīmē, ka tiek paņemti divi argumenti ar kaut kādu tipu un tiek atgriezta vērtība ar tādu pašu tipu.

Savukārt izteikumam add 1 tips ir add 1 :: Num a => a -> a vai, ignorējot visu pirms => zīmes, vienkārši a -> a. Tas ir tāpēc, ka mēs jau padevām vienu argumentu. Šis izteikuma tips mums ļauj saprast, ka mums šim izteikumam vajag padot vēl vienu argumentu, un tad tas atgriezīs rezultātu.

Tagad izpildīsim

λ> :t add 1 3

un redzēsim tipu add 1 3 :: Num a => a vai, ignorējot visu pirms => zīmes, vienkārši a. Šim izteikumam vairs nevajag padot argumentus, jo tam ir noteikts rezultāts ar tipu a. Citiem vārdiem, šis izteikums reducējas uz noteikto vērtību, ko var ātri saprast, jo nav neviena karinga operatora.

Jūs pamanījāt, ka mēs pagaidām ignorējam Num prefiksu. Tā ir tipu klase, un pie tās mēs drīz nonāksim. Bet pirms tam mēs izskatīsim vēl vienu piemēru izteikumu tipiem.

Izskatīsim piemērus ar funkciju map:

λ> :t map
map :: (a -> b) -> [a] -> [b]

λ> :t map (+2)
map (+2) :: Num b => [b] -> [b]

λ> :t map (+2) [1..5]
map (+2) [1..5] :: (Enum b, Num b) => [b]

Pirmajā mēs redzam standarta map definīciju, kas der jebkādiem tipiem. Otrajā mēs redzam, ka pazuda (a -> b) no tipa, jo mēs jau padevām funkciju (+2). Otrās izteiksmes tips ir [b] -> [b]. Kāpēc ne [a] -> [b] - tāpēc, ka Haskell saprot, ka funkcija (+2) atgriež tādu pašu tipu, kāds bija padots, par ko var pārliecināties, izpildot λ> :t (+2). Savukārt trešais piemērs jau reducējas uz noteiktu rezultātu, tāpēc tips ir vienkārši [b].

Mēs redzam, ka katrā rindā tipu mainīgājiem parādās jaunās tipu klases. Intuitīvi var saprast, ka tās klases ievieš ierobežojumus uz iespējamiem argumentiem. Jūs varat salīdzināt, kā izmainīsies tipu apraksti, ja (+2) vietā tiktu izmantota funkcija sqrt (aprēķināt kvadrātsakni).

Varbūt kādam jau ienāca prātā doma, ka, ja Haskell valodā tips ir gan funkcijām, gan izteiksmēm, tad tās divas lietas ir viens un tas pats. Tas nav tālu no patiesības, jo mēs viegli varam izveidot funkciju no jebkuras izteiksmes. Piemēram, mums ir izteiksme map (+2) un mēs varam viegli izveidot funkciju no tās izteiksmes:

λ> let mapPlus2 = map (+2)
λ> mapPlus2 [1,2,3]
[3,4,5]

Uzdevumi

Neizmantojot GHCi, pamēģiniet paši uzrakstīt tipu funkcijai

filter (\x -> not $ elem x "aeiou") . map toUpper

[Char] -> [Char]

Neizmantojot GHCi, pamēģiniet paši uzrakstīt tipu izteiksmei

[(a, b) | a <- [1..10], let b = a^2]

(Enum t, Num t) => [(t, t)]

Tipu klases

Tipu klašu koncepts ir līdzīgs OOP konceptam interface. Tas apraksta, kādas darbības var veikt ar tipa vērtībām. Piemēram, salīdzināšanas funkcijas (==) tips ir Eq a => a -> a -> Bool. Mēs redzam tipu klasi Eq. Pie tās klases pieder visi tipi, kuru vērtības var salīdzināt. Tā, ka tipu mainīgais ir vienāds abiem argumentiem, mēs varam lasīt šo pierakstu šādi: funkcija (==) saņem divus argumentus vienāda tipa a un atgriež Bool, pie tam tipam a ir jāimplementē tipu klasi Eq.

Funkcija, kas pārbauda, vai viens arguments ir lielāks par otru - (>), kurās tips ir Ord a => a -> a -> Bool. Ord klase apvieno tos tipus, kuru vērtības var būt lielākas vai mazākas par citām tāda paša tipa vērtībām.

Iepriekš izmantotās funkcijas (+2) tips ir Num a => a -> a. Num klase apvieno tipus, ar kuriem var veikt aritmetiskās operācijas.

Saraksta [1, 2, 3, 4, 5] tips ir Num t => [t]. Savukārt, saraksta [1 .. 5] tips ir (Enum t, Num t) => [t]. Tas nozīmē, ka tipam t ir jāimplementē gan Num, gan Enum tipu klases. Enum apvieno visus tipus, kuru vērtības ir sakārtotas, un tās var izmantot ģeneratoros, piemēram [1 .. 10] vai ['a' .. 'z']. Tagad mēs saprotam, ka funkcija succ patiesībā atgriež nākamo vērtību tipam, kas implementē Enum - succ 'a' atgriež 'b'.

Haskell ļauj veidot savus tipus, tipu klases, kā arī tipu klases var mantot īpašības no citām tipu klasēm.

Tipu klašu veidošana

Haskell ļauj veidot savas tipu klases. Kā piemēru izskatīsim Eq tipu klases definīciju:

class  Eq a  where
    (==), (/=) :: a -> a -> Bool
    x /= y     =  not (x == y)

Šeit mēs redzam, ka ir nodefinēta tipu klase, kurai ir divas iespējamās darbības. Pie tam, darbībai (==) ir aprakstīts tikai tips, bet darbībai (/=) - gan tips, gan kods. Kāpēc tas ir definēts tiešī šādi - jo salīdzināšanas funkcija var atšķirties dažādiem tipiem. Savukārt darbība (/=) vienmēr ir preteja darbībai (==), tāpēc mēs varam uzreiz nodefinēt tās kodu.

Lai aprakstītu kodu darbībai ar konkrētu tipu tiek izmantots atslēgvārds instance:

instance Eq Integer where
    x == y                =  x `integerEq` y

instance Eq Float where
    x == y                =  x `floatEq` y

Var iztēloties, ka, piemēram, sarakstiem šī funkcija būs krietni sarežģītāka un rekursīva.

Tipu klašu īpašību mantošana

Haskell valodā tipu klases var mantot īpašības no citām tipu klasēm. Piemēram, Ord klase manto visu no Eq klases, un Ord klasei ir aprakstītas papildus īpašības:

class  (Eq a) => Ord a  where
    (<), (<=), (>=), (>) :: a -> a -> Bool
    max, min             :: a -> a -> a

Klašu darbību tipiem ir tāds pats apraksts, kā jebkurai funkcijai. Tas nozīmē, ka darbībai var aprakstīt ierobežojumus, izmantojot klases:

class Foo a where
    foo         :: Bar b => a -> b

Kā var redzēt, ierobežojums ir aprakstīts rezultātam. Savukārt ierobežojumi argumentiem ir aprakstāmi ar klašu mantošanu vai ar instancēm.

Klases var mantot īpašības no vairākām klasēm:

class (Foo a, Bar a) => Baz a where

Tipu veidošana

Haskell ļauj programmētājam veidot savus tipus, aprakstot iespējamās vērtības:

data Foo = A | B | C | D

Šis ir tips, kuram iespējamās vērtības ir A, B, C un D. Šobrīd ar šo tipu nevar neko darīt, jo tas neimplementē nekādu darbību. Pat ja mēģina izprintēt jebkādu vērtību, tiek parādīts error No instance for (Show Foo) arising from a use of `print'. Tas nozīmē, ka šim tipam vajag mantot darbības no tipu klases Show, lai būtu iespēja izvadīt vērtības. Salabosim to:

data Foo = A | B | C | D
    deriving (Show)

main = print A

Ar deriving atslēgvārdu mēs pateicām kompilatoram, ka tips Foo tagad pieder pie Show tipu klases. Šī klase apvieno visus tipus, kurus var izvadīt.

Papētīsim mūsu tipu vēl nedaudz. Mēs redzam, ka B iet pēc A, un mēs gribētu, lai izteiksme succ A atgrieztu B. Sākumā pārbaudīsim succ tipu:

λ> :t succ
succ :: Enum a => a -> a

Redzam, ka succ argumentam ir jābūt no Enum tipu klases. Papildinām mūsu tipu ar to:

data Foo = A | B | C | D
    deriving (Show, Enum)

main = do
    print $ succ A
    print [A .. D]

Kā var saprast no piemēra, ģenerators [A .. D] arī pieprasa, lai tips būtu no Enum klases.

Tipu konstruktori

Haskell ļauj veidot sarežģītākus augstākas kārtas tipus, kuri sastāv no vairākām vērtībām. Pie tam, to vērtību skaits arī var būt atšķirīgs. Izveidosim tipu, kas apraksta transportlīdzēkļus - velosipēdiem būs parametri nosaukums un riteņu diametrs, savukārt mašīnām - nosaukums, riteņu diametrs un dzinēja tilpums.

data Vehicle = Bicycle String Integer | Car String Integer Float
    deriving (Show)

main = print $ Bicycle "Kross" 26

Šeit Vehicle ir tipa konstruktors, savukārt Bicycle un Car ir vērtības konstruktori.

Mēs redzam, ka abiem konstruktoriem ir kopējie elementi - nosaukums un riteņu diametrs. Izdalīsim tos atsevišķā tipā:

data Transport = Transport String Integer
    deriving (Show)
data Vehicle = Bicycle Transport | Car Transport Float
    deriving (Show)

main = print $ Car (Transport "Ford" 16) 2.0

Record pieraksts

Mēs iemācījāmies veidot augstākas kārtas tipus, bet pamanījām ļoti nopietnu trūkumu - vērtībām nav nosaukumu un mēs nevaram saprast, ko konkrētā vērtība nozīmē. Haskell ļauj izmantot Record pierakstu, kas ir pārskatāmāks:

data Vehicle = Bicycle {name :: String, wheelSize :: Integer}
    | Car {name :: String, wheelSize :: Integer, engine :: Float}
    deriving (Show)

main = print $ Car {
        name = "Ford",
        wheelSize = 16,
        engine = 2.0
    }

Tipu parametri

Haskell ļauj neprecizēt konkrētus tipus konstruktorā, tā vietā var izmantot tipu parametrus.

data Car a b c = Car {name :: a, wheelSize :: b, engine :: c}
deriving (Show)

main = do
    print $ Car {
        name = "Ford",
        wheelSize = 16,
        engine = 2.0
    }
    print $ Car {
        name = "Ford",
        wheelSize = "16 inches",
        engine = "2.0 litres"
    }

Lielāka priekšrocība ir tā, ka, veidojot funkciju, kas strādā ar šiem tipiem, mēs neesam piesieti pie konkrētiem zemākas kārtas tipiem.

Maybe konstruktors

Viens no populārākajiem veidiem, kā tiek izmantoti tipu parametri, ir Maybe tipa konstruktors, kas tiek izmantots gadījumos, kad mainīgais var nepastāvēt:

data Maybe a = Nothing | Just a

To var izmantot šādi:

foo :: Integral a => a -> Maybe a
foo x = if even x
        then Just (x `div` 2)
        else Nothing

main = do
    print $ foo 5
    print $ foo 6

Pateicoties tipa parametram, tiek panākts tas, ka Maybe var būt jebkāda tipa - Maybe Int, Maybe [Float], Maybe Car utt.

Uzdevumi

Izveidojiet kvadrātsaknes (sqrt) funkciju, kas atgriež Nothing, ja skaitlis ir negatīvs.

mySqrt n
    | n >= 0    = Just $ sqrt n
    | otherwise = Nothing

main = do
    print $ mySqrt 16
    print $ mySqrt (-5)

Funktori

Haskell valodā nopietnu lomu spēlē tipu klase Functor. Tā apvieno visus tipu konstruktorus (vai kontekstus), kuriem ir implementēta funkcija fmap:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Pats Functor klases apraksts ir ļoti interesants. Mēs redzam, ka, ja agrāk mēs izmantojām klases parametru kā tipu, tad šeit f tiek izmantots kā tipu konstruktors. Tas nozīmē, ka tad, kad tiks veidota Functor instance, tai vajadzēs padot nevis tipu, bet tipa konstruktoru, piemēram, Maybe.

fmap

Mēs redzam, ka fmap funkcijai ir divi argumenti. Pirmais ir funkcija, kas pieņem tipu a un atgriež tipu b. Savukārt, otrs arguments ir tips a, bet ar tipa konstruktoru f un fmap rezultātam ir tips b ar kontekstu f. Var saprast, ka fmap ir domāta, lai izņemtu vērtību tipa a no f konteksta, izpildītu funkciju (a -> b) izmantojot to vērtību, un rezultātu iepakotu atpakaļ f kontekstā.

Skaidrs, ka šo saprast var būt grūti, tāpēc turpināsim ar piemēriem.

Funktoru piemēri

Paņemsim mums zināmu konstruktoru Maybe. Ja mums ir tips Maybe Int un vērtība, piemēram, Just 5, mēs nevaram izdarīt operacijas, kuras parasti ir pieejamas ar tipu Int. Piemēram, funkcijas (+2) tips ir Num a => a -> a bez tipu konstruktora. Šis kods izsauks kļūdu:

λ> (+2) $ Just 5

Bet mēs zinām, ka fmap var atbrīvot vērtību no datu konstruktora konteksta un izpildīt funkciju, kas var strādāt ar šo tipu:

λ> fmap (+2) $ Just 5
Just 7
λ> fmap (+2) $ Nothing
Nothing

Lai saprastu, kā tas strādā, var apskatīties Functor instanci Maybe konstruktoram:

instance Functor Maybe where
    fmap func (Just val) = Just (func val)
    fmap func Nothing = Nothing

Mēs varam redzēt, ka ar šabloniem Just val un Nothing tiek definētas divas versijas funkcijai fmap.

Cits mums zināms piemērs vērtībai, kas ir iepakota kontekstā, ir saraksti. Tiešām, [Int] ir nekas cits, ka datu konstruktors. Tas varēja izskatīties List Int, bet [Int] cukurs ir ērtāks. Ja mēs atcerēsimies fmap aprakstu:

fmap :: (a -> b) -> f a -> f b

un iztēlosimies, ka f a un f b vietā ir attiecīgi [a] un [b], tad mēs redzēsim, ka fmap tips sarakstiem ne ar ko neatšķirās no map funkcijas apraksta:

map :: (a -> b) -> [a] -> [b]

Tāpēc nav nekāds pārsteigums, ka Functor instance sarakstiem izskatās šādi:

instance Functor [] where
    fmap = map

par ko ir viegli pārliecināties:

λ> fmap (+2) [1 .. 5]
[3,4,5,6,7]

Monādes

Daudzi ir dzirdējuši par monādēm un ka to konceptu ir grūti izprast. Bet ar esošajām zināšanām par tipu sistēmu Haskellā Jums pietiks, lai viegli apgūtu šo konceptu.

return

Patreiz Jūs jau zināt, ka Functor tipu klase "izpako" vērtību no konteksta, padod to funkcijai bez kontekstiem un rezultātu "iepako" atpakaļ. Tagad izdomāsim, ka mums ir nepieciešama vienkāršāka funkcija - kas pieņem parasta tipa argumentu un iepako to kontekstā. Nosauksim to par return:

return :: a -> m a

Šīs funkcijas piemēri:

λ> return 5 :: Maybe Int
Just 5
λ> return 5 :: [Int]
[5]

Kā redzat, izteikuma tipu var definēt pēc izteikuma ar :: palīdzību

bind vai (>>=)

Atgriežoties pie fmap funkcijas - tā izņem vērtību no konteksta, padod to parastai funkcijai un pēc tam ieliek atpakaļ kontekstā. Bet, ja mums ir funkcija, kas pati atgriež vērtību kontekstā? Teiksim, funkcija ar tipu a -> m b, līdzīgi funkcijai return. Un vēl, mēs gribam tai funkcijai padot vērtību kontekstā. Šim gadījumam palīdz funkcija (>>=) vai kā to pieņemts saukt - bind:

(>>=) :: m a -> (a -> m b) -> m b

Pēc tipa var saprast, ka šai funkcijai ir divi argumenti. Pirmais ir vērtība kontekstā, piemēram Just 5. Otrais ir funkcija, kas saņem argumentu bez konteksta, izdara darbību un atgriež rezultātu, kas jau ir iepakots kontekstā. Piemēram, funkcija var būt (\x -> Just (x + 2)). Funkcijas (>>=) rezultāts ir vērtība kontekstā.

Piemēri:

λ> (>>=) (Just 5) (\x -> Just (x + 2))
Just 7
λ> (>>=) [4,5] (\x -> [x + 2])
[6,7]

Abos piemēros augstāk ir funkcija (x + 2), kuras rezultāts tiek iepakots kontekstā. Mēs varam atcerēties, ka funkcija return iepako kontekstā, un varam izmantot to, lai dabūtu vienu funkciju, kas der abiem gadījumiem:

λ> let foo x = return $ x + 2
λ> (>>=) (Just 5) foo
Just 7
λ> (>>=) [4,5] foo
[6,7]

Haskell pats saprot, kādā kontekstā vajag iepakot vērtību - to var izprast no pirmā argumenta. Ja vēlreiz apskatīsimies (>>=) tipu, mēs redzēsim, ka visur tiek izmantots viens un tas pats konteksts m. Ja mēs mēģinātu implementēt (>>=) versiju, kura saņem argumentu vienā kontekstā, piemēram, Maybe, bet atgriež citā, piemēram, [], tad Haskell parādītu kļūdu, jo (>>=) tipa apraksts pieprasa, lai konteksts būtu vienāds. Tas ir viens no piemēriem, kā Haskell tipu sistēma kontrolē programmas pareizu darbību.

Pievērsiet uzmanību, ka (>>=) var ērti izmantot infix pierakstā:

λ> Just 5 >>= foo
Just 7

Patreiz Jums tas var nebūt acīmredzami, bet (>>=) funkcijai ir milzīgs pielietojums Haskell valodā.

Monad tipu klase

Ir tipu klase, kas sevī apvieno funkcijas (>>=) un return. Tā tipu klase saucas Monad. Tās definīcija iekļauj sevī vēl pāris papildus funkcijas, bet bind un return ir galvenās.

Izpētīsim Monad klases definīciju:

infixl 1  >>, >>=
class  Monad m  where
    (>>=)            :: m a -> (a -> m b) -> m b
    (>>)             :: m a -> m b -> m b
    return           :: a -> m a
    fail             :: String -> m a

    m >> k           =  m >>= \_ -> k

(>>) ir (>>=) versija, kas ignorē argumentu - funkcija ir noderīga, lai būvētu virkni neatkarīgu operāciju. Piemēram, do notāciju var pārrakstīt šādi:

main = print 1 >> print 2

Tātad, ja Jums ir tipu konstruktors, kuram Jūs gribat nodefinēt funkcijas (>>=) un return, tad Jūs varat to izdarīt, nodefinējot Monad klases instanci:

instance Monad MyConstructor where
    a >>= b   = someCode a b
    return a  = someCode a

Vēlreiz par funktoriem un monādēm

Patreiz Jums, visticamāk, ir liela putra, un Jūs jaucat funktorus, monādes un tā tālāk. Tāpēc izveidosim tabulas, lai atšķirtu Functor un Monad pamatfunkcijas - fmap, return un (>>=):

	Pirmais arguments	Otrais arguments	Rezultāts
fmap	Funkcija ar tipu a -> b	Vērtība kontekstā: f a	Vērtība kontekstā: f b
(>>=)	Vērtība kontekstā: m a	Funkcija ar tipu a -> m b	Vērtība kontekstā: m b
return	Vērtība bez konteksta: a	-	Vērtībā kontekstā: m a

Un vēlreiz funkciju tipi:

fmap	Functor f => (a -> b) -> f a -> f b
(>>=)	Monad m => m a -> (a -> m b) -> m b
return	Monad m => a -> m a

Funkciju return saprast ir viegli. Ir vērts iegaumēt galvenās atšķirības starp fmap un (>>=). Pirmkārt, fmap pirmais arguments ir funkcija, otrais ir vērtība, savukārt (>>=) pirmais arguments ir vērtība, otrais ir funkcija. Otrkārt, fmap izmantotā funkcija atgriež vērtību bez konteksta (kontekstu veido pati fmap funkcija), savukārt (>>=) izmantotā funkcija pati atgriež vērtību kontekstā un (>>=) nedara papildus darbību.

Tātad, lai tipu konstruktors (vai konteksts) varētu izmantot fmap, tam ir jābūt definētai Functor instancei. Savukārt, lai konteksts varētu izmantot (>>=) un return, tam ir jābūt definētai Monad instancei.

Mūsu zināmiem konstruktoriem Maybe un [] arī ir sarakstītas Monad instances:

instance Monad [] where
    return x = [x]

    xs >>= f = concat (map f xs)


instance Monad Maybe where
    return x  = Just x

    (>>=) m g = case m of
                   Nothing -> Nothing
                   Just x  -> g x

Turpmāk visus konstruktorus, kas implementē Monad klasi, mēs vienkārši sauksim par monādēm. Tātad, varam teikt, ka Maybe un [] ir monādes.

Lai redzētu, kādas instances ir sarakstītas noteiktajam konstruktoram, var izmantot GHCi funkciju :info:

λ> :info []
data [] a = [] | a : [a]        -- Defined in `GHC.Types'
instance Eq a => Eq [a] -- Defined in `GHC.Classes'
instance Monad [] -- Defined in `GHC.Base'
instance Functor [] -- Defined in `GHC.Base'
instance Ord a => Ord [a] -- Defined in `GHC.Classes'
instance Read a => Read [a] -- Defined in `GHC.Read'
instance Show a => Show [a] -- Defined in `GHC.Show'

IO Monāde

Mēs jau zinām, kā izvadīt rindu - ar funkciju print. Tagad, kad mums ir zināšanas par monādēm un tipu klasēm, apskatīsimies funkcijas print tipu:

λ> :t print
print :: Show a => a -> IO ()

Mēs jau zinām, ka Haskell valodā katrai izteiksmei ir savs tips. Mēs redzam, ka funkcijas print rezultāta tips ir IO (). Mēs jau varam saprast, ka tas ir datu konstruktors IO ar vērtību (), kas ir tukšs pāris. Haskell valodā tukšs pāris bieži tiek izmantots kā tukša vērtība.

IO datu konstruktors ir monāde. Tas nozīmē, ka tam ir implementēta Monad instance un ir sarakstīti kodi funkcijām return un (>>=). Konkrēti IO monādei šos kodus nevar attēlot ar Haskell kodu - tās ir realizētas zemāka līmeņa valodā. Bet, lai darbotos ar šo monādi, tas nav nepieciešams - pietiek zināt funkciju nosaukumus.

IO darbības

IO darbības (IO actions) ir nosaukums, ar kuru tiek apzīmētas IO monādes funkcijas. Tās darbības atšķiras no citām ar to, ka tās izpildas uzreiz - tas ir, nestrādā Lazy princips. Izpētīsim vienkāršu programmu, kas izmantos IO darbības un funkciju cap, kuru sarakstījām nesen:

import Data.Char

cap [] = ""
cap (x:xs) = toUpper x : xs

main = do
    putStrLn "Ievadiet rindu"
    str <- getLine
    (putStrLn . cap) str

Konstrukciju str <- getLine var lasīt kā "izpildīt IO darbību getLine un piesaistīt tās rezultātam vārdu str". Pie tam, <- atbrīvo no konteksta, tas ir, str tips ir String, nevis IO String. Tāpēc zemāk mēs varam mierīgi to padot funkcijai cap, kuras argumenta tips ir String.

Tālāk mēs nedaudz paeksperimentēsim ar šo programmu, pielietojot monādiskās funkcijas.

Mūs interesē tipi katram izteikumam do notacijā. putStrLn "Ievadiet rindu" tips ir IO (). getLine tips ir IO String. Ja iztēloties, ka IO () ir m a, bet IO String ir m b, tad mēs redzam, ka abas izteiksmes var izmantot kā argumentus funkcijai (>>), kuras tips ir m a -> m b -> m b. Aizvietosim abas rindas ar:

str <- putStrLn "Ievadiet rindu" >> getLine

Izteiksmes putStrLn "Ievadiet rindu" >> getLine tips ir IO String, vai m a. Savukārt funkcijas (putStrLn . cap) tips ir String -> IO (), vai a -> m b. Atceramies funkcijas (>>=) tipu - m a -> (a -> m b) -> m b. Acīmredzami, ka mēs varam apvienot arī šīs rindas:

putStrLn "Ievadiet rindu" >> getLine >>= putStrLn . cap

Tā kā mums palika tikai viena rinda, mēs varam atbrīvoties no do notācijas:

import Data.Char

cap [] = ""
cap (x:xs) = toUpper x : xs

main = putStrLn "Ievadiet rindu" >> getLine >>= putStrLn . cap

Uzdevumi

Uzrakstiet programmu, kas ierakstītai rindai apgriež katru vārdu otrādi un aizvieto katru simbolu 'a' ar '4', 's' ar '5' un 'o' ar '0'. Uzrakstiet versiju ar do notaciju, pēc tam pārveidojiet to, izmantojot (>>) un (>>=) funkcijas. Izmantojiet funkcijas words un unwords.

flipWord = foldl (\x y -> y : x) ""

replaceChar c
    | c == 'a' = '4'
    | c == 'o' = '0'
    | c == 's' = '5'
    |otherwise = c

processString = unwords . map (map replaceChar . flipWord) . words

main = do
    putStrLn "Izvadiet rindu"
    str <- getLine
    putStrLn $ processString str

putStrLn "Izvadiet rindu" >> getLine >>=  putStrLn . processString

Monādiskās funkcijas

Šeit būs sarakstītas noderīgas funkcijas darbībām ar monādēm. Dažas funkcijas nāk noklusējuma pakā (Preludē), dažām ir jāveic atsevišķs Control.Monad imports.

(=<<) - pretējā virziena bind funkcija. Darbības principu var izprast no funkcijas definīcijas:

f =<< x  =  x >>= f

join (Control.Monad) - noņem vienu konteksta līmeni, piemēram, m (m a) pārtop par m a. Funkcijas definīcija:

join x  =  x >>= id

Piemēri:

λ> join $ Just (Just 3)
Just 3
λ> join $ Just (Nothing)
Nothing
λ> join $ [[1], [2,3], [4]]
[1,2,3,4]

Nedaudz par id funkciju - tā funkcija atgriež vērtību bez izmaiņām. Var teikt, ka tā funkcija neko nedara. Funkcijas id kods ir id x = x.

Interesants fakts par id funkciju - tā ir vienīgā tīra funkcija, kuras tips ir a -> a, bez konteksta. Padomājiet, kāpēc tieši tā, kā arī padomājiet, kāpēc join definīcija ir tieši tāda.

Atgriežoties pie join - tās tips ir Monad m => m (m a) -> m a. Vēlreiz Jūs varat pamanīt, ka ar Haskell funkcijām bieži darbības principu var saprast, izpētot tās tipu.

liftM (Control.Monad) - Pārveidot funkciju a -> b par m a -> m b. Piemēram, mēs padodam funkciju sqrt, izteikuma liftM sqrt rezultāts būs jauna funkcija ar tipu m a -> m b. Kā var noprast, šī jaunā funkcija pieņem vērtību kontekstā un atgriež vērtību kontekstā. Piemērs:

λ> (liftM sqrt) (Just 5)
Just 2.23606797749979

Funkcijas liftM definīcija:

liftM :: Monad m => (a1 -> r) -> m a1 -> m r
liftM f m1 = do
    x1 <- m1
    return (f x1)

liftM2 (Control.Monad) - pārveido funkciju tipa a -> b -> c par m a -> m b -> m c:

liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2 = do
    x1 <- m1
    x2 <- m2
    return (f x1 x2)

Eksistē arī liftM3, liftM4 un liftM5:

liftM3 :: Monad m =>
        (a1 -> a2 -> a3 -> r)
        -> m a1 -> m a2 -> m a3 -> m r

liftM4 :: Monad m =>
        (a1 -> a2 -> a3 -> a4 -> r)
        -> m a1 -> m a2 -> m a3 -> m a4 -> m r

liftM5 :: Monad m =>
        (a1 -> a2 -> a3 -> a4 -> a5 -> r)
        -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r

ap (Control.Monad) - noder, ja mums ir funkcija monādē, piemēram m (a -> b), un vērtība monādē m a. Rezultāts ir tajā pašā monādē - m b.

ap :: Monad m => m (a -> b) -> m a -> m b
ap = liftM2 id

Piemērs:

λ> ap (Just (+2)) (Just 3)
Just 5
λ> ap [(+2), (^2)] [3,4]
[5,6,9,16]

Ap noder kā aizvietojums liftMn funkcijām: liftMn f x1 x2 .. xn = return f `ap` x1 `ap` x2 `ap` .. `ap` xn.

Uzdevumi

Uzrakstiet funkciju, kas pārveido sarakstu ["abc", "de", "f"] par rindu "abcdef", izmantojot monādiskās funkcijas.

myConcat l = join l

Izveidojiet map funkcijas analogu, izmantojot monādiskās funkcijas.

myMap f = liftM f

Izveidojiet fmap funkcijas versiju, izmantojot (>>=) un return.

myFmap f n = n >>= return . f

Izmantojot monādiskās funkcijas, uzrakstiet funkciju, kas sasummē katru saraksta elementu ar katru otra saraksta elemenu. Piemēram, mySum [2, 3] [5, 6] - [7, 8, 8, 9]

let mySum l1 l2 = liftM2 (+) l1 l2

Uzrakstiet funkcijas liftM4 kodu.

liftM4 f m1 m2 m3 m4 = do
    x1 <- m1
    x2 <- m2
    x3 <- m3
    x4 <- m4
    return (f x1 x2 x3 x4)

Uzdevums, kas neattiecas uz monādiskām funkcijām, bet ir domāts, lai pārbaudītu visu, kas ir iemācīts iepriekš. Izveidojiet programmu, kas saņem rindu ar vairākiem skaitļiem un izvada katra skaitļa ciparu summu, piemēram, "1234 5678" -> "10 26". Izmantojiet funkcijas read un show konvertācijai uz un no Integer, un funkciju sum, lai sasummētu visus saraksta skaitļus. Izmantojiet (>>) un (>>=), neizmantojiet do notāciju. Nevienā funkcijā nedrīkst būt norādīti argumenti - izmantojiet eta reduction visur, piemēram, nevis "foo l = map func l", bet "foo = map func".

toInt = read . return

sumDigits = map (show . sum . map toInt) . words

main = putStrLn "Ievadiet skaitļus" >> getLine >>= putStrLn . unwords . sumDigits

Kopsavilkums

Ap šo laiku mēs esam izgājuši cauri galvenajiem tematiem, ar ko ir pietiekami, lai apgūtu Haskell pamatus. Apkoposim galvenos jēdzienus, kurus ir jāatceras Haskell programmētājam.

Argumenti tiek pierakstīti pēc funkcijas nosaukuma ar atstarpēm. Argumentus var nerakstīt, ja funkcija tiek saīsināta ar eta reduction.
Pastāv gan prefix, gan infix pieraksti funkcijām. Ja funkcijas nosaukums ir burtciparu, tad prefix pierakstā nav nekādu delimiteru - foo a b, bet infix pierakstā ir jāizmanto backquotes simbolus - a `foo` b. Savukārt simbolu funkcijas jeb operatori prefix pierakstā tiek ielikti iekavās - (+) a b, bet infix pierakstā delimiterus izmantot nevajag - a + b
Haskell valodā nopietna loma ir sarakstiem. Galvenās funkcijas darbam ar sarakstiem ir map un fold.
Haskell funkcijas ir Lazy - tiek izpildītas tikai, kad tas tiek prasīts. Tas pats attiecās arī uz rekursīviem datu tipiem.
Tipi ir gan funkcijām, gan datiem, gan izteikumiem. Tipa aprakstā tiek izmantots karing operators ->. Tipa aprakstā var izmantot tipa mainīgus.
Tipu konstruktori vai konteksti veido augstākas kārtas tipus. Tipu konstruktoros var būt mainīgie tipi, piemēram, Maybe a.
Tipu klases apvieno konstruktoru grupas un ļauj definēt nepieciešamās funkcijas grupām. Ar instance konstrukcijām tiek definētas funkciju versijas konkrētam konstruktoram.
Functor klase definē fmap funkciju, Monad klase definē (>>=) un return funkcijas. Maybe un [] konstruktori ir gan funktori, gan monādes.
IO darbības nav Lazy un notiek uzreiz. IO klase ir monāde.

Apmācības turpinājumā mēs vairāk fokusēsimies uz Haskell funkcijām, veidosim dažādas programmas, eksperimentēsim ar funkciju kompozīcijām un sarakstu funkcijām.

1. Teorētiskais minimums

Ievads

Kas ir Haskell

Daži koda piemēri

Funkcijas

Programmas

Kā iesākt

Pirmā programma

Darbs ar interpretatoru

Starpība starp kompilatoru un interpretatoru

Tipi

Primitīvie tipi

Saraksti

Pāri

Funkcijas kā argumenti

Uzdevumi

Argumentu pierakstīšanas iespējas

Pattern matching sarakstiem

Citas pattern matching iespējas

Noderīgas funkcijas

Uzdevumi

Map & Fold

Map

Fold

Map & Fold kodi

Uzdevumi

Funkciju definēšanas iespējas

Prefix un infix pieraksti

Anonīmās funkcijas

Uzdevumi

Karings, Kompozīcijas un aplikācijas

Karings

Kompozīcijas

Aplikācijas

Kompozīcijas un aplikācijas operatori

Uzdevumi

Lazy

Lazy piemēri

Lazy un rekursīvie dati

Savstarpējas rekursijas

List comprehension

Tipu sistēma

Izteiksmju tipi

Uzdevumi

Tipu klases

Tipu klašu veidošana

Tipu klašu īpašību mantošana

Tipu veidošana

Tipu konstruktori

Record pieraksts

Tipu parametri

Maybe konstruktors

Uzdevumi

Funktori

fmap

Funktoru piemēri

Monādes

return

bind vai (>>=)

Monad tipu klase

Vēlreiz par funktoriem un monādēm

IO Monāde

IO darbības

Uzdevumi

Monādiskās funkcijas

Uzdevumi

Kopsavilkums

>> 2. Darbs ar sarakstiem