Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Coati 17. 02. 2023, 00:27:31
-
Jak můžu napsat funkci převádějící List<a> na Vect<a,n> (kde n je, logicky, velikost vektoru). Překladač hlásí, že nezná n, to ale nemusí být známo v době překladu.
-
Sice jsi nenapsal ani v jakým jazyce se snažíš to udělat (nebo jsem slepej), takže můžeme jenom hádat, ale tipnul bych, že to přesně z tohohle důvodu nejde - Vect<a, n> prostě potřebuje v době překladu vědět, kolik je n, protože Vect<a, 4> má jinou implementaci než Vect<a, 5>. Takže snad jedině přes velikej if podle velikosti Listu.
-
nejdriv zjistit velikost listu a pak pokracovat na vektor.
-
nejde - Vect<a, n> prostě potřebuje v době překladu vědět, kolik je n, protože Vect<a, 4> má jinou implementaci než Vect<a, 5>. Takže snad jedině přes velikej if podle velikosti Listu.
Ten parametr n nemusí mít známou hodnotu, pokud jde v jazyce mít tento typ:
structure Sigma {α : Type u} (β : α → Type v) where
fst : α
snd : β fst
V haskelloidních jazycích to bývá nějak takto:
data DPair : (a : Type) -> (p : a -> Type) -> Type where
MkDPair : {p : a -> Type} -> (x : a) -> p x -> DPair a p
Pak jde ta funkce napsat tak, aby fungovala za běhu (kdy se ten seznam, a tedy i n, načte například ze souboru nebo je po spuštění programu zadá uživatel).
-
nebo zacit s nejakou velikosti na zacatku a kdyz by pridavani presahlo velikost, tak udelat novy vetsi vektor a stary vektor prekopirovat a pridat novou hodnotu. to je ale uz heuristika.
-
Zdá se mi to nebo si tu Idris pokládá zdánlivě triviální otázky na které si odborně odpovídá pod jiným účtem ;D
viz minule https://forum.root.cz/index.php?topic=27054.0
-
Zdá se mi to nebo si tu Idris pokládá zdánlivě triviální otázky na které si odborně odpovídá pod jiným účtem ;D
viz minule https://forum.root.cz/index.php?topic=27054.0
To je zajímavá hypotéza...
-
nejde - Vect<a, n> prostě potřebuje v době překladu vědět, kolik je n, protože Vect<a, 4> má jinou implementaci než Vect<a, 5>. Takže snad jedině přes velikej if podle velikosti Listu.
Ten parametr n nemusí mít známou hodnotu, pokud jde v jazyce mít tento typ:
structure Sigma {α : Type u} (β : α → Type v) where
fst : α
snd : β fst
V haskelloidních jazycích to bývá nějak takto:
data DPair : (a : Type) -> (p : a -> Type) -> Type where
MkDPair : {p : a -> Type} -> (x : a) -> p x -> DPair a p
Pak jde ta funkce napsat tak, aby fungovala za běhu (kdy se ten seznam, a tedy i n, načte například ze souboru nebo je po spuštění programu zadá uživatel).
Jaký to má potom praktický efekt?
Mám funkci:
format x : String
...
format x : Int
...
formatAll xs : [String | Int]
...
loadFromFile File -> Error [String | Int], ErrorState
...
Načtu ze souboru, a obsah musím převést do konečně známého tvaru. Pokud tam budu posílat boolean, tak zmršit na int. Pokud tam mám Date, tak nevím.
Jak se bude chovat kód, ve kterém formatAll obsahuje kolekci, jejíž signaturu znám až po načtení souboru? Půjde to korektně přeložit? A když to načte bool, nebo Date, co se stane?
-
Aby nedošlo k omylu, já to zadání chápu. Jen jsem ho zjednodušil.
Obecně v jazycích se předpokládají kolekce jako nekonečné. Tudíž proč někde uchovávat délku kolekce? Třeba proto, že mám funkce, které dokáží zpracovat jen konkrétní délku - což je můj příspěvek/dotaz. A nebo proto, že mám různé specializované funkce pro různé délky. Tak pak nevím proč to rvát do typu, když se můžu zeptat v nějakém switchi.
K čemu je zajímavé, že je ta délka součástí typu? Jaké to má praktické použití?
-
Aby nedošlo k omylu, já to zadání chápu. Jen jsem ho zjednodušil.
Obecně v jazycích se předpokládají kolekce jako nekonečné. Tudíž proč někde uchovávat délku kolekce? Třeba proto, že mám funkce, které dokáží zpracovat jen konkrétní délku - což je můj příspěvek/dotaz. A nebo proto, že mám různé specializované funkce pro různé délky. Tak pak nevím proč to rvát do typu, když se můžu zeptat v nějakém switchi.
K čemu je zajímavé, že je ta délka součástí typu? Jaké to má praktické použití?
To má smysl při optimalizacích. Třeba Rust má vector ("nekonečný") a array, kde je délka součástí typu. Dává to perfektní smysl, stejně jako skutečnost, že to je dáno při kompilaci natvrdo. Samozřejmě si dovedu představit i nějakou realtimovou "oblast", kde se dynamicky vytvoří alokace řádků pevné délky. Ale je to taková specialitka...
-
Ja to chápem tak, že pamäť pre vektor sa alokuje ako počet dát krát veľkosť dát, takže musia byť dáta za sebou v pamäti.
Nekonečná kolekcia je niečo ako zreťazený zoznam a má porozhadzované prvky v pamäti a ešte prvý prvok musí mať smerník na samotné dáta a smerník na druhý prvok, druhý prvok má smerník na svoje dáta a smerník na ďalší prvok, atď. Posledný prvok má smerník na ďalší prvok nastavený na Null. Takže sa dajú ľahko pridať ďalšie dáta, stačí správne ponastavovať smerníky na ďalší prvok v predchádzajúcom a pridávanom prvku.
-
kdyz mas delku kolekce primo v typu/objektu tak pri kazdem add/delete automaticky upravujes hodnotu delky. jinak si musis udelat (nekonecnou) smycku a delku spocitat.
-
kdyz mas delku kolekce primo v typu/objektu tak pri kazdem add/delete automaticky upravujes hodnotu delky. jinak si musis udelat (nekonecnou) smycku a delku spocitat.
Takže cheš říct, že když mám:
parseList : String -> [Int]
tak ten kompilátor si nemůže vytvořit paměťovou buňku ve které bude jednak ta kolekce čísel ale i informace o počtu?
-
kdyz mas delku kolekce primo v typu/objektu tak pri kazdem add/delete automaticky upravujes hodnotu delky. jinak si musis udelat (nekonecnou) smycku a delku spocitat.
Takže cheš říct, že když mám:
parseList : String -> [Int]
tak ten kompilátor si nemůže vytvořit paměťovou buňku ve které bude jednak ta kolekce čísel ale i informace o počtu?
proto se mi libi Go a dalsi jazyky, ktere delku vektoru schovavaji v typu a je to pro bezpecnost; proto se mi libi C a assembler kde to nikdo nehlida a inteligent musi hlidat sam.
-
kdyz mas delku kolekce primo v typu/objektu tak pri kazdem add/delete automaticky upravujes hodnotu delky. jinak si musis udelat (nekonecnou) smycku a delku spocitat.
Takže cheš říct, že když mám:
parseList : String -> [Int]
tak ten kompilátor si nemůže vytvořit paměťovou buňku ve které bude jednak ta kolekce čísel ale i informace o počtu?
proto se mi libi Go a dalsi jazyky, ktere delku vektoru schovavaji v typu a je to pro bezpecnost; proto se mi libi C a assembler kde to nikdo nehlida a inteligent musi hlidat sam.
Asi nerozumím. Kde v tom mám hledat odpověď na mou námitku?
Já chci, aby mi kompilátor hlídal. Čím víc, tím lépe. Tady se ale bavíme o tom, proč dávat do typu něco co nepotřebuji a nejedná se o nic, co by měl kompilátor hlídat.
-
Ja to chápem tak, že pamäť pre vektor sa alokuje ako počet dát krát veľkosť dát, takže musia byť dáta za sebou v pamäti.
Nekonečná kolekcia je niečo ako zreťazený zoznam a má porozhadzované prvky v pamäti a ešte prvý prvok musí mať smerník na samotné dáta a smerník na druhý prvok, druhý prvok má smerník na svoje dáta a smerník na ďalší prvok, atď. Posledný prvok má smerník na ďalší prvok nastavený na Null. Takže sa dajú ľahko pridať ďalšie dáta, stačí správne ponastavovať smerníky na ďalší prvok v predchádzajúcom a pridávanom prvku.
"Nekonečná" kolekce může být taky vektor. A naštěstí většinou i bývá.
-
Jsem myslel, že dneska se to dělá tak, že si vytvořím třídu ve který bude ten list i jeho délka jako vlastnost. V okamžiku převodu na vektor budu délku pak vědět. No vlastně v tý třídě může být rovnou i ten vektor...
Nebo ne?
-
Jsem myslel, že dneska se to dělá tak, že si vytvořím třídu ve který bude ten list i jeho délka jako vlastnost. V okamžiku převodu na vektor budu délku pak vědět. No vlastně v tý třídě může být rovnou i ten vektor...
Nebo ne?
deka listu ve tride listu muze byt, ale michat tam i vektor je nadbytecne.
-
Jsem myslel, že dneska se to dělá tak, že si vytvořím třídu ve který bude ten list i jeho délka jako vlastnost. V okamžiku převodu na vektor budu délku pak vědět. No vlastně v tý třídě může být rovnou i ten vektor...
Nebo ne?
deka listu ve tride listu muze byt, ale michat tam i vektor je nadbytecne.
Spíš je tam nadbytečný ten spojový seznam, většinou chceš jenom vektor. A když ho spojíš s vektorem, výhody listu zabiješ úplně.
-
Jsem myslel, že dneska se to dělá tak, že si vytvořím třídu ve který bude ten list i jeho délka jako vlastnost. V okamžiku převodu na vektor budu délku pak vědět. No vlastně v tý třídě může být rovnou i ten vektor...
Nebo ne?
deka listu ve tride listu muze byt, ale michat tam i vektor je nadbytecne.
Spíš je tam nadbytečný ten spojový seznam, většinou chceš jenom vektor. A když ho spojíš s vektorem, výhody listu zabiješ úplně.
To se takhle nedá říct. Pokud tu kolekci používáš tak, že tam často přidáváš a odebíráš prvky na různá místa, bude spojový seznam lepší volba.
-
Spíš je tam nadbytečný ten spojový seznam, většinou chceš jenom vektor. A když ho spojíš s vektorem, výhody listu zabiješ úplně.
To se takhle nedá říct. Pokud tu kolekci používáš tak, že tam často přidáváš a odebíráš prvky na různá místa, bude spojový seznam lepší volba.
Ano, pro tento velmi specifický případ se spojový seznam celkem hodí (za předpokladu, že moc nepotřebuješ náhodný přístup), sice jsem to v praxi neviděl, ale nezpochybňuju to. Ale když tam přidáš vektor - a to je základ mého příspěvku - už můžeš spojový seznam zahodit, protože režii přidávání a odebírání na vektoru se nevyhneš.
-
Spíš je tam nadbytečný ten spojový seznam, většinou chceš jenom vektor. A když ho spojíš s vektorem, výhody listu zabiješ úplně.
To se takhle nedá říct. Pokud tu kolekci používáš tak, že tam často přidáváš a odebíráš prvky na různá místa, bude spojový seznam lepší volba.
Ano, pro tento velmi specifický případ se spojový seznam celkem hodí (za předpokladu, že moc nepotřebuješ náhodný přístup), sice jsem to v praxi neviděl, ale nezpochybňuju to. Ale když tam přidáš vektor - a to je základ mého příspěvku - už můžeš spojový seznam zahodit, protože režii přidávání a odebírání na vektoru se nevyhneš.
No, a moje pointa mého původní příspěvku je, že nevím, proč bych to měl drátovat do typů. Prostě si vytvořím kolekci [Foo] a nechám kompilátor odvodit podle užití, jak moc v kódu používám přístup k počtu prvků (-> přidá count do interní struktury pro Foo), jak často přidávám/odebírám prvky uvnitř seznamu (-> zvolí zda použít vektor, nebo spojový seznam). To mě, jako uživatele typů nezajímá, a kompilátor to dokáže rozhodnout lépe.
-
No, a moje pointa mého původní příspěvku je, že nevím, proč bych to měl drátovat do typů. Prostě si vytvořím kolekci [Foo] a nechám kompilátor odvodit podle užití, jak moc v kódu používám přístup k počtu prvků (-> přidá count do interní struktury pro Foo), jak často přidávám/odebírám prvky uvnitř seznamu (-> zvolí zda použít vektor, nebo spojový seznam). To mě, jako uživatele typů nezajímá, a kompilátor to dokáže rozhodnout lépe.
A jak to pozná? Pokud to nedělá runtimovou analýzu v konkrétním běhu nebo nějakou dlouhodobou statistiku, tak bych na to nespoléhal...
-
No, a moje pointa mého původní příspěvku je, že nevím, proč bych to měl drátovat do typů. Prostě si vytvořím kolekci [Foo] a nechám kompilátor odvodit podle užití, jak moc v kódu používám přístup k počtu prvků (-> přidá count do interní struktury pro Foo), jak často přidávám/odebírám prvky uvnitř seznamu (-> zvolí zda použít vektor, nebo spojový seznam). To mě, jako uživatele typů nezajímá, a kompilátor to dokáže rozhodnout lépe.
A jak to pozná?
Jak to píšu. Pozná to na základě znalosti kódu. Koukne a vidí, že ta kolekce se používá tady a tady a tady a tady, způsobem tak a tak a tak. Tudíž nejoptimálnější by bylo mít tu strukturu takto.
Pokud to nedělá runtimovou analýzu v konkrétním běhu nebo nějakou dlouhodobou statistiku, tak bych na to nespoléhal...
JIT je dobrý na něco jiného. Na zohlednění reálných dat a reálného chování.
Ani v jednom případě bych k tomu programátora nepouštěl.
-
No, a moje pointa mého původní příspěvku je, že nevím, proč bych to měl drátovat do typů. Prostě si vytvořím kolekci [Foo] a nechám kompilátor odvodit podle užití, jak moc v kódu používám přístup k počtu prvků (-> přidá count do interní struktury pro Foo), jak často přidávám/odebírám prvky uvnitř seznamu (-> zvolí zda použít vektor, nebo spojový seznam). To mě, jako uživatele typů nezajímá, a kompilátor to dokáže rozhodnout lépe.
A jak to pozná?
Jak to píšu. Pozná to na základě znalosti kódu. Koukne a vidí, že ta kolekce se používá tady a tady a tady a tady, způsobem tak a tak a tak. Tudíž nejoptimálnější by bylo mít tu strukturu takto.
A jak z toho (obecně) pozná, jaká je frekvence kterých operací? To přece musí záviset mimo jiné na vstupních datech.
-
No, a moje pointa mého původní příspěvku je, že nevím, proč bych to měl drátovat do typů. Prostě si vytvořím kolekci [Foo] a nechám kompilátor odvodit podle užití, jak moc v kódu používám přístup k počtu prvků (-> přidá count do interní struktury pro Foo), jak často přidávám/odebírám prvky uvnitř seznamu (-> zvolí zda použít vektor, nebo spojový seznam). To mě, jako uživatele typů nezajímá, a kompilátor to dokáže rozhodnout lépe.
A jak to pozná?
Jak to píšu. Pozná to na základě znalosti kódu. Koukne a vidí, že ta kolekce se používá tady a tady a tady a tady, způsobem tak a tak a tak. Tudíž nejoptimálnější by bylo mít tu strukturu takto.
A jak z toho (obecně) pozná, jaká je frekvence kterých operací? To přece musí záviset mimo jiné na vstupních datech.
To píšu výše, ne?
-
No, a moje pointa mého původní příspěvku je, že nevím, proč bych to měl drátovat do typů. Prostě si vytvořím kolekci [Foo] a nechám kompilátor odvodit podle užití, jak moc v kódu používám přístup k počtu prvků (-> přidá count do interní struktury pro Foo), jak často přidávám/odebírám prvky uvnitř seznamu (-> zvolí zda použít vektor, nebo spojový seznam). To mě, jako uživatele typů nezajímá, a kompilátor to dokáže rozhodnout lépe.
A jak to pozná?
Jak to píšu. Pozná to na základě znalosti kódu. Koukne a vidí, že ta kolekce se používá tady a tady a tady a tady, způsobem tak a tak a tak. Tudíž nejoptimálnější by bylo mít tu strukturu takto.
A jak z toho (obecně) pozná, jaká je frekvence kterých operací? To přece musí záviset mimo jiné na vstupních datech.
To píšu výše, ne?
Aha, OK.