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

1-definice.hs

-- jednořádkový komentář

{- 
   více
   řádkový
   komentář
-}   

-- Výrazy se v Haskellu píšou s malým písmenkem na začátku.

-- Na levé straně je jméno hodnoty. Používáme =, abychom definovali výraz pod nějakým jménem jako:

ctyricetDva = 42

pozdrav = "Ahoj"

-- Funkce jsou v Haskellu také hodnoty
prictiJednicku = \x -> x + 1

-- Ekvivalentní zápisy z jiných jazyků:

-- Python: prictiJednicku = lambda x: x + 1
-- C#: Func<int, int> prictiJednicku = x => x + 1;
-- C++: auto prictiJednicku = [](auto x) -> auto { return x + 1 }

-- Funkce více argumentů můžeme udělat tak, že uděláme funkci,
-- která vrátí funkci
prictiJednickuASecti = \x -> (\y -> prictiJednicku x + prictiJednicku y)
-- Poznámka:           Tahle ^ závorka není nutně potřeba!

dvakrat = \x -> x * 2

-- Aplikace funkce je _zleva_ asociativní a má velmi vysokou precedenci:

-- >>> dvakrat (prictiJednicku 42)
-- C++> dvakrat(prictiJednicku(42))
-- 86

-- >>> dvakrat prictiJednicku 42
-- to samé jako
-- >>> ((dvakrat prictiJednicku) 42)
-- C++> (dvakrat(prictiJednicku))(42)
-- (tady nedává smysl)

-- Definice funkce je tak častá, že Haskell má i syntaktický cukr
-- tedy místo `dvakrat = \x -> x * 2` stačí napsat:
dvakrat' x = x * 2

-- Podobně pro další funkce:
prictiJednicku' x = x + 1
prictiJednickuASecti' x y = prictiJednicku x + prictiJednicku y

-- Obecně:
-- >>> foo x y = ...
-- je syntaktický cukr pro
-- >>> foo = \x -> \y -> ...

-- Tedy definice funkce vypadá takhle:
-- <název funkce> <arg1> <arg2> ... <argN> = <tělo funkce>

-- Funkce se vyhodnocují stejně jako v lambda kalkulu.
-- Více viz předchozí cvičení (hezky jsem to tam rozepsal...)
ctyricetCtyri  = prictiJednicku (prictiJednicku ctyricetDva)
{-
Příklad vyhodnocení:
ctyricetCtyri = (\x -> x + 1) (prictiJednicku ctyricetDva)   [ vložíme definici `prictiJednicku` ]
              = ((prictiJednicku ctyricetDva) + 1)           [ dosadíme x := prictiJednicku ctyricetDva ]
              = (((\x -> x + 1) ctyricetDva) + 1)            [ vložíme definici `prictiJednicku` ]
              = ((ctyricetDva + 1) + 1)                      [ dosadíme x := ctyricetDva ]
-}


-- Obvod obdélníku:

obvod a b = 2 * (a + b)

-- Obsah obdelniku

obsah a b = a * b

2-operatory.hs

-- Každý operátor je funkce, pokud jej uzávorkujeme
foo  = 5 + 10
foo' = (+) 5 10

-- Naopak z binárních funkcí můžeme udělat binární operátory
-- pomocí backticků (znaku `)
bar  = mod 10 3    -- funkce mod je modulo
bar' = 10 `mod` 3 

-- Typicky se tahle notace používá pro funkce `mod` (modulo)
-- a funkci `div`.

3-castecna-aplikace.hs

{-
Každé funkci můžeme dát jen menší počet argumentů než požaduje.
Pokud má funkce N argumentů a my ji zavoláme s K argumenty,
pak dostaneme novou funkci, která bere (N - K) argumentů.
-}

-- N = 3
sectiTri x y z = x + y + z
-- Vzpomeňte si, že tohle je jen syntaktický cukr pro:
sectiTri' = \x -> \y -> \z -> x + y + z

-- K = 2
-- tahle funkce bere (N - K) = 1 argument
prictiJednicku = sectiTri 0 1
{-
prictiJednicku = sectiTri 0 1
               = (\x -> \y -> \z -> x + y + z) 0 1        [ vložení definice sectiTri ]
               = (\x -> (\y -> \z -> x + y + z)) 0 1      [ uzávorkování ]
               = (\y -> \z -> 0 + y + z) 1                [ dosazení x := 0 ]
               = (\y -> (\z -> 0 + y + z)) 1              [ uzávorkování ]
               = (\z -> 0 + 1 + z)                        [ dosazení y := 1 ]
-}

-- Každá funkce bere jen jeden argument.
-- Jen potenciálně vrací další funkci... :)


tri = prictiJednicku 2
{-
tri = (\z -> 0 + 1 + z) 2 
    =        0 + 1 + 2
    = 3
-}

4-pomocne-definice.hs

-- Občas si chceme pořídit pomocné definice:

-- `let` <promenna> = <výraz> `in` <výraz> 
sectiTri x y z =
    let tmp = x + y
    in tmp + z
    
-- Tahle ^ varianta je sama o sobě výraz (má hodnotu).
-- Dá se tedy psát i něco jako
-- >>> 2 * (let a = 42 in a + 10) + 7

-- alternativně
sectiTri' x y z = tmp + z
    where
        tmp = x + y
        
-- Osobně spíš doporučuji druhý způsob :)

5-typy.hs

-- Haskell je jazyk se statickými typy.
-- Nicméně je ale schopen pro každý výraz najít nejobecnější typ i bez naší pomoci!

-- Typy mají velké písmenko na začátku.
-- Pokud se chcete zeptat GHCi na typ, použijte `:type <výraz>`.
-- Pokud vám GHCi vrátí moc složitý typ (tj. obsahuje, napište `:type +d <výraz>`

pozdrav :: String
pozdrav = "Ahoj!"

-- Pokud se zeptáte GHCi, tak vám řekne typ `pozdrav`u
-- >>> :t pozdrav
-- String

ctyricetDva :: Int
ctyricetDva = 42

--- >>> :t ctyricetDva
-- Int

-- `prictiJednicku` je funkce, která vezme Int a vrátí Int
prictiJednicku :: Int -> Int
prictiJednicku = \x -> x + 1

-- `sectiTri` je funkce, která vezme Int a vrátí (Int -> (Int -> Int))
sectiTri :: Int -> (Int -> (Int -> Int))
sectiTri x y z = x + y + z

-- Z příkladu výše jde vidět, že šipka `->` je _zprava_ asociativní!
-- Tedy se její typ dá zapsat bez závorek jako:
sectiTri' :: Int -> Int -> Int -> Int
sectiTri' x y z = x + y + z

-- Zpravidla píšeme typy pro top-level funkce a deklarace
-- jako formu dokumentace. :)
-- Samozřejmě to není potřeba, protože je Haskell natolik chytrý,
-- že ty typy odvodí i sám, ale dokumentace se hodí.
-- Navíc často se v Haskellu programuje tak, že nejdříve napíšete všechny typy
-- a až potom to naprogramujete...

6-kvadraticka-rovnice.hs

-- Dvojice (pairs) se píšou v Haskellu následovně:
-- Každý prvek dvojice může mít různý typ!

dvojice = (42, "Ahoj!")

-- >>> :t dvojice
-- (Int, String)

-- Následující příklad ukazuje základní použití všech věcí, které jsme si zatím ukazovali:

-- | Vyřeší kvadratickou rovnici tvaru `ax^2 + bx + c = 0`,
--   vrací obě řešení jako pár (dvojici)
vyresKvadratickouRovnici :: Double -> Double -> Double -> (Double, Double)
vyresKvadratickouRovnici a b c = (reseni (+), reseni (-))
    where
        diskriminant = b^2 - 4 * a * c
        -- `reseni` je funkce, která bere další funkci jako svůj argument
        reseni op = (-b `op` sqrt diskriminant) / (2 * a)

-- Cvičení: Podívejte se na funkci výše a pochopte jak funguje.
-- Nápovědou vám budiž všechny předchozí soubory!

7-seznamy.hs

-- (spojové) seznamy v Haskellu:

prazdnySeznam = []

-- v Prologu se píše `[X|Xs]` pro X hlavu, Xs ocásek
-- v Haskellu píšeme `(x:xs)` pro x hlavu, xs ocásek

prvniTri = (1:(2:(3:[])))

-- Samozřejmě má i Haskell syntaktický cukr pro seznamy!

prvniTri' = [1, 2, 3]

prvnichPet = [1, 2, 3, 4, 5]

-- Typ seznamu čísel se píše jako [Int]
-- >>> :t prvnichPet
-- [Int]

-- Všechny položky seznamu musí mít stejný typ!

-- Cvičení: Odkomentuj řádek níže a Haskell vyplivne error:
-- neplatnySeznam = ["Ahoj", 42, 3.1415]

999-haskell-type-system.pl

% Tento soubor obsahuje jednoduchý typový systém
% pro lambda kalkul (takzvaný STLC) s inty a booly navíc.
% https://en.wikipedia.org/wiki/Simply_typed_lambda_calculus
% Je to takový zjednodušený základ pro typový systém Haskellu.

?- set_prolog_flag(occurs_check, true).
% ^ Tahle vlajka zařídí to, že Prolog selže při unifikaci druhu `X = f(X)`.
% To se nám hodí, aby se Prolog nesnažil najít řešení pro rovnici typu `A = A -> B`
% (To by se mohlo stát u výrazu jako `\x -> x x`)

% Vyhledávání v asociovaném seznamu
% to jest seznamu, který v sobě má (key, value) dvojice
lookup([(X,A)|_], X, A).
lookup([(Y,_)|T], X, A) :- \+ X = Y, lookup(T, X, A).

% `typ/4` najde typ daného výrazu
% a prochází až do hloubky dané Fuel
% což je číslo v Peanově aritmetice
% typ(+LookupDictionary, ?Expression, ?Type, +Fuel)

% aplikace E na F má typ B pokud
% ... E má typ A -> B
% ... F má typ A
typ(G, app(E, F), B, s(N)) :-
    typ(G, E, A -> B, N),
    typ(G, F, A, N).
    
% funkce \x -> E má typ A -> B pokud
% ... E má typ B v prostředí, ve kterém má x typ A
typ(G, lam(var(X), E), A -> B, s(N)) :-
    typ([(X, A) | G], E, B, N).
    
% x má typ A, pokud má tento typ v prostředí
typ(G, var(X), A, s(_)) :-
    lookup(G, X, A).

% čísla mají typ int
typ(_, X, int, s(_)) :-
    integer(X).

% konstanty fls, tru mají typ bool
typ(_, fls, bool, s(_)).
typ(_, tru, bool, s(_)).

% A + B má typ int, pokud
% ... A má typ int
% ... B má typ int
typ(_, A + B, int, s(N)) :-
    typ(G, A, int, N),
    typ(G, B, int, N).
    
% Cvičení: Přidejte si ifzero(X, Then, Else), která má typ A, pokud:
% ... X má typ int
% ... Then má typ A
% ... Else má také typ A

% Překonvertuje Prologovská čísla na Peanova
into_peano(0, z).
into_peano(N, s(P)) :-
    N > 0,
    N1 is N - 1,
    into_peano(N1, P).

% Vyrobí výraz dle typu, omezeno hloubkou dle Fuel
synth(Expr, Type, Fuel) :-
    into_peano(Fuel, N),
    typ([], Expr, Type, N).

% Zjisti typ pro daný výraz
infer(Expr, Type) :-
    into_peano(10000, N), % 
    typ([], Expr, Type, N).

%
%   P Ř Í K L A D Y :
%
% najdi všechny výrazy hloubky < 4 typu int
% > synth(E, int, 4).
%
% zjisti typ T pro \x -> 2 + x
% > X = var(x), infer(lam(X, 2 + X), T).
% 
% najdi všechny výrazy hloubky < 5 a typu bool -> bool -> int
% > synth(E, bool -> bool -> int, 5).