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

0-warmup.md

Cvičení jsme začali rozvičkou, psali jsme ve dvojicích následující funkce:

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry = _

curry :: ((a, b) -> c) -> a -> b -> c
curry = _

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

Nejprve se o implementaci pokuste sami, níže jsem rozepsal postup, který jsme použili na cvičeních:

Funkce uncurry:

1. Všimneme si, že tahle funkce má dva argumenty, tedy je musíme převzít:

uncurry = \f -> \ab -> _

f má typ a -> b -> c ab má typ (a, b) Na to přijdeme buď tím, že se podíváme na sekci "Relevant bindings" v "Typed hole" erroru, nebo najetím myši v IDE. (Nebo rozmyšlením dle typu funkce...)

2. Ze cvičení víme, že foo = \x -> E je to samé jako foo x = E (syntaktický cukr):

uncurry f ab = _

3. Nyní máme vytvořit hodnotu typu c. Jediný způsob jak ji vytvořit je pomocí funkce f, musíme ji tedy použít:

uncurry f ab = f firstArg secondArg
  where
    firstArg = _
    secondArg = _

4. firstArg musí být něco typu a a secondArg má být něco typu b. Jediný způsob jak něco takového získat je z ab, který má typ (a, b), tj. dvojice typů a a b. Musíme tedy rozbalit ab pomocí pattern matchování:

uncurry f (x, y) = f firstArg secondArg
  where
    firstArg = _
    secondArg = _

x je typu a, y je typu b

5. Nyní firstArg má být něco typu a a takovou věc máme -- x:

uncurry f (x, y) = f firstArg secondArg
  where
    firstArg = x
    secondArg = _

6. Podobně pro secondArg a y:

uncurry f (x, y) = f firstArg secondArg
  where
    firstArg = x
    secondArg = y

7. Víme, že v Haskellu můžeme cokoliv inline-ovat, takže inlinujeme firstArg a secondArg (hodily se nám při vytváření, ale teď už nejsou k ničemu):

uncurry f (x, y) = f x y

A máme hotovo! :)

Funkce curry:

Analogicky k předchozí :)

curry f x y = f (x, y)

Funkce zipWith:

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

1. Nejprve převezmeme argumenty f :: (a -> b -> c), xs :: [a], ys :: [b].

zipWith f xs ys = _

2. Když najedeme na typed hole (tj. na _), Haskell říká, že tam chce dostat něco typu [c]. Mohli bychom vrátit něco jako prázdný seznam, ale to není úplně košér (rozumné funkce nezahazují svůj vstup).

Všimneme si, že když bychom nějak dostali jednu věc typu a a jednu věc typu b, tak pomocí funkce f vyrobíme jednu věc typu c.

3. Použijeme pattern matching na xs:

zipWith f [] ys = _
zipWith f (x:xs) ys = _

Co vůbec můžeme vrátit když je první seznam prázdný? Všimněme si, že jediná rozumná věc je prázdný seznam!

zipWith f [] ys = []
zipWith f (x:xs) ys = _

4. Použijeme pattern matching na ys v nedořešeném (druhém) případě:

zipWith f [] ys = []
zipWith f (x:xs) [] = _
zipWith f (x:xs) (y:ys) = _

Opět, dle stejného argumentu jako výše nemáme jak vyrobit cokoliv typu c. Takže jediný seznam věcí s typem c (tj. [c]) je prázdný seznam.

zipWith f [] ys = []
zipWith f (x:xs) [] = []
zipWith f (xs:xs) (y:ys) = _

5. Trochu po sobě uklidíme a zapodtržítkujeme nepoužívané argumenty:

zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = _

6. Zbývá nám vyřešit jediný případ. Zase bychom mohli vrátit prázdný seznam, ale v tu chvíli bychom nepoužili žádný argument v celé funkci, což asi není to co jsme chtěli.

Máme ale f :: (a -> b -> c), x :: a, xs :: [a], y :: b, ys :: [b]. Pomocí f a b jsme schopni vytvořit něco typu c a označíme to jako z.

zipWith f (x:xs) (y:ys) = _
  where
    z = f x y

7. Jak to využijeme? Mohli bychom typed hole (tj. _) nahradit něčím jako [ z ], ale to asi není úplně fajn, protože v tu chvíli jsme zahodili celý zbytek vstupních seznamů (xs a ys).

Vrátíme tedy z : zs, kde zs :: [c] ještě nevíme...

zipWith f (x:xs) (y:ys) = z : zs
  where
    z = f x y
    zs = _

8. Nyní chceme vytvořit zs typu [c]. Jak to uděláme? Mohli bychom zase pattern matchovat na xs a ys a aplikovat na jeden, ale pak bychom měli nějak hodně případů.

Všimneme si ale, že tohle je skvělé místo kde použít rekurzi!

   zs = zipWith f xs ys

9. Zase slušně inlinujeme pomocné definice (jsou dostatečně jednoduché):

zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

Dohromady tedy dostáváme:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

Tahle funkce se chová jako map, ale bere dva seznamy a spojuje je po prvcích :)

Jak si ulehčit práci?

1. Používejte Typed Holes -- pokud nevíte co chcete napsat, plácněte tam _ a nechte si od GHC/IDE pomoct! :)
2. Řiďte se pomocí typů, je to taková logická skládačka, ve které je docela těžké selhat :D
3. Pište i své funkce co nejobecněji to jde. Všimněte si, že jsme se často spoléhali na argumenty jako "je jen jeden způsob jak vytvořit něco typu c". Takové argumenty už ale neplatí pro Int. Například funkce typu a -> a je jen jedna, ale funkcí Int -> Int je (2^32)^(2^32), což je fakt hodně.
4. Naučte se používat Hoogle -- Haskellový vyhledávač, který umí najít funkci nejen dle jména, ale i dle typu: https://hoogle.haskell.org/ Je fakt dobrý! Když do něj hodíte něco jako (Int -> String) -> [Int] -> [String], tak pořád pochopí že jde o map!
5. Naučte se používat své IDE! Pokud používate Haskell Language Server (což byste měli), tak se s ním naučte pracovat. Konkrétně když jste nad Typed Hole, tak můžete zavolat Code Action (kliknout na 💡).

Akce umí věci jako:

• "introduce lambda", což vyrobí nové argumenty
• "case split on <proměnná>", což vyrobí case-of
• "refine hole", které se snaží upřesnit výsledek
• a dokonce "attempt to fill hole", které vám občas napíše celou funkci samo!

Literatura

• Jak vyvíjet pomocí typed holes [anglicky] -- https://reasonablypolymorphic.com/blog/typeholes/

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

-- >>> take 5 jednicky
-- [1, 1, 1, 1, 1]

-- V GHCi můžete použít `:print jednicky`, což vám ukáže co všechno z `jednicky` již bylo doopravdy vyhodnoceno.
-- Vyzkoušejte si to, pak napište `take 10 jednicky` a pak to vyzkoušejte znovu.
-- Měli byste vidět, že se vám spočítalo dalších 5 prvků, které předtím spočítány nebyly.
-- Podobně vyzkoušejte `jednicky !! 15`, a následný `:print jednicky`


-- 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)
-- Všimněte si, že je často jednodušší vyrobit
-- nekonečný seznam a vzít z něj malý, konečný kousek.
-- Nekonečné seznamy v Haskellu se totiž chovají jako iterátory/generátory
-- z klasických programovacích jazyků!

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

-- Důsledky:
-- `head (mergeSort xs)` trvá pouze `O(n)`, protože se spočtou jen porovnání pro první prvek,
-- kterých je nejvýše `n`.
-- To je ale trochu zvláštní, protože `mergeSort` má složitost `O(n log n)`.

-- Nyní si vyrobíme nekonečný seznam fibonacciho čísel!
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- Cvičení: podrobně si rozmyslete co tohle dělá, jak to funguje a v jakém prostoru. :) [Ano, je to efektivní]

2-spongebobCase.hs

import Data.Char ( toLower, toUpper )
-- ^ z modulu `Data.Char` importujeme funkce 'toLower, toUpper :: Char -> Char'.

-- sPoNgEbOb CaSe
-- Na každý znak aplikujeme příslušnou funkci z `stridane`
spongebobCase :: String -> String
spongebobCase s = zipWith (\f c -> f c) stridane s
    where
        -- Nekonečný seznam funkcí, které upraví znak
        -- Konkrétně: první funkce vrátí malé písmenko, druhá velké, třetí zase malé, ...
        stridane :: [Char -> Char]
        stridane = cycle [toLower, toUpper]
        
-- >>> spongebobCase "Vitejte na cviceni z Neproceduralniho programovani!"
-- "vItEjTe nA CvIcEnI Z NePrOcEdUrAlNiHo pRoGrAmOvAnI!"

3-listComprehension.hs

foo :: [Int]
foo = filter (>5) (map (*2) [1..10])

-- List Comprehension je způsob, jak hezky zapsat seznamy.
-- Znáte z Pythonu!
foo' :: [Int]
foo' = [2 * x | x <- [1..10], 2 * x > 5]
-- matematicky { 2x | x ∈ {1, ..., 10}, 2x > 5 }

-- ekvivalentní `foo` i `foo''`
foo'' :: [Int]
foo'' = [y | x <- [1..10], let y = 2 * x, y > 5]

-- Pozor, že tahle notace je sice hezká, ale "špatně spojovatelná".
-- Typicky se z ní nedají vytáhnout rozumné podfunkce ven
-- a hůře se to dekomponuje.
-- Pokud je to možné, spíš doporučuji explicitní `filter` a `map` :)

-- Nekonečný seznam prvočísel pomocí pseudo-Eratosthenova síta
primes :: [Int]
primes = filterPrime [2..]
    where
        -- Runtime error: my víme, že tuhle funkci _nikdy_ nebudeme volat s prázdným seznamem.
        -- Haskell to ale neví a hází warning. Řešení => hodíme runtime error.
        filterPrime [] = error "filterPrime: impossible" 
        -- Invariant: první číslo je vždy prvočíslo.
        -- V každém kroku vymažeme jeho násobky ze zbylých dostupných čísel a zarekurzíme se.
        filterPrime (p:xs) = p : filterPrime [x | x <- xs, x `mod` p /= 0]
        -- ekvivalentně pomocí `filter`:
        -- filterPrime (p:xs) = p : filterPrime (filter (\x -> x `mod` p /= 0) xs)