Vyšší typy

klokan

Re:Vyšší typy
« Odpověď #15 kdy: 02. 04. 2018, 06:39:38 »

Ne, není to volovina, ani absolutní, ani relativní. Pokusím se o vysvětlení ještě jednou. U funkcí je ω→ω typ funkce, konkrétně prvního řádu. Funkce vyššího řádu je například (ω→ω)→ω. Podobně v případě druhů * značí konkrétní (=plně instanciovaný) typ a *→* je funktor (přesněji endofunktor) prvního řádu, tj. není to konkrétní typ (v Haskellu by se řeklo "typový konstruktor"), ale pořád je jen prvního řádu. Vyššího řádu je např. (*→*)→* (shodou okolností druh monád). V AJ je výraz "higher-kinded type" zkratkou za "type of a higher-order kind", přičemž celá ta terminologie pochází z formální logiky. Uznávám, že je trochu zmatená, ale je ustálená a nemá smysl se o ni hádat (konec konců je logická, viz ta analogie a funkcemi). Ať tak či onak, takto se toto výrazivo používá v Haskellu a jiných funkcionálních jazycích.

Tak mám dojem, že se snad konečně shodneme. Sám říkáš zcela správně, že *->* je konstruktor prvního ŘÁDU (ovšem ne prvního DRUHU). Hodně lidí si plete řád a druh, ale není to totéž. Druh je v podstatě jenom arita typového konstruktoru, přičemž monomorfní neboli plně instanciovaný typ má aritu 0 (druh *), a arity > 0 jsou vyšší druhy.

Naproti tomu typový konstruktor vyššího řádu je takový, který předpokládá typový argument vyššího druhu, např. (*->*)->*. Ta analogie s funkcemi ve skutečnosti funguje tak, že hodnota je objekt druhu *, funkce je objekt druhu *->* (nebo vyššího) a funkce vyššího řádu je funkce, jejíž parametr je sám funkce (objekt vyššího druhu).

Takže v kostce:

* je první druh prvního řádu (analogicky proměnná).

*->* ale taky *->*->*->* jsou vyšší druhy (HKT) prvního řádu (analogicky klasické funkce).

(*->*)->* je vyšší druh (HKT) vyššího řádu (HRT) (analogicky funkce vyššího řádu).

Ta terminologie je zavádějící, uznávám. Netvrdím, že nikdo nikdy nikde nepoužíval druh ve smyslu řád, ale striktně korektní definice to rozlišuje, stejně jako veškerá peer reviewed literatura, kterou jsem kdy na toto téma četl... nebo napsal.

Mimochodem to, že v jazyku bez HKT nejdou implementovat monády, není kvůli tomu, že údajně teprve (*->*)->* je vyšší druh. Právě naopak. Když si zkusíš definovat monádu jako typovou třídu v Rustu nebo Swiftu, to, na co narazíš, bude typová signatura operátoru bind (>>=). Ono klasické M a -> (a -> M b) -> M b prostě nebude možné vyjádřit, protože M a a M b jsou dvě různé instanciace typu - tradááá - VYŠŠÍHO DRUHU M (*->*), a jazyk bez podpory HKT je tak vidí jako dva naprosto spolu nesouvisející typy druhu *, které obecně a priori nejsou instancemi téže typové třídy Monad.


Jester

Re:Vyšší typy
« Odpověď #16 kdy: 02. 04. 2018, 12:37:32 »
Ne, není to volovina, ani absolutní, ani relativní. Pokusím se o vysvětlení ještě jednou. U funkcí je ω→ω typ funkce, konkrétně prvního řádu. Funkce vyššího řádu je například (ω→ω)→ω. Podobně v případě druhů * značí konkrétní (=plně instanciovaný) typ a *→* je funktor (přesněji endofunktor) prvního řádu, tj. není to konkrétní typ (v Haskellu by se řeklo "typový konstruktor"), ale pořád je jen prvního řádu. Vyššího řádu je např. (*→*)→* (shodou okolností druh monád). V AJ je výraz "higher-kinded type" zkratkou za "type of a higher-order kind", přičemž celá ta terminologie pochází z formální logiky. Uznávám, že je trochu zmatená, ale je ustálená a nemá smysl se o ni hádat (konec konců je logická, viz ta analogie a funkcemi). Ať tak či onak, takto se toto výrazivo používá v Haskellu a jiných funkcionálních jazycích.

Tak mám dojem, že se snad konečně shodneme. Sám říkáš zcela správně, že *->* je konstruktor prvního ŘÁDU (ovšem ne prvního DRUHU). Hodně lidí si plete řád a druh, ale není to totéž. Druh je v podstatě jenom arita typového konstruktoru, přičemž monomorfní neboli plně instanciovaný typ má aritu 0 (druh *), a arity > 0 jsou vyšší druhy.

Naproti tomu typový konstruktor vyššího řádu je takový, který předpokládá typový argument vyššího druhu, např. (*->*)->*. Ta analogie s funkcemi ve skutečnosti funguje tak, že hodnota je objekt druhu *, funkce je objekt druhu *->* (nebo vyššího) a funkce vyššího řádu je funkce, jejíž parametr je sám funkce (objekt vyššího druhu).

Takže v kostce:

* je první druh prvního řádu (analogicky proměnná).

*->* ale taky *->*->*->* jsou vyšší druhy (HKT) prvního řádu (analogicky klasické funkce).

(*->*)->* je vyšší druh (HKT) vyššího řádu (HRT) (analogicky funkce vyššího řádu).

Ta terminologie je zavádějící, uznávám. Netvrdím, že nikdo nikdy nikde nepoužíval druh ve smyslu řád, ale striktně korektní definice to rozlišuje, stejně jako veškerá peer reviewed literatura, kterou jsem kdy na toto téma četl... nebo napsal.

Mimochodem to, že v jazyku bez HKT nejdou implementovat monády, není kvůli tomu, že údajně teprve (*->*)->* je vyšší druh. Právě naopak. Když si zkusíš definovat monádu jako typovou třídu v Rustu nebo Swiftu, to, na co narazíš, bude typová signatura operátoru bind (>>=). Ono klasické M a -> (a -> M b) -> M b prostě nebude možné vyjádřit, protože M a a M b jsou dvě různé instanciace typu - tradááá - VYŠŠÍHO DRUHU M (*->*), a jazyk bez podpory HKT je tak vidí jako dva naprosto spolu nesouvisející typy druhu *, které obecně a priori nejsou instancemi téže typové třídy Monad.
Neshodneme, máš v tom guláš (minimálně v anglické terminologii), *→* ani *→*→*→*→*→*→*→*→*→*→*→* nejsou HK, protože "higher-kinded" je synonymní pro "vyšší řád" druhu, což právě - podle mě zcela jasně - popisuje už ta Wikipedie (ta je ostatně taky peer-reviewed). Z vědecké literatury pak třeba "Generics of a higher kind" nebo tak nějak (píšu to z hlavy, je to starý článek). A BTW, *→* i (*→*)→* mají stejnou aritu, ale odlišný druh, druh nemá nic společného s aritou, je to "typ typu". Z těchto dvou jen ten druhý je HK (analogicky k template template - proto jdou v C++ naimplementovat generické monády a v Javě ne). Možná, že polopaticky to je vysvětlené někde na Stackoverflow, kde se lidi ptají, proč Java nemá HKT - má jen *→* (případně s vyšší aritou), tj. končí na prvním řádu, kdežto HK znamená řád >1.

klokan

Re:Vyšší typy
« Odpověď #17 kdy: 02. 04. 2018, 13:51:07 »
To je neskutečná hromada žvástů. KIND se odjakživa vztahuje k aritě typového konstruktoru a tudíž to NENÍ řád. Typy vyššího řádu se v ustálené terminologii nazývají Higer RANK. Ta tvoje tolik vyzdvihovaná Wikipedie nepřesně používá výraz Higer ORDER, což je sice mimo exaktní terminologii, ale každému, kdo se obtěžuje si to doopravdy přečíst je snad jasné, o čem je řeč. S KINDem aspoň operuje korektně na rozdíl od toho, co sis myslel, že se tam píše.

Oni to totiž není jenom samoůčelné slovíčkaření. Rozdíl mezi vyšším druhem (HK) a vyšším řádem (HR) je zásadní. Pro pochopení si na úvod si přečti třeba https://www.google.com.au/url?sa=t&source=web&rct=j&url=https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf&ved=2ahUKEwje1dS9wpvaAhXGVbwKHeaiBQMQFjAAegQICBAB&usg=AOvVaw11xOuncGG5HNJIw_d_IaNb, jinak je zajímavé např. https://www.google.com.au/url?sa=t&source=web&rct=j&url=https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/putting.pdf&ved=2ahUKEwi9763Gv5vaAhWJwbwKHdKtA484ChAWMAJ6BAgIEAE&usg=AOvVaw2VimUnjZAnCN0bVC_h5sV9 nebo https://www.google.com.au/url?sa=t&source=web&rct=j&url=https://nerget.com/thesis.pdf&ved=2ahUKEwi9763Gv5vaAhWJwbwKHdKtA484ChAWMAN6BAgDEAE&usg=AOvVaw2S78pPMtPTxtaPFFkGCaEs. Pokud máš pro svůj alternativní svět nějaké reference, které nejsou jenom pomýlená představa o tom, co píšou na Wikipedii nebo citace na úrovni "XYZ nebo takňák", sem s nimi. Klidně se s tebou vsadím o učebnici matematiky pro první třídu.

Máš pravdu v tom, že (*->*)->* a *->* mají stejnou aritu - ovšem liší se řádem neboli rankem, což ti stále nedochází. Nicméně gratuluju, poprvé si v tomhle threadu prohlásil něco, co je blbě jenom z poloviny. Jen tak dál  ;)

Jester

Re:Vyšší typy
« Odpověď #18 kdy: 02. 04. 2018, 14:02:55 »
Typy vyššího řádu se v ustálené terminologii nazývají Higer RANK. [...] Rozdíl mezi vyšším druhem (HK) a vyšším řádem (HR) je zásadní.
Pominu urážky a jen poznamenám, že "řád" je v angličtině v matematickém kontextu "order". Když ani nevíš, co se jak překládá, tak už se nedivím, že píšeš věci bez hlavy a paty. Přečti si tu referenci, co jsem dal, i když evidentně máš problém porozumět (přinejmenším) anglickému textu, tak to asi k ničemu nebude.

Jester

Re:Vyšší typy
« Odpověď #19 kdy: 02. 04. 2018, 14:11:59 »
...
P.S. Ty tvoje odkazy výslovně uvádí přesně to, to tady píšu furt dokola: *→* není HK. Tímto jsi ze sebe udělal totálního debila. Přečti si ty texty nejdřív sám, pak se můžeš pokorně připlazit zpátky a omluvit se.


Re:Vyšší typy
« Odpověď #20 kdy: 02. 04. 2018, 18:00:35 »
P.S. Ty tvoje odkazy výslovně uvádí přesně to, to tady píšu furt dokola: *→* není HK. Tímto jsi ze sebe udělal totálního debila. Přečti si ty texty nejdřív sám, pak se můžeš pokorně připlazit zpátky a omluvit se.
Máš sice pravdu, Jestere, ale škoda, že to shazuješ takhle zbytečnými urážkami. To přece není nutný, ne? (Jo, vím, že sis nezačal :) )

Re:Vyšší typy
« Odpověď #21 kdy: 02. 04. 2018, 18:18:14 »
*->* ale taky *->*->*->* jsou vyšší druhy (HKT) prvního řádu (analogicky klasické funkce).

(*->*)->* je vyšší druh (HKT) vyššího řádu (HRT) (analogicky funkce vyššího řádu).
Imho se mýlíš. Snad se shodnem na tom, že List<T> v Javě má kind * -> * a List<Int> má kind *. No a pak si už můžeš snadno kdekoli najít, jestli Java má nebo nemá higher-kinded types. Najdeš, že nemá. Protože * -> * je first order kind a není to teda "higher-order kind" neboli "higher-kinded type". V Javě nejsou typy s kindem (* -> *) -> *, narozdíl od Haskellu.

Jester

Re:Vyšší typy
« Odpověď #22 kdy: 03. 04. 2018, 18:54:52 »
Tak kde to vázne, kde je ta omluva? Šup šup

jdusizasvym

Re:Vyšší typy
« Odpověď #23 kdy: 03. 04. 2018, 21:24:26 »
Tak kde to vázne, kde je ta omluva? Šup šup

Ach jo, ty jsi po technické stránce a co se týče hard skills opravdu chytrý a inteligentní, ale sociálně jsi ***... Je to dost škoda kurvit si zbytečně image a tím všechno, co umíš a znáš zahodit do ****

Re:Vyšší typy
« Odpověď #24 kdy: 03. 04. 2018, 23:30:52 »
Ajajaj, přestřelka zboj vs. mirek po bambilijóntéosmé?
OK, lads, fire at will.

BTW, zkusili jste se tu už někdy zeptat místního plebsu (kam se počítám i já), esli už někdo pochopil ty gonády a jak je použil ve své lopatorobotě?
 :D

Re:Vyšší typy
« Odpověď #25 kdy: 03. 04. 2018, 23:38:25 »
PS:
Leibnizova filosofie
Monády
Základní pojem jeho filosofie je monáda. Navazuje na Reného Descarta, který soudil, že všechny přírodní jevy lze vyložit pojmy rozlehlosti a pohybu a že základem světa jsou dvě substance – materiální a duchovní. Naproti tomu tvrdí, že je pohyb něco čistě relativního, závisí pouze na stanovisku pozorovatele, které těleso se jeví v pohybu a které ne. Descartovo pojetí substancí kritizuje ještě v druhém ohledu, z hlediska kontinuity a dělitelnosti.

HUH?

Re:Vyšší typy
« Odpověď #26 kdy: 04. 04. 2018, 01:03:34 »
přestřelka zboj vs. mirek po bambilijóntéosmé?
Co mám já a zboj společnýho se sporem mezi Jestrem a klokanem?

klokan

Re:Vyšší typy
« Odpověď #27 kdy: 04. 04. 2018, 07:50:23 »
Tak kde to vázne, kde je ta omluva? Šup šup

Tak si to prosím tě skutečně přečti a podívej se na mou odpověď Mirkovi Prýmkovi. Pokud budeš mít nějakou věcnou připomínku případně pokud můj příklad doopravdy vyvrátíš, můžeme se bavit místo si nadávat. Zatím si stojím za tím, co říkám.

klokan

Re:Vyšší typy
« Odpověď #28 kdy: 04. 04. 2018, 08:09:56 »
*->* ale taky *->*->*->* jsou vyšší druhy (HKT) prvního řádu (analogicky klasické funkce).

(*->*)->* je vyšší druh (HKT) vyššího řádu (HRT) (analogicky funkce vyššího řádu).
Imho se mýlíš. Snad se shodnem na tom, že List<T> v Javě má kind * -> * a List<Int> má kind *. No a pak si už můžeš snadno kdekoli najít, jestli Java má nebo nemá higher-kinded types. Najdeš, že nemá. Protože * -> * je first order kind a není to teda "higher-order kind" neboli "higher-kinded type". V Javě nejsou typy s kindem (* -> *) -> *, narozdíl od Haskellu.

Proč si myslím, že mám pravdu, se pokusím ilustrovat. K tvé poznámce o Javě: Problém je, že Java je na tohle špatný příklad. Její typový systém má různá jiná omezení, a to, že nejde definovat typ s kindem (*→*)→* není jenom kvůli tomu, že nepodporuje HK. Krásně je to vidět v Rustu, ten taky nemá HK, ale přesto se dá deklarovat např:

struct Kráva<T, I: FromIterator<T>> { ... }

Jako demonstrace toho, na co dojede jazyk bez HK, a potažmo kde vlastně začínají HK, si vezměme starou známou monádu. V Haskellu se operátor bind (>>=) deklaruje následovně:

(>>=):: Monad m => m a → (a → m b) → m b

Typové proměnné a a b jsou volné, implicitně je to forall a,b. Parametr je tady pouze m s kindem *→*. To je přesně ten klíčový moment, který jazyk bez HK nedovolí. Když se totiž budu snažit o totéž v Rustu, compiler mi nevezme nic jako

fn bind<A, B, M<A>: Monad>(a: M<A>, f: FnOnce(A)→M<B>)→M<B>

právě proto, že M tady má kind *→*. Jediná možnost bude něco na následující způsob:

trait Monad<A> {
        fn bind<B, R: Monad<B>>(self, f: FnOnce(A)→R)→R;
}

kde se Self (neboli ekvivalent M<A>) předem zredukuje na kind * instanciací pro dané A. Totéž platí pro R, resp. M<B>.

V praxi to znamená, že v Haskellu se definuje >>= obecně např. pro monádu IO (*→*) a pak se může rovnou napsat

getLine >>= putStrLn

V Rustu to ale nebude možné. Compiler stejně tak nevezme žádné

impl<A> IO<A> for Monad<A> { ... }

protože typové parametry metody bind zůstávají neinstanciované. Aby to fungovalo, musím nejdřív explicitně deklarovat:

impl IO<()> Monad<()> { … }
impl IO<String> Monad<String> { … }

a pak teprve můžu provést getLine.bind(putStrLn). Neboli musím ručně implementovat Monad<A> (*) pro každý možný typ A, což evidentně není možné, a právě proto v takovám jazyku bez HK nejde zkonstruovat obecnou monádu. Respektive jde, pokud například v Rustu tyhle explicitní deklarace automatizuju makrem, což je přesně to samé, jako když použiju template template v C++. Obojí je ohejbák, jak si vynahradit to, že jazyk neumí typové parametry s kindem *→*.

klokan

Re:Vyšší typy
« Odpověď #29 kdy: 04. 04. 2018, 08:12:06 »
Typy vyššího řádu se v ustálené terminologii nazývají Higer RANK. [...] Rozdíl mezi vyšším druhem (HK) a vyšším řádem (HR) je zásadní.
Pominu urážky a jen poznamenám, že "řád" je v angličtině v matematickém kontextu "order". Když ani nevíš, co se jak překládá, tak už se nedivím, že píšeš věci bez hlavy a paty. Přečti si tu referenci, co jsem dal, i když evidentně máš problém porozumět (přinejmenším) anglickému textu, tak to asi k ničemu nebude.

To, že order je řád, tady nikdo nezpochybňuje. Řád není totéž co kind (druh), a právě proto tam používají termín order a ne kind. To je, řekl bych, jasné.