Z tego co czytam, to w programowaniu funkcyjnym istotną rolę odgrywają "immutable data strutures" oraz "persistent data structures".
- 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).
- 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.