funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Types will carry you over the Monads

19. 8. 2014 — k47

Teď nechci zabřednout do bažin internetu a napsat další monádový tutoriál, ale jen zveřejnit jeden postřeh, díky kterému jsem pochopil sílu Applicatives:

Vždycky, když jsi v úzkých, následuj typy a ty tě dovedou do cíle.


Funkce bind definovaná na monádě má typ:

bind :: M a -> (a -> M b) -> M b

Ten říká, že mám nějaké M a a pak funkci z a do M b a když je nějak zkombinuji, dostanu M b. Z typu je vidět, že do funkce a -> M b musím dodat a, které je uvězněno v M a a jinak není možné pokračovat. Monády tedy popisují operace, které jsou sekvenční a jeden krok závisí na výsledku toho předchozího.

Pokud tedy například M a reprezentuje asynchronní operaci, která eventuálně vyprodukuje hodnotu typu a, argument a -> M b představuje další async akci, která k tomu, aby vůbec začala, potřebuje znát a - tedy předchozí výsledek. Jde tedy o řetězení async operací, které je jasně patrné z typu funkce.


Applicative definuje jednu funkci, které tady budu říkat apply 1 a která má typ:

apply :: M a -> M (a -> b) -> M b

Ten říká, že mám nějaké M a a nějaké M (a -> b) (tedy funkci a -> b uvnitř M) a když je nějak zkombinuji, dostanu M b. Ale na rozdíl od předchozího případu, M (a -> b) nepotřebuje a k tomu aby začal pracovat.

Pokud je M opět asynchronní operace, pak druhý argument představuje jinou asynchronní operaci, která nezávisle na prvním argumentu vyprodukuje funkci a -> b. Když jsou oba dva argumenty připraveny, je možné zavolat funkci z druhého argumentu s výsledkem toho prvního a dostat tak výsledek reprezentovaný async operací M b.

Opět: I tohle je patrné z typu funkce a není možné to udělat jinak a stále vyhovovat typové signatuře.


Pro úplnost ještě uvedu funktor, jehož funkce fmap má typ:

fmap :: M a -> (a -> b) -> M b

Když by M byla zase async operace, pak argument a -> b představuje pure transformaci výsledku této operace, který sám nedělá žádná async kouzla.

To všechno je zas patrné z pouhého typu.

Ještě se sluší dodat, že každá monáda je applicative a každá applicative je funktor.

Doufám, že jsem tedy nakonec nenapsal další monádový tutoriál, ale něco, co bude aspoň trochu užitečné, A mimochodem: Titulek je variace na jméno alba We will carry you over the mountains od Magyar Posse.


Dále k tématu:


  1. V Haskellu tahle funkce má jiné pořadí argumentů a nese jméno (<*>), které může být podobně jako axaxaxas mlö vysloveno jen jako posměšný a krutý smích autorů Haskellu.

Právě naopak, CG "žere míň výkonu", protože se většinu času o paměť nemusí starat. Když už ji začne uvolňovat, projde každý živý objekt v dané generaci jen jednou a většina z nich je v tom okamžiku už mrtvá. Některé aplikace můžou vytrvale alokovat stovky megabajtů paměti každou vteřinu a nic moc se neděje. ARC naproti tomu musí něco dělat vždy, když je vytvořena nebo smazána reference na objekt, což bývá velice často. ARC si také neumí bez pomoci poradit s cykly v objektovém grafu, s čímž GC nemá problém.

ARC má výhodu v tom, že nezpůsobuje pauzy, které většina GC potřebují k životu. Některé GC však fungují bez stop-the-world pauz, ale ty nejsou vůbec triviální.

Pokud ARC nekopíruje objekty a nedělá kompaci (což podle mých informací nedělá), může postupně dojít k fragmentaci paměti, což vede k neefektivnímu využití paměti a ztížení práce alokátoru. Pro GC, které kopíruje a kompaktuje paměť, alokace představuje jen inkrementace pointeru.

Např. PHP, které taky používá refcounting, správou paměti typicky stráví 20% času (a PHP je jako takové velice pomalé, takže to je pořádných 20%). Lidé z facebooku, kteří implementovali PHP virtuální stroj HHVM, který také používá refcounting, říkali, že 30% vygenerovaného kódu se jen stará o refcounting.

Jako vždycky: pro a proti.

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články