Novinky kolekcí ve Scale 2.13

11. 10. 2018 #Scala #API #DS

Nadcházející verze Scaly 2.13 přinese jednu velkou změnu: Nový framework kolekcí. Došlo k jejich internímu překopání, zjednodušení a celkovému uhlazení (konečně funkční mechanismus pohledů). Velká část z těchto změn by měla být interní záležitostí. Nové kolekce sice nebudou binárně kompatibilní s těmi ve verzi 2.12 (zmizí například (ne)oblíbený hlavolam CanBuildFrom). Bude třeba překompilovat, ale na úrovni zdrojových textů by kompatibilita měla být z velké části zachována.

Kromě toho, ale přibylo několik metod, které mi vždycky chyběly a musel jsem je tisíckrát obcházet a nahrazovat. Tady je seznam těch, které jsem objevil.

In place operace nad měnitelnými kolekcemi

mapInPlace
flatMapInPlace
filterInPlace
dropInPlace, dropRightInPlace, dropWhileInPlace
takeInPlace, takeRightinPlace, takeWhileInPlace
sliceinPlace, patchInPlace, padToInPlace,
sortInPlace, sortInPlaceBy, sortInPlaceWith

O řazení na místě se stará scala.util.Sorting.stableSort, který interně používá buď java.util.Arrays.sort nebo, pokud používám vlastní Ordering, merge sort. To je malý nedostatek, protože merge sort potřebuje alokovat pomocné pole a není tedy úplně in place.

Vylepšené `groupBy` metody:

def groupMap[K, B](key: A => K)(f: A => B): immutable.Map[K, Seq[B]]
def groupMapReduce[K, B](key: A => K)(f: A ⇒ B)(reduce: (B, B) ⇒ B): immutable.Map[K, B]

groupMap je přesně to, co mi chybělo. Následující dva řádky mají identické chování.

xs.groupMap(key)(f)
xs.groupBy(key).map { case (k, vs) => (k, vs.map(f)) }

Je to jednak kratší a navíc nejsou třeba alokace dočasných kolekcí.

xs.groupMapReduce(keyF)(mapF)(redF)
xs.groupBy(keyF).map { case (k, vs) => vs.map(mapF).reduce(redF) }

collectFirst

collect je užitečná metoda, která kombinuje map a filter. Jako argument se ji předá parciální funkce, elementy, pro které je definovaná budou zachovány a transformovány. Následující dva řádky se chovají identicky:

xs.collect { case x if f(x) => g(x) }
xs.filter(f).map(g)

Není třeba vytvářet kolekci mezivýsledku + parciální funkce nemusí obsahovat jen jeden predikát, ale libovolný pattern matching (ideální například pro regexy)

Pro souměrnost přibyla collectFirst, které funguje jako find po níž následuje map.

Bezpečná maxima a minima

Dříve existovaly jednak metody head a last, které pro prázdnou kolekci vyhodily výjimku a pak bezpečné metody headOption a lastOption, ale pro získání minim a maximu existovaly jen výjimky házející verze. Ve verzi 2.13 bude tento nedostatek napraven a přibudou metody maxOption, minOption, maxByOption, minByOption.

V podobném duchu se nesou nové metody parsující string na čísla: toInt přibude bezpečný bratříček toIntOption. Možná jde o drobnosti, ale na druhou stranu vyplňují mezery v ortogonalitě.

Různé užitečné drobnosti

distinctBy vybere neopakující se elementy a odfiltruje duplikáty, argumentem je funkce určující, podle čeho se bude porovnávat duplicita

xs.distinctBy(f)

// je identické jako

val ys = xs.reverse.map { x => (f(x), x) }.toMap.values.toSet
xs.filter(ys)

Další je metoda partitionWith, která kombinuje partition a následnou transformaci obou stran v jednom kroku.

xs.partitionWith(f)

// stejné jako

val ys = xs.map(f)
val ls = ys.collect { case Left(l) => l }
val rs = ys.collect { case Right(r) => r }
(ls, rs)

Nové datové struktury

Neměnné immutable.HashMap a immutable.HashSet pod kapotou přešly na rychlejší a paměťově efektivnější implementaci CHAMP (konečně).
Přibyl mutable.ArrayDeque, jako možná náhrada za mutable.ArrayBuffer, která podporuje rychlé vkládání nejen na konec, ale i na začátek.
Další věc důležitá pro všechny, kteří chtějí vymáčknout z hardwaru vždy o něco víc, je immutable.ArraySeq. Jde o obyčejné ploché pole zabalené do rozhraní, které ho neumožňuje měnit. Proto je na jednu stranu velice rychlé a kompaktní, na druhou stranu aktualizace kopírují kompletní obsah bez strukturálního sdílení.

To jsou některé zajímavé změny, které přijdou. Scala 2.13 je zase jedna verze, která po dlouhé době vypadá zajímavě.

Dodatek: Pořád mi chybí metoda top(k), která by vrátila k největších elementů (a její varianty topkBy(k, f) atd). Nejpohodlněji se to samé dá zařídit pomocí xs.sortBy(f).take(10), ale jde o neoptimální řešení s komplexitou O(n log(n)). To samé se dá zařídit přes haldu nebo quickselect v čase O(n log(k)), ale musím všechno napsat sám.

0xDEADBEEF