Úloha k procvičení 6 - Immutable funkcionální list

Při práci s více vlákny lze na narazit na mnoho problémů. Jedním z nich je jak zajistit, aby si jednotlivá vlákna navzájem nepřepisovala a zároveň nečetla sdílená data. Toto by mohlo vést k nekonzistenci takových dat, což by vedlo k chybné funkci programu.

Jedním z možných řešení této situace je jednoduše neumožnit přepisování sdílených dat. V Javě se jedná o vytváření tzv. immutable objektů (tříd). U immutable objektu není možné po jeho vytvoření měnit jeho vnitřní stav. V Javě je typickým představitelem immutable objektu třídy String, v případě primitivních datových typů se jedná o použití klíčového slova final. Výhodou tohoto řešení je, že jakmile je objekt vytvořen, programátor nemusí hlídat jaká vlákna k němu přistupují (samozřejmě toto je výhoda i jednovláknových programech). Ví totiž, že se jeho stav měnit nebude a tedy nemůže dojít k nekonzistenci dat. Nevýhodou je vyšší paměťová a výpočetní náročnost. V případě potřeby změn dat je potřeba vytvořit nový objekt (copy-on-write). Viz třída String, kdy je například vytváření Stringu v iteraci neefektivní.

Za domácí úkol máte vytvořit immutable implementaci listu předepsaného v interface Pr2List (zkráceně list). Tento list je vlastně spojový seznam jak naznačuje i obrázek. Jedná se o druh listu běžně používaný například ve fukncionálních jazycích (Lisp, Scala …). Viz https://en.wikipedia.org/wiki/Cons. List typicky obsahuje odkaz na prvek který uchovává a na list, který obsahuje další prvky. Výjimkou je poslední prvek listu (nazývaný Nil), který reprezentuje zároveň prázný list. Zároveň také naimplementujte metody pro filtrování a mapování obsahu. Viz dále.

Jednotlivé metody listu si nyní projdeme, nezapomeňte si zároveň prostudovat javadoc:

• append(T t) - tato netoda přidá nový prvek do listu mezi poslední stávající prvek a Nil. (Nil zde nebereme jako typický prvek listu). Vrací instanci nového listu, který obsahuje i vkládaný prvek.
• cons(T t) - přidá prvek na začátek listu a vrátí list obohacený o nový prvek. Všimněte si, že tato je narozdíl od append paměťově relativně nenáročná. Implementujte ji tak.
• isEmpty() - vrátí true pokud je list prázný, tedy pokud se jedná o Nil. Jinak vrací false.
• size() - vrátí počet prvků v listu. Pro Nil je size 0.
• filter(Predicate<T> predicate) - vrátí list bez prvků, které porušují zadaný predicate. Predicate je třída, používaná podobně jako například Comparator. Obsahuje jedinnou metodu, která dokáže pro každý prvek vrátit true anebo false.
• map(Function<T, O> function) - Pozor, nezaměňovat s datovou strukturou Map, pořád se používá list. S Mapou jako takovou je toto spojeno v trochu širším slova smyslu. Funkce map použije zadanou function, která pro každý prvek typu T vrací prvek typu O. map potom vrací nový list typu O, který obsahuje prvky vzniklé aplikací function na prvky původního listu.
• head() - vrátí první prvek v list
• tail() - vrátí list reprezentující zbytek listu, tedy všechno mimo head()
• iterator() - vrací Iterator pro list. Třída Iterator z definice není immutable. Pro ani v tomto úkolu nemusí být Iterator pro list immutable.
• view() - funkce view() souvisí s funkcemi filter a map. Viz níže.

Ukazuje se, že někdy při použití funkcí map a filter není třeba tyto hned aplikovat na všechny prvky listu, ale je výhodnější je vyhodnotit lazy. Představme si například situaci, kdy chceme z listu načíst první prvek, který splňuje daný predikát. Pak je zbytečné vyhodnotit vůči tomuto predikátu všechny prvky listu. V případě, že je list velký a víme, že někde blízko začátku se nachází vyhovující prvek, může se jednat o velkou časovou i paměťovou úsporu.

Funkce view() vrátí takovou instanci listu, která si při volání funkcí map a filter bude pamatovat zadané function a predicate a bude je vyhodnocovat teprve až to bude potřeba a to jen na minimálním množství prvků. Nezapomeňte i správně implementovat Iterator pro třídy reprezentující view. Pozor: jestltiže na view zavoláme tail(), vrátí se opět view reprezentující tail se stejnými vlastnostmi jako měl původní view.

Pro implementaci si stáhněte zdrojové kódy s příslušnými interface a factory třídou ListFactory. Řešení vytvořte do balíčku cz.cvut.k36.pr2.hw.hw06.impl. Odevzdávejte vámi vytvořené třídy potřebné k provozování listu, včetně implementované třídy ListFactory. Neodevzdávejte interface Pr2List, Predicate a Function.

Ukázkový kód práce s listem není záměrně k dispozici. Pro testování vašeho řešení si tento kód vytvořte.