tut8.hs

factors_ :: Int -> Int -> [Int]
factors_ p k =
    if k * k > p
    then [p]
    else if p `mod` k == 0
        then k:factors_ (p `div` k) k
        else factors_ p (k + 1)

factors :: Int -> [Int]
factors p = factors_ p 2

factors' :: Int -> [Int]
factors' = go 2
  where
    go k p
        | k * k > p      = [p]
        | p `mod` k == 0 = k:go k (p `div` k)
        | otherwise      = go (k + 1) p

isPrime :: Int -> Bool
isPrime n = factors n == [n]

primesTo :: Int -> [Int]
primesTo n = [p | p <- [2..n], isPrime p]

-- prime reseni bez pouziti let/where
gap_ :: (Int, Int) -> [Int] -> (Int, Int)
gap_ (p, q) (a:b:r) = if b - a > q - p then gap_ (a, b) (b:r) else gap_ (p, q) (b:r)
gap_ (p, q) _       = (p, q)

gap :: Int -> (Int, Int)
gap n = gap_ (2, 3) (primesTo n)

-- hezci reseni
gap' :: Int -> (Int, Int)
gap' = go . primesTo
  where
    go [a, b] = (a, b)
    go (a:b:r)
        | b - a >= q - p = (a, b)
        | otherwise      = (p, q)
      where
        (p, q) = go (b:r)
    go _ = undefined


modularPow :: Integer -> Integer -> Integer -> Integer
modularPow b 0 k = 1
modularPow b e k
    | even e    = h
    | otherwise = b * h `mod` k
  where
    h = modularPow (b * b `mod` k) (e `div` 2) k

googolMod :: Integer -> Integer -> Integer
googolMod n k = modularPow 10 (10 ^ n) k

googolMod' :: Integer -> Integer -> Integer
googolMod' 0 k = 10 `mod` k
googolMod' n k = googolMod' (n - 1) k ^ 10 `mod` k
-- 10^(10^(n + 1)) = 10^(10 * 10^n) = (10^(10^n))^10



-- Pattern matching

isZero :: Int -> Bool
isZero 0 = True
isZero x = False

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
-- Pozor, hodně pomalé

-- Patterny se zkoušejí shora dolů. Pokud žádný neuspěje - runtime error

encode :: Char -> Char
encode 'a' = 'd'
encode 'b' = 'q'

-- > encode 'c'
-- *** Exception: ...: Non-exhaustive patterns in function encode
--
-- Další příklady:

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

first :: (a, b, c) -> a
first (x, _, _) = x

len :: [a] -> Int
len []     = 0
len (_:xs) = 1 + len xs

-- [] matchuje prázdný seznam
-- (x:xs) matchuje neprázdný seznam s hlavou x a zbytkem xs
-- (x1:x2:xs) matchuje seznam délky alespoň 2, x1 je první prvek, x2 druhý
-- [x] matchuje seznam s právě jedním prvkem
-- [x,y]
-- atp.

-- Zpátky k fukčním typům. Proč vypadají typy funkcí více argumentů takto?
--
-- a -> b -> c
--
-- Důvod je jednoduchý: všechny funkce v Haskellu jsou pouze unární. Jak to
-- funguje? Podívejme se zpátky na funkci pyth. Jakmile aplikujeme pyth
-- na nějaké číslo x, dostaneme zpátky novou funkci typu Double -> Double, kde
-- první číslo je fixované (a jeho hodnota je x).

pyth3 :: Double -> Double
pyth3 = pyth 3.0

-- > pyth3 4.0
-- 5.0
--
-- > pyth3 10.0
-- 10.44030650891055
--
-- Tedy, a -> b -> c znamená:
--
-- a -> (b -> c)
-- ^    \______/
-- |        |
-- vstup    výstup
--

add :: Int -> Int -> Int
-- add x y = x + y
-- lépe
add = (+)

addTwo :: Int -> Int
-- addTwo x = add 2 x
-- lépe:
addTwo = add 2

-- nebo
-- addTwo = (+) 2
--
-- Syntaktická zkratka:
-- (+ 2) 3 --> 3 + 2
-- (2 +) 3 --> 2 + 3
-- (/ 2)
--
-- Funkce, které vracejí funkce jako návratové hodnoty jsou v Haskellu skoro
-- všude. Můžeme mít ale i funkce, jejichž argumenty jsou funkce!

twice :: (a -> a) -> a -> a
twice f x = f (f x)

-- > twice (+2) 4
-- 8
--
-- Pozor: a -> a -> a -> a  vs  (a -> a) -> a -> a

map' :: (a -> b) -> [a] -> [b]
map' _ []     = []
map' f (x:xs) = f x:map' f xs

i :: a -> a
i x = x

-- > i length [1..5]
-- 5
--
-- Proč tohle funguje?


-- Poznámka ohledně whitespace. Jak Haskell pozná, že začínáte novou definici
-- nebo pokračujete v předchozí? Narozdíl od C# resp. Prologu nemá Haskell ';'
-- resp. '.'
--
-- Odpověd je odsazení. Pár klíčových slov uvozuje tzv. layout (where, let,
-- of, do). Haskell si pak zapamatuje odsazení následujícího kódu.
--
-- Pokud je odsazení další řádky větší, tak je to pokračování předchozí řádky.
-- Pokud je odsazení stejné, tak je to nová řádka (třeba v případě where
-- další lokální definice). Menší odsazení pak ukončuje layout.

test :: Int -> Int
test x =
 x + 2  -- v pořádku, pokračování předchozí řádky

test2 :: Int -> Int
test2 x = z
  where
    y = x * x +
        x       -- Pokračování předchozí řádky
    z = y * y   -- Nová definice

test3 = (+)     -- Konec where

-- Ukázali jsme si, že se funkce dají vracet jako návratové hodnoty a používat
-- jako argumenty. Funkce také můžeme ukládat do datových struktur.

fns :: (Ord a, Integral a) => [a -> a]
fns = [(+2), (*3), max 2, (`div` 2)]

applyArg :: a -> (a -> b) -> b
applyArg x f = f x

-- > map (applyArg 5) fns
-- [7,15,5,2]
--
-- Funkci applyArg použijeme pravděpodobně právě jednou. Můžeme dosáhnout
-- stejného výsledku bez toho, abychom zbytečně definovali extra funkce?
--
-- Odpovědí jsou lambda výrazy (možná taky znáte jako anonymní funkce).
-- Lambdy jsou vlastně něco jako funkční literály.
--
-- Syntax:
--
--   \ arg1 arg2 ... argN -> body
--
-- > :t \x y -> not x || y
-- \x y -> not x || y :: Bool -> Bool -> Bool
--
-- Za tělo funkce se považuje všechno vpravo od ->. Pokud rozsah těla lambdy
-- chceme omezit, stačí vhodně uzávorkovat.
--
-- Předchozí příklad můžeme napsat jako:
--
-- > map (\f -> f 5) fns
-- [7,15,5,2]


-- Příklady na procvičení: mocnění funkcí, součet, součin, mocnina pomocí mocnění funkcí, všechna rozdělení množiny na dvě podmnožiny
-- skládání seznamu fcí