Монада Identity или почему Haskell - самый лучший императивный язык программирования

Введение⌗

Предположим, что у нас есть целая библиотека архи-полезных функций:

timesTwo :: Int -> Int
timesTwo = (* 2)

timesTen :: Int -> Int
timesTen = (* 5) . timesTwo

isBig :: Int -> Bool
isBig = (>= 100)

countChars :: String -> Int
countChars = length

Мы составили (популярную) компьютерную программу на базе этой библиотеки (точка . – операция композиции функций):

program = isBig . timesTen . countChars

Программа принимает на вход строку, а выдаёт значение “истина/ложь”. Пользователи пользуются ею для решения своих задач:

> program  "Hello?"
False
> program  "This is big"
True

Встаёт задача добавления разнообразной отладочной информации в каждую из функций нашей библиотеки. Данную информацию нужно собирать на протяжении времени работы всей программы.

Императивные программисты в похожей ситуации на своём языке, вероятно, начнут с грязного хака вроде некоторой глобальной переменной-журнала, в котором по ходу выполнения программы накапливается отладочная информация из всех функций (каждая функция добавляет инфу в глобальный массив и т.п.). Глобальные переменные? Это плохой тон.

Подобные подходы ведут к плохой архитектуре ПО, проблемам с многопоточностью и дополнительным неприятностям (в частности, затратам на поддержку кода) в будущем.

В функциональном программировании есть штука существенно мощнее, чем императивные языки – монада.

Первая попытка⌗

Вместо использования глобальных переменных и прочих сайд-эффектов, лучше поразмыслить, какие же нововведения требуется добавить в программу наболее абстрактном уровне. Итак, в дополнение к уже существующему функционалу нам требуется:

1. Снабдить каждую функцию специфической отладочной информацией (руками или автоматически).
2. Реализовывать эту информацию во время выполнения (вызова) функции и
3. Последовательно накапливать её до окончания выполнения всей программы.

Самая поверхностная идея довольно проста: использовать не просто a, но особый тип (String, a), т.е. обыкновенную пару для хранения результатов вычислений. Далее, просто переопределить композицию функциональных блоков программы таким образом, чтобы вторые элементы пары (наша дебаг-строка) склеивались.

Есть особый контекст, есть специальные правила композиции (связывания) таких контекстов… Нам нужна монада! Вместе с реализацией тайпкласса Monad мы получим единый интерфейс монадических комбинаторов для комфортной работы с нашим контекстом.

Опишем монадический тип, моделирующий такие вычисления. Для тайпкласса Monad наш контекст должен быть Functor и Applicative. На самом деле, такие реализации уже есть в base:

newtype FancyResult a = FancyResult { runFancy :: (String, a) }
-- просто короткий синоним
type FR a = FancyResult a

instance Functor FancyResult where
  fmap f (FancyResult (str, a)) = FancyResult (str, f a)

instance Applicative FancyResult where
  pure a = FancyResult ("", a)
  FancyResult (str1, rf) <*> FancyResult (str2, r) = FancyResult (str1 ++ str2, rf r)

instance Monad FancyResult where
  return = pure
  FancyResult (str, a) >>= mf = FancyResult (str ++ str', b)
    where FancyResult (str', b) = mf a

Вот и всё. Теперь напишем функцию добавления дебаг-строчки к контексту (т.е. скливание с тем, что есть до сих пор) и модифицируем собственно функции нашей архиважной библиотеки:

-- добавление дебага в буффер
addDebug :: String -> a -> FR a
addDebug str a = FancyResult (str ++ " ", a)


timesTwo' :: Int -> FR Int
timesTwo' x = do
  addDebug "timesTwo" ()

  return (x * 2)

timesTen' :: Int -> FR Int
timesTen' x = do
  addDebug "timesTen" ()

  n <- timesTwo' x
  return (n * 5)

isBig' :: Int -> FR Bool
isBig' x = do
  addDebug "isBig" ()

  return (x >= 100)

countChars' :: String -> FR Int
countChars' s = do
  addDebug "countChars" ()

  return (length s)

program' s = isBig' =<< timesTen' =<< countChars' s

Всё работает. Первый элемент пары - накопленный дебаг, второй - собственно результат вычисления.

> runFancy $ program' "Hello?"
("countChars, timesTen, timesTwo, isBig, ",False)
> runFancy $ program' "This is big"
("countChars, timesTen, timesTwo, isBig, ",True)

В данном случае мы модифицируем каждую функцию библиотеки (потому что у нас требование: вставить соответствующий дебаг в каждую функцию). Вообще же, совершенно не обязательно модифицировать функции библиотеки: мы можем “поднять” и использовать в монаде FancyResult все наши чистые функции из Введения, а дебаг вставлять уровнем выше:

program'' :: String -> FancyResult Bool
program'' s = do
  addDebug "counting characters... " ()
  cn <- return $ countChars s

  addDebug "multiplying... " ()
  n <- return $ timesTen cn

  addDebug "comparing... " ()
  return $ isBig n

Вот, собственно, и вся модификация кода программы. В любом случае, мы на пути к хорошей архитектуре ПО.

Небольшое отступление: монада Identity⌗

Напишем крутую монаду, которая ничего не делает (то есть никак не действует на содержимое контекста):

import Data.Coerce

newtype Transparent a = Transparent { runTransparent :: a }

instance Functor Transparent where
  -- coerce :: Coercible a b => a -> b, очень хорош для тривиальных "обёрток" типа newtype выше
  fmap f = coerce f

instance Applicative Transparent where
  pure = Transparent
  (<*>) tf = coerce tf

instance Monad Transparent where
  return = pure
  m >>= k = k (runTransparent m)

Данная монада не такая полезная, как монада FancyResult выше. Операция связывания – просто обычная композиция функций, без всяких примочек. Тем не менее, теперь мы можем использовать синтаксис do-нотации, похожий на то, что так привычно императивным программистам:

prog :: Int -> Transparent Int
prog x = do
  a <- return 1
  b <- return 2
  c <- return $ a + b

  return $ product [a, b, c, x]

Эта монада очень важна и уже определена подобным образом в Data.Functor.Identity.

type Identity = Transparent
runIdentity = runTransparent

Тождественная монада пригодится нам чуть позже в трансформерах монад.

Мощь абстракции⌗

Нетрудно заметить, что наша первая попытка с монадой FancyResult, хоть и идёт в правильном направлении, но всё же недостаточно общая.

Моноид⌗

Заметим, что использование String (т.е. [Char]) для накопления результата – не самое универсальное решение. Вместо этого для хранения отладочной информации, вообще говоря, подойдёт абсолютно любой моноид (структура с ассоциативной бинарной операцией и единицей относительно неё). На место спискам символов в будущем может придти, например, база данных или сетевой буффер, поэтому лучше обобщить, выразив лишь саму идею накопления-склеивания.

Параметризуем FancyResult некоторым моноидом:

newtype FancyResult w a = FancyResult { runFancy :: (w, a) }

instance Monoid w => Functor (FancyResult w) where
  fmap = fmap

instance Monoid w => Applicative (FancyResult w) where
  pure a = FancyResult (M.mempty, a)
  FancyResult (w1, rf) <*> FancyResult (w2, r) = FancyResult (w1 `M.mappend` w2, rf r)

instance Monoid w => Monad (FancyResult w) where
  return = pure
  FancyResult (w1, a) >>= mf = FancyResult (w1 `M.mappend` w2, b)
    where FancyResult (w2, b) = mf a

-- на данный момент пусть моноидом будут списки символов
type FR a = FancyResult String a

Тождественная монада и WriterT⌗

В чём на самом деле отличие “навороченной” монады FancyResult от тождественной монады? В упаковке и конкатенации соседних элементов моноида w при монадическом связывании выражений. При этом, FancyResult w теперь уже ничего не знает об этой конкатенации, как раньше с (++), и сейчас полагается только на абстрактный интерфейс Monoid: функции mempty и mappend.

Оказывается, именно эту идею и представляет трансформер монад WriterT w m:

class (Monoid w, Monad m) => MonadWriter w m

Тайпкласс замечательно абстрагирует и разделяет данный класс задач на три элемента:

1. Моноид для хранения/накопления результата (тип w).
2. “Внешняя” монада, выполняющая последовательную конкатенацию в моноиде (собственно, для этого и нужен сам WriterT)
3. “Внутренняя” монада, которая и представляет логику, т.е. контекст настоящей задачи (тип m)

Поскольку FancyResult на самом деле не несёт никакой иной логической нагрузки, то внутренняя монада в нашем случае будет просто тождественной монадой Identity. Кстати, так устроен обычный Writer:

type Writer w = WriterT w Identity

WriterT String Identity a⌗

Итак, мы можем смело удалить тип FancyResult и весь код, который с ним связан, и оставить только FR a:

type FR a  = WriterT String Identity a

Вместо конкретной постройки FancyResult, теперь мы используем writer из интерфейса к MonadWriter для “встраивания” дебаг-строки в результат вычисления:

addDebug :: String -> a -> FR a
addDebug str a = writer (a, str ++ " ")

Наши “программы”program' и program'' и сопутствующие библиотечные функции остаются без изменения:

> runIdentity . runWriterT $ program' "Hello?"
(False,"countChars timesTen timesTwo isBig ")
> runIdentity . runWriterT $ program' "Haskell is cool."
(True,"countChars timesTen timesTwo isBig ")