💾 Archived View for danieljanus.pl › blog › pl › 2010 › 11 › 25 › zippery-w-clojure › index.gmi captured on 2024-08-25 at 00:18:47. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Zippery w Clojure

Niniejszy artykuł jest pierwszym z dwuczęściowego minicyklu, stanowiącego demonstrację wykorzystania Clojure w praktyce do prostego, acz nietrywialnego zadania, na które natknąłem się w codziennej pracy. Dzisiejsza część może wydać się mało interesująca i mocno teoretyczna, ale mam nadzieję, że następny odcinek pokaże, jak można ją ciekawie wykorzystać (na razie nie zdradzę, jakie to wykorzystanie).

Planuję, że takie artykuły lub cykle zdominują Clojurową część tego bloga – będę się tu dzielił rozwiązaniami praktycznych problemów, na jakie natrafiam. Nie będzie tu artykułów w stylu „hej, jaki fajny nowy framework XYZ, napiszmy w nim Hello World przy wykorzystaniu technologii ABC!”, chyba że XYZ lub ABC będą przydatnymi narzędziami do rozwiązania problemu z życia wziętego. Bo takie rozwiązywanie w Clojure daje dużo radości: nie przypadkiem taki właśnie jest tytuł książki M. Fogusa i C. Housera [1].

A dziś opowiem o ciekawej strukturze danych, jaką są zippery. (Mierzi mnie trochę używanie angielskiej nazwy, ale nie potrafię wymyślić dobrego polskiego odpowiednika tego słowa; będę szczęśliwy widząc propozycje w komentarzach!) Cóż to takiego?

Zipper [2] jest strukturą danych, dającą iluzję imperatywności przy manipulowaniu drzewami. Pamiętamy, że Clojurowe natywne struktury danych są niezmienne (immutable): jeśli mamy listę składającą się z liczb 2 i 5, to nie możemy jej w żaden sposób zmienić (np. dodać elementu) – możemy co najwyżej stworzyć na jej podstawie nową listę, która będzie zawierać wszystkie elementy listy wyjściowej i jeszcze jakiś.

Niezmienność jest bardzo przydatna (o filozoficznych podstawach takiego podejścia, które zadecydowały o jego wykorzystaniu w Clojure, można poczytać w artykule „On State and Identity” [3]), ale wymusza myślenie w innych kategoriach. To jest to, co czasami nazywa się „myśleniem funkcyjnym”: zamiast zastanawiać się, w jaki sposób zmienić wartość naszej zmiennej, aby doprowadzić ją do pożądanego stanu, pytamy o to, jak z jednych wartości robić inne. Przy tym nigdzie nie jest powiedziane, że taki sposób myślenia jest koniecznie lepszy od imperatywnego, do którego przyzwyczajeni są programiści języków takich jak Java. Jest po prostu inny. Warto się go nauczyć, bo okazuje się, że wiele problemów się upraszcza, gdy już umysł się przestawi na taki modus operandi. Bywa jednak i tak, że o danym problemie imperatywnie myśli się wygodniej niż funkcyjnie. Tu właśnie wkraczają zippery.

Image

Wyobraźmy sobie, że chcemy dodać liczbę 4 do konkretnego drzewa BST, tak jak na rysunku powyżej. Załóżmy chwilowo, że nie interesuje nas ogólna funkcja dodająca do BST, a tylko chcemy wstawić czwórkę w konkretne miejsce. Jak to zrobić imperatywnie?

Zejdź dwa razy w dół w prawo („dobierz się” do węzła 6).
Wstaw czwórkę na lewo od bieżącego węzła.

I już. A teraz funkcyjnie – pamiętamy, że z drzewa robimy nowe drzewo:

Nowym drzewem jest drzewo, którego korzeniem jest korzeń drzewawyjściowego, lewym poddrzewem – lewe poddrzewo drzewa wyjściowego, aprawym poddrzewem drzewo, którego korzeniem jest korzeń prawegopoddrzewa drzewa wyjściowego, lewym poddrzewem – drzewo składające sięz tylko jednego węzła 4, a prawym poddrzewem – prawe poddrzewo prawegopoddrzewa drzewa wyjściowego.

Pierwsze podejście jest łatwiejsze, prawda? Zipper pozwala nam zachować je prawie niezmienione, nie rezygnując przy tym z zalet niezmienności. Oto jak można by opisać dodawanie do drzewa z zipperem:

Stwórz zipper na podstawie drzewa wyjściowego.
Wykonaj na tym zipperze operację „zejdź w dół”, otrzymując nowy zipper.
Wykonaj na tym zipperze operację „przejdź w prawo”, otrzymując nowy zipper.
Wykonaj na tym zipperze operację „zejdź w dół”, otrzymując nowy zipper.
Wykonaj na tym zipperze operację „wstaw 4 przed bieżącym elementem”, otrzymując nowy zipper.
Wykonaj na tym zipperze operację „daj drzewo wynikowe”, otrzymując pożądane drzewo.

Clojure zawiera implementację zipperów w bibliotece standardowej (w przestrzeni nazw “clojure.zip”). Oto jak można by zapisać powyższy przykład w Clojure:

(def nowe-drzewo
  (let [z1 (zip drzewo)
        z2 (down z1)
        z3 (right z2)
        z4 (down z3)
        z5 (insert-left z4 4)]
    (root z5)))

(tu explicite nazywam kolejne kroki obliczeń). Albo tak, używając makra “->”:

(def nowe-drzewo
  (-> drzewo
      zip
      down
      right
      down
      (insert-left 4)
      root)))

Proste i wygodne. Pod spodem zipper to po prostu oryginalne drzewo plus informacja o tym, w którym miejscu drzewa w tej chwili jesteśmy, plus lista „zmian”, jakie do tej pory zostały na nim wykonane.

Rozwiązując mój problem (na razie nie zdradzam, jaki), natknąłem się na potrzebę posiadania funkcji, która działałaby jak “map”, ale na drzewach, a nie listach. To znaczy, przekształcałaby każdy element, niezależnie od tego, jak głęboko w drzewie siedzi, aplikując do niego jakąś funkcję, i zwracała w wyniku nowe drzewo. Co więcej, chciałem móc dodatkowo kontrolować, które węzły są zmieniane: funkcja ma dostawać dodatkowy predykat i tylko kiedy zwróci on “true” na wartości danego węzła, zmieniać tę wartość. Nie ma chyba takiej funkcji w standardowej bibliotece, ale dzięki zipperom można ją łatwo napisać.

Tak się szczęśliwie składa, że Clojurowe zippery mają funkcję “next”, która spaceruje po drzewie „w głąb”. Mając je, mogłem pomyśleć tak o swojej implementacji:

Jeśli zipper jest na końcu drzewa, to wynikiem transformacji jest wynikowe drzewo dla tego zippera, w przeciwnym razie wynikiem jest ta sama transformacja wywołana rekurencyjnie dla zippera uzyskanego przez wykonanie operacji „edit” (edycji bieżącego węzła w razie potrzeby) i „next”.

Tłumacząc to na Clojure, dostajemy:

(defn map-zipper [f pred z]
  (if (zip/end? z)
    (zip/root z)
    (recur f pred (-> z (zip/edit #(if (pred %) (f %) %)) zip/next)))))

I testujemy:

> (map-zipper inc integer?
              (zip/vector-zip [1 [2 [3 4]] [5] [6 [[7 8 9]]]]))
[2 [3 [4 5]] [6] [7 [[8 9 10]]]]

Trzeba podać predykat “integer?”, bo zipper działający na zagnieżdżonych wektorach działa na poszczególnych poddrzewach, a nie tylko na liściach (które tu są liczbami). Możemy łatwo zobaczyć, jakie poddrzewa odwiedza “map-zipper”:

> (map-zipper #(do (println %) %)
              (constantly true)
              (zip/vector-zip [1 [2 [3 4]] [5] [6 [[7 8 9]]]]))
[1 [2 [3 4]] [5] [6 [[7 8 9]]]]
1
[2 [3 4]]
2
[3 4]
3
4
[5]
5
[6 [[7 8 9]]]
6
[[7 8 9]]
[7 8 9]
7
8
9
[1 [2 [3 4]] [5] [6 [[7 8 9]]]]

Links

[1]

[2]

[3]