Niezmienne struktury i głęboka hierarchia kompozycji

Zajmuję się tworzeniem aplikacji GUI, intensywnie pracującej z grafiką - na przykład możesz myśleć o niej jako edytorze wektorów. Bardzo kuszące jest uczynienie wszystkich struktur danych niezmiennymi - tak, że prawie bez wysiłku mogę cofnąć / powtórzyć, skopiować / wkleić i wiele innych rzeczy.

Dla uproszczenia skorzystam z następującego przykładu - aplikacja służy do edytowania kształtów wielokątnych, więc mam obiekt „Wielokąt”, który jest po prostu listą niezmiennych punktów:

Scene -> Polygon -> Point

I tak mam tylko jedną zmienną zmienną w moim programie - tę, która przechowuje bieżący obiekt Scene. Problem, który mam, zaczyna się, gdy próbuję zaimplementować przeciąganie punktowe - w wersji zmiennej po prostu chwytam Pointobiekt i zaczynam modyfikować jego współrzędne. W niezmiennej wersji - utknąłem. Mógłbym zapisać indeksy Polygonw bieżącym Sceneindeksie przeciągniętego punktu Polygoni zastąpić go za każdym razem. Ale to podejście nie jest skalowane - gdy poziomy składu wzrosną do 5 i dalej, płyta kotłowa stałaby się nie do zniesienia.

Jestem pewien, że problem ten można rozwiązać - w końcu jest Haskell z całkowicie niezmiennymi strukturami i monadą IO. Ale po prostu nie mogę znaleźć jak.

Czy możesz mi podpowiedzieć?

Mógłbym zapisać indeksy wielokąta w bieżącej scenie, indeks przeciągniętego punktu w wielokącie i zamieniać go za każdym razem. Ale to podejście nie jest skalowane - gdy poziomy składu wzrosną do 5 i dalej, płyta kotłowa stałaby się nie do zniesienia.

Masz całkowitą rację, to podejście nie jest skalowane, jeśli nie możesz obejść płyty kotła . W szczególności zmieniono płytę główną do tworzenia zupełnie nowej Sceny z małą podsekcją. Jednak wiele języków funkcjonalnych stanowi konstrukt do radzenia sobie z tego rodzaju manipulowaniem strukturami zagnieżdżonymi: soczewkami.

Soczewka jest zasadniczo narzędziem do pobierania i ustawiania niezmiennych danych. Obiektyw skupia się na niewielkiej części większej struktury. Biorąc pod uwagę soczewkę, są dwie rzeczy, które możesz z nią zrobić - możesz zobaczyć małą część wartości większej struktury lub możesz ustawić małą część wartości większej struktury na nową wartość. Załóżmy na przykład, że masz obiektyw, który skupia się na trzecim elemencie na liście:

thirdItemLens :: Lens [a] a

Ten typ oznacza, że ​​większa struktura jest listą rzeczy, a mała podsekcja jest jedną z tych rzeczy. Biorąc pod uwagę ten obiektyw, możesz wyświetlić i ustawić trzeci element na liście:

> view thirdItemLens [1, 2, 3, 4, 5]
3
> set thirdItemLens 100 [1, 2, 3, 4, 5]
[1, 2, 100, 4, 5]

Powodem, dla którego soczewki są przydatne, jest to, że są to wartości reprezentujące metody pobierające i ustawiające, i można nad nimi streścić w taki sam sposób, jak inne wartości. Możesz tworzyć funkcje zwracające soczewki, na przykład listItemLensfunkcję, która pobiera liczbę ni zwraca soczewkę wyświetlającą ten nelement na liście. Dodatkowo soczewki mogą być złożone :

> firstLens = listItemLens 0
> thirdLens = listItemLens 2
> firstOfThirdLens = lensCompose firstLens thirdLens
> view firstOfThirdLens [[1, 2], [3, 4], [5, 6], [7, 8]]
5
> set firstOfThirdLens 100 [[1, 2], [3, 4], [5, 6], [7, 8]]
[[1, 2], [3, 4], [100, 6], [7, 8]]

Każda soczewka zawiera zachowanie podczas przechodzenia przez jeden poziom struktury danych. Łącząc je, możesz wyeliminować płytę kotłową do przechodzenia przez wiele poziomów złożonych struktur. Załóżmy na przykład, że masz scenePolygonLens iwidok iwielokąta w scenie i polygonPointLens nwidok nthpunktu w wielokącie, możesz stworzyć konstruktor soczewek, który skupia się na konkretnym punkcie, na którym ci zależy w całej scenie:

scenePointLens i n = lensCompose (polygonPointLens n) (scenePolygonLens i)

Załóżmy teraz, że użytkownik klika punkt 3 wielokąta 14 i przesuwa go o 10 pikseli w prawo. Możesz zaktualizować scenę w następujący sposób:

lens = scenePointLens 14 3
point = view lens currentScene
newPoint = movePoint 10 0 point
newScene = set lens newPoint currentScene

To ładnie zawiera całą podstawkę do przemierzania i aktualizowania Sceny w środku lens, wszystko, o co musisz się martwić, to to, na co chcesz zmienić punkt. Możesz dodatkowo to wyodrębnić za pomocą lensTransformfunkcji, która akceptuje soczewkę, cel i funkcję aktualizowania widoku celu przez soczewkę:

lensTransform lens transformFunc target =
  current = view lens target
  new = transformFunc current
  set lens new target

Pobiera to funkcję i zamienia ją w „aktualizator” w skomplikowanej strukturze danych, stosując funkcję tylko do widoku i używając go do budowy nowego widoku. Wracając do scenariusza przesunięcia trzeciego punktu 14. wielokąta w prawo o 10 pikseli, co można wyrazić w następujący lensTransformsposób:

lens = scenePointLens 14 3
moveRightTen point = movePoint 10 0 point
newScene = lensTransform lens moveRightTen currentScene

I to wszystko, czego potrzebujesz, aby zaktualizować całą scenę. To bardzo skuteczny pomysł i działa bardzo dobrze, gdy masz jakieś fajne funkcje do konstruowania obiektywów wyświetlających fragmenty twoich danych, na których Ci zależy.

Jednak obecnie wszystko to jest dość popularne, nawet w społeczności programistów funkcjonalnych. Trudno jest znaleźć dobre wsparcie biblioteki do pracy z soczewkami, a jeszcze trudniej jest wyjaśnić, jak one działają i jakie są korzyści dla twoich współpracowników. Podejmij to podejście z odrobiną soli.

Pracowałem nad dokładnie tym samym problemem (ale tylko z 3 poziomami składu). Podstawową ideą jest klonowanie, a następnie modyfikowanie . W niezmiennym stylu programowania klonowanie i modyfikacja muszą odbywać się razem, co staje się obiektem polecenia .

Zauważ, że w zmiennym stylu programowania klonowanie i tak byłoby konieczne:

• Aby umożliwić cofanie / ponawianie
• System wyświetlania może wymagać jednoczesnego wyświetlania modelu „przed edycją” i „podczas edycji”, nakładających się (jako linie-widma), aby użytkownik mógł zobaczyć zmiany.

W zmiennym stylu programowania

• Istniejąca struktura jest głęboko sklonowana
• Zmiany są wprowadzane w sklonowanej kopii
• Mechanizm wyświetlania ma renderować starą strukturę w linie-widma, a sklonowana / zmodyfikowana struktura w kolorze.

W niezmiennym stylu programowania

• Każda akcja użytkownika powodująca modyfikację danych jest odwzorowana na sekwencję „poleceń”.
• Obiekt polecenia dokładnie określa, jaką modyfikację należy zastosować, oraz odniesienie do oryginalnej struktury.
  • W moim przypadku mój obiekt polecenia zapamiętuje tylko indeks punktów, który należy zmienić, i nowe współrzędne. (tj. bardzo lekki, ponieważ nie jestem absolutnie niezmienny).
• Kiedy obiekt polecenia jest wykonywany, tworzy zmodyfikowaną głęboką kopię struktury, dzięki czemu modyfikacja jest trwała w nowej kopii.
• Gdy użytkownik wprowadza więcej zmian, powstanie więcej obiektów poleceń.

Głęboko niezmienne obiekty mają tę zaletę, że głębokie klonowanie czegoś wymaga po prostu skopiowania odwołania. Ich wadą jest to, że nawet niewielka zmiana głęboko zagnieżdżonego obiektu wymaga zbudowania nowej instancji każdego obiektu, w którym jest zagnieżdżony. Zmienne obiekty mają tę zaletę, że zmiana obiektu jest łatwa - po prostu zrób to - ale głębokie klonowanie obiektu wymaga zbudowania nowego obiektu, który zawiera głęboki klon każdego zagnieżdżonego obiektu. Co gorsza, jeśli ktoś chce sklonować obiekt i dokonać zmiany, sklonować ten obiekt, wprowadzić kolejną zmianę itp., To bez względu na to, jak duże lub małe są zmiany, należy zachować kopię całej hierarchii dla każdej zapisanej wersji stan obiektu. Paskudny.

Podejście, które może być warte rozważenia, to zdefiniowanie abstrakcyjnego typu „być może ruchomego” ze zmiennymi i głęboko niezmiennymi typami pochodnych. Wszystkie takie typy miałyby AsImmutablemetodę; wywołanie tej metody na głęboko niezmiennej instancji obiektu po prostu zwróci tę instancję. Wywołanie go w instancji podlegającej mutacji zwróci instancję głęboko niezmienną, której właściwości były głęboko niezmiennymi migawkami ich odpowiedników w oryginale. Niezmienne typy ze zmiennymi odpowiednikami zastosowałyby AsMutablemetodę, która skonstruowałaby zmienną instancję, której właściwości byłyby zgodne z właściwościami oryginału.

Zmiana zagnieżdżonego obiektu w głęboko niezmienny obiekt wymagałaby najpierw zastąpienia zewnętrznego niezmiennego obiektu zmiennym, a następnie zastąpienia właściwości zawierającej przedmiot, który ma zostać zmieniony, zmiennym itp., Ale dokonanie powtarzanych zmian w tym samym aspekcie obiekt ogólny nie wymagałby tworzenia żadnych dodatkowych obiektów, dopóki nie zostanie podjęta próba wywołania AsImmutableobiektu zmiennego (co pozostawiłoby obiekty zmienne zmienne, ale zwróciłoby obiekty niezmienne zawierające te same dane).

Jako proste, ale znaczące optymalizacje, każdy zmienny obiekt może zawierać buforowane odwołanie do obiektu swojego powiązanego niezmiennego typu, a każdy niezmienny typ powinien buforować swoją GetHashCodewartość. Podczas wywoływania AsImmutablezmiennego obiektu, przed zwróceniem nowego niezmiennego obiektu, sprawdź, czy pasuje on do buforowanego odwołania. Jeśli tak, zwróć odwołanie do pamięci podręcznej (porzucając nowy niezmienny obiekt). W przeciwnym razie zaktualizuj odwołanie w pamięci podręcznej, aby przechowało nowy obiekt i zwróć to. Jeśli tak się stanie, wielokrotne połączenia zAsImmutablebez jakichkolwiek mutacji pośrednich przyniosą te same odniesienia do obiektów. Nawet jeśli nie zaoszczędzisz kosztów budowy nowych instancji, unikniesz kosztów pamięci związanych z ich utrzymaniem. Ponadto, porównania równości między niezmiennymi obiektami mogą być znacznie przyspieszone, jeśli w większości przypadków porównywane elementy są równe względem odniesienia lub mają różne kody mieszające.