Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Last active April 29, 2021 19:46
Show Gist options
  • Save jiribenes/cf48cd082ca28b072029f586d2d758d6 to your computer and use it in GitHub Desktop.
Save jiribenes/cf48cd082ca28b072029f586d2d758d6 to your computer and use it in GitHub Desktop.
Cvičení z Neprocedurálního programování - 9
-- Líné vyhodnocování
nekonecny :: [Int]
nekonecny = map (*2) [1..]
-- Jak vůbec Haskell udrží nekonečný seznam v paměti?
-- => logicky jej nemůže udržovat celý!
-- Vyhodnocuje jen _líně_
-- >>> take 5 nekonecny
-- [2, 4, 6, 8, 10]
-- Haskell si teď myslí, že seznam vypadá takhle:
-- 2:4:6:8:10:_
-- s tím, že ještě nemá spočítán zbytek seznamu
{-
Líné vyhodnocování
=================
- vyhodnoť jen když je potřeba
- vyhodnoť jen co je potřeba
- vyhodnoť výraz nejvýše jednou
Pozorování: Líné vyhodnocování neudělá více kroků než striktní.
-}
{-
Příklad líného vyhodnocování v Pythonu:
```
x = 5
if (x == 5):
print("Hello!")
else:
launchMissiles()
```
-}
-- Nekonečný seznam jedniček
jednicky :: [Int]
jednicky = 1 : jednicky
{-
Takhle nějak to v paměti vypadá:
/---\
/ \
\|/ |
|------|---|---|
| 1 | x |
|------|-------|
HEAD TAIL
-}
-- Pomocná definice Fibonacciho čísel
fibo :: Integer -> Integer
fibo 0 = 1
fibo 1 = 1
fibo n = fibo (n - 1) + fibo (n - 2)
-- Ke spočtení délky seznamu _nepotřebujeme_ znát jeho obsah!
-- Tedy následující příklad se spočte instantně:
ctyri = length [2 + 1 :: Integer, 10000 ^ 10000, 1 `div` 0, fibo 4200000000]
-- >>> ctyri
-- 4
-- | Vrátí čísla od n do nekonečna
from :: Int -> [Int]
from n = n : from (n + 1)
-- Jak se to vyhodnocuje?
-- from 10
-- 10 : from 11
-- 10 : 11 : from 12
-- 10 : 11 : 12 : from 13
-- | Vezme prvek a vrátí nekonečnou řadu tohoto prvku.
repeat' :: a -> [a]
repeat' x = x : repeat' x
-- >>> repeat 42
-- [42, 42, 42, ...]
-- | Iteruje funkci nad počátečním prvkem:
iterate' :: (a -> a) -> a -> [a]
iterate' f x = x : iterate' f (f x)
-- >>> iterate not True
-- [True, False, True, False, ...]
-- Obecně:
-- >>> iterate f [1..]
-- [1, f 1, f (f 1), f (f (f 1)), ...]
-- pomocí take a repeat
-- Hezký RL příklad:
mocninyDvojky = iterate (\x -> x * x) 2
-- >>> take 7 mocninyDvojky
-- [2, 4, 8, 16, 32, 64, 128]
-- Chceme něco jako `[x] * n` v Pythonu
-- Ideálně chceme využít `take` a `repeat`
replicate' :: Int -> a -> [a]
replicate' n x = take n (repeat x)
-- | Z konečného, neprázdného seznamu
-- vyrobí nekonečný!
cycle' :: [a] -> [a]
cycle' [] = []
cycle' xs = xs ++ cycle' xs
-- >>> cycle []
-- []
-- >>> cycle [42]
-- [42, 42, 42, ...]
-- >>> cycle [1, 2, 3]
-- [1, 2, 3, 1, 2, 3, 1, 2, 3, ...]
{-
Python:
result = None
for x in xs:
result = f(x, result)
return result
V Haskellu funkce `foldr`
-}
-- | Naše verze funkce 'foldr' --
-- postupně "skládá" seznam s operací, která je asociativní zprava
foldRight :: (a -> b -> b) -> b -> [a] -> b
foldRight _ acc [] = acc
foldRight f acc (x:xs) = f x (foldRight f acc xs)
{-
Jak to vypadá:
foldRight f acc xs =
foldRight f acc [x1, x2, x3, x4, x5] =
x1 `f` (x2 `f` (x3 `f` (x4 `f` (x5 `f` acc)))) =
f x1 (f x2 (f x3 (f x4 (f x5 acc))))
Reálně tedy z:
xs = x1 : (x2 : (x3 : (x4 : (x5 : [] ))))
vyrábí:
==> x1 `f` (x2 `f` (x3 `f` (x4 `f` (x5 `f` acc))))
-}
-- Příklady:
sum' :: [Int] -> Int
sum' xs = foldRight (+) 0 xs
length' :: [a] -> Int
length' xs = foldRight (\_ acc -> acc + 1) 0 xs
-- Verze pro fajnšmekry:
length'' = foldRight (const (+ 1)) 0
-- Kde const je funkce zahazující svůj _druhý_ argument:
const :: a -> b -> a
const x _ = x
minimum' :: [Int] -> Int
minimum' [] = error "minimum': empty list" -- vrátí runtime error, není moc hezké!
minimum' (h:t) = foldRight min h t
maximum' :: [Int] -> Int
maximum' [] = error "maximum': empty list" -- vrátí runtime error, není moc hezké!
maximum' (x:xs) = foldRight max x xs
product' :: [Int] -> Int
product' xs = foldRight (*) 1 xs
-- Tahle funkce je identita na seznamech.
-- Cvičení: Proč? :)
identitaNaSeznamech :: [a] -> [a]
identitaNaSeznamech = foldRight (:) []
-- Dokonce i `map` jde napsat pomocí foldr!
map' :: (a -> b) -> [a] -> [b]
map' f = foldRight (\x acc -> f x : acc) []
-- | Vrátí True pokud prvek x je v seznamu
elem' :: Int -> [Int] -> Bool
elem' x = foldRight (\y acc -> x == y || acc) False
-- | Fold zleva -- foldl ve std knihovně
-- Není to to samé jako foldr!
foldLeft :: (b -> a -> b) -> b -> [a] -> b
foldLeft _ acc [] = acc
foldLeft f acc (x:xs) = foldLeft f (f acc x) xs
{-
Jak to vypadá:
foldLeft f acc xs =
foldLeft f acc [x1, x2, x3, x4, x5] =
((((acc `f` x1) `f` x2) `f` x3) `f` x4) `f` x5
Reálně tedy z:
xs = x1 : (x2 : (x3 : (x4 : (x5 : [] ))))
vyrábí:
==> ((((acc `f` x1 `f` x2) `f` x3) `f` x4) `f` x5
-}
-- Rozmyslete si podobnost s akumulátorem v Prologu!
-- Příkladná funkce:
reverse' :: [a] -> [a]
reverse' = foldLeft (\acc x -> x : acc)
{-
reverse' [1, 2, 3]
= foldLeft (\acc x -> x : acc) [] [1, 2, 3]
= (([] `f` 1) `f` 2) `f` 3)
= 3 : (2 : (1 : []))
= [3, 2, 1]
-}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment