Krótko o transformatorach monad

transformatory.md

Krótko o transformatorach monad

Dziś chciałbym opowiedzieć nieco o transformatorach monad, które dla osób, które poznały dopiero Haskella i jego podstawowe mechanizmy jak funktory, funktory aplikatywne i monady, są mało intuicyjne a ich mechanizm działania jest dość tajemniczy. Chciałbym wspomnieć o tym:

• czym jest transformator monad;
• jak definiować własne transformatory monad;
• jak implementować własne transformatory monad.

Wstęp

Z pewnością, skoro chcesz dowiedzieć się, czym jest transformator monad, wiesz również, czym jest monada, albo przynajmniej kojarzysz ten koncept. Usystematyzujmy sobie wiedzę na ten temat.

Monada jest to funktor (jak również funktor aplikatywny), który ma operację przekazywania wartości, oznaczaną jako >>= (czyt. bind) oraz kanoniczne zanurzenie wartości w ten funktor, nazwane jako return.

class (Applicative m) => Monad m where
  return :: a -> m a
  return = pure
  (>>=) :: m a -> (a -> m b) -> m b

Operacja bind pozwala na wypakowanie wartości z funktora, przekazanie jej do funkcji a -> m b (zwaną też akcją monadyczną). Szereg takich przekazań pozwala na składanie akcji monadycznych.

foo a = doThis a >>= \x -> transformThat x >>= \y -> finishThis y

bądź inaczej zapisane jako

foo a = do
  x <- doThis a
  y <- transformThat x
  finishThis y

czy też w bardziej zwartej formie

foo = doThis >=> transformThat >=> finishThis

Monady pozwalają na pisanie kodu w sposób łudząco podobny do kodu imperatywnego, z tą różnicą że monady segregują i kontrolują efekty uboczne. De facto monada jest implementacją pewnego efektu ubocznego.

Przykładowo Writer pozwala na kumulowanie wartości, które mają własność monoidu Monoid a, State pozwala na zarządzanie modyfikowalnym stanem a Error pozwala na zgłaszanie błędów, które wprowadzają zachowanie fail-first, podobnie jak wyjątki.

Oczywiście każda z monad wprowadza jeden efekt uboczny, jednak wiemy, że czasem trzeba napisać taki kod, który będzie łączył kilka efektów ubocznych na raz. Na przykład napisanie kompilatora prostego języka, który będzie miał możliwość odczytywania wartości uprzednio zdefiniowanych, operowania na stosie i emitowania kodu bajtowego, będzie potrzebowało monady, która łączy naturę Reader, State i Writer.

Transformatory monad

Ku temu są właśnie transformatory monad. Pozwalają na dodanie do monady konkretnych implementacji efektów ubocznych. Oznacza się zazwyczaj, dodając na końcu T. Takim sposobem StateT transformuje monady dodając możliwość modyfikowania stanu, ReaderT dodaje możliwość odczytu danych ze środowiska, itd.

Jak tego używać?

Normalnie.

Załóżmy, że mamy monadę IO i chcemy mieć dostęp do IORefów — referencji do mutowalnych fragmentów pamięci (tak, Haskell pozwala na mutowalne struktury danych, w szczególności mutowalne zmienne). Nie jest kłopotem napisać bardzo prostą funkcję w oparciu o IORefy.

import Data.IORef

sumIO :: [Int] -> IO Int
sumIO xs = do
  acc <- newIORef (0 :: Int)
  forM_ xs $ \x -> modifyIORef acc (+ x)
  readIORef acc

Większym zaś kłopotem jest przekazywanie IORefów do innych fragmentów kodu, które potrzebują współzielonego i modyfikowalnego stanu (edgy af). Wtedy naturalnym pomysłem jest uprzednia alokacja IORefów i umożliwienie odczytu tych IORefów z pewnej struktury. Na przykład możemy zrobić maszynę licznikową składającą się z dwóch liczników. Wtedy modelujemy stan jako

data CounterMachineState = CMState
  { counterX :: IORef Int
  , counterY :: IORef Int
  }

i definiujemy typ type CounterMachine a = ReaderT CounterMachineState IO a. W taki sposób uzyskaliśmy połączenie Reader + IO. Tym samym otrzymujemy operacje takie jak ask i asks.

foo :: CounterMachine ()
foo = do
  x <- readIOref =<< asks counterX -- ...i możemy coś z tym robić
  -- (więcej kodu) --

W zasadzie transformatory monad są jednym z najważniejszych narzędzi średnio-zaawansowanego programisty Haskella.

Jak je się robi?

Dla przykładu pokażę, jak zrobić MaybeT (jako ćwiczenie można zrobić EitherT). W zasadzie transformatory monad to nic innego jak zagnieżdżone monady. Naprawdę. Jedynym ciekawym faktem jest to, że są ku temu narzędzia, które pozwalają od tego stronić, bo same dobieranie się do warstw monad może być dość przykrym doświadczeniem, kiedy mamy nałożone kilka transformatorów (taką reguła kciuka są co najwyżej 2 transformatory nałożone na siebie, nie licząc bazowej monady; dla więcej niż dwóch transformatorów należy się zastanowić, czy kod będzie optymalny i czy nie popełniliśmy jakiejś gafy architektonicznej).

Więc jak wygląda struktura opisująca MaybeT? Tak właśnie:

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

Definiujemy funktor, funktor aplikatywny i samą monadę, bo transformowana monada musi nadal zostać monadą.

instance (Functor m) => Functor (MaybeT m) where
  fmap f = MaybeT . (fmap f <$>) . runMaybeT
  
instance (Applicative m) => Applicative (MaybeT m) where
  pure = MaybeT . pure . Just
  mf <*> ma = MaybeT $ (<*>) <$> runMaybeT mf <*> runMaybeT ma

instance (Monad m) => Monad (MaybeT m) where
  ma >>= f = MaybeT $ do
    maybeA <- runMaybeT ma
    case maybeA of
      Nothing -> return Nothing
      Just a -> runMaybeT (f a)

Kod binda jest samowytłumaczalny — jeśli brak wartości, to zwróć dalej brak w transformowanej monadzie. Jeśli wartość istnieje, wykonaj akcję monadyczną na tej wartości w transformowanej monadzie.

Ponadto funktor, jaki funktor aplikatywny, wykorzytuje instancje funktora i funktora aplikatywnego dla struktury Maybe.

Teraz przejdziemy do definiowania instancji klasy typów MonadTrans, która pozwala na uniesienie monady m do jej transformowanej wersji. Wygląda ona następująco:

class MonadTrans (t :: (* -> *) -> * -> *) where
  lift :: (Monad m) => m a -> t m a

Piszemy wobec tego następującą instancję dla MaybeT, która jest w miarę naturalna.

instance MonadTrans MaybeT where
  lift = MaybeT . fmap Just

Po prostu opakowuje zwyczajne m a w m (Maybe a), nie zmieniając zachowania monady m.

To już wszystko?

Niby tak, ale kurcze nie do końca. Taka wersja transformatora kazałaby nam ciągle wykonywać lift, żeby wykonać jakieś akcje transformowanej monady. Może być to dość niewygodne, wobec tego został zastosowany inny sposób.

Do każdej monady jest napisana stowarzyszona klasa typów, która mówi, że ta konkretna monada ma własności jak Reader, Writer, etc. Przykładowo

{-# LANGUAGE MultiParamTypeClasses #-}    -- pozwala na def. klas typów z kilkoma parametrami
{-# LANGUAGE FunctionalDependencies #-}   -- pozwala na określenie, jak typ jest dedukowany, 
                                          -- a -> b czyt. jako typ a determinuje typ b

class (Monoid w) => MonadWriter w (m :: * -> *) | m -> w where
  tell :: w -> m ()

mówi o tym, że monada potrafi zapisywać "na boku" w, który jest monoidem.

Tym samym możemy napisać instancję dla MaybeT:

{-# LANGUAGE MultiParamTypeClasses #-}
instance (MonadWriter w m) => MonadWriter w (MaybeT m) where
  tell = lift . tell

która pozwoli na zwyczajne korzystanie z funkcjonalności monady Writer bez unoszenia jej za pomocą lift, innymi słowy, będziemy mogli korzystać z tego w następujący sposób:

foo :: MaybeT (WriterT [String] IO) Int
foo = do
  tell ["hello"]
  -- kod -- 

zamiast

foo :: MaybeT (WriterT [String] IO) Int
foo = do
  lift $ tell ["hello"]
  -- kod --

Kod w ten sposób staje się bardziej przejrzysty, niż klasyczny kod z operacją lift.

Oczywiście, możemy dorzucić własną klasę typów:

class (Monad m) => MonadMaybe m where
  -- | Indicates that there's no value returned.
  nothing :: m a
  
instance (Monad m) => MonadMaybe (MaybeT m) where
  nothing = MaybeT $ return Nothing
  
instance (MonadMaybe m) => MonadWriter w (WriterT w m) where
  nothing = lift nothing
  
-- i tak dalej...

która będzie spełniała podobną rolę co MonadWriter. W ten sposób możemy uzyskać bezbolesną możliwość nakładania na siebie transformatorów monad w dowolnej kolejności, bez używania lift, by móc uzyskać pożądane połączenie efektów ubocznych.

Nie wszystko złoto co się świeci

Mimo tego wspaniałego pomysłu, transformatory monad są bardzo niewydajne, kiedy są połączone ze sobą. Głównym problemem jest tutaj głębokość uzyskanego stosu monad, z którym rośnie czas wykonywania operacji, w szczególności bind.

Jednakże jedną z możliwości usprawnienia czasu działania pożądanego stosu monad jest użycie już gotowych stosów monad jak Control.Monad.RWS (paczka mtl i transformers), bądź... napisanie takiej monady samemu (tak wygląda na przykład implementacja GHC, która jest naprawdę szybka, jeśli chodzi o czasy kompilacji).