pax_global_header 0000666 0000000 0000000 00000000064 14434637552 0014527 g ustar 00root root 0000000 0000000 52 comment=17cf9447709776b47c4a982b16162b3f0f65fb98
xlogin-main/ 0000775 0000000 0000000 00000000000 14434637552 0013315 5 ustar 00root root 0000000 0000000 xlogin-main/.gitignore 0000664 0000000 0000000 00000000067 14434637552 0015310 0 ustar 00root root 0000000 0000000 _build/*
build/*
data/*
tmp/*
*.pdf
*.svg
*.png
*.jpg
xlogin-main/README.md 0000664 0000000 0000000 00000000061 14434637552 0014571 0 ustar 00root root 0000000 0000000 # xlogin
new xlogin site
# build
`make all`
xlogin-main/common/ 0000775 0000000 0000000 00000000000 14434637552 0014605 5 ustar 00root root 0000000 0000000 xlogin-main/common/header.md 0000664 0000000 0000000 00000000452 14434637552 0016360 0 ustar 00root root 0000000 0000000 # xkucerak
[index](/index.html)
[index](/algo/index.html)
[test](/algo/test.html)
[index](/kocicky/index.html)
[rozdavek_03](/kocicky/rozdavek_03.html)
[test](/kocicky/test.html)
[rozdavek_01](/kocicky/rozdavek_01.html)
[index](/kocicky/cvicenia/index.html)
[ex_01](/kocicky/cvicenia/ex_01.html)
xlogin-main/common/index.css 0000664 0000000 0000000 00000001063 14434637552 0016426 0 ustar 00root root 0000000 0000000 html {
text-align: justify;
}
body {
width: 60%;
margin: auto;
max-width: 800px;
margin-top: 5em;
margin-bottom: 10em;
}
img {
display:block;
max-width:80%;
margin:auto;
}
.quote {
margin-top:2em;
color:black;
padding:1em;
text-align: center;
font-style: italic;
}
@media screen and (max-width: 850px) {
body {
width: 80%;
}
}
@media screen and (max-width: 540px) {
body {
width: 90%;
}
}
@media screen and (max-width: 300px) {
body {
width: 100%;
}
}
xlogin-main/common/out_to.sh 0000664 0000000 0000000 00000000043 14434637552 0016447 0 ustar 00root root 0000000 0000000 out_file=$1
shift 1
$@ > $out_file
xlogin-main/common/preprocess.py 0000664 0000000 0000000 00000013071 14434637552 0017346 0 ustar 00root root 0000000 0000000 from sys import argv
from glob import glob
from os import path
from typing import Optional
import re
TAGS = {
'#root': [('kocicky', '/kocicky/'), ('lowlevel', '/lowlevel/'), ('algo', '/algo/'), ('bell', '/bell/')],
'#kocicky': [('kocicky', '/kocicky/'), ('cvičenia', '/kocicky/cvicenia/'), ('xkucerak', '/')],
'#typci': [('typci', '/typci/'), ('xkucerak', '/')],
'#lowlevel': [('lowlevel', '/lowlevel/'), ('xkucerak', '/')],
'#algo': [('algo', '/algo/'), ('xkucerak', '/')],
'#bell': [('bell', '/bell/'), ('xkucerak', '/')],
}
DESIGN = {
'root':
"""
```
__ __ __
/ž \\_____ /j \\_____ /b \\_____
\\__/-="="` \\__/-="="` \\__/-="="`
```
""",
'':
"""
'typci-old':
```
(⌐■_■)(⌐■_■)
(⌐■_■) (⌐■_■)
(⌐■_■) (⌐■_■)
(⌐■_■) (⌐■_■)
(⌐■_■) (⌐■_■)
(⌐■_■)(⌐■_■)
```
""",
'typci':
"""
```
,_ _
|\\_,-~/
/ | ,--.
▝▀▜█▛▜█▛▀ / ,-'
\\ _T_/-._( (
/ `. \\
| _ \\ |
\\ \\ , / |
|| |-_\\__ /
((_/`(____,-' λ
```
""",
'kocicky':
"""\
```
|\\ _,,,---,,_
/,`.-'`' -. ;-;;,_
|,4- ) )-,_..;\\ ( `'-'
'---''(_/--' `-'\\_)
```
""",
'lowlevel':
"""\
```
,adPPYba,
a8" ""
8b
"8a, ,aa
`"Ybbd8"'
```
""",
'algo':
"""
```
; / ,--.
["] ["] ,< |__**|
/[_]\\ [~]\\/ |// |
] [ OOO /o|__| Finding Karel
```
""",
'bell':
"""
```
_
/\\`--.
|o-| )>=====o
\\/.--'
```
"""
}
PRESETS = {
'kocicky':
"""\
maintitle: Seminár teórie kategórii
pagetitle: Seminár teórie kategórii
header: kocicky
nav: #kocicky
""",
'typci':
"""\
maintitle: Seminár teórie typov
pagetitle: Seminár teórie typov
header: typci
nav: #typci
""",
'lowlevel':
"""\
maintitle: Coočerák's Cringe C Code Corner
pagetitle: Coočerák's Cringe C Code Corner
header: lowlevel
nav: #lowlevel
""",
'algo':
"""\
maintitle: Algoritmy
pagetitle: Algoritmy
header: algo
nav: #algo
""",
'root':
"""\
nav: #root
header: root
""",
'bell':
"""\
maintitle: Should ring a bell
pagetitle: Should ring a bell
nav: #bell
header: bell
"""
}
def get_posts(relpath):
posts = []
for file in glob(f"pages/{relpath}/*.pst", recursive=True):
posts.append(file)
return posts
def build_navigation(posts):
navigation = []
for post in posts:
rel_path = path.join(*post.split(path.sep)[1:])
rel_filename, rel_extenion = path.splitext(rel_path)
html_path = rel_filename + ".html"
navigation.append((path.split(rel_filename)[-1], '/' + html_path))
return navigation
def distinct(lst):
res = []
seen = set()
for e in lst:
if e in seen:
res.append(e)
seen.add(e)
return res
def parse_navigation(nav):
m = re.match(r'\[([^\]]+)\]\(([^\)]+)\)', nav)
name = m.group(1)
link = m.group(2)
return name, link
def print_header(state):
title = 'xkucerak' if state.title is None else state.title
if state.pagetitle is not None:
title += ': ' + state.pagetitle
HEADER = \
f"""\
# {title}
"""
nav = state.nav if state.nav is not None else ['**']
navigation = []
posts = []
for n in nav:
if n.startswith('#'):
navigation.extend(TAGS[n])
if n.startswith('['):
navigation.append(parse_navigation(n))
posts.extend(posts)
navigation.extend(build_navigation(distinct(posts)))
print(HEADER)
if state.header is not None:
print(DESIGN[state.header.strip()])
for name, link in navigation:
real_link = '%ROOT%' + link if link.startswith('/') else link
print(f'[{name}]({real_link})')
print()
class State:
def __init__(self):
self.nav = None
self.pagetitle = None
self.header = None
self.title = None
def eval_value(state, name, value) -> Optional[str]:
if name == 'nav':
state.nav = value.split()
if name == 'posttitle':
state.pagetitle = value
print(f'pagetitle: {value}')
if name == 'header':
state.header = value
if name == 'maintitle':
state.title = value
if name == 'preset':
return PRESETS[value]
if __name__ == "__main__":
filename = argv[1]
counter = 0
state = State()
with open(filename, 'r') as f:
header_added = False
stack = [(f.readlines(), [0])]
overall_index = 0
while stack:
lines, index_ptr = stack[-1]
index = index_ptr[0]
if index >= len(lines):
stack.pop()
continue
line = lines[index]
if not header_added and overall_index == 0 and not line.strip().startswith('---'):
print_header(state)
header_added = True
print(line, end='')
if not header_added and line.strip().startswith('---'):
counter += 1
if counter == 2:
print_header(state)
header_added = True
if counter == 1:
if ':' in line:
line_split = line.split(':')
if len(line_split) == 2:
name, value = line_split
res = eval_value(state, name.strip(), value.strip())
if res is not None:
stack.append(([s + '\n' for s in res.splitlines()], [0]))
index_ptr[0] += 1
overall_index += 1
xlogin-main/common/tikz-to-png.lua 0000664 0000000 0000000 00000001757 14434637552 0017505 0 ustar 00root root 0000000 0000000 local function file_exists(name)
local f = io.open(name, 'r')
if f ~= nil then io.close(f); return true
else return false end
end
--- Create a standalone LaTeX document which contains only the TikZ picture.
--- Convert to png via Imagemagick.
local function tikz2image(src, outfile)
local f = io.open("tmp.tex", 'w')
f:write("\\documentclass[tikz,convert={outfile=" .. outfile .. "}]{standalone}")
f:write("\\usepackage{tikz-cd}")
f:write("\\begin{document}\n")
f:write(src)
f:write("\n\\end{document}\n")
f:close()
os.execute("pdflatex -shell-escape tmp.tex")
end
function RawBlock(el)
-- Don't alter element if it's not a tikzpicture environment
if not el.text:match'^\\begin{tikzcd}' then
return pandoc.read(el.text, 'latex').blocks
end
local fname = pandoc.sha1(el.text) .. ".svg"
local out_file = "pages/" .. fname
if not file_exists(out_file) then
tikz2image(el.text, out_file)
end
return pandoc.Para({pandoc.Image({}, '/~xkucerak/' .. fname)})
end
xlogin-main/gibfile 0000664 0000000 0000000 00000003531 14434637552 0014643 0 ustar 00root root 0000000 0000000 set sh /bin/zsh
set cp /bin/cp
set sed /bin/sed
set rsync /bin/rsync
set python /usr/bin/python3
set pandoc /usr/bin/pandoc
set findsrc /home/sixkey/apps/gib/_build/gib.findsrc
set nochange /home/sixkey/apps/gib/_build/gib.nochange
set out_to $(sh) $(srcdir)/common/out_to.sh
set root ~xkucerak
set all
# Manifest
out manifest.txt
cmd $(findsrc) $(srcdir) manifest.txt
src src_files src_dirs manifest.txt
out dirs
dep manifest.txt
cmd $(nochange) /bin/mkdir -p tmp $(src_dirs:pages*) tmp/$(src_dirs:pages*) $(src_dirs:data*)
# Pages
set pages
for file $(src_files:pages/*.pst)
out $(file:*.pst:$1).pst.prep
dep dirs
dep $(file)
dep common/preprocess.py
cmd $(out_to) tmp/$(out) $(python) $(srcdir)/common/preprocess.py $(srcdir)/$(file) > tmp/$(out)
for file $(src_files:pages/*.pst)
let stem $(file:*.pst:$1)
out $(stem).html.raw
dep dirs
dep $(stem).pst.prep
cmd $(pandoc) tmp/$(stem).pst.prep -f markdown-markdown_in_html_blocks+raw_html -t html -o tmp/$(out) --lua-filter=$(srcdir)/common/tikz-to-png.lua --filter pandoc-include -s --standalone --css %ROOT%/index.css -s --mathjax
for file $(src_files:pages/*.pst)
let stem $(file:*.pst:$1)
out $(stem).html
add pages $(out)
dep dirs
dep $(stem).html.raw
cmd $(out_to) $(out) sed -e s/\/usr\/share\/javascript\/mathjax\/MathJax/mathjax\/MathJax/g -e s,%ROOT%,/$(root),g -e s,%IMGROOT%,$(root),g tmp/$(stem).html.raw
# Data
set datafiles
for file $(src_files:data/*)
out moved_$(file)
dep dirs
add datafiles moved_$(file)
cmd $(cp) $(srcdir)/$(file) $(file)
out data_pls
dep $(datafiles)
dep dirs
cmd $(rsync) -r data/ pages/
# Css
out css
dep common/index.css
dep dirs
cmd $(cp) $(srcdir)/common/index.css pages
# Collect
set xlogin $(pages) data_pls css
add all $(xlogin)
# Syncing
out sync
dep $(all)
cmd $(rsync) -r pages/ aisa:public_html
xlogin-main/pages/ 0000775 0000000 0000000 00000000000 14434637552 0014414 5 ustar 00root root 0000000 0000000 xlogin-main/pages/algo/ 0000775 0000000 0000000 00000000000 14434637552 0015336 5 ustar 00root root 0000000 0000000 xlogin-main/pages/algo/index.pst 0000664 0000000 0000000 00000000116 14434637552 0017173 0 ustar 00root root 0000000 0000000 ---
preset: algo
---
### Príspevky
[kvadratické sondovanie](kv_sond.html)
xlogin-main/pages/algo/kv_sond.pst 0000664 0000000 0000000 00000001674 14434637552 0017541 0 ustar 00root root 0000000 0000000 ---
preset: algo
---
### O nepríjemnosti kvadratického sondovania.
V prípade, že v kvadratickom sondovaní použijem konštanty $c_1 = c_2 = 1$, kde uvažujem $mod\ 7$, tak dostanem
\begin{equation}
\begin{aligned}
h(x, i) = (h(x) + i + i^2) \mod 7
\end{aligned}
\end{equation}
potom uvážme $x$ také, že $h(x) = 0$, potom
\begin{equation}
\begin{aligned}
h(x, i) &= (i + i^2) \mod 7\\
h(x, 0) &= 0\\
h(x, 1) &= 2\\
h(x, 2) &= \boxed{6}\\
h(x, 3) &= 5\\
h(x, 4) &= \boxed{6}\\
\end{aligned}
\end{equation}
A teda v obecnosti nemám garantované, že kvadratické sondovanie "obíde" celú tabuľku kým nájde jednu pozíciu dvakrát a to aj v prípade, že $n$ je prvočíslo a $c_2 \not \equiv 0 \mod n$ a $c_1 \not \equiv 0 \mod n$.
(V prípade, že $c_2 = c_1 = 1$ tak dokonca nefunguje pre žiadnu voľbu $n$).
Konštanty, pre ktorú túto vlastnosť platí ale samozrejme existujú, napríklad v prípade $c_1 = 2, c_2 = 3, n = 6$.
xlogin-main/pages/bell/ 0000775 0000000 0000000 00000000000 14434637552 0015332 5 ustar 00root root 0000000 0000000 xlogin-main/pages/bell/ia014.pst 0000664 0000000 0000000 00000006651 14434637552 0016710 0 ustar 00root root 0000000 0000000 ---
preset: bell
---
created in 2022
### Languages
LISP, Algol, ISWIM, SASL, ML, Haskell, Agda, Idris,
### Lambda calculus
lambda calculus, variable, application, abstraction, combinators (I, K, S,
$\omega$, $\Omega$), lambda term, bound variable, free variable, closed term,
combinator, $\beta$-reduction, redex, substitution, fresh variable, name
capture, $\alpha$-conversion, $\alpha$-equivalence, full $\beta$-reduction,
$\beta-normal$ form, Church-Rosser, unique $\beta$-normal form, strong
normalization property, $\beta$-equivalence, normal form for two
$\beta$-equivalent normalizing terms, $\eta$-conversion, $\beta\eta$-reduction,
confluence of $\beta-eta$-reduction
### Evaluation Strategy
full $\beta$-reduction, applicative order, normal order, call-by-value,
### Mathematics in \lambda-calculus
Booleans and boolean operators, pairs, church numerals and operations (succ,
plus, times, exp, pred, minus), lists
### Applied Lambda-calculi
$\delta$-reduction, constants, $\beta\delta$-reduction, Church-Rosser, syntactic
sugar, conditions, infix notation
### Recursion
manual recursion using $\omega$ combinator, using fixed-point operator FIX, Y
combinator, $\Theta$ combinator
### Simply typed $\lambda$-calculus
variable, application, abstraction (with type), abstraction value,
call-by-value, type syntax, simple type, base type, atomic type, function type,
type constructor, typing context $\Gamma$, type binding, well typed, progress
and preservation property, weak normalization under call-by-value, strong
normalization under full $\beta$-reduction, fix as a primitive, unit, sequence
(as a primitive, derived form), derived form, let, let rec, pairs, lists, type
ascription, lambda cube
### Polymorphism
parametric polymorphism, ad-hoc polymorphism, let polymorphism, system HM, type variable,
monotype, polytype, generic type, free/bound type variable, instantiation,
type substitution, specialization, type ordering, polymorphic fix operator, type
rank
### Type inference
Hindley-Milner algorithm, syntax-directed rule system, algorithm $\mathcal{W}$,
principal type scheme, complexity of $\mathcal{W}$
### System F
variable, typed abstraction, application, type abstraction, type application,
abstraction value, type abstraction value, type variable, type constructor,
universal type, progress and preservation, strong normalization (Girard 1972),
undecidability of "inverse erasure" (Wells 1994), decidability of type-checking,
undecidability of type reconstruction (Kfoury, Wells 1999)
### Type classes
ad-hoc polymorphism, type class, type class declaration, instance declaration, type classes and system HM, deriving, constructor class, kinds, multiparamer type classes, functional dependencies, qualified types, type class environment
### Functor, Applicative, Monad
functor, functor laws (identity, homomorphism), function lifting, applicative functor, applicative functor laws (identity, homomorphism, interchange, composition, fmap), applicative lifting, monad, monadic laws (identity, asociativity), do notation, `MonadError`, `MonadFail`, `MonadState`, Monad tranformers, `MonadTrans`, monad tranformer lifting rules
### Generalized algebraic data types
data where notation, phantom type, generalized algebraic data type (first-class phantom type), type refinement, type inference, safe list, vectors, type families
### Dependent types
dependant types, indexed, parameterized, family, finite sets, dependent pairs,
xlogin-main/pages/bell/ib005.pst 0000664 0000000 0000000 00000011702 14434637552 0016702 0 ustar 00root root 0000000 0000000 ---
preset: bell
---
### Základné pojmy
znak, abeceda, $\Sigma$, $\Sigma^*$, $\Sigma^+$, zreťazenie, prefix, sufix,
iterácia, pozitívna iterácia, doplnok, zrkadlový obraz, substitúcia,
nevypúšťajúca substitúcia, homomorfizmus, inverzný homomorfizmus
### Konečná reprezentácia
gramatika, terminály, neterminály, pravidlá, odvodenie, vetná forma, veta,
reťaz
### Chomského hierarchia
frázová gramatika, kontextová gr., monotónna gr., bezkontextová gr., regulárna
gr., pravolineárna gr.,
### Regulárne jazyky
regulárna gramatika, konečný automat, stavová jednotka, vstupná páska, množina
stavov, koncové stavy, prechodová funkcia, rozšírená prechodová funkcia,
reprezentácia tabuľkou, reprezentácia prechodovým grafom, reprezentácia
výpočetným stromom, synchrónna paralelná kompozícia, lemma o vkládaní, hra
dvoch hráčov, Myhillova-Nerodova veta, dosažitelný stav, pravá kongruencia,
zprava invariantná ekvivalencia, prefixová ekvivalencia, minimálny automat,
determinizmus prechodovej funkcie, jazyková ekvivalencia stavov, redukt
automat, minimalizácia automatu, nedeterministický konečný automat, FA $\har$
reg. gramatika
### Rozšírenia konečných automatov
nedeterminstický konečný automat, determinizácia, exponenciálne zložitý príklad
determinizácie, epsilon kroky, odstraňovanie epsilon krokov
### Regulárne výrazy
definícia regulárnych jazykov induktivne, regulárny výraz (syntax a sémantika),
regex $\har$ FA, Kleeneho veta, regulárny prechodový graf, RPG $\to$ eNFA, RPG
$\to$ RPG s dvoma stavmi
### Uzáverove vlastnosti
zjednoteni, prienik, komplement, zreťazenie, iterácia, regulárna substitúcia,
homomorfizmus, inverzný homomorfizmus
### Bezkontextové gramatiky
bezkontextová gramatika, derivačný strom, ľavá a pravá derivácia,
jednoznačnosť/nejednoznačnosť, vnútorná nejednoznačnosť, nepoužiteľný symbol,
redukovaná gramatika, nedosažiteľný symbol, nenormovaný (redundantný)
neterminál, jednoduché pravidlo, necyklická gramatika, vlastná gramatika,
Chomského normálna forma, lemma o substitúcii, pumping lemma pre CFL,
Greibachovej normálna forma, rekurzivný neterminál, ľavorekurzívny neterminál,
pravorekurzívny neterminál, neľavorekurzívna gramatika, eliminácia
bezprostrednej ľavej rekurzie, eliminácia ľavej rekurzie, vlastná
neľavorekurzívna CFG $\to$ GNF, k-GNF, zdvojená GNF, operátorová normálna forma
### Zásobníkové automaty
nedeterministický zásobníkový automat (push-down automaton - PDA),
konfigurácia, vnútorná konfigurácia, zásobníková abeceda, akceptovanie prázdnym
zásobníkom, akceptovanie koncovímy stavmi, rozšírený zásobníkový automat,
syntaktická analýza zhora-dolu, syntaktická analýza zdola-hore, prevedenie PDA
na jednostavové PDA, prevedenie PDA na CFG
### Vlastnosti bezkontextových jazykov
uzavretie na (zjednotenie, zreťazenie, iteráciu, pozitívnu iteráciu, prienik s
$\mathcal{L_3}$, substitúciu, homomorfizmus, inverzný homomorfizmus),
neuzavretie na (prienik a doplnok), rozhodnuteľnosť (overenie práznosti $L =
\emptyset$, $w \in L$, konečnosť, sebavloženie, $L = \Sigma^*$), vlastnosť
sebevloženia,
### Deterministické zásobníkové automaty
determinisický zásobníkový automat, deterministický bezkontextový jazyk (DCFL),
bezprefixové jazyky, rozšírenie jazyka na bezprefixovosť, rozšírený
deterministický zásobníkový automat, normálna forma PDA, DPDA $\to$ PDA - ktoré
prečíta celé slovo., DCFL vlastná podtrieda CFL
### Uzáverové vlastnosti deterministických jazykov
uzavrenosť na (prienik s regulárnym jazykom, doplnok), neuzavrenosť na prienik,
zjednotenie
### Turingov stroj
Turingov stroj, konfigurácia, riadiacia jednotka, páska, prechodová funkcia TM, výpočet, akceptovanie,
zamietnutie, zastavenie, cyklenie, úplný turingov stroj, jazyk akceptovaný
TM, jazyk rozpoznávaný TM, TM s obojstranne nekonečnou páskou, TM s viacerými páskami,
nedeterministický TM, TM pomocou 2 zásobníkov, TM pomocou 4 počítadiel, TM
pomocou 2 počítadiel
### Rekurzívne, rekurzívne spočetné jazyky a rozhodnuteľnosť problémov
rekurzívny jazyk, rekurzívne spočetný, problémy (rozhodnuťeľné, nerozhodnuteľné,
čiastočne rozhodnuteľný), funkcie (rozhodnuteľné, čiastočne rozhodnuteľné),
násobné stopy, uzavrenosť na (prienik, zjednotenie, zreťazenie, iteráciu),
uzavrenosť rekurzívneho jazyka na doplnok, neuzavrenosť rekurzívne spočetného
jazyka na doplnok
### Lineárne ohraničený automat a kontextové jazyky
Lineárne ohraničený automat, vzťah LBA - kontextových jazykov a
rozhodnuteľnosti, uzavrenosť kontextových jazykov na (zjednotenie, prienik,
zreťazenie, iteráciu a komplement)
### (Ne)Rozhodnuteľnosť
Churchova téza, izomorfizmus TM a jeho binárnej reprezentácie (kódovanie),
univerzálny turingov stroj, problem zastavenia, diagonalizácia, postov
korespondenčný problém, redukcie
xlogin-main/pages/bell/ib031.pst 0000664 0000000 0000000 00000003214 14434637552 0016700 0 ustar 00root root 0000000 0000000 ---
preset: bell
---
### Basic terms
Euclidean norm, overfitting, underfitting
### Anomaly detection
outlier, point outlier, contextual outlier, collective outlier, statistical model, proximity method (distance, density, clustering, ABOD), supervised method, semi-supervised method, unsupervised method, knn, LOF
### Probabilistic classification
conditionally independent, bayes classifier, optimality, complexity reduction using bayes formula, Laplace smoothing, continous features probability, pros/cons, bayesian network
### Linear model
binary classification, linear regression, input vector, weight vector, linear (affine) classifier, non-linear classifier, one-hot encoding, consistent classifier, perceptron algorithm, Rosenblatt theorem, batch learning algorithm, function approximation, gradient, squared error function, dataset, gradient descent, linear regression, pros/cons
### Logistic regression
logistic regression, odds, logistic sigmoid, binary cross-entropy, maximum-likelihood vs cross-entropy
### SVM
support-vector machine, support vector, margin, distance, lineary separable, reduction to quadratic programming, pros/cons
### Neural networks
neuron, inner potential, weights, bias, activation function (sgn, id, logistic sigmoid, tanh, relu, leaky relu, elu), multilayer perceptron, input/hidden/output layers, perceptron, expressive power of MLP (Cybenko's theorem), batch gradient descent, stochastic gradient descent, minibatch, convergence, overfitting, hold-out validation, transfer learning, vanishing gradient, convolutional neural network, convolutional layers, pooling layers (max-pool, L2-pool, average-pool), backpropagation
xlogin-main/pages/bell/ib107.pst 0000664 0000000 0000000 00000000051 14434637552 0016700 0 ustar 00root root 0000000 0000000 # Enumerácia vyčíslitelných funkcií
xlogin-main/pages/bell/index.pst 0000664 0000000 0000000 00000000562 14434637552 0017174 0 ustar 00root root 0000000 0000000 ---
preset: bell
---
Táto stránka slúži ako (moja) zbierka kľúčových slov pre jednotlivé predmety.
Tieto termíny by mali pôsobiť minimálne povedomo.
[IB005 - Formálne jazyky a automaty](ib005.html)
[IB031 - Úvod do strojového učenia](ib031.html)
[IA014 - Advanced Functional Programming](ia014.html)
[IV109 - Modelovanie a simulácie](iv109.html)
xlogin-main/pages/bell/iv109.pst 0000664 0000000 0000000 00000022323 14434637552 0016734 0 ustar 00root root 0000000 0000000 ---
preset : bell
---
vytvorené v 2022
### Komplexné systémy
komplexný systém (organizovaná zložitosť), agregát (neorganizovaná zložitosť),
stroje (organizovaná jednoduchosť), analytické metódy, štatistika, simulácia,
príklady komplexných systmémov (ekosystém, trh, podnebie, organizácia,
mravenisko, bunka, mesto...), emergentné chovaniea, statická rovnováha,
dynamická rovnováha, nelineárne vzťahy, spätná väzba, vznik systému zo spodu/z
vrchu, adaptabilné, induktívne vs. deduktívne myslenie, centralizované vs
decentralizované, lineárne uvažovanie, krátkodobé uvažovanie, korelácia a
kauzalita, potom - takže preto, experiment 2-4-6, výhody výpočetných modelov,
systémový pohľad
### Obecné princípy
model, simulácia, mapa, účel nad realizmus, myslenie ako modelovanie,
abstraktné, konkrétne, účely výpočetných modelov a simulácii (porozumenie,
objavovanie a formalizovanie hypotéz, predpovedanie, návrh a zásahy do
systémov, výuka, tréning, zábava), matematické vs výpočetné modely, štatistické
vs. výpočetné, základné fázy modelovania (formulácia problému, základný návrh,
budovanie modelu, verifikácia modelu, simulácie a analýza, sumarizácia
výsledkov), návrh moledov (jednoduchosť, okraje modelu, prkvy, popis vzťahov),
validácia a verifikácia
### Spätné väzby
pozitívne a negatívne, negatívna spätná väzba (šoférovanie auta, termostat),
pozitívna spätná väzba (erózia, formácia miest, monopol), pozitívny cyklus,
negatívny cyklus
### Matematické modelovanie
modelovanie z vrchu, súhrné premenné, systémy rovníc, stav systému, chovanie
systému, diskrétny (rekurentné rovnice, logistická rovnica, Fiegenbaumov
diagram) vs. spojíty čas (diferenciálne rovnice), numerické metódy, diskretizácia, approximácia
(eulerova metóda, metóda runge-kutta), systémová dynamika (zásobarne, toky,
parametre, vzťahy), líšky a zajace, SIRS, polya processa (čierne a biele kamene), demografia, veková
pyramída, cohort, hypotéza Gaia, daisyworld, vývoje (lineárne, exponenciálne,
logistický, prestrel a kolaps)
### Medze rastu
nosnosť planéty, vysoká abstrakcia, hrubý model, pessimism in pesimism out
### Bunečné automaty
modelovanie od spodu, diskrétny priestor a čas, mriežka, triedy
(legal, totalistic, outer-totalistic, additive), wolfrámová klasifikácia (fixný
stav, jednoduché cyklenie, chaotické, zložité vzory), Langtonov parameter,
conway's game of life, nerozhodnuteľnosť GOL, Langtonov automat, rozšírenia
bunečných automatov, príklady (vzory na zvieratách, požiare, erózia, chémia)
### Agent based model
ABM, príklady (dravec korisť, hlenka, mravce [pohrebisko, skládka, cesty k
potrave, swarm intelligence], termiti, boids, fireflies, segregation, doprávna
zápcha, nepokoje, trhy, ekosystémy, epidémia, vojny, súboje), autonomny agent,
lokálnosť a emergentné chovanie, netlogo (agenti, políčka, links, kontexty),
systémová dynamika vs. ABM, samoorganizácia, fázový prechod, centralizovaný vs.
decentralizovaný, náhoda, rast kvetiny (rast v tme spôsobuje naklonenie k
svetlu), celok vs. časť, robustnosť vs. efektivita, decentralizované uvažovanie
### Teória hier
využitie (ekonómia, politológia, psychológia, biológia, ..), agenti
(racionalita, rozhodovanie, znalosti o chovaní ostatných), 2/3 číslo, piráti,
hra s nulovým súčtom (kameň papier nožnice), hra s nenulovým súčtom,
stratégia, ekvilibrium, čistá stratégia, mixovaná stratégia
### Spolupráca
vznik alrtuizmu, prisonner dilema, kura, lov na jeleňa, realita vs. racionálna
stratégia, Axelrodov turnaj, TFT má výhodu robustnosti, rozšírenia: rušenie -
priestor, altruizmus v hre s nenulovým súctom, tien budúcnosti, vývoj noriem,
norms game (boldness, vengefulness), altruizmus v bunečnom automate
### Modelovanie komplexných sietí
komplexná sieť, spoločné vlastnosti, abstraktné modely, náhodné grafy vs.
namerané grafy, príklady (firmy, vzťahy, sexuálne vzťahy, biológia, internet,
nueronové siete), small world phenomenon, clustering, scale-free, Milgramov
experiment, six degrees of seperation, Erdos/Bacon number, koeficient
zhlukovania, distribúcia stupňov pri náhodnom a komplexnom grafe, Poissonov a
mocninový zákon, príklady mocniného zákonu (rozdelenie bohatsva - Paretov
princip, meteority, velikosť mesta, zastúpenie slov v texte, ...),
assortativity, grafové motívy, váhy hran, degree centrality, closeness
centrality, betweeness centrality, hubs, Erdos-Renyi model (log n distance,
poisson degree distribution, fázový prechod), small-world graphs (log n
distance, cycles with chords, poisson degree distribution), scale-free networks
(construction, preferential attachment, log n distance, power law degree
distribution, positive feedback loop in construction), zhlukovanie v sieťach,
robustnosť siete, chyby a útoky na náhodné a bezškálovité siete, dynamické
efekty pozitívne spätné väzby v poškodených sieťach, šírenie po sieťach a
imunizácia (kritická hranica a uniformná imunizácia v homogénnych a
bezškálovitých sieťach), Kleinbergov model, dylema väzňa v sieťach, simulovanie
SIR modelu na sieti
### Metódy analýza modelov
sensitivity analysis, referenčné dáta, súvislosť, štatistická analýza,
### Modelovanie epídémii
príklady (choroby, počítačové vírusy, názory, informácie, móda), parametre
(infekčnosť, inkubačná doba, úmrtnosť), otázky (dynamika, vpliv štruktúry
kontaktov, prevencia, imunizácia), SIS (logistický rast), SIR (McKendrick
model), SIRS (), modelovanie pomocou agentov (S, I, R), epidémie v sieťach,
rozšírenia (kontakty v populácii, heterogenita populácie, dynamika v čase,
zásahy proti, mutácie), populácie (homogénna, subpopulácia, abstraktný model
spol. života, sociálna sieť, konkrétne dáta), smallpox model, systém EpiSimS,
### Modelovanie myslenia
motivácia (pochopenie prírody, komplexné systémy, algo), kognitívne modelovanie
vs. umelá inteligencia, symbolické modelovanie vs. konekconistické modelovanie,
procukčný systém, produčné kolízie, klasifikačný systém, bucket brigade,
genetický algoritmus, woods example, el farol bar example, adaptive control of
thought-rational), neurónové siete, deep learning
### Evolúcia
jednoduchý proces s komplikovanými dôsledkami, príklady (mole), survival of the
reproducers, netopiere vs. mole, koevolúcia vírov a antivírov, genetický
algoritmus, mutation and crossover, TSP, evolved virtual creatures, Axelrod's
prisoner dilemma, evolučne stabilná stratégia, altruizmus, lokálne extrémy,
tierra
### Modelovanie dopravy a davov
mikrosimulácia pomocou ABM vs makrosimulácia pomocou súhrnýčh premenných,
otázky (efekty mýtneho, verejná doprava, plán ciest, emisie, hluk),
Braessov paradox, modelovanie davu (požiary, koncerty, uzly záujmu)
### Počasie a klíma
počasie vs. klíma, dynamika a fyzika v modelovaní počasia, grid point models,
spectral models, Global forecast system, Aladin, IPCC, modelovanie klími
(zistenie dát, interpretácia dát, modelovanie a kalibrácia modelu, zhrnutie),
rôzne modely (trojrozmerné modely, jednoduché abstraktné modely)
### Biológia
model vs. simulácia, výhody (núti ujastniť detaily, lacná a neškodná
manipulácia), bunka organizmus (rast organizmu, formovanie vzorov na kožuchu,
diferenciácia buniek, vpliv teploty, výber partnera, etc.), druh (pohyb, stáda,
etc., epidémia), ekosystém (evolučné mechanizmy, znečistenie), počítač v bio: objavovanie vs.
modelovanie a simulácia, systémová biológia, SBML, in vivo in vitro in silico,
vývoj vulvy u C. elegans, statecharts model, kalibrovanie modelu pomocou
nezrovnalostí, genetic regulatory networks (spätné väzby), boolean networks,
kinetické modely, diferenciálne rovnice, hybridné modely, chemotaxe, brezový les
pomocou CA
### Sociálne vedy
prehrávanie minulosti pomocou ABM, absencia reálných meraní v archeológii,
Anasazi culture (dobré dáta z minulosti, multiagent model, jedlo - sťahovanie -
rozdelenie), modelovanie vzbury (ABM - HLGR, etnické násilie, pozitívna a
negatívna spätná väzba), modelovanie ekonómie: neoklasická ekonómia pomocou
analytického riešenia vs. agent-based computational economics, artificial stock
market (classifier na hodnote dividend a aktuálnej cene, induktívne učenie
agentov, genetický algoritmus, vývoj pri rýchlom a pomalom učení), presun od
matematických modelov k agentom
### Pákové body
systémove myslenie do bežného života, konstanty-parametry-čísla, velikosti buferov a ďalších stabilizujúcich zásobarieň, štruktúra materiálnych zásobarieň a tokov, doba opozdenia, sila negatívych spätných väzieb, sila pozitívnych spätných väzieb, štruktúra informačných tokov, pravidlá systému, menenie vyvíjanie a samoorganizovanie štruktúru systému, ciele systému, paradigma z ktorého vychádza systém, moc presahovať paradigma, sústredenie na stred zoznamu vs. sústredenie na začiatok zoznamu, politika (paradigmata, ciele, samoorganizácia, pravidlá, informačné toky)
> A hen is only an egg's way of making another egg. - Samuel Butler
TODO: ACT-R
TODO: Systémové modelovanie
xlogin-main/pages/bell/pb009.pst 0000664 0000000 0000000 00000014731 14434637552 0016722 0 ustar 00root root 0000000 0000000 # Basics
raster graphics, vector graphics, color mixing: additive, subtractive; pixel format: integer, float; conversions: rasterization, vectorization
# Rasterization
rasterization of line: Digital Differential Analyzer, Bresenham Algorithm, DDA with antialiasing; circle rasterization: Digital Differential Analyzer, approximation aspects ( determinants, taylor expansion, etc.); reconstruction; aliasing; flood-fill (4-neigh, 8-neigh version), rasterization of a triangle: line rasterization + bucket-fill, Pineda algorithm; barycentric coordinates, color mixing in triangle;
# Clipping
point clipping: axis-aligned-box, convex polygon (edge function), general polygon (ray casting); line clipping: axis-aligned-box (Cohen-Sunderland, Cyrus-Beck, Liang-Barsky, Nicholl-Lee-Nicholl; polygon clipping: Sutherland-Hodgman, Greiner-Hormann
# Spacial data representation
requirements (uniqueness, unambiguity, completeness, precision, compactness, ease of use, wide application, good for algorithms, error proof); geometry vs. topology; vertex, edge, face, solid; point cloud, wireframes, surface (polygon mesh, implicit surface, parametric surface), volumetric (voxels, octree, constructive solid geometry, B-rep); implicit, parametric, explicit; photogrammetry; range-image (2.5D representation); point-cloud visualization (billboarding, splatting, conversion to mesh via trianglulation); particle systems (billboarding, metaballs); surface representation: wireframe, polygon soup, polygonal mesh; mesh types (structured mesh, unstructured mesh, hybrid mesh); manifold mesh; half-edge; winged-edge; parametric surface; implicit surface; metaballs; ray casting; ray marching (uniform sampling, binary search, sphere-based search); voxel volume representation (scalar, vector); slicing; iso-surface extraction (threshold, marching cubes); volume ray marching; octree; solid modeling; volumetric mesh; constructive solid geometry (CSG) (conversion to mesh, raymarching, raycasting); Boundary representation (B-rep); Euler Formula
# Affine spaces and transformations
points vs. vectors; vector space; affine space; affine transformations (translation, rotation, scale, shear) homogeneous coordinates; homogeneous transformations (translation, rotation, scale, shear); line transfer and applications (rotation around a plane normal, mirror through plane); model space; world space; camera perspective; view matrix; look-at function; perspective vs. orthographic; points at infinity in homogeneous coordinates; perspective projection; orthographic projection; P * V * M * p;
# Curves
parametric representation; implicit representation; parametric representation as a combination of points; derivatives of curves; parametric continuity classes $C^i$; geometric continuity classes $G^i$; Lagrange Polynomial; Catmull-Rom Cubic Spline (Hermite Cubic); Bernstein Polynomial; Bezier Curve; deCastelqau algorithm; B-spline (knots, knot spans, basis functions); deBoor algorithm; rational curves; weights for control points;
# Surfaces
parametric surfac; barycentric coordinates; explicit vs. implicit; curves on surfaces (general curve, isocurves); parametric continuity classes; geometric continuity classes; Lagrange surface; Hermite bicubic; Ferguson surface; ruled surface; Coons bilinear surface; Bezier surfaces; deCasteljau algorithm; B-spline surface; deBoor surface; Bezier triangle and its deCastelqau algorithm; rational surfaces;
# Visibility checking
motivation (objects are big and many polygons hidden, many polygons are outside the frustum, many polygons are behind other polygons, many polygons are back-polygons); approaches (object space methods, image space methods); back-face culling; depth duffer (z-buffer); z-fighting artifacts; a-buffer; ray casting; accelerated ray casting; z-buffer vs. raycasting; painter's algorithm (algoirthm, infinite loop prevention, benefits and problems); bsp-trees (construction, use for rendering, benefits and problems); view frustum culling; transformation to ndc (local space, world space, view space, clip space, ndc space)
# Colors
emission spectrum; achromatic light; absorption/reflection spectrum; black and white; difffuse reflection vs. specular reflection; human vision; human eye (pupil, iris, lens, retina, fovea, optic nerve); rods vs. cones; trichromatic vision; types of cones (short, mid, long) (sensitivity green and blue); oppoent process theory (green red, blue yellow, black white); intensity vs. brightness; adaptation to light conditions; horizontal and vertical vs. diagonall resolution; lightness-color constancy; lateral inhibition; color vision deficiencies; receptor sensitivity; light spectrum; metamers; additive model (rgb); subtractive model (cmyk); conversions; other models (hsv vs. hsl, hcv vs. hcl; Y'CrCb; SML; L*a*b; Pantone); CIE XYZ; CIE colorspace; CIE chromacity diagram; sRGB (other models; Adobe RGB; CMYK); Gamut; displaying colors; color depth (true color, deep color);
# Lighting
empirical vs. physical models; light sources (ambient, point, spot, directional, surface light); surface lighting effects (ambient, diffuse, specular, refraction); Lambert's law; empirical Phong model; Fresnel's law; Blinn-Phong specular model; Phong lighting model;
# Shading
shading; interpolation; flat shading; Gouraud shading; Phong shading
# Texture
2d texture; texture mapping (uv mapping); basic texture mappings (planar, cylindrical, spherical, box); problems with real-to-discrete step (nearest neighbour, bilinear filtering); magnification and minification; mipmaps and trilinear filtering; examples of texture types (diffese texture, light map, environment texture, bump map, normal map, displacement map, specular map); 3d texture; procedural texture; texture wrapping;
# Rendering equation
rendering equation (radiance, emitted radiance; irradiance; bidirectional reflectance distribution function; BRDF (steradian, non-negativity, conservation of eneregy, Helmholtz reciprocity principle, isotropic material, anisotropic)
# Ray tracing
basic ray tracing (primary ray, secondary ray, shadow ray); ray tracing tree; Snell's law (indices of refraction); local illumination; Ray-AABB intersection; AABB tree; surface lights; motion blur; antialiasing; distributed raytracing (sampling primary rays for pixel, sampling shadow rays for surface light);
# Radiosity
radiosity; emitted radiosity; system of linear equations; form factor;
# Photon mapping
two passes (light distribution to surfaces in the scene - casting light rays, casting primary rays); phonot map; colour bleeding; caustics;
xlogin-main/pages/bell/pv080.pst 0000664 0000000 0000000 00000016360 14434637552 0016745 0 ustar 00root root 0000000 0000000 # Privacy
privacy, personal data, anonymity, pseudonimity, unlinkability, unobservability, Mixes (Mix network), Common Criteria, Identity
# Personal Data Protection
privacy protection vs. personal data protection, GDPR, data subject, personal data, theoretically identifiable vs. practically identifiable, sensitive presonal data, processing of personal data, controller, processors, principles relating to processing of personal data (art 5), controller duties, lawfulness of processing (art 6), right to access (art 15), absorption principle, balanced sanctions
# Privacy techniques and selected issues
data aggregation, statistical databases, computer ethics, problems with copies, general and professional ethical principles
# Cryptography
cryptography, steganography, cryptanalysis, cryptology, confidentiality, data integrity, data authentication, entity authentication, data availability, non-repudiation of origin, Kerckhoffs' principle'
# Encoding and Encryption
encoding, decoding, encryption, key targeting attacks ( bruteforce search, educated guess using pt-ct statistical analysis, decrypting and judging if meaningful ) and countermeasures ( big keys, randomness of ciphertext ), Vernam Cipher, inicialization vector, stream ciphers, block cipher, data encryption standard, lock ciphers attacks ( brute-force, ciphertext-only, known-plaintext-ciphertext, chosen-plaintext, chosen-ciphertext ), attacker model, passive adversary, active adversary, advanced encryption standard, modes of operation (ECB, CBC, CTR, OCB, OFB ), randomness, true random, pseudorandom, deterministic generator, non-deterministic generator, hybrid generator, system generator vs. std lib generators
# Hash Functions
hash function, digital signature, avalanche effect, one-wayness ( preimage resistance ), weak collision resistance ( second preimage resistance ), strong collision resistance, birthday paradox
# Authentication
symmetric crypto ( shared key ), message authentication code ( MAC ), hash-based message authentication code ( HMAC ), authenticated encryption through composition ( mac-pt-then-encript, mac-ct-after-encrypt, encrypt-and-mac-plaintext ), authenticated encryption with associated data ( AEAD ), Public-key cryptography, hybrid encryption, digital signature, using keypair for signing and encryption, rsa, public-key certificate, certificate generation, certification authority, certificate chain validation, public-key infrastructure, timestamping
# Electronic identification ( eIDAS )
eIDAS assurance levels, simple electronic signature, advanced electronic signature, qualified electronic signature, legal effects of electronic signatures (art 25)
# Hard problems
integer factorization, discrete logarithm, rsa issues ( small primes, prime bias, quantum computers ), roca vulnerability
# Cryptograhic protocols
unilateral authentication, cryptographic protocol, challenge-response, relay attack, authentication and key establishment / authenticated key establishment, session key, ephemeral key,
key transport ( key distribution center, key translation center ), time-variant parameters, Diffie-Hellman, man-in-the-middle for DH, authentication protocls attacks ( replay, reflection, relay, interleaving, middle-person, dictionary, forward search, pre-capture ), station-to-station protocol, Needham-Schroeder symmetric key protocol, kerberos, key distribution center, authentication server, ticket-granting-server, transport layer security ( TLS ), secure shell
# Secure programming
security features != secure features, defensive programming, bug, vulnerability, proof of concept, exploit, whitehat, blackhat, blue vs. red team, whitebox, graybox, blackbox, archicecture review, code review, deployment review
# Identity and access management
identity, attributes for identification ( domain, functional, temporal - permanent-given, permanent-gained, permanent-situational, transitional ), methods for authentication ( something we know, something we have, something we are, somewhere we are ), direct attacks ( online passwords guession, offline passwords guessing, password capture ), bypass attacks ( interface bypass, defeating recovery mechanisms ), password manager, single-sign-on, multiple factor authentification, password recomemendations ( long, complex, mfa, password manager ), hardware tokens, biometrics, authentication vs. identification, problems with biometrics ( never 100% match, remote authentication, not secrets ), failure to enrol ( FTE ), failure to capture ( FTC ), biometrics characteristics ( universality, distinguishability, ease-of-sampling, cost, user acceptance, attack-resistance ), fingerprints ( replay attacks with fakes vs. liveness detection )
# Authorization
authorization vs. authentication, role-based access control, identity management, saml, spml, freeipa, oauth, least privilege, default deny, NIST, eIDAS
# Computer security
computer security, information security, cybersecurity, confidentiality, integrity, authorization, availability, authentication, accountability, trusted system, asset, vulnerability, security policy, system as a state machine, countermeasures, controls, attacker model ( objectives, methods, capabilities, funding level, outsider vs. insider ), adversary classes, Needham & Schroeder, dolev yao, formal security evaluation vs. pen testing, security analysis vs. vulnerability assessment, threat model, thread modeling, STRIDE, 3 + 1 key questions
# Network testing and assessment
active network monitoring, passive network monitoring, hub vs. switch, packet capture, network tap, network span, intrusion detection, intrusion detection system ( IDS ), intrusion prevention system, host-based IDS, network-based IDS, approaches to intrusion detection ( sigatur-based, specificatio-based, anomaly based, vulnerability assessment, network mapping, vulnerability scanning, penetration testing
# Network-based attacks
distributed denial of service ( direct, reflection, syn flooding ), address resolution attacks
# Usable security
usefulness, utility, usability (learnability, efficiency, memorability, errors, satisfaction ), security vs. usability vs. usable security, don't blame the user, mental model, impact pyramid, principles ( you are not your user, prefer system usability over user training, the user is not your enemy, think of usability on all levels, have secure defaults,
# Security policy, risk assessment, business security, operations
steps ( risk assessment execution, security policy, security architecture,
security mechanisms, monitoring of events ), security policy, Bell-LaPadula
confidentiality policy, security policy at high level, system security policy,
risk, risk assessment, principal risk assessment qusetions, quantitative risk
assessment, annula loss expectency, problems with
quantitative risk assessment, qualitative risk assessment,
information security management system, ISO/IEC 27000
plan do check act ( PDCA ), ISO/IEC 27000 nine steps to success, it security audit,
business continuity planning, disaster recovery, recovery point objective, recovery time objective
# Security standards
ISO vs. IETF, NIST, Common Criteria, functionality vs. assurance, target of evaluation, protection profile, security target, security funcional requirements
# Misc.
phishing, spear phishing, social engineering, identity theft, mental model
xlogin-main/pages/index.pst 0000664 0000000 0000000 00000000150 14434637552 0016247 0 ustar 00root root 0000000 0000000 ---
preset: root
pagetitle: xkucerak
author: Filip Kučerák
---
:::{.quote}
Život je boj.
--VoZP
:::
xlogin-main/pages/kachnapls/ 0000775 0000000 0000000 00000000000 14434637552 0016360 5 ustar 00root root 0000000 0000000 xlogin-main/pages/kachnapls/vim_coc_disable_hlint.pst 0000664 0000000 0000000 00000002114 14434637552 0023406 0 ustar 00root root 0000000 0000000 ### How to disable hlint in coc.
I currently run [coc](https://github.com/neoclide/coc.nvim) together with [haskell-language-server](https://github.com/haskell/haskell-language-server) in vim for
haskell development. I wrote a simple piece of code, that was blasted with
hlint suggestions. Is there a simple way of disabling it?
[Here](http://marco-lopes.com/articles/Vim-and-Haskell-in-2019/) i found, than
you need to put `"hlintOn" : false` to `haskell → settings →
languageServerHaskell → hlintOn`. I still have no idea, how to use settings
mentioned
[here](https://haskell-language-server.readthedocs.io/en/latest/configuration.html).
I've tried a lot of different placements in `:CocConfig`, yet no seem to a)
make sense or b) work.
My current settings for haskell in coc are:
```json
"haskell": {
"command": "haskell-language-server-wrapper",
"args": ["--lsp"],
"rootPatterns": ["*.cabal", "stack.yaml", "cabal.project", "package.yaml", "hie.yaml"],
"filetypes": ["haskell", "lhaskell"],
"settings": {
"languageServerHaskell": {
"hlintOn": false
}
}
}
```
xlogin-main/pages/kocicky/ 0000775 0000000 0000000 00000000000 14434637552 0016050 5 ustar 00root root 0000000 0000000 xlogin-main/pages/kocicky/cvicenia/ 0000775 0000000 0000000 00000000000 14434637552 0017631 5 ustar 00root root 0000000 0000000 xlogin-main/pages/kocicky/cvicenia/ex_01.pst 0000664 0000000 0000000 00000003600 14434637552 0021274 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
posttitle: Cvičenie 1
---
Nech kategória C je $(\mathbb{R}, (+n), (\cdot))$ a kategória D je $(\mathbb{R}^+, (\times n), (\cdot))$, potom obe kategórie reprezentujú grupu. Vieme povedať, že v $C$ a v $D$ je jeden objekt, nazvyme tieto objekty $c$ a $d$. Vieme, že $id_c = (+0)$, a $id_d = (\times 1)$.
Na chvíľu uvážme, že miesto funkcií $(+n)$ a $(\times m)$ budeme uvažovať len $n$ a $m$. Funkcia, ktoré potom budú zobrazovať morfizmy budú $F : (+n) \mapsto (\times m)$ a $f : n \mapsto m$.
\newcommand \Fun[2]{ \text{#1 } #2}
\begin{equation}
\begin{aligned}
\Fun{F}{(+0)} &= \Fun{F}{id_c} = id_{\Fun{F}{c}} = id_d = (\times 1) \\
f(0) &= 1
\end{aligned}
\end{equation}
\begin{equation}
\begin{aligned}
\Fun{F}{((+a) \cdot (+b))} &= \Fun{F}{(+(a + b))} = \Fun{F}(+ a) \cdot \Fun{F}(+ b) \\
f(a + b) &= f(a) \times f(b)
\end{aligned}
\end{equation}
Potom si všimnime, že $f$ je len $exp$. Opačne:
\begin{equation}
\begin{aligned}
\Fun{G}{(\times 1)} &= \Fun{G}{id_d} = id_{\Fun{G}{d}} = id_c = (+ 0) \\
g(1) &= 0
\end{aligned}
\end{equation}
\begin{equation}
\begin{aligned}
\Fun{G}{((\times a) \cdot (\times b))} &= \Fun{G}{(\times (a \times b))} = \Fun{G}(\times a) \cdot \Fun{G}(\times b) \\
g(a \times b) &= g(a) + g(b)
\end{aligned}
\end{equation}
Potom si všimnime, že $g$ je len $log$. Pre príklad, $F$ zobrazuje $(+a)$ na $(\times \exp a)$.
V haskell verzií, kde morfizmy reprezentujeme ako funkcie (Uvedomme si, že toto nie je jediný spôsob) `Double -> Double` potom bude *fmap* vyzerať následovne:
```hs
fmap h = \x -> x * exp ( h 0 )
```
`h 0` vybaluje z funkcie $(+n)$ jeho $n$.
Rovnako to funguje aj opačným smerom s funkciou $log$.
```hs
fmap h = \x -> x + log ( h 1 )
```
Pri pointfree som neuvážil, že *fmap* nie je len *f*. Pointfree verzia ale existuje a vyzerá následovne:
```hs
fmap = (*) . exp . ( flip ( $ ) ) 0
```
xlogin-main/pages/kocicky/cvicenia/ex_0602_h1.pst 0000664 0000000 0000000 00000000126 14434637552 0022033 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
---
Jako druhá kategorie se vám bude hodit produkt kategorií.
xlogin-main/pages/kocicky/cvicenia/ex_0602_h2.pst 0000664 0000000 0000000 00000000123 14434637552 0022031 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
---
Konkrétně $C \times C$, kde $C$ je původní kategorie.
xlogin-main/pages/kocicky/cvicenia/index.pst 0000664 0000000 0000000 00000010675 14434637552 0021501 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
---
## 2. Funktory a prirodzené transformácie
1. Majme C, grupu reálnych čísel so sčítaním a D, monoid kladných reálnych čísel s násobením. Skúste si C a D nakresliť v podobe kategórií. Následne skúste nájsť dva funktory F: C →D a G : D → C také, že sú vzájomne inverzné. [riešenie](ex_01.html)
## 3. Produkty a koprodukty
1. Vymyslete kandidáta na koprodukt Int a Bool jiný než Either a ukažte, že nemůže být lepší než Either, protože se dá najít víc než jeden morfizmus z vašeho kandidáta do Either.
2. Ukažte, že následující datová struktura PreList je instancí bifunktoru. PreList je datová struktura odvozená od List, ve které byla rekurze nahrazena druhým typovým parametrem pro zjednodušení.
3. \def\C{\mathcal{C}}
Nechť $\C$ je kategorie a $c$ v ní libovolný objekt. Předpokládejme navíc, že pro libovolný další objekt $d$ existuje v $\C$ produkt $c\times d$. Tímto způsobem jsme vytvořili přiřazení, které každému objektu z $\C$ přiřadí nějaký objekt z $\C$. Vymyslete, jak toto zobrazení na objektech rozšířit na funktor. Najděte tedy způsob, jak pro každou šipku $f\colon d\to d'$ najít šipku $c\times f\colon c\times d\to c\times d'$. Navíc ukažte, že toto přiřazení je funktoriální (tedy že zachovává kompozice a identity).
Nezapomeňte, že v obecné kategorii je produkt definován pouze svou univerzální vlastností (první diagram třetího rozdavku)!
Když to člověk dělá poprvé, tak je to spíš těžší cvičení, ale myslím, že pro pochopení základních kategoriálnách konceptů a způsobu uvažování je superužitečné. *Vitek*
## 4. Yoneda
1. Mějme kategorii **Grp** (objekty := grupy, morfismy := homomorfismy) a
zapomínající funktor $U: Grp \to Set$, který grupu $G$ pošle na svoji nosnou
množinu. Popiště přirozené transformace mezi hom-funktorem $Grp(Z,-)$ a $U$. (Z
jsou celá čísla se sčítáním)
2. Mějme kategorii **Cat** (objekty := malé kategorie, morfismy := funktory). Mějme
kategorie **1** (jediný objekt s id morfismem) a **2** (2 objekty a,b; morfismy id_a,
id_b, a->b).
Popiště přirozené transformace mezi $Cat(1,-)$ a $Cat(2,-)$.
3. V části `Yoneda in haskell` jsme si řekli, že `Reader a` se dá chápat jako
hom-funktor `Set(a,-)`. Dále typ `List ()` se dá chápat jako reprezentace
přirozených čísel. Jak můžeme vytvořit jinou reprezentaci přirozených čísel
pomocí Yonedy a funktoru `List`?
## 5. CCC
1. Mějme kategorii všech částečně uspořádaných množin, kde objekty jsou částečně uspořádané množiny a morfismy jsou monotónní zobrazení ($f$ je monotónní, pokud pro každé $x$, $y$ platí, že pokud $x \le y$ pak $f(x) \le f(y)$) Tato kategorie je CCC. Co jsou produkty, exponenciály a terminální objekt v této kategorii?
2. Mějme kategorii **Cat**, kde objekty jsou malé kategorie a morfismy jsou funktory. Tato kategorie je CCC. Co jsou produkty, exponenciály a terminální objekt v této kategorii?
## 6. Adjunkcie
1. Mějme kategorie $\textbf{Set}$, a $\textbf{Vect}_R$ (reálné vektorové prostory).
Mějme funktor $F: \textbf{Set} \rightarrow \textbf{Vect}_R$ takový, že množinu $S$ namapuje na vektorový prostor s bází $S$. Mějme funktor $U: \textbf{Vect}_R \rightarrow \textbf{Set}$ takový, že vektorový prostor namapuje na jeho množinu vektorů. Ukažte, že $F$ je levý adjunkt $U$ - například pomocí universal arrow adjunkce. [rozbor a riešenie](https://www.math3ma.com/blog/what-is-an-adjunction-part-2)
2. Zkuste si pomocí adjunkcí zadefinovat produkt v kategorii.
V Bartoszovi (knize, i přednáškách) je případně rozebrána část řešení
pomocí $HomSet$ definice, ale přirozenost zobrazení mezi funktory nechal
na čtenáři. Možná bude snazší použít Universal arrow definici.
[hint 1](ex_0602_h1.html) [hint 2](ex_0602_h2.html)
## 8. Koprvoky
1. Ukažte, že pravidla pro haskellové monády odpovídají pravidlům pro
skládání šipek v ko-Kleisliho kategoriích.
2. Navrhněte dvě různé platné instance třídy Comonad pro stromy s
libovolnou aritou: data Tree a = Node a [Tree a].
3. Uvažme tuto implementaci zaveditelnou pro každý funktor:
>> `duplicate wx = fmap (λx → wx) wx.`
> Rozhodněte, zda může vést při vhodné implementaci extract taková
implementace k platné komonádě
> a) u funktoru Stream,
> b) u některého jiného funktoru,
> c) obecně u všech funktorů.
xlogin-main/pages/kocicky/index.pst 0000664 0000000 0000000 00000006633 14434637552 0017717 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
---
## Disclaimer
*Hlavná osnova sa presunula [tu](https://is.muni.cz/auth/el/fi/jaro2022/IV125/seminar-category_theory.qwarp), táto stránka je len dôsledok sunk cost falacy. V prípade, že ku stránke nemáte prístup, píšte na kocicky@fi.*
*Pre tento semester hlavná osnova skončila.*
*Prezentujúcim aj účastníkom ďakujeme za účasť 🐸❤️.*
## Osnova semináru
25.02.2022 - Úvod do kategórii ([rozdavok](rozdavek_01.pdf), [stránka](rozdavek_01.html))
04.03.2022 - Funktory a prirodzené transformácie ([rozdavok](rozdavek_02.pdf))
11.03.2022 - Produkty a koprodukty ([rozdavok](rozdavek_03.pdf), [stránka](rozdavek_03.html))
18.03.2022 - Yoneda lemma ([rozdavok](rozdavek_04.pdf), [poznámky](poznamky_04.pdf))
25.03.2022 - Kartézsky Uzavrené Kategórie a Lambda kalkulus ([rozdavok](rozdavek_05.pdf))
01.04.2022 - Adjunkcie ([rozdavok](rozdavek_06.pdf))
08.04.2022 - Monády ([rozdavok](rozdavek_07.pdf))
15.04.2022 - Voľno
22.04.2022 - ~~Komonády~~ Koprvoky ([rozdavok](rozdavek_08.pdf))
29.04.2022 - Voľno
06.05.2022 - F-algebry a F-koalgebry ([rozdavok](rozdavek_09.pdf), [stránka](rozdavek_09), [článok](https://www.sciencedirect.com/science/article/pii/S0304397500000566))
27.05.2022 o 15:15 - (Ko)limity ([rozdavok](rozdavek_10.pdf))
## Organizácia
Seminár prebieha každý piatok od 13:30 do 15:10 v ~~A220~~ A218. Každý člen semináru pripraví počas semestru _aspoň_ jednu prezentáciu, ktorá by mala odprezentovať zadanú tému. Téma a jej "prednášajúci" sa určí vždy _aspoň_ dva týždne dopredu. V prípade, že máte seminár zapísaný sa zároveň očakáva, že sa semináru budete zúčastňovať _vždy_, keď to bude možné.
V prípade potreby môžete písať na mail __kocicky@fi.muni.cz__ alebo na irc kanál __#fimu-kocicky__.
V prípade, že máte k semináru nejaké materiály (rozdavok, prezentáciu, ...) ~~môžete mi ich poslať. Zverejním ich na tejto stránke v časti osnova.~~ pošlite ich na __kocicky@fi.muni.cz__.
V prípade, že chcete dostávať organizačné maily k semináru a nie ste zapísaný do predmetu, pošlite mail na kocicky@fi.
## Literatúra
Ako primárny zdroj osnovy a kľúčových slov k danej téme slúži Jan-Willem Buurlage. Milewski slúži ako zdroj intuície a príkladov. Awodey je skutočne doplnkový.
__Osnova__: Jan-Willem Buurlage - [Categories and Haskell](https://github.com/jwbuurlage/category-theory-programmers)
__Odporúčaný__: Bartosz Milewski - [Category Theory for Programmers](https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface), prípadne jeho [prednášky](https://www.youtube.com/playlist?list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_).
__Doplnkové__:
- Steve Awodey: [Category Theory](https://englishonlineclub.com/pdf/Category%20Teory%20[EnglishOnlineClub.com].pdf)
- Emily Riehl: [Category Theory in Context](https://math.jhu.edu/~eriehl/context.pdf)
__Iné__:
Rutten, J.J., 2000. Universal coalgebra: a theory of systems. Theoretical computer science, 249(1), pp.3-80.
## Nástroje
Na tvorbu rozdavku sa môže hodiť [pandoc](https://pandoc.org/) a [tikzcd](https://ctan.math.washington.edu/tex-archive/graphics/pgf/contrib/tikz-cd/tikz-cd-doc.pdf). Kresliť diagramy môžete napríklad [tu](https://tikzcd.yichuanshen.de/).
Príklad rozdavku z prvého semináru v md je [tu](rozdavek_01.md). tikzcd je generovaný kresliacim nástrojom vyššie.
xlogin-main/pages/kocicky/rozdavek_01.pst 0000664 0000000 0000000 00000011631 14434637552 0020727 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
geometry: margin=1cm
output: pdf_document
header-includes: |
\usepackage{tikz-cd}
\usepackage{adjustbox}
\pagenumbering{gobble}
\usepackage[labelformat=empty]{caption}
---
## Seminár 1: Úvod do teórie kategórií
### Kategória - $C(O, A, \circ)$:
- $O$ - kolekcia objektov
- $A$ - kolekcia _arrows_ - morfizmy medzi objektami z $O$
- $\circ$ - binárne skladanie morfizmov
- musí platiť asociativita - $(h \circ g) \circ f = h \circ (g \circ f) = h \circ g \circ f$
- identita $id$ je voči operátoru neutrálna aj zľava aj sprava, nech $f : a \to b$ potom $f \circ id_a = id_b \circ f = f$
- $id$ / $1$ - identické morfizmy pre všetky objekty ($id_a$ - identický morfizmus pre $a \in O$)
- $Hom(a, b)$ - kolekcia morfizmov **z** $a$ **do** $b$
### Kategórie
- _Malá_: aj $O$ aj $A$ sú množiny
- _Veľká_: nie malá
- _Lokálne malá_: pre všetky objekty $a, b \in C$ je $Hom(a, b)$ množina
- _Riedka (thin)_: pre všetky objekty $a, b \in C$ platí $|Hom(a, b)| \in \{0, 1\}$
- _Voľná (free)_: kategória generovaná z orientovaného grafu pomocou voľnej konštrukcie (doplnenie identít a zložením hrán - pre každú cestu z $u$ do $v$ existuje hrana reprezentujúca túto cestu)
### Špeciálne objekty
- *iniciálny objekt*
- $a$ je iniciálny objekt $\iff \forall b \in O_C \ldotp\exists! m \in A_C \ldotp m: a \rightarrow b$
- do každého objektu kategórie vedie unikátna šípka
- v kategórii "typov" (Set) si môžeme predstaviť `void`, pretože pre každý iný typ `T` existuje funkcia `asburd : void -> T`
- unikátny až na unikátny izomorfizmus
- *terminálny objekt* (duálny k iniciálnemu objektu)
- $a$ je terminálny objekt $\iff \forall b \in O_C \ldotp\exists! m \in A_C \ldotp m : b \rightarrow a$
- z každého objektu kategórie vedie unikátna šípka
- v kategórii "typov" si môžeme predstaviť `unit`, pretože pre každý iný typ existuje funkcia `unit : T -> ()`
- unikátny až na unikátny izomorfizmus
*Opačná kategória* $C^{op}$ - Kategória s opačnými morfizmami (od $C$). Môžme hovoriť o duálnych pojmoch (napr. terminálny objekt je iniciálny v opačnej kategórii, mono je duálne s epi, atď).
### Špeciálne morfizmy
- _monomorfizmus (mono)_
- $f : a \to b \in C$ je monomorfizmus $\iff$
> $\forall x \in C \ldotp \forall g, h : x \to a \in C \ldotp \{ f \circ g = f \circ h \implies g = h \}$
- v **Set** je morfizmus $f$ mono $\iff$ funkcia $f$ je injektívna
- _epimorfizmus (epi)_ (duálny k monomorfizmu)
- $f : a \to b \in C$ je epimorfizmus $\iff$
> $\forall x \in C \ldotp \forall g, h : b \to x \in C \ldotp \{ g \circ f = h \circ f \implies g = h \}$
- v **Set** je morfizmus $f$ epi $\iff$ funkcia $f$ je surjektívna
- _izomorfizmus_
> $f : a \to b \in C$ je izomorfizmus $\iff$
> $\exists g : b \to a \in C \ldotp \{ g \circ f = id_a \land f \circ g = id_b \}$
- _endomorfizmus_
> $f : a \to a$
- _automorfizmus_
> endomorfizmus + izomorfizmus
### Príklady kategórií:
- **0** - kategória bez prvkov a morfizmov
- **1** - kategória s práve jedným prvkom a jeho identitou
- **2** - kategória s práve dvoma prvkami, medzi ktorými sú morfizmy
- **Set** - kategória množín a funkcií
- **Grp** - kategória grúp a homomorfizmov
- **Cat** - kategória malých kategórií a funktorov
- _Order_ - kategória usporiadania s $\le$
- _Voľná kategória_ - konštrukcia z orientovaného grafu
- _Monoid ako kategória_ - kategória s jedným objektom a endomorfizmami
- _Grupa ako kategória_ - kategória s jedným objektom a automorfizmami
- **Hask** - "kategória typov v jazyku Haskell a funkcií"
\vspace{5em}
\begin{tikzcd}[row sep=large]
& & void \arrow[ld, "absurd_{int}"', bend left] \arrow[rd, "absurd_{bool}", bend right] \arrow[loop, distance=2em, in=125, out=55] \arrow[rrdddd, "absurd_{unit}", bend left=49] \arrow[lldddd, "absurd_{kocicka}"', bend right=49] & & \\
& int \arrow[rr, "isEven"] \arrow[loop, distance=2em, in=215, out=145] \arrow[rrrddd, "unit_{int}"] \arrow[lddd, "kocicka_{int}"'] & & bool \arrow[loop, distance=2em, in=35, out=325] \arrow[rddd, "unit_{bool}"] \arrow[lllddd, "kocicka_{bool}"] & \\
& & & & \\
& & & & \\
kocicka \arrow[rrrr, "unit_{kocicka}", bend right] \arrow[loop, distance=2em, in=215, out=145] & & & & unit \arrow[llll, "kocicka_{unit}"] \arrow[loop, distance=2em, in=35, out=325]
\end{tikzcd}
### Zdroje:
Milewski, B., 2022. Category Theory for Programmers: The Preface (Part One: 1-4). [online] Bartosz Milewski's Programming Cafe. Available at: [Accessed 3 March 2022].
Buurlage, J-W, 2022. Categories and Haskell (Chapter 1). [online] Github. Available at: [Accessed 3 March 2022].
xlogin-main/pages/kocicky/rozdavek_03.pst 0000664 0000000 0000000 00000007416 14434637552 0020737 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
geometry: margin=10mm
output: pdf_document
header-includes: |
\usepackage{tikz-cd}
\usepackage{adjustbox}
\pagenumbering{gobble}
\usepackage[labelformat=empty]{caption}
---
## Seminář 3: Produkty, koprodukty a algebraické datové typy (ADT)
### Produkty
\begin{tikzcd}[sep=large]
& x \arrow[dl, "f"'] \arrow[dr, "g"] \arrow[d, "q", dashed] & \\
a & a \times b = c \arrow[l, "p_1"] \arrow[r, "p_2"'] & b
\end{tikzcd}
- Objekt $c \in \mathcal{C}$ s projekcemi $p_1: c \to a$ a $p_2: c \to b$
je produkt objektů $a$ a $b \Longleftrightarrow \\
\forall x \in \mathcal{C} . \forall f: x \to a, g: x \to b . \exists! q: x \to c .$
$(f = p_1 \circ q \land g = p_2 \circ q)$
- $q$ *faktorizuje* $f$ a $g \Longleftrightarrow f = p_1 \circ q \land g = p_2 \circ q$
- $q$ je *univerzální mapování*
#### Příklady
- V **Set** *kartézský součin*
- V **Poset** (částečně uspořádaná množina) *infimum*
#### Haskell
```haskell
data (,) a b = (,) a b
fst (x, _) = x -- p_1
snd (_, y) = y -- p_2
q :: (j -> a) -> (j -> b) -> j -> (,) a b
q f g x = (f x, g x)
```
## Koprodukty (sumy)
\begin{tikzcd}[sep=large]
& x & \\
a \arrow[ru, "f"] \arrow[r, "i_1"'] & a + b = c \arrow[u, "q"', dashed] & b \arrow[lu, "g"'] \arrow[l, "i_2"]
\end{tikzcd}
- Objekt $c \in \mathcal{C}$ se zahrnutími (*inkluzemi*) $i_1: c \gets a$ a $i_2: c \gets b$
\usepackage{tikz-cd}
je koprodukt objektů $a$ a $b \Longleftrightarrow \\
\forall x \in \mathcal{C} . \forall f: x \gets a, g: x \gets b . \exists! q: x \gets c .$
$(f = q \circ i_1 \land g = q \circ i_2)$
### Příklady
- V **Set** *disjunktní sjednocení*
- V **Poset** (částečně uspořádaná množina) *supremum*
### Haskell
```haskell
data Either a b = Left a | Right b
-- i_1 = Left
-- i_2 = Right
q :: (a -> j) -> (b -> j) -> Either a b -> j
q f _ (Left x) = f x
q _ g (Right x) = g x
```
\newpage
### Bifunktory
#### Produkt kategorií $\mathcal{C} \times \mathcal{D}$
Skládá se z
- $O_{\mathcal{C} \times \mathcal{D}} = \{(c, d) | c \in O_\mathcal{C}, d \in O_\mathcal{D}\}$
- $A_{\mathcal{C} \times \mathcal{D}} = \{(f, g) | f: a \to c \in A_\mathcal{C},
g: b \to d \in A_\mathcal{D}\}$
Musí platit
- *identita* pro $(a, b)$ je $(id_a, id_b)$
- $(f, h) \circ (g, k) \equiv (f \circ g, h \circ k)$
#### Bifunktor $F$ = funktor z produktu kategorií $F: \mathcal{C} \times \mathcal{D} \to \mathcal{E}$
V každé kategorii $\mathcal{C}$, kde pro každé dva objekty $a$ a $b$ můžemem najít jejich produkt,
existuje bifunktor $\times$ (zapisován infixově).
\begin{align*}
\times&: \mathcal{C} \times \mathcal{C} \to \mathcal{C}\\
&: (a, b) \mapsto a \times b\\
&: (f: a \to a', g: b \to b') \mapsto (f \times g: a \times b \to a' \times b')
\end{align*}
\begin{tikzcd}[sep=large]
a \arrow[d, "f"'] & a \times b \arrow[d, dashed, "f \times g"] \arrow[l, "p_1"'] \arrow[r, "p_2"] & b \arrow[d, "g"] \\
a' & a' \times b' \arrow[l, "p'_1"] \arrow[r, "p'_2"'] & b'
\end{tikzcd}
#### Bifunktory v Haskellu
```haskell
class Bifunctor f where
bimap :: (a -> b) -> (c -> d) -> f a c -> f b d
bimap g h = first g . second h
first :: (a -> b) -> f a c -> f b c
first g = bimap g id
second :: (c -> d) -> f a c -> f a d
second h = bimap id h
{-# MINIMAL bimap | first, second #-}
instance Bifunctor (,) where
bimap g h (x, y) = (g x, h y)
instance Bifunctor Either where
bimap g _ (Left x) = Left (g x)
bimap _ h (Right y) = Right (h y)
```
### ADT a funktory
- Pro každý ADT umí GHC instancovat funktor s pomocí rozšíření (od GHC 9.2.1 bez rozšíření)
```haskell
{-# LANGUAGE DerivingFunctor #-}
data Example a = Ex a Int (Example a) (Example Int)
deriving (Functor)
```
xlogin-main/pages/kocicky/rozdavek_06.pst 0000664 0000000 0000000 00000014110 14434637552 0020727 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
geometry: margin=10mm
output: pdf_document
header-includes: |
\usepackage{tikz-cd}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{layout}
\usepackage{adjustbox}
\pagenumbering{gobble}
\usepackage[labelformat=empty]{caption}
---
## Seminář 6: Adjunkce
### Unit/counit adjunkce
Kategorie $\mathcal{C}, \mathcal{D}$, Funktory $L:\mathcal{D} \to \mathcal{C}$, $R:\mathcal{C} \to \mathcal{D}$
\begin{itemize}
\setlength\itemsep{0em}
\item $L$ je levý adjunkt $R$
\item $R$ je pravý adjunkt $L$
\end{itemize}
Značení: $L \dashv{} R$
Pokud existují přirozené transformace:
\begin{itemize}
\setlength\itemsep{0em}
\item $\eta:I_\mathcal{D} \Rightarrow R \circ L$(unit)
\item $\epsilon:L \circ R \Rightarrow I_\mathcal{C}$(counit).
\end{itemize}
\begin{center}
\begin{tikzcd}
& & & {} \arrow[ddd, no head] & & & \\
Ld \arrow[rrd, "R"', maps to] & & d \arrow[ll, "L"', maps to] \arrow[d, "\eta_d"] \arrow["I_\mathcal{D}"', maps to, loop, distance=2em, in=125, out=55] & & c \arrow[rr, "R", maps to] \arrow["I_\mathcal{C}"', maps to, loop, distance=2em, in=125, out=55] & & Rc \arrow[lld, "L", maps to] \\
& & RLd & & LRc \arrow[u, "\epsilon_d"] & & \\
& & & {} & & &
\end{tikzcd}
\end{center}
Pro tyto transformace platí následující rovnosti:
\begin{itemize}
\setlength\itemsep{0em}
\item $L = L \circ I_\mathcal{D} \to L \circ R \circ L \to I_\mathcal{C} \circ L = L$
\item $R = I_\mathcal{D} \circ R \to R \circ L \circ R \to R \circ I_\mathcal{C} = R$
\end{itemize}
### Hom-Set adjunkce
Kategorie $\mathcal{C}, \mathcal{D}$, Funktory $L:\mathcal{D} \to \mathcal{C}$, $R:\mathcal{C} \to \mathcal{D}$
$L \dashv{} R \iff Hom_\mathcal{C}(Ld, c) \cong{} Hom_\mathcal{D}(d, Rc)$
$\Phi$ je přirozený isomorfismus mezi HomSety
\begin{center}
\begin{tikzcd}
Ld \arrow[dd, bend right] \arrow[dd] \arrow[dd, bend left] & & d \arrow[ll, "L"', maps to] \arrow[dd, bend right] \arrow[dd] \arrow[dd, bend left] \\
{} \arrow[rr, shift right=2] & & {} \arrow[ll, "\Phi"', shift right=2] \\
c \arrow[rr, "R"', maps to] & & Rc
\end{tikzcd}
\end{center}
### Adjunkce unvierzální šipkou (Universal arrow adjunction)
Kategorie $\mathcal{C}, \mathcal{D}$, Funktory $L:\mathcal{D} \to \mathcal{C}$, $R:\mathcal{C} \to \mathcal{D}$
$L \dashv{} R \iff$ existuje přirozená transformace $\eta:I_\mathcal{D} \Rightarrow R \circ L$ taková, že $\forall c \in O_\mathcal{C}, \forall d\in O_\mathcal{D}$ a $\forall f: d \to Rc$ $\exists! g: Ld \to c$, že následující diagram komutuje:
\begin{center}
\begin{tikzcd}
d \arrow[rd, "f"'] \arrow[r, "\eta_d"] & RLd \arrow[d, "Rg"]
& Rc
\end{tikzcd}
\end{center}
### Ekvivalence definic
HomSet $\to$ Unit/Counit:
- $\eta_d:I_\mathcal{D}\Rightarrow R \circ L d = \Phi_{d, Ld}(I_\mathcal{D}(Ld))$
- $\epsilon_c:L \circ R \Rightarrow I_\mathcal{C} = \Phi_{Rc, c}^{-1}(I_\mathcal{C}(Rc))$
\medskip
Universal arrow $\to$ HomSet:
- $\Phi_{d,c}:Hom_\mathcal{C}(Ld, c) \to Hom_\mathcal{D}(d, Rc) = (\alpha:Ld \to c) \mapsto R\alpha \circ \eta$
\medskip
Unit/Counit $\to$ Universal arrow:
- $R(\Delta) \circ \eta_c=f$
- $\Delta = \epsilon_c \circ Lf= g$
### Unikátnost adjunkcí (až na přirozený isomorfismus)
Nechť $L,L': D \to c$ a $R: C \to D$ a $L \dashv{} R, L' \dashv{} R$ s přirozenými bijekcemi $\Phi_{d,c}$ a $\Phi_{d, c}'$. Pak pro libovolné $d \in O_\mathcal{D}$ platí, že:
>> $Hom_\mathcal{C}(Ld,-) \cong{} Hom_\mathcal{D}(c, R-)\cong{} Hom_\mathcal{C}(L'd, -)$
Z toho jde pomocí Yonneda embedding ukázat, že $F$ a $F'$ jsou přirozeně isomorfní.
### Příklady
#### Exponenciál CCC popsaný adjunkcí:
- $L=z \to z \times a$
- $R = b \to a \Rightarrow b$
- Unit: $\eta = z \to a \Rightarrow z \times a$
- Counit: $\epsilon = (a\Rightarrow b) \times a) \to b = eval$
#### Free/Forgetful adjunkce
Kategorie $\textbf{Mon}$ - objekty jsou monoidy, morfismy jsou homomorfismy mezi nimi. Mějme $X \in O_{\textbf{Set}}$ jako abecedu a $F(X)$ je monoid takový, že $F(X) = (X^*, ++, ())$. $X^*$ je množina slov složených z prvků $X$ - například: $w=(x1,x2,x3)$, $u=(x1)$, $z=()$. $++$ je operace zřetězení a $()$ je prázdné slovo.
Pak $F:\textbf{Set} \rightarrow \textbf{Mon}$ je takový funktor, který pro každou množinu vybere monoid jí generovaný. Mějme funktor $U:\textbf{Mon} \rightarrow \textbf{Set}$, který monoid namapuje na jeho množinu. $X$ je tedy generátor monoidu $F(X)$ a $U(F(X))$ namapuje $X$ na množinu generovanou $X$ a operací $++$.
Nyní můžeme definovat přirozenou transformaci $\eta: Id_{\textbf{Set}} \Rightarrow U \circ F$ takovou, že $\eta_X(x) = (x)$.
Nyní chceme ukázat, že pro libovolné f existuje právě jedno g takové, že následující daigram komutuje:
\begin{center}
\begin{tikzcd}
X \arrow[rd, "f"'] \arrow[r, "\eta_X"] & U(F(X)) \arrow[d, "U(g)"] \\
& U(M)
\end{tikzcd}
\end{center}
Tedy chceme najít morfismus $g$ takový, že je homomorfismus mezi monoidy a zároveň splňuje rovnost:
$f(x)=U(g)(\eta_Xx) = U(g)((x))$.
Takový morfismus $g$ je:
- $g(()) = id_M$
- $g((x)) = f(x)$
- $g((x1,x2,…,x_n ))=f(x1)f(x2)…f(x_n)$
xlogin-main/pages/kocicky/rozdavek_09.pst 0000664 0000000 0000000 00000007206 14434637552 0020742 0 ustar 00root root 0000000 0000000 ---
preset: kocicky
header-includes:
- \usepackage[a4paper]{geometry}
- \newcommand{\Hom}{\mathit{Hom}}
- \newcommand{\id}{\mathit{id}}
lang: cs
---
## Seminár 9: Koalgebry, koindukce, bisimulace atd.
Uvažujeme endofuktory $F : \mathcal C \to \mathcal C$.
$F$-algebra je objekt $A$ společně se šipkou $\alpha : FA \to A$.
$F$-algebry tvoří kategorii; homomorfismus $F$-algeber
$(A,\alpha) \to (B,\beta)$ je šipka $f: A \to B$
taková, že $f \circ \alpha = \beta \circ Ff$.
Iniciální $F$-algebra je nejmenším pevným bodem funktoru $F$.
Šipce z iniciální $F$-algebry do $F$-algebry $(A, \alpha)$ říkáme
*katamorfismus* a značíme ho $(\!\lvert \alpha \rvert\!)$.
```Haskell
type Algebra f a = f a -> a
data Fix f = Fix { unFix :: f (Fix f) }
cata :: Functor f => Algebra f a -> Fix f -> a
cata alpha = alpha . fmap (cata alpha) . unFix
```
Duálně: $F$-koalgebra je objekt $A$ společně se šipkou $\alpha : A \to FA$.
Homomorfismus $f : (A, \alpha) \to (B, \beta)$ splňuje
$\beta \circ f = Ff \circ \alpha$.
Finální $F$-koalgebra je největším pevným bodem funktoru $F$.
Šipce z $F$-koalgebry $(A, \alpha)$ do finální $F$-algebry říkáme
*anamorfismus* a značíme ho $[\!( \alpha )\!]$.
```Haskell
type CoAlgebra f a = a -> f a
-- Fix f je tentýž, protože funktory v Haskellu mají jen jeden pevný bod
ana :: Functor f => CoAlgebra f a -> a -> Fix f
ana alpha = Fix . fmap (ana alpha) . alpha
```
*Příklady:*
- $FX = 1 + X$. Iniciální $F$-algebra je $\mathbb N$. Finální $F$-koalgebra
je $\mathbb N \cup \{\infty\}$.
- $FX = A \times X$. Terminální $F$-koalgebra je proud (stream).
- $FX = \mathcal P(A \times X)$. $F$-koalgebry jsou přechodové systémy s
návěštími (LTS). Finální $F$-koalgebra neexistuje.
**Indukce a koindukce:**
Budeme se teď pohybovat v kategorii Set (nebo nějaké podobné, kde můžeme
hovořit o prvcích, podmnožinách, relacích).
*Princip indukce:* Iniciální $F$-algebra je minimální (nemá žádné vlastní
podalgebry).
Definice *kongruence* (nemusí to být ekvivalence):
$F$-kongruence mezi $F$-algebrami $(A, \alpha)$ a $(B, \beta)$
je $F$-algebra $(R, \rho)$, která má homomorfismy $\pi_1$ do $(A, \alpha)$
a $\pi_2$ do $(B, \beta)$. Na $R$ se můžeme dívat jako na relaci
$\{(\pi_1(r), \pi_2(r)) \mid r \in R\}$.
Pokud $R$ je kongruence nad $X$, pak $\pi_1(R) \cap \pi_2(R)$ je podalgebra
$X$.
*Alternativní formulace principu indukce:* Každá kongruence nad iniciální
$F$-algebrou je nadmnožinou identity.
*Princip **koindukce**:* Finální $F$-koalgebra je jednoduchá (nemá žádný
vlastní kvocient).
Kvocient koalgebry $S$ je koalgebra $T$ taková, že existuje epimorfismus
(v případě Set surjektivní zobrazení) $S \to T$.
Definice *bisimulace*: $F$-bisimulace mezi $F$-koalgebrami $(A, \alpha)$
a $(B, \beta)$ je $F$-koalgebra $(R, \rho)$, která má homomorfismy
$\pi_1$ do $(A, \alpha)$ a $\pi_2$ do $(B, \beta)$. Na $R$ se můžeme dívat
jako na relaci $\{(\pi_1(r), \pi_2(r)) \mid r \in R\}$.
*Alternativní formulace principu koindukce:*
Každá bisimulace nad finální $F$-koalgebrou je podmnožinou identity.
*Příklad:* Vezměme si klasickou bisimulaci nad přechodovými systémy s návěštími
(LTS). Tedy $R$ je bisimulace pokud pro každé $(x, y) \in R$ platí:
* $x \xrightarrow{a} x' \implies \exists y' : y \xrightarrow{a} y'
\land (x', y') \in R$.
* $y \xrightarrow{a} y' \implies \exists x' : x \xrightarrow{a} x'
\land (x', y') \in R$.
Dokažte, že tento pojem bisimulace je shodný s pojmem $F$-bisimulace, kde
$FX = \mathcal P(A \times X)$.
xlogin-main/pages/lowlevel/ 0000775 0000000 0000000 00000000000 14434637552 0016245 5 ustar 00root root 0000000 0000000 xlogin-main/pages/lowlevel/cv_zap.pst 0000664 0000000 0000000 00000003511 14434637552 0020257 0 ustar 00root root 0000000 0000000 ---
preset: lowlevel
---
## PB071 Skúšobný zápočet - RPN Evaluation
Vašou úlohou je napísať vyhodnocovanie RPN výrazov. Program očakáva ľubovoľne
dlhý RPN výraz a na štandardný výstup vypíše jeho výsledok. Rozhranie
programu je následovné:
> `./rpneval [FILE]`
V prípade, že program dostane prvý argument `FILE`, je jeho úlohou vyhodnotiť výraz v
tomto súbore, inak vyhodnotí výraz zo štandardného vstupu.
### RPN
RPN (Reverse Polish Notation) je postfixová notácia, v ktorej operandy
prichádzajú *po* argumentoch. Náš evaluátor bude obsahovať len **binárne**
operátory $+, -$ a funkciu $sum$, ktorá sčíta všetky hodnoty.
Výraz je postupnosť prirodzených čísel spolu s
funkciami `+, -, sum`. V prípade, že súbor neobsahuje korektný RPN výraz,
program skončí s chybou. Korektný výraz je taký, ktorý sa dá vyhodnotiť na hodnotu.
Príklady vyhodnotenia
> `3 4 +` $\rightsquigarrow$ `7`
> `1 2 3 + +` $\rightsquigarrow$ `6`
> `3 4 -` $\rightsquigarrow$ `-1`
> `1 2 3 sum` $\rightsquigarrow$ `6`
> `1 1 1 + - 1 2 3 sum 1 -` $\rightsquigarrow$ `4`
> `1 + 2` $\rightsquigarrow$ `error`
> `Hello, world!` $\rightsquigarrow$ `error`
*TIP*: pred začiatkom si rozmyslite, akú abstraktnú dátovú štruktúru sa oplatí používať.
### Požiadavky
- Pre reprezentáciu výrazu použite **dynamickú štruktúru** (uvedomte si, že
výraz môže byť *ľubovoľne* dlhý). V prípade, že vstupný súbor neexistuje,
program skončí s chybou.
- Program musí strážiť funkcie, ktoré môžu zlyhať. V prípade zlyhania postupujte podobne ako v domácich úlohách alebo na cvičeniach.
- Program musí pred koncom uvoľniť všetky alokované zdroje.
*skončiť s chybou* - skončiť s nenulovým návratovým kódom a chybovou hláškou na **štandardný chybový výstup**.
xlogin-main/pages/lowlevel/index.pst 0000664 0000000 0000000 00000000215 14434637552 0020102 0 ustar 00root root 0000000 0000000 ---
preset: lowlevel
---
### Príspevky
Príspevky k predmetu PB071
[životný cyklus](lifecycle.html)
[cvičný zápočet](cv_zap.html)
xlogin-main/pages/lowlevel/lifecycle.pst 0000664 0000000 0000000 00000007007 14434637552 0020740 0 ustar 00root root 0000000 0000000 ---
preset: lowlevel
---
V prípade, že štruktúra obsahuje dynamicky alokované prvky, sa môže hodiť vytvoriť funkcie obsluhujúce životný cyklus tejto štruktúry. Základné funkcie tohto charakteru sú:
- my_data_type_new - alokuje miesto na štruktúru a uvádza ju do konzistentného stavu
- my_data_type_init - uvádza už existujúcu štruktúru do konzistentného stavu
- my_data_type_clean - upratuje **vnútro** štruktúry, no neuvoľní pamäť štruktúry
- my_data_type_destroy - upratuje vnútro aj uvoľňuje pamäť štruktúry
Pomenovanie týchto funkcií nie je štandard, kľudne ich môžete meniť. Je ale šikovné mať toto pomenovanie ustálené. Neskôr pri programovaní, tak človek môže jednoducho používať rozhranie bez toho, aby vždy musel loviť meno v nejakom hlavičkovom súbore. Vo väčšine prípadov nepotrebujeme implementovať všetky. Dôvod, prečo sa môže `T_init` a `T_clean` hodiť, je, keď očakávame, že sa naša štruktúra môže nachádzať na zásobníku. V tomto prípade pochopiteľne nemôžeme na jej ukazovateli volať `free`. V prípade, že je naša štruktúra na zásobníku a chceme ju len inicializovať, nechceme aby prebehala žiadna alokácia.
### Príklad zo siedmeho týždňa
V tomto prípade sa jedná o "overkill", pretože nepotrebujem ako `T_init`, tak `T_clean`. Pre ilustráciu sme implementovali všetky metódy.
```c
enum retcode
{
OK,
MEM_ERR
};
enum retcode list_node_init( struct node *node, size_t size, const void *src )
{
assert( src != NULL );
assert( size != 0 );
void *data = malloc( size );
if ( data == NULL )
return MEM_ERR;
memcpy( data, src, size );
node->data = data;
node->next = NULL;
return OK;
}
struct node* list_node_new( size_t size, const void *src )
{
assert( src != NULL );
assert( size != 0 );
struct node *node = malloc( sizeof( struct node ) );
if ( node == NULL )
return NULL;
if ( list_node_init( node, size, src ) != OK ) {
free( node );
return NULL;
}
return node;
}
void list_node_clean( struct node* node )
{
assert( node != NULL );
free( node->data );
}
void list_node_destroy( struct node* node )
{
assert( node != NULL );
list_node_clean( node );
free( node );
}
```
Rozumná podmnožina týchto metód potom veľmi zjednodušuje zvyšný kód.
```c
bool list_push_back(struct list *list, const void *data)
{
assert( list != NULL );
assert( data != NULL );
struct node *new_node = list_node_new( list->elem_size, data );
if ( new_node == NULL )
return false;
if ( list->tail != NULL ) {
list->tail->next = new_node;
} else {
list->head = new_node;
}
list->tail = new_node;
return true;
}
bool list_pop_front(struct list *list, void *data)
{
assert( list != NULL );
if ( list->head == NULL )
return false;
if ( data != NULL )
memcpy( data, list->head->data, list->elem_size );
struct node *new_head = list->head->next;
list_node_destroy(list->head);
if ( new_head == NULL ) {
list->tail = NULL;
}
list->head = new_head;
return true;
}
```
Táto dekompozícia nám uľahčuje uvažovanie o zdrojoch. Na základe vstupných a výstupných podmienok `T_new` a `T_destroy` vieme, že sa o tieto veci ďalej jednoducho nemusíme starať. V prípade, že sa naša štruktúra zmení, musíme meniť upratovanie len (primárne) na jednom mieste.
xlogin-main/pages/misc/ 0000775 0000000 0000000 00000000000 14434637552 0015347 5 ustar 00root root 0000000 0000000 xlogin-main/pages/misc/yet_another_monad_tutorial.pst 0000664 0000000 0000000 00000016761 14434637552 0023574 0 ustar 00root root 0000000 0000000 ---
preset: misc
pagetitle: xkucerak
author: Filip Kučerák
---
# Yet another monad tutorial
In this post, I would like to look at monads. The concept of a monad enjoys
quite a bit of popularity these days and deservingly receives a lot of tutorials,
which try to explain what monad is. This post will be yet another monad tutorial.
Many of the tutorials, will start by explaining the pragmatic look at monads
e.g. 'the thing that allows me to do side effects', 'the thing that can be used
like an error', 'the thing that contains some hidden accessible state' etc.
All these exploration of monads are perfectly fine, but they sometimes fail to
explain what is the main point of monad is, or rather explain the true idea
behind the abstraction. For me, the first time monads really clicked, was while
reading Bartosz Milewski's blog about category theory for programmers, and I
would highly recommend you check it out (either the aforementioned blog,
YouTube series which covers the blog or his course at MIT). This post will be
heavily inspired by his work, but will not explain the (whole) categorical
machinery (the closest explanation is probably in his YouTube series). I will
use pseudocode in haskell - which is a language where monads are commonplace -
but the ideas should work regardless of the language.
First, let us discuss the act of composition in programmming. With any programmming
language,
Imagine, we want to write a program, which needs to return `"yes"` if number is
even and `"no"` if it is not. Given functions `is_even : Int->Bool` and
`show_bool : Bool -> Str`, writing such a function is as easy as composing
these two functions. Here is an example in python
```py
def foo( number : int ) -> str:
return show_bool( number )
```
and even nicer one in haskell
```hs
foo = show_bool . is_even
```
We see that such a composition would be trivial in majority of programming
languages. Let us now focus on the haskell example, as it contains the act of
composition in a quite literal manner with the composition operator `(.)`. The
type of the operator is `(b -> c) -> (a -> b) -> (a -> c)`, which says 'if you
give me two functions such that result of one is the input of the other, I can
compose them. This can be easily seen in a simple picture:
a f b g c
. ----> . ----> .
| ^
| g . f |
-----------------
In this diagram, every point corresponds to a type, arrow to a function and
the `(.)` operator to arrow (function) composition. Note, that
a) for any `a`, there is function `id_a : a -> a`
b) `id_a` is neutral to composition `f . id_a = f` for `f : a -> b` and
`id_a . g = g` for `g : b -> a`
c) `(.)` is asociative, meaning `f . g . h = ( f . g ) . h = f . ( g . h )`
A structure, with object collection, arrow collection, asociative composition
of arrows and neutral arrows is called a category. In this blog, we will use
the category `Set` which is a category, where each object is a set, and each
arrow is a function. The neutral arrows will be identity maps and composition
will be the standard function composition.
We have `Set`, functions are arrows, we can compose them, everything is
beautiful and everything works, so where is the problem? Often, functions
instead of returning results, return something, we will call embelished value.
By embellished result, I will mean a value of an embellished type and by
embellished type I will mean a unary type constructor, which is the embellishment. Let us give some examples of embellished `Int`.
- I will not return Int, but a list of ints : `[Int]` for `[-]`
- Sometimes I return Int, but sometimes I return nothing: `Maybe Int` for `Maybe -`
- I do not return Int, but Int that depends on some context of type `c`: `c -> Int` for `c -> -`
- Sometimes I return Int, but sometimes I return this other type `l`: `Either l Int` for `Either l -`
- I return Int, but also additional content of type `m`: `(Int, m)` for `(-,m)`
All this embellishments are quite common in programming. For example, Imagine,
you have function, which can fail without any message. This can be easily
mapped a function with result using the `Maybe -`. Let us consider the previous
example, but this time, every function can fail at any time.
The previous image
Int Bool Str
.--------->.------------>.
is_even show_bool
becomes this disconnected mess
Int Maybe Bool
.--------->.
is_even
Bool Maybe Str
.------------>.
show_bool
We can see, that there is no clear way of composing these two functions. We will need
to manually get the result of `is_even` and using some nontrivial logic to give
it to `show_bool` to obtain the final result.
```hs
foo :: Int -> Maybe String
foo n = case is_even n of
Just a -> show_bool a
Nothing -> Nothing
```
which clearly requires more work, than previously and note, that `Maybe -` is
the 'easy' to deal with embellishment. Now imagine, that the functions can
no longer fail, but will together with the result produce a message which
needs to be logged.
The disconnected diagram becomes
Int (Bool, String)
.--------->.
is_even
Bool (Str, String)
.------------>.
show_bool
Now, the composition is harder, because we not only need to retrieve the `Bool`
from the result of `is_even` but also connect the logs from functions `is_even`
and `show_bool`.
The composition can look like this:
```hs
foo:: Int -> (String, String)
foo n = let (b, m) = is_even n
(s, m') = show_bool b
in (s, m ++ m')
```
Once again, the composition becomes quite a chore. Is there a better way? Can
we compose these functions elegantly? We would need something, that can
compose arrows, with embellished results i.e. an operator `(*) : ( b -> m c )
-> ( a -> m b ) -> ( a -> m c )` and would allow us to do something along the lines
illustrated in the following figure.
a b c
.---------------->.----------------->.
| f : a -> m b g : b -> m c ^
| |
|------------------------------------|
g * f
But note, that our diagram changed. Now an arrow between `a` and `b` does not
mean function of type `a -> b` but rather of type `a -> m b`, this in a way
gives us the ability to compose `m b` ends with `b` starts. We also have new
composition, instead of using `(.)` we will use the discussed `(*)`
composition. Remember, that we had identities `id_a: a -> a` but as arrows are
functions of type `a -> m b`, they will no longer be the identity functions,
but rather functions of the type `a -> m a`.
Okay, but where is the monad? Well this is actually it. Monad[1] is type
constructor `m` which has identities of the type `a -> m a` called `return` and
composition of `a -> m b` arrows often called the fish operator or `(<=<) : ( b
-> m c ) -> ( a -> m b ) -> ( a -> m c )`. Monad is a solution to the problem
of embellished composition. Some will probably note, that there are also
monadic laws, which need to hold, but they are just conditions from the fact
that `(<=<)` needs to be asociative and that `return` is neutral. Which we
discussed as conditions for category.
[1] The programmers version of a monad. The category we talked about is called
the Kleisli category. Monads can be also modelled through functors which can
be joined i.e. there is an natural tranformation `m ( m a ) => m a` and natural
tranformation `a => m a`.
xlogin-main/pages/typci/ 0000775 0000000 0000000 00000000000 14434637552 0015544 5 ustar 00root root 0000000 0000000 xlogin-main/pages/typci/index.pst 0000664 0000000 0000000 00000000034 14434637552 0017400 0 ustar 00root root 0000000 0000000 ---
preset: typci
---
👀