Naučte mě Perl 6, IV. Pole

26.4.2016 16:11 | Přečteno: 1834× | Perl | | poslední úprava: 29.4.2016 13:22

Tento blog o Perlu 6 se bude věnovat polím, ukážeme způsoby jak je vytvořit, operace na nich, zmíníme se o lenosti a paralelismu, nakonec je použijeme (možná až příliš) k definici podprogramu, který bude počítat permutace podle požadovaného počtu inverzí.

IV. Pole

Perl 5 obsahuje základní prostředky pro tvorbu, filtraci a úpravu pole, ale některé operace nad poli se museli dělat buď pomocí knihoven nebo poněkud neohrabaně. Perl 6 přidává nové možnosti pro definici a práci s poli a přidává i nové způsoby využití.

Definice pole

Pro definici pole můžeme, kromě samozřejmého výčtu prvků my @a=(1,'a',3);, použít i range operátor .., tedy místo @a=('a', 'b', 'c', 'd') lze psát i @a='a' .. 'd';. Tento operátor má i formu bez krajních bodů, @a=0 ..^ 10 v @a jsou čísla 0 až 9, co ale jde zapsat zkráceně i jako @a=^10;. Ke zkrácenému zápisu lze i přičítat, tj. pokud budeme chtít do @a uložit 10 čísel od 121, tak můžeme použít i @a=^10+121.

Další možností pro definici pole je konstrukce pomocí řídících struktur, která je podobná např. té z Pythonu.

  say ($_-1 if .is-prime for ^20);  #(1 2 4 6 10 12 16 18)
  my $a=1;
  say ( $a *= 2  while $a < 12 );    #(2 4 8 16)

Nejzajímavější konstrukce pole je pomocí operátoru .... Který umí nejen aritmetické a geometrické posloupnosti, ale pomocí kódu si můžete definovat posloupnosti vlastní.

  say 11, 9 ...  1;                  #(11 9 7 5 3 1)
  say 1, 2, 4 ... 128;               #(1 2 4 8 16 32 64 128)
  say 0, 1, * + * ...^ * > 1000;     #(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987)
  say { (^10).pick } ... 0;          #(2 4 4 8 4 6 1 8 2 3 7 4 8 3 5 5 5 2 7 9 0)

Lenost je ctnost

Pole se v Perlu 6 vyhodnocují od nultého prvku a až jsou potřeba, tak není problém mít pole jako nekonečnou posloupnost, 1, 2 ... * bude pole všech kladných čísel, (^10).roll(*) bude nekonečné pole s náhodnými čísly v rozmezí 0 až 9.

Operace s poli

V Perlu 6 je mnoho metod a operátorů pro práci s poli např. map, grep, first, reduce, Z, », … . Pro paralelní zpracování lze použít race, hype, ale zatím to často nefunguje.

  say ( 2, 4, 8 ...^ 2 ** 5000 ).race.map( { $_ if ($_ - 1).is-prime }).elems;     #20
  say ( 2 .. * ).grep({ !.is-prime }).head(12); #(4 6 8 9 10 12 14 15 16 18 20 21)
  dd  ( ([\*] (1 .. *)) ZR=> 1 .. * ).head(5);  #(1 => 1, 2 => 2, 3 => 6, 4 => 24, 5 => 120).Seq

Počet permutací podle inverzí

V této sekci použijeme práci s polem k napsání podprogramu count_permutation, který nám při zadání počtu prvků n a inverzí i vrátí počet permutací nad n-prvkovou množinou, které mají právě i inverzí. Při nezadání inverzí nám vrátí pole, kde nultý prvek bude odpovídat 0 inverzím, první 1 inverzi atd. Podobně při nezadání počtu prvků dostaneme pole, kde 2 prvek bude odpovídat permutaci na dvouprvkové množině, třetí na 3 prvkové atp. Při volání bez parametru podprogram vrátí (pole polí) triangle ne nepodobný Pascalovu, který bude odpovídat všem uvažovatelným kombinacím počtu prvků a inverzí.

subset NaturalNumber of Int where * >= 0 ;

sub rotate_sum ( @a is copy, NaturalNumber $n  ) {
    @a.prepend: 0 xx $n;
    [Z+]  @a, { .rotate } ... { .[0] != 0 } ;
}

multi count_permutation () {
    state @triangle = [], [1], {[ .&rotate_sum(++$) ]} ... * ;
    @triangle;
};

multi count_permutation ( NaturalNumber :$elements! ) {
    count_permutation.[ $elements ]
};

multi count_permutation ( NaturalNumber  :$elements!,  NaturalNumber :$inversions! ) {
    count_permutation( :$elements ).[ $inversions ] // 0
};                                                             

multi count_permutation ( NaturalNumber :$inversions! ) {
     { count_permutation( :elements( $++ ), :$inversions ) }  ... *
};

Použití:

say "Počet permutací na 10 prvkové množině, které mají 8 inverzí je: ",
count_permutation :10elements, :8inversions ;

say "\nPočet permutací na nejvýše 9 prvkové množině, které mají 10 inverzí je postupně: ", count_permutation( :10inversions ).[^10];

say "\nPrvních 11 řádků trianglu. Neviděli jste už někde tento triangle např. v kombinatorické knížce?";
.say  for count_permutation.[^11]

Výstup:

Počet permutací na 10 prvkové množině, které mají 8 inverzí je: 8095

Počet permutací na nejvýše 9 prvkové množině, které mají 10 inverzí je postupně: (0 0 0 0 0 1 71 573 2493 8031)

Prvních 11 řádků trianglu. Neviděli jste už někde tento triangle např. v kombinatorické knížce?
[]
[1]
[1 1]
[1 2 2 1]
[1 3 5 6 5 3 1]
[1 4 9 15 20 22 20 15 9 4 1]
[1 5 14 29 49 71 90 101 101 90 71 49 29 14 5 1]
[1 6 20 49 98 169 259 359 455 531 573 573 531 455 359 259 169 98 49 20 6 1]
[1 7 27 76 174 343 602 961 1415 1940 2493 3017 3450 3736 3836 3736 3450 3017 2493 1940 1415 961 602 343 174 76 27 7 1]
[1 8 35 111 285 628 1230 2191 3606 5545 8031 11021 14395 17957 21450 24584 27073 28675 29228 28675 27073 24584 21450 17957 14395 11021 8031 5545 3606 2191 1230 628 285 111 35 8 1]
[1 9 44 155 440 1068 2298 4489 8095 13640 21670 32683 47043 64889 86054 110010 135853 162337 187959 211089 230131 243694 250749 250749 243694 230131 211089 187959 162337 135853 110010 86054 64889 47043 32683 21670 13640 8095 4489 2298 1068 440 155 44 9 1]

Závěr

Perl 6 díky lenosti, paralelního zpracování a např. operátoru ... dovoluje variabilitu při práci s poli a rozšiřuje jejich použití i v nových situacích.        

Komentáře

[kolcon]

jak mam Perl rad, tak se mi P6 moc nelibi... tohle fakt nekomu prijde citelne?

sub rotate_sum ( @a, NaturalNumber $n ) { [Z+] ( [flat(0 xx $n, @a)], { .rotate } ... { .[0] != 0 } ); }

[wamba]

Uvedu můj pohled proč je to nečitelné:

• použil jsem hodně věcí typických pro Perl 6,
• nenapsal jsem k tomu dokumentaci, ani příklady použití,
• moje schopnost psát čitelný kód je omezena,
• nebyla úplně moje priorita to napsat nejčitelněji jak to jde, a uznávám, že např. [flat(0 xx $n, @a)] by si asi zasloužilo rozepsat na více řádků (možná pomocí prepend).

Pokusím se vysvětlit, co to dělá.

Nejdříve na příkladu, při zadání 1 2 2 1 a 3

0 0 0 1 2 2 1
0 0 1 2 2 1 0
0 1 2 2 1 0 0
1 2 2 1 0 0 0
-----------------
1 3 5 6 5 3 1

vrátí 1 3 5 6 5 3 1.

Teď ke kódu:

• [flat(0 xx $n, @a)] nultý prvek bude pole @a a před ním $n nul,
• { .rotate } další prvek získáme tak, že předešlí prvek rotujeme,
• { .[0] != 0 } získávej nové prvky (pole) dokud nebude na začátku nula,
• [Z+] sečti pole po prvcích.

Z mého pohledu, toho dělá tento kód poměrně hodně. A po rozluštění toho nultého prvku se mi zdá i poměrně čitelný. A kdyby jsem tento podprogram napsal např. pomocí for, tak by to podle mě kód prodloužilo a čitelnost nezlepšilo. Doufám, že jsem tento kód alespoň částečně vysvětlil.

[kolcon]

ok... chapu snahu o idiomaticky zapis, to je OK. Jen bych teda asi zmenil nazev zapisku na "co vsechno jde v P6". Protoze jestli si toto nekdo vygoogli jako tutorial pro P6, tak potes koste... (imho)

[wamba]

Cílem blogu určitě není abych někoho učil Perl 6, první blog — Úvod odstavec Naučte mě Perl 6. Ten název měl evokovat, že bych se taky něco (nejen o Perlu 6) rád dozvěděl od čtenářů.

Co se týká operátoru ..., tak je to věc, na kterou je potřeba si zvyknout. Mně nečitelný nepřipadá. Já na něj nahlížím jako na jakýsi druh koncové rekurze, kde se zaznamenávají i mezivýsledky. Ale je pro mě snadnější a přirozenější myslet pomocí operátoru ..., než používat přímo podprogramy s koncovou rekurzí.

[kolcon]

aha, ja teda nazev " Naučte mě Perl 6, dil XX" chapu tak, ze se tu naucim Perl, a ne tak, ze ty chces naucit Perl od ctenaru :)

[wamba]

Mírně jsem opravil kód v rotate_sum. Snad je to teď čitelnější.

[lama]

say 0, 1, * + * ...^ * > 1000

Takze jestli to spravne chapu:

Vyraz s hvezdickou vytvori lambda funkci. Takze treba * + * se prelozi na:

def f1(a, b): return a + b

Prvni hvezdicka je prvni parametr, druha druhy, ...

Druhy vyraz s hvezdickou je druha lambda funkce:

def f2(a): return a > 1000

Potom pri pouziti:

say 0, 1, f1 ...^ f2

runtime nejak dynamicky zjisti ze jsou tam funkce misto hodnot a zavola je k vygenerovani hodnot.

A jde nejak zapsat pomoci hvezdicek treba b - a ?

[wamba]

Ano chápete to dobře. Co se týká hvězdičky tak první znamená první parametr a druhá druhý atd. Tak buď můžete použít místo whatever kódu blog { $^b - $^a } nebo v případě s infix operátor jako je - lze použít i hyper operátor R, který operátor obrací * R- *.

say ( 0, 1, {$^b - $^a} ...^ * ).[^10];
say ( 0, 1,    * R- *   ...^ * ).[^10];

[Yokotashi]

Klingoni!

[xsubway]

autodie - The art of Klingon Programming? :)