Administrace komentářů

Ahoj,

ucim se ted trochu Haskell, protoze me napadla urcita teoreticka idea/koncepce v programovani, a rad bych se dozvedel, jestli uz neco takoveho neexistuje (a pod jakym nazvem to hledat). Rikam si, ze prave komunita lidi kolem Haskellu a funkcionalniho programovani by mohla znat odpoved, protoze jsou to vetsinou velice zdatni teoretici. Proto se ptam tady, protoze vim, ze se tady hodne takovych lidi pohybuje.

Ve funkcionalnim programovani (a la Haskell) mame jen ciste funkce. Tedy realny program (na realnem pocitaci) lze chapat jako jeden velky stavovy automat, nad kterym je jedna cista funkce, ktera vstup a vnitrni stav prevadi do vystupu a noveho vnitrniho stavu.

V praxi to tak ovsem nedelame, protoze by to bylo neefektivni. V praxi je totiz casta situace, ze ten vnitrni stav se tou operaci zmeni jen pomerne malo, nebo jen jeho cast; a provadeni vypoctu timto zpusobem by znamenalo, ze se pro vystup prepocitavaji i veci, ktere uz jsme vypocitali v minulem stavovem prechodu. V praxi se to resi imperativnim programovanim, ktere uklada ruzne mezivysledky.

Zajimalo me tedy, jestli existuje nejaky systematictejsi postup, jak by bylo mozne z onoho popisu "cista funkce nad globalnim stavem" odvodit, ktere veci uz neni potreba prepocitavat. Tim by bylo mozne definovat program vyse uvedenym zpusobem (jako funkci pro stavovy automat), coz je velmi elegantni, a pozdeji ho prevest na "imperativni" model, a neprijit tak o tu efektivitu. V podstate, velice neformalne, to znamena tu funkci "zderivovat", tedy najit funkci, ktera mi pro zmenu vstupu vrati zmenu na vystupu.

Jenze, co to vlastne znamena, "zmena" nejake veliciny, v tomto pripade? Obecne to zavisi od situace. Ale muzeme zkusit jednoduche pripady, a podivat se, jak bychom to tam asi chteli mit. Vezmeme si napriklad klasickou trojici funkci map/filter/reduce, ktere operuji nad posloupnostmi a ktere lze povazovat za urcite stavebni prvky, z kterych lze poskladat tu velkou prechodovou funkci, kterou chceme timto zpusobem optimalizovat.

Vsechny tri map/filter/reduce pracuji s argumentem posloupnosti. "Zmenou" v tomto pripade tedy muze byt pridani/ubrani/zmena jednoho prvku. U map i filter je derivace pomerne primocara - prepocita se jeden prvek. U reduce je zajimave, pokud je redukcni operace grupova, pak staci prepocitat take v podstate jen jeden prvek.

No a tohle me na tom zaujalo, a proto se tady na to ptam. Nikdy predtim jsem si neuvedomil, ze by optimalizace mohly zaviset na tom, jestli je neco grupa nebo ne (napriklad cloveka okamzite napada otazka - bylo by mozne to priohnout tak, aby funkce v reduce grupova byla?). Zni to zajimave, takze, chtel jsem se zeptat, rozviji uz nekdo takovou teorii? A souvisi to cele nejak s linym vyhodnocovanim?