Cvičení z Neprocedurálního programování - 9

1-lazy.hs

-- 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, ...]

2-fold.hs

{-

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]
  
-}