Harmadik előadás

Magasabbrendű függvények

A magasabbrendű függvények függvényt várnak, vagy függvényt adnak vissza. Két példa:

map    :: (a -> b)    -> [a] -> [b]  -- elemenkénti feldolgozás
filter :: (a -> Bool) -> [a] -> [a]  -- szűrés

map    even [1..4]   ==  [False, True, False, True]
filter even [1..10]  ==  [2, 4, 6, 8, 10]

A map és a filter megvalósítása generátorokkal és szűrőkkel:

map    f l = [f e | e <- l]
filter p l = [  e | e <- l, p e]

Szeletek

A szeletek operátorokból képzett függvények.

(3 <), (< 3), (^ 2), (4 *), (`div` 2)

A szeletek jól használhatók magasabbrendű függvényekkel.

map (+ 1) [1..5]  ==  [2, 3, 4, 5, 6]

Mi a következő kifejezések végeredménye?

filter (4<)   [1..10]
filter (<4)   [1..10]
map (2^)      [1..10]
map (^2)      [1..10]
map (`mod` 2) [1..10]
map (2 `mod`) [1..10]

A példák megoldásai

Mi a következő kifejezések végeredménye?

filter (4<)   [1..10] == [5,6,7,8,9,10]
filter (<4)   [1..10] == [1,2,3]
map (2^)      [1..10] == [2,4,8,16,32,64,128,256,512,1024]
map (^2)      [1..10] == [1,4,9,16,25,36,49,64,81,100]
map (`mod` 2) [1..10] == [1,0,1,0,1,0,1,0,1,0]
map (2 `mod`) [1..10] == [0,0,2,2,2,2,2,2,2,2]

Függvények kompozíciója

(.) :: (b->c) -> (a->b) -> (a->c) -- függvénykompozíció

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

Állítsuk elő 2 hatványainak listáját hatékonyan.

Készítsük el az even párját, az odd függvényt.

Adjuk meg egy lista utolsó tíz elemét.

Állítsuk elő az 1, 11, 111, 1111, ... sorozatot.

Állítsuk elő a 3, 33, 333, 3333, ... sorozatot.

Állítsuk elő az 1, 31, 331, 3331, ... sorozatot.

A példák megoldásai

Állítsuk elő 2 hatványait.

[2^n | n <- [0..]]

iterate (*2) 1
iterate f x = [x] ++ iterate f (f x)

Készítsük el az even párját, az odd függvényt.

odd  =  not . even

Adjuk meg egy lista utolsó tíz elemét.

reverse . take 10 . reverse

A példák megoldásai (2)

Állítsuk elő az 1, 11, 111, 1111, ... sorozatot.

iterate ((+1) . (*10)) 1

Állítsuk elő a 3, 33, 333, 3333, ... sorozatot.

iterate ((+3) . (*10)) 3

Állítsuk elő az 1, 31, 331, 3331, ... sorozatot.

iterate ((+21) . (*10)) 1

Névtelen függvények

Matematikai minta: x ↦ x + 1

\x -> x + 1           -- ugyanaz mint (+1)
\x -> 2*x + 1         -- ugyanaz mint (+1) . (*2)
\x -> x `mod` 2 == 0  -- ugyanaz mint even

Szeletek és névtelen függvények

Minden szelet egyszerűen átírható névtelen függvénnyé; a fordító is ezt teszi.

(+1)               ===       \x -> x + 1
(`mod` 5)          ===       \x -> x `mod` 5
(2^)               ===       \x -> 2 ^ x

A szeletek használata javasolt, ahol lehetséges.

Számok típusai

A Haskell számrendszere gazdag.

stb.

Esetleges polimorfizmus

(+) :: a -> a -> a

nem jó, mert az összeadás nem értelmezett minden típusra.

Ezért ezt finomítjuk:

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

Alosztályok

Ábra: A Prelude típusosztályainak hierarchiája

Alkalmazás:

Fractional a => a -> a

tulajdonképpen

(Fractional a, Num a,
 Eq a, Show a)        => a -> a

mivel Fractional a-ból következik a többi.

Esetleges polimorfizmus (2)

(+), (-), (*)  :: Num a        => a -> a -> a
(/)            :: Fractional a => a -> a -> a

A számliterálok és a kifejezések is polimorfak:

1230  :: Num a        =>  a
3 + 5 :: Num a        =>  a
1.1   :: Fractional a =>  a
3 / 5 :: Fractional a =>  a
pi    :: Floating a   =>  a

Fordítási időben dől el, hogy a 3+5 kifejezésben a 3 és az 5 milyen számok és hogy az összeadás melyik összeadás.