Scala - persistent/immutable data structures

Z tego co czytam, to w programowaniu funkcyjnym istotną rolę odgrywają "immutable data strutures" oraz "persistent data structures".

1. Czy stosowanie np. kolejki, która nie jest "trwała" postrzegane jest jako niekoszerne/niefunkcyjne?
2. W przypadku implementacji zwykłego BST, co jest cechą, która mówi o tym, że takie BST jest "trwałe"? W moim rozumieniu, jest to możliwość "cofnięcia się w czasie" i spojrzenia, jak takie drzewo wyglądało w jakimś momencie swojego życia. Czy dobrze to rozumiem?

Immutable struktury sie niezmieniaja, dodajac element, tworzysz nowa, ktora dzieli czesc starej(persistent).

yarel napisał(a):

Z tego co czytam, to w programowaniu funkcyjnym istotną rolę odgrywają "immutable data strutures" oraz "persistent data structures".

1. Czy stosowanie np. kolejki, która nie jest "trwała" postrzegane jest jako niekoszerne/niefunkcyjne?

Kolejka może być trwała -- w tym sensie, co napisał @lion137 -- że każda zmiana oznacza tworzenie nowej danej, a stare dalej są sobie w pamięci (o ile są potrzebne) lub są w odpowiednim momencie zwalniane/odśmiecane automatycznie. Trwałość to sposób implementacji, a kolejkę można zaimplementować różnie. W tym, można zaimplementować kolejkę dość prosto w sposób trwały bez (znaczącej) starty złożoności czasowej (i pamięciowej również) -- https://rafal.io/posts/haskell-queues.html (punkt 0.2, w Haskellu, ale zasada jest jasna).

To czy coś jest kolejką nie ma nic wspólnego ze sposobem jej zaimplementowania (trwałym czy nie), ale z tym, w jaki sposób jest dostęp do struktury (w kolejce powinny być określone odpowiedniki operacji: front, is_empty, push_back, pop_front).

Całe hohoho związane z trwałością danych wynika z matematycznego podejścia do funkcji (które ma wiele zalet, jeśli chodzi o poprawność algorytmów i znajdowanie błędów), a w matematyce funkcja nigdy niczego nie modyfikuje, tylko po prostu zwraca wynik, który jest nową daną (bez psucia starej).

A więc stosowanie struktur nietrwałych w programowaniu funkcyjnym ja bym widział raczej jako niekoszerne... Chyba, że za pośrednictwem monad, ale tu chyba nie o tym piszemy. :) (Monady zresztą też są trwałymi strukturami z punktu widzenia matematyki).

2. W przypadku implementacji zwykłego BST, co jest cechą, która mówi o tym, że takie BST jest "trwałe"? W moim rozumieniu, jest to możliwość "cofnięcia się w czasie" i spojrzenia, jak takie drzewo wyglądało w jakimś momencie swojego życia. Czy dobrze to rozumiem?

Z trwałości wynika taka możliwość, ale może też być inaczej zaimplementowana. W trwałości ważne jest to, że nie masz nigdy operacji, które zmieniają daną (czyli mutatorów/transformatorów), jedynie operacje, które wyciągają dane (akcesory) i tworzą nowe (konstruktory). W C++ (nie tylko, ale to mi dość bliski język głównego nurtu) łatwo zaimplementować niezmienną (trwałą) strukturę spełniając w klasie następujące warunki:

• wszystkie pola prywatne;
• brak pól mutable;
• wszystkie metody (oprócz konstruktorów) opatrzone słowem const po nagłówku.

Na przykład trwały stos bez dużego narzutu związanego z pamięcią (wskaźniki automatyczne) i czasem wyglądać może tak:

#include <memory>

template<typename T>
class PersistenStack {
private:
    struct Cons {
        T item;
        std::shared_ptr<Cons> next;
        Cons(const T & item_, const std::shared_ptr<Cons> & next_) : item(item_), next(next_) {}
    };
    std::shared_ptr<Cons> top_ptr;
public:
    PersistenStack() : top_ptr(nullptr) {}

    T top() const {
        return top_ptr->item;
    }

    PersistenStack<T> push(const T & x) const {
        PersistenStack<T> aux;
        aux.top_ptr = std::make_shared<Cons>(x, top_ptr);
        return aux;
    }

    PersistenStack<T> pop() const {
        PersistenStack<T> aux;
        aux.top_ptr = top_ptr->next;
        return aux;
    }
};

#include <iostream>

int main() {
    using namespace std;

    PersistenStack<int> s1;
    PersistenStack<int> s2;

    s1 = s1.push(1);
    s1 = s1.push(2);
    s2 = s1.push(3);  // tutaj mamy już dwa stosy dzielący wspólny ogon

    cout << s1.top() << endl;
    s1 = s1.pop();
    cout << s1.top() << endl;
    s1 = s1.pop();

    cout << s2.top() << endl;
    s2 = s2.pop();
    cout << s2.top() << endl;
    s2 = s2.pop();
    cout << s2.top() << endl;
    s2 = s2.pop();
}

Drzewo BST bardzo podobnie, tylko zamiast jednego next są dwa -- no i dostęp może być do wnętrza drzewa, nie tylko do górnego elementu (jak w stosie). Ale zasada ta sama. Kolejka -- trochę więcej zabawy, ale da się na podstawie sposobu podanego wyżej.

Źle mi było pisać z telefonu, ale jak Chcesz więcej o immutable (i persistent) strukturach danych to jest kurs Scali na Courserze:
https://www.coursera.org/learn/progfun1
Jest darmowy, tam wszystko Znajdziesz.

Kurs na courserze dobrze wprowadza w trwałe struktury w Scali, ale wydajne (czyli z structural sharing) trwałe struktury można zaimplementować też w innych językach. Obrazkowe i fajne wytłumaczenia jak działają trwałe struktury danych można przeczytać też na http://www.vavr.io/vavr-docs/ lub https://medium.com/@dtinth/immutable-js-persistent-data-structures-and-structural-sharing-6d163fbd73d2

Zaletą niemutowalnych struktur jest ułatwione rozumowanie w typowej logice (tzn niezorientowanej na wyciskanie najwyższej wydajności kosztem czytelności). Używając np niemutowalnych map:

• widzimy dokładnie gdzie te mapy są zmieniane - tylko w funkcjach, które pobierają mapę jako argument i zwracają jej nową wersję,
• nie musimy się zastanawiać czy mapę w danym miejscu trzeba sklonować czy nie, bo nigdy nie trzeba
• mając mutowalne mapy nie wiemy czy instancja mapy zwrócona z danej funkcji nie będzie też zwrócona w innym wywołaniu
• nie musimy się martwić synchronizacją, bo niemutowalne struktury danych są tylko do odczytu
• świetnie się więc nadają do przetwarzania wielowątkowego
• samo structural sharing można wykorzystać na wiele sposobów, np skeszować sobie kilka początkowych stanów map w bibliotece (np kilka domyślnych zestawów nagłówków), a potem w kodzie użytkownika lekko zmieniać
• itd

Dzięki za wszystkie odpowiedzi, kolejne elementy układanki wskoczyły na swoje miejsce. Gdzieś mi się zapaliła lampka, że Scala nie była najlepszym wyborem jeśli chodzi o naukę programowania funkcyjnego :D Robię różne zadania i często łapię się na tym, że jednak rozwiązanie nie jest właściwe z perspektywy paradygmatu funkcyjnego, a pokusa korzystania z mutowalnych struktur danych bywa duża.

Polecam książkę https://www.manning.com/books/functional-programming-in-scala
Całkiem spoko wprowadza w świat FP, aczkolwiek nie wszystkie elementy polecam (tzn konkretnie to monady IO są niewygodne w Scali).

Sprobuj tego:
https://iloveponies.github.io/120-hour-epic-sax-marathon/

Wibowit napisał(a):

Polecam książkę https://www.manning.com/books/functional-programming-in-scala
Całkiem spoko wprowadza w świat FP, aczkolwiek nie wszystkie elementy polecam (tzn konkretnie to monady IO są niewygodne w Scali).

Dzięki bardzo, patrząc po darmowych rozdziałach napisana w sposób bardzo przystępny i skupiająca się nie tyle na składni Scali, co na konceptach. Wygląda na to czego potrzebuję :) Do tej pory często posiłkowałem się "Scala Cookbook" Alvin Alexander, ale to w zasadzie tylko składnia Scalowa w pigułce.

yarel napisał(a):

Dzięki za wszystkie odpowiedzi, kolejne elementy układanki wskoczyły na swoje miejsce. Gdzieś mi się zapaliła lampka, że Scala nie była najlepszym wyborem jeśli chodzi o naukę programowania funkcyjnego :D Robię różne zadania i często łapię się na tym, że jednak rozwiązanie nie jest właściwe z perspektywy paradygmatu funkcyjnego, a pokusa korzystania z mutowalnych struktur danych bywa duża.

Do nauki paradygmatu funkcyjnego zdecydowanie polecam Haskella -- tu nie masz wyjścia, musisz programować funkcyjnie ze wszystkimi tego zaletami i wadami. Haskell (jeśli wytrzymasz) szybko wymusi odpowiednie podejście... :)