2. Darbs ar sarakstiem

Sarakstu funkcijas

Pirmajā daļā mēs esam apguvuši galvenos Haskell konceptus. Tagad mēs veltīsim laiku jauno funkciju pētīšanai, programmu veidošanai, moduļu apgūšanai un uzdevumu pildīšanai. Un, tā kā sarakstiem Haskell valodā ir nopietna nozīme, mēs sāksim ar tiem.

scan - funkcija, kas dara pilnībā to pašu, ko dara fold, bet atgriež nevis pēdējo akumulatora vērtību, bet visas starpvērtības.

λ> scanl (\a b -> 2*a + b) 1 [2..4]
[1,4,11,26]

scanl funkcijas kods:

scanl f q ls = q : case ls of
    []   -> []
    x:xs -> scanl f (f q x) xs

Pievērsiet uzmanību case .. of konstrukcijai.

Viens no scan pielietošanas piemēriem ir bezgalīgas Fibonači virknes ģenerācija:

fib = 0 : scanl (+) 1 fib

main = print $ take 20 fib

Tikpat viegli ir iegūt bezgalīgu sarakstu ar divnieka pakāpēm:

pows2 = scanl (+) 1 pows2

main = print $ take 20 pows2

Uzdevums: uzrakstiet scanl funkcijas kodu, izmantojot nevis case .. of, bet pattern matching.

myScanl f q []     = q : []
myScanl f q (x:xs) = q : myScanl f (f q x) xs

Uzdevums: uzģenerējiet bezgalīgu sarakstu ar faktoriāļiem - visiem pozitīviem, veseliem skaitļiem sākot no 1, izmantojot scanl.

facts = scanl (*) 1 [2..]

main = print $ take 10 facts

length - atgriež saraksta garumu.

λ> length [1..10]
10

concat - salīmē vairākus sarakstus vienā:

λ> concat [[1], [2, 3]]
[1,2,3]
λ> concat $ words "abc def qwer"
"abcdefqwer"

Funkcijas concat kods:

concat :: [[a]] -> [a]
concat = foldr (++) []

foldr - analogs foldl ar divām atšķirībām. Pirmkārt, foldr iet cauri sarakstam no otra gala. Otrkārt, funkcija, ko izmanto foldr, pieņem argumentus pretējā secībā - sākumā saraksta elements, tad akumulators.

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

scanr - analoģiski scanl satur visas akumulātora vērtības.

scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 []     = [q0]
scanr f q0 (x:xs) = f x q : qs
    where qs@(q:_) = scanr f q0 x

drop - dzēst n elementus no saraksta sākuma.

drop :: Int -> [a] -> [a]
drop n xs     | n <= 0 = xs
drop _ []              = []
drop n (_:xs)          = drop (n-1) xs

λ> drop 5 [1..10]
[6,7,8,9,10]

takeWhile - atlasīt elementus no saraksta sākuma, kamēr tie atbilst noteikumam. Pēc pirmā neatbilstošā var būt atbilstoši elementi, bet tie neiespaidos rezultātu - takeWhile atlasa līdz pirmajam neatbilstošajam elementam, tad apstājas.

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ []                 = []
takeWhile p (x:xs) | p x       = x : takeWhile p xs
                   | otherwise = []

λ> takeWhile (<3) [1,2,3,1,2,1]
[1,2]

dropWhile - dzēst elementus no saraksta sākuma, kamēr tie atbilst noteikumam.

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ []                 = []
dropWhile p (x:xs) | p x       = dropWhile p xs
                   | otherwise = x:xs

λ> dropWhile (<3) [1,2,3,1,2,1]
[3,1,2,1]

reverse - apgriež sarakstu otrādi.

λ> reverse [1..5]
[5,4,3,2,1]

Uzdevums: uzrakstiet programmu, kas pieprasa ievadīt rindu un noņem atstarpes no tās sākuma un beigām. Izdomājiet, kā var realizēt atkārtotas darbības.

twice f = f . f

trim = twice (reverse . dropWhile (== ' '))

main = getLine >>= print . trim

nub - funkcija no bibliotēkas Data.List, izņemt no saraksta visus dublikātus.

λ> import Data.List
λ> nub [1,1,12,1,12,3,4,2,2,3,2,341324,1,412,4,4,21]
[1,12,3,4,2,341324,412,21]

Uzdevums: uzrakstiet funkcijas nub alternatīvu, izmantojot funkciju foldl.

myNub = foldl check []
    where
        check xs x
            | x `elem` xs = xs
            | otherwise   = xs ++ [x]

Ja apskatās funkcijas nub kodu, tad mēs redzēsim, ka tas ir ļoti mazs - nub = nubBy (==). Skaidrs, ka visu darbu dara funkcija nubBy, kura pie reizes ir arī augstākas kārtas funkcija, jo pirmais tās arguments ir funkcija (==). Izpētīsim funkciju nubBy:

nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq []     = []
nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)

Sākumā šis kods nav īpaši saprotams. Tāpēc paskaidrosim ar vārdiem: funkcija nubBy rekursīvi iet cauri sarakstam, pie katra elementa filtrējot atlikušo sarakstu, izmantojot Bool funkciju. Piemēram, ja Bool funkcija ir (==), tad pie katra elementa funkcija izfiltrē no atlikušā saraksta visus elementus, kas ir vienādi ar patreizejo elementu. Tādejādi beigās no saraksta tiks izfiltrēti visi dublikāti.

Asociatīvie saraksti

Tiem, kam ir pieredze tādās valodās kā PHP, Python vai JavaScript, nebūs svešs asociatīvo sarakstu koncepts. Asociatīvais saraksts ir saraksts, kurā indeksi ir nevis skaitļi no 0, bet jebkāda vērtība vai skaitļi jebkurā secībā, piemēram:

var list = [
    "Monday"  : 123,
    "Tuesday" : 456
]

Haskell neļauj par saraksta atslēgām izmantot patvaļīgus datus, bet ir veids, kā realizēt asociatīvus sarakstus, kā arī ir funkcijas, kas atvieglo darbu ar tiem. Lai izveidotu tādu sarakstu, mēs izmantosim pārus - katrs saraksta elements būs pāris, kur pirmais elements ir indekss, bet otrais ir vērtība:

list = [
    ("Monday",  123),
    ("Tuesday", 456)
]

Ir izveidotas funkcijas, kas ļauj darboties ar šādiem datu tipiem:

zip - paņem divus sarakstus un izveido asociatīvo sarakstu, kurā indeksi ir elementi no pirmā saraksta, bet vērtības ir elementi no otra.

zip :: [a] -> [b] -> [(a, b)]
zip (a:as) (b:bs) = (a,b) : zip as bs
zip _      _      = []

λ> zip ["Forty", "Fifty", "Sixty"] [40, 50, 60]
[("Forty",40),("Fifty",50),("Sixty",60)]

Izpētot zip kodu, jūs redzēsiet, ka zip paredz gadījumus, kad sarakstiem nav vienāds garums - tādā gadījumā rezultātā būs tik daudz elementu, cik īsākajā no abiem sarakstiem:

λ> zip [1,2,3,4] ["I", "II", "III", "IV", "V"]
[(1,"I"),(2,"II"),(3,"III"),(4,"IV")]
λ> zip [1,2,3,4] ["I", "II", "III"]
[(1,"I"),(2,"II"),(3,"III")]

lookup - Meklē elementu asociatīvajā sarakstā, izmantojot indeksu.

lookup :: Eq a => a -> [(a, b)] -> Maybe b
lookup _key []                      = Nothing
lookup  key ((x,y):xys) | key == x  = Just y
                        | otherwise = lookup key xys

λ> lookup 2 [(1,"I"),(2,"II"),(3,"III")]
Just "II"
λ> lookup 4 [(1,"I"),(2,"II"),(3,"III")]
Nothing

Eksistē funkcija, kurai nosaukums ir līdzīgs zip, bet ir citādāks pielietojums:

zipWith - izpilda divu argumentu funkciju uz elementiem no 2 sarakstiem.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []

λ> zipWith (*) [1,2,3] [4,5,6]
[4,10,18]

Nav grūti pamanīt, ka zip un zipWith kodi ir līdzīgi. Tāpēc Jūsu uzdevums būs uzrakstīt zip funkciju, izmantojot zipWith:

zip = zipWith (,)

Uzdevums: uzrakstiet funkcijas, kas pārbauda, vai indekss vai elements ir sarakstā. Izmantojiet kopējo palīgfunkciju abām funkcijām.

exists f i = any ((==i) . f)
indexExists i = exists fst i
elemExists  i = exists snd i

>> 3. Eta-conversion