Podivný případ funkcí fold a reduce

Kdo se nestydí za svoje tweety z minulého roku, ten se málo vzdělává.

Kanonická podoba reduce, například z Java Stream API, je následující:

Optional<T> reduce(BinaryOperator<T> accumulator);

Metodu foldLeft bohužel streamy nemají (o tom později), ale kdyby ano, měla by vypadat asi takto:

<U> U foldLeft(U initial, BiFunction<U, ? super T, U> accumulator);

Na první pohled se liší v možnosti specifikovat výchozí hodnotu. Ale počkat, i streamy obsahují variantu reduce, kde je možné specifikovat výchozí hodnotu:

T reduce(T identity, BinaryOperator<T> accumulator);

Liší se tedy fold a reduce jen tím, že fold dovoluje mít rozdílné typy výchozí hodnoty (resp. akumulátoru) a položek samotných? Ale počkat, vždyť i streamy mají jednu variantu reduce pro tuto možnost:

<U> U reduce(U identity, BiFunction<U, ? super T, U> accumulator, BinaryOperator<U> combiner);

Jenom je tam navíc nějaký combiner…

Tenhle směr uvažování je samozřejmě úplně vadný. Jako vždycky, když se snažím zamést nějaký detail pod koberec, se nakonec ukáže, že onen detail je ve skutečnosti stěžejní fakt. Klíčové vodítko totiž tentokrát není v signatuře funkce, ale v sémantických zákonech, které musí její parametry ‎dodržovat, které jsou vyjmenované v JavaDocu reduce:

The identity value must be an identity for the accumulator function. This means that for all t, accumulator.apply(identity, t) is equal to t. The accumulator function must be an associative function.

Proč mají parametry reduce taková omezení? Protože ta abstrakce má velmi specifický účel. Díky těm omezením je možné práci na získání výsledku zcela arbitrárně rozdělit a skládat, což je vlastnost umožňující mimo jiné automatizovaný a škálovatelný paralelismus, kterým je reduce proslavený. Ona iniciální hodnota tak třeba nemusí být použita jen jednou, ale pro každé vlákno zpracování zvlášť (proto by se o ní nemělo mluvit jako o “výchozí” nebo “akumulační”, ale o “neutrální”). Výsledky všech vláken je pak zase možné libovolně kombinovat dokud nedostaneme finální výsledek. Proto je v poslední variantě reduce onen combiner - jako náhražka za to, že výchozí data a mezivýsledky není možné v důsledku rozdílných datových typů transparentně míchat.

Naproti tomu fold je navržen jako zcela všeobecná abstrakce iterace, která ze svojí podstaty nemůže splňovat pravidla umožňující arbitrární reorganizaci výpočtu. Jednotlivé položky se prostě musí popořadě aplikovat na výchozí hodnotu, jinak by to prostě nebyla abstrakce iterace.

Tweet ze začátku tedy není vyloženě špatně, reduce je skutečně speciální případ foldu pro monoidy, ale tato specializace jej také předurčuje ke zcela jinému použití. To je tak nějak evidentní, jakmile to člověk potřebuje prakticky použít a ne jen jalově filosofovat, že.

Evidentně nejsem sám, kdo s těmi termíny trochu žongluje. Když si pod výchozí hodnotou představíme nějaký stav, a pod položkami události, které tento stav mění, je to de facto základ frontendové architektury Redux, jejíž jméno intuitivně evokuje právě reduce. Ten však paradoxně v její implementaci použít nejde, protože pořadí a návaznost CRUD operací rozhodně nejde zpřeházet nebo provádět nad separátními výchozími hodnotami. Pak se v tom má někdo vyznat. Ať žije Foldux!

Fold‎ ve Stream API‎

Absence foldLeft i foldRight (a všech odvozených utilit jako třeba scan) ve streamech je vůbec kapitola sama pro sebe, protože dovoluje pochopit, co vlastně streamy jsou (a nejsou).

Streamy na jednu stranu implementují flatMap, což z nich dělá funktory a směřuje to k plnohodnotnému funkcionálnímu programování, ale na druhou stranu neimplementují fold, kterým FP naopak zabijou. Čím je reduce tak speciální, že si na rozdíl od svého většího bráchy, foldu, začlenění do Stream API zasloužil? A co je vlastně collect? A co si o tom všem myslí Jan Tleskač?

Vezmu to odzadu. Kdo se ze streamu snaží vykřesat alespoň krapet funkcionálního programování, většinou skončí u collect, který vypadá, že se foldu blíží nejvíc svojí schopností vyrábět ze streamů jiné kolekce. Ale je to past, protože ve skutečnosti je to hybrid s názvem “mutable reduce”, který je téměř identický s třetí variantou reduce z předchozí kapitoly jen s tím rozdílem, že nebere jako parametry obecné funkce, ale metody svého akumulátoru, čímž ho, na rozdíl od standardního reduce, mutuje.

Ani collect se tedy nijak neblíží obecné abstrakci iterace. Proč? Jednoduše proto, že Java prostě řeší iteraci for cyklem, pro který si ze streamu můžeme vzít Iterator. Operátory streamu tam nejsou proto, aby do Javy zavedly generické FP, ale protože mají nějaký význam pro jednoduchost nebo výkonnost zpracování dat v kolekcích jako třeba onen paralelismus. Fold by proti for cyklu žádné takové vylepšení nepřinesl (je to jen změna z externího na interní iterátor) a naopak by nesl zátěž v podobě nemožnosti paralelizovat takto zpracovaný stream.

Továrna na absolutno

Analizovat fold a reduce komparativně je fajn a dává to nějaký vhled, ale ke zjištění, zda se fold a reduce liší nějak fundamentálně, to nestačí. K tomu je potřeba vědět co tyto funkce jsou. Že budu chtít odpověď od teorie kategorií mi bylo tak nějak jasné, ale kde začít?

Intuitivně jsem začal od toho, že jedno z nejjednodušších použití reduce je ke spočítání délky pole. O funkci délky pole si taky pamatuju, že to je z kategorického pohledu “natural transformation”. Může tedy být reduce takový “template” pro tvorbu přirozených transformací? Měl by z tohoto titulu v teorii kategorií nějaký speciální status? Tady už moje vědomosti krutě končí, tak jsem se prostě zeptal.

A bylo mi odpovězeno.

I don’t thik so. Fold is a catamorphism, and it’s defined for an F-algebra f b -> b. An algebra is specifically not a polymorphic function. In particular, you can see that the type parameters in fold occur both in covariant and contravariant positions.

Čtenáři Stopařova průvodce galaxií jistě docení rozkošnou situaci získání odpovědi, která je nesrozumitelná z důvodu neuvědomělé neznalosti otázky. No nic, tak snad zase za rok.

TL;DR

Jako v dobrém detektivním příběhu, když Poirot odhalí všechny úskoky a vyloží protagonistům jak to všechno doopravdy bylo‎, se identifikovaný vrah přizná a doplní chybějící detaily a motivaci.‎ Proč se mi sakra tyhle materiály vždycky dostanou do ruky až když to všechno vymyslím sám?

Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful from Malcolm Wallace on Vimeo.