💾 Archived View for danieljanus.pl › blog › pl › 2012 › 01 › 10 › praktyczne-uzycie-monady-state › i… captured on 2021-12-04 at 18:04:22. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
Wreszcie rozumiem monady!
Pierwszy raz zetknąłem się z nimi dobrych osiem lat temu, przy okazji nauki Haskella; wtedy jednak nie starczyło mi cierpliwości, aby zaznajomić się z podstawami teoretycznymi. Sprawy nie ułatwiał fakt, że trudno o naprawdę przystępne i zrozumiałe wprowadzenie do tego tematu: wygląda na to, że każdy adept Haskella, zrozumiawszy monady, pisze na ten temat własny tutorial. Ja się powstrzymam od tego naturalnego odruchu i po prostu odeślę do niesamowicie szczegółowego, ośmioczęściowego cyklu artykułów [1] autorstwa Mike'a Vaniera, który – wreszcie! – sprawił, że coś mi „zaskoczyło” w umyśle. Zamiast tego w tym wpisie wynotuję najważniejsze spostrzeżenia, jakie zapamiętałem, a potem pokażę dwie wersje pewnego kodu operującego na sekwencjach bitów: niemonadyczną i napisaną z użyciem monady “state”.
Mike zakłada znajomość Haskella, jak pisze we wstępie, na poziomie typów polimorficznych i klas typów; w praktyce jednak myślę, że do zrozumienia tekstu wystarczy pewne obycie z haskellową notacją (bardzo zresztą przypominającą zwykłą notację matematyczną), bo bardziej zaawansowane rzeczy są wyjaśniane w tekście na bieżąco. Bardzo polecam.
Oto więc moje notatki:
Reszta tego wpisu będzie poświęcona właśnie przykładowemu użyciu monady stanu w Clojure. Pisałem wcześniej [2], że nie widziałem dotąd kodu, który dałby się wyrazić przejrzyściej zapisany z użyciem monad niż bez nich – i właśnie na taki kod się natknąłem.
Wyobraźmy więc sobie, że mamy strumień bitów. Dla prostoty zdefiniujmy sobie przykładowy strumień, na którym będziemy testować nasze funkcje, jako clojurowy wektor zer i jedynek.
(def v [1 1 1 0 1 0 1 0 1 0])
Chcemy naddać naszemu strumieniowi pewne uporządkowanie: zdekodować zera i jedynki, które z niego przychodzą, według jakiegoś kodu o zmiennej długości. Najbardziej oczywistym, znanym każdemu kodem jest kod binarny: czytamy ze strumienia ileś bitów, traktujemy je jako binarną (bez znaku) reprezentację pewnej liczby i zwracamy tę liczbę. Łatwo napisać w Clojure funkcję, która to robi.
(defn read-binary [n bits]
(loop [res 0 n n [fst & rst :as bs] bits]
(if (zero? n)
[res bs]
(recur (+ res res fst) (dec n) rst))))
Spróbujmy wczytać z naszego strumienia czterobitową liczbę:
(read-binary 4 v) ;=> [14 (1 0 1 0 1 0)]
Czternaście. Ale zauważmy, że zdekodowana liczba nie jest jedyną zwracaną wartością! Żeby dało się z naszego strumienia odczytywać dalsze liczby, musimy zwrócić parę (wektor dwuelementowy): wartość odczytana plus reszta strumienia, z której będziemy czytać dalej. Piszemy wszak funkcyjnie: nie zmieniamy naszych wartości w miejscu, tylko z jednych wartości produkujemy następne.
Innym rodzajem kodu jest kod unarny: czytamy po prostu ze strumienia jedynki, aż napotkamy pierwsze zero – wtedy przestajemy czytać i naszą wartością jest liczba przeczytanych bitów. W ten sposób dowolną liczbę dodatnią n da się zareprezentować na n bitach. Implementacja jest równie prosta:
(defn read-unary [bits]
(loop [n 1 [fst & rst] bits]
(if (zero? fst)
[n rst]
(recur (inc n) rst))))
Sprawdzamy:
(read-unary v) ;=> [4 (1 0 1 0 1 0)]
Trzy jedynki i zero, razem cztery skonsumowane bity, więc odczytaną liczbą jest 4. Działa.
Spróbujmy teraz skleić nasze funkcje, to znaczy odczytać ze strumienia dwie liczby: najpierw zakodowaną unarnie, a potem binarnie na sześciu bitach.
(let [[x v1] (read-unary v)
[y v2] (read-binary 6 v1)]
[x y])
;=> [4 42]
Wynik jest poprawny, ale kod nieelegancki: tak naprawdę nie interesują nas te wszystkie “v”, “v1”, “v2”, które przepychamy przez nasze funkcje; potrzebujemy tylko przeczytanych liczb, a poszczególne części strumienia są nam tylko po to, żeby mieć z czego czytać. Im więcej składanych ze sobą operacji, tym łatwiej się pomylić.
Tu wkracza monada stanu, która umożliwia ukrycie tych pośrednich wartości i bardziej eleganckie złożenie “read-unary” i “read-binary”. Monadycznie zapisalibyśmy to jakoś tak:
(domonad state-m
[x read-unary
y (partial read-binary 6)]
[x y])
;=> #
Wygląda to bardzo podobnie. “domonad state-m” jest jak “let”. Tak jak chcieliśmy, nie przekazujemy naszego stanu (strumienia) explicite; zamiast tego przy “x” i “y” podajemy funkcje, które mają być zawołane na aktualnym stanie, żeby uzyskać żądaną wartość i nowy stan.
No dobrze, ale gdzie tu miejsce na nasz stan początkowy? Jak go przekazać? Proste: powyższa formuła, jak widać z mało czytelnego wyniku, zwróciła jakąś funkcję. Wystarczy ją teraz zawołać na naszym początkowym stanie, aby uzyskać wynik wraz ze stanem końcowym:
(*1 v) ;=> [[4 42] nil]
Jedyne, co wydaje się nadmiarowe w naszym złożeniu, to owo “partial” pojawiające się wyżej. Jest to efekt uboczny faktu, że Clojure w odróżnieniu od Haskella rozróżnia funkcje jedno- i więcejargumentowe (tak dokładniej to w Haskellu występują wyłącznie funkcje jednoargumentowe). Skoro w “domonad state-m” powinny na przemian pojawiać się symbole i funkcje jednoargumentowe biorące stan, to gdy nasza funkcja akceptuje coś jeszcze (tu: liczbę bitów), powinniśmy zrobić z niej funkcję jednoargumentową za pomocą “partial”. Alternatywnie, jeżeli chcemy trzymać się stylu monadycznego, możemy przepisać “read-binary” jako:
(defn read-binary [n]
(fn [bits]
(loop [res 0 n n [fst & rst :as bs] bits]
(if (zero? n)
[res bs]
(recur (+ res res fst) (dec n) rst)))))
Teraz zamiast “(partial read-binary 6)” możemy napisać po prostu “(read-binary 6)”.
Teraz, kiedy umiemy już składać operacje stanowe, zilustrujemy to przy pomocy jeszcze jednego kodu, a właściwie rodziny kodów nazywanych kodami Golomba. Po szczegółowy opis odsyłam do Wikipedii [3], natomiast dla potrzeb tego artykułu wystarczy nam wiedza, że te kody są parametryzowane jedną liczbą m. Liczba w kodzie Golomba jest podzielona na dwie części, z których pierwsza jest zakodowana unarnie, a druga – nie większa niż m – binarnie. W implementacji możemy więc skorzystać z naszych gotowych już funkcji “read-unary” i “read-binary”.
Bez dłuższych już komentarzy przedstawię dwie implementacje: eksplicytną i używającą monady stanu. Obie będą używać pomocniczej funkcji “read-bit”, czytającej po prostu jeden bit ze strumienia i używanej tak samo jak “read-unary” czy “read-binary”.
(defn read-bit [[bit & bits]] [bit bits])
Najpierw wersja niemonadyczna:
(defn read-golomb [m]
(fn [bits]
(let [k (clog2 m)
r (- (bit-shift-left 1 k) m)
[a bits1] (read-unary bits)
[b bits2] ((read-binary (dec k)) bits1)
[ir bits] (if (< b r)
[b bits]
(let [[nb bits] (read-bit bits)]
[(+ b b nb (- r)) bits]))]
[(+ (* (dec a) m) ir) bits])))
A teraz używająca monad. Żeby nie przeplatać “let” i “domonad”, można po prostu zdefiniować funkcję zwracającą pewną stałą wartość i niezmieniony stan – nazwę ją “m-const”:
(defn m-const [x]
(fn [state]
[x state]))
Używając jej, możemy zaimplementować “read-golomb” tak:
(defn read-golomb-monadic [m]
(domonad state-m
[k (m-const (clog2 m))
r (m-const (- (bit-shift-left 1 k) m))
a read-unary
b (read-binary (dec k))
nb (if (< b r) (m-const nil) read-bit)]
(+ (* (dec a) m)
(if (< b r) b (+ b b nb (- r))))))
Czytelniej?