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 za­břed­nout do bažin in­ter­netu a napsat další mo­ná­dový tu­to­riál, ale jen zve­řej­nit jeden po­střeh, díky kte­rému jsem po­cho­pil sílu Ap­pli­ca­ti­ves:

Vždycky, když jsi v úzkých, ná­sle­duj typy a ty tě do­ve­dou do cíle.


Funkce bind de­fi­no­vaná 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 zkom­bi­nuji, do­stanu M b. Z typu je vidět, že do funkce a -> M b musím dodat a, které je uvěz­něno v M a a jinak není možné po­kra­čo­vat. Monády tedy po­pi­sují ope­race, které jsou sek­venční a jeden krok závisí na vý­sledku toho před­cho­zího.

Pokud tedy na­pří­klad M a re­pre­zen­tuje asyn­chronní ope­raci, která even­tu­álně vy­pro­du­kuje hod­notu typu a, ar­gu­ment a -> M b před­sta­vuje další async akci, která k tomu, aby vůbec začala, po­tře­buje znát a – tedy před­chozí vý­sle­dek. Jde tedy o ře­tě­zení async ope­rací, které je jasně patrné z typu funkce.


Ap­pli­ca­tive de­fi­nuje 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 zkom­bi­nuji, do­stanu M b. Ale na rozdíl od před­cho­zího pří­padu, M (a -> b) ne­po­tře­buje a k tomu aby začal pra­co­vat.

Pokud je M opět asyn­chronní ope­race, pak druhý ar­gu­ment před­sta­vuje jinou asyn­chronní ope­raci, která ne­zá­visle na prvním ar­gu­mentu vy­pro­du­kuje funkci a -> b. Když jsou oba dva ar­gu­menty při­pra­veny, je možné za­vo­lat funkci z dru­hého ar­gu­mentu s vý­sled­kem toho prv­ního a dostat tak vý­sle­dek re­pre­zen­to­vaný async ope­rací M b.

Opět: I tohle je patrné z typu funkce a není možné to udělat jinak a stále vy­ho­vo­vat typové sig­na­tuře.


Pro úpl­nost ještě uvedu funk­tor, jehož funkce fmap má typ:

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

Když by M byla zase async ope­race, pak ar­gu­ment a -> b před­sta­vuje pure trans­for­maci vý­sledku této ope­race, který sám nedělá žádná async kouzla.

To všechno je zas patrné z pou­hého typu.

Ještě se sluší dodat, že každá monáda je ap­pli­ca­tive a každá ap­pli­ca­tive je funk­tor.

Doufám, že jsem tedy na­ko­nec ne­na­psal další mo­ná­dový tu­to­riál, ale něco, co bude aspoň trochu uži­tečné, A mi­mo­cho­dem: Ti­tu­lek je va­ri­ace na jméno alba We will carry you over the moun­ta­ins od Magyar Posse.


Dále k tématu:


  1. V Haskellu tahle funkce má jiné pořadí ar­gu­mentů a nese jméno (<*>), které může být po­dobně jako axa­xa­xas mlö vy­slo­veno jen jako po­směšný a krutý smích autorů Haskellu.

Právě naopak, CG „žere míň výkonu“, pro­tože se vět­šinu času o paměť nemusí starat. Když už ji začne uvol­ňo­vat, projde každý živý objekt v dané ge­ne­raci jen jednou a vět­šina z nich je v tom oka­mžiku už mrtvá. Ně­které apli­kace můžou vy­tr­vale alo­ko­vat stovky me­ga­bajtů paměti každou vte­řinu a nic moc se neděje. ARC na­proti tomu musí něco dělat vždy, když je vy­tvo­řena nebo sma­zána re­fe­rence na objekt, což bývá velice často. ARC si také neumí bez pomoci po­ra­dit s cykly v ob­jek­to­vém grafu, s čímž GC nemá pro­blém.

ARC má výhodu v tom, že ne­způ­so­buje pauzy, které vět­šina GC po­tře­bují k životu. Ně­které GC však fun­gují bez stop-the-world pauz, ale ty nejsou vůbec tri­vi­ální.

Pokud ARC ne­ko­pí­ruje ob­jekty a nedělá kom­paci (což podle mých in­for­mací nedělá), může po­stupně dojít k frag­men­taci paměti, což vede k ne­e­fek­tiv­nímu vy­u­žití paměti a ztí­žení práce alo­ká­toru. Pro GC, které ko­pí­ruje a kom­pak­tuje paměť, alo­kace před­sta­vuje jen in­kre­men­tace poin­teru.

Např. PHP, které taky po­u­žívá re­f­coun­ting, sprá­vou paměti ty­picky stráví 20% času (a PHP je jako takové velice pomalé, takže to je po­řád­ných 20%). Lidé z fa­ce­booku, kteří im­ple­men­to­vali PHP vir­tu­ální stroj HHVM, který také po­u­žívá re­f­coun­ting, říkali, že 30% vy­ge­ne­ro­va­ného kódu se jen stará o re­f­coun­ting.

Jako vždycky: pro a proti.

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