Комонада, она как монада, только комонада
Я подразумеваю, что читатель знает Haskell, по крайней мере, до монад.
Monad — это класс типов, позволяющий (неформально говоря) из функций, которые возвращают что то вроде MyMonad КакойтоТип выполнять некие функции, взаимодействующие с монадой. Функции, использующие монады, нужно связывать между собой специальными функциями (>>), (>>=), (=<<).
Так вот, Comonad — это тоже класс типов, который позволяет функциям взаимодействовать с эффектами комонады, только у этих функций комонада указывается не в возвращаемом типе, а в аргументе. Ни что не мешает указывать одинаковые или разные комонады в каждом аргументе, да ещё и монаду в возвращаемом значении.
Для связки комонадных выражений тоже используются специальные функции — (=>>), (<<=), (=>=), (=<=) со своими нюансами.
В общем, схожесть между монадами и комонадами есть, и их применение можно сочетать.
Для того, что бы стало понятно решим практический пример, напишем мини библиотечку для расчёта и отображения гистограммы.
Хотя задача не очень масштабна, мы разделим её на части:
- основная часть (двигатель гистограммы), т.е. расчёт;
- Реализация хранения и накопления данных гистограммы;
- отображение гистограммы (вывод на терминал).
Двигатель гистограммы
И так, расчёт. В нём не будет ни монад, ни комонад, однако он важен. В результате предварительного расчёта будет формироваться функция типа
type CalcPos x = x -> Maybe Int
по заданному исходному значению определяющая номер кармана гистограммы, в который следует добавить единицу (как рассчитывается гистограмма, и что, это, собственно такое легко навикипедить). Если исходное число выходит за заданный диапазон, функцию вернёт Nothing.
Весь результат предварительного расчёта по заданным исходным данным будет храниться в структуре
data HistoEngine x = HistoEngine { low :: x -- Нижняя граница гистограммы
, step :: x -- Шаг гистограммы
, size :: Int -- кол-во карманов гистограммы
, calcPos :: CalcPos x
}
Остальные поля записи не нужны функции calcPos, все необходимые ей данные она получит при создании через замыкания, но остальные поля могут потребоваться в других случаях.
Функция mkHistoEngine — это то, с чего начинается построения гистограммы. За исходные данные принимаем нижнюю и верхнюю границы анализируемого диапазона и количество карманов гистограммы. Функция mkHistoEngine заполняет и возвращает HistoEngine, включая calcPos задаваемую лямбдой.
mkHistoEngine :: (Show x, Ord x, RealFrac x) => x -> x -> Int -> HistoEngine x
(определение функции тривиально и будет приведено ниже, в полном коде).
Исходя из принципа инкапсуляции (Gabriel Gonzalez, к примеру, полагает что комонады это объекты, так что не погнушаемся одним из принципов ООП). Можно было бы вынести весь вышеприведённый код в отдельный модуль, предоставив извне доступ к HistoEngine без её внутреннего содержания. Но тогда нам придётся предоставить функции для получения значений некоторых полей HistoEngine.
histoEngPosFn:: HistoEngine x -> CalcPos x
histoEngPosFn = calcPos
histoEngSize:: HistoEngine x -> Int
histoEngSize = size
В дельнейшем понадобится вывести шкалу гистограммы. Вместо того, что бы создать функции доступа ещё для пары полей целесообразно сформировать сразу значения шкалы.
gistoXList:: (RealFrac x, Enum x) => HistoEngine x -> [x]
gistoXList HistoEngine{..} = take size [low+ step*0.5,(low + step*1.5)..]
(я использовал расширение RecordWildCards, по этому {…}).
Однако, где же комонады? Пора переходить к ним.
Гистограмма как комонада
Комонада будет в примере выполнять роль связующего звена между расчётом, хранением и отображением. Тип её данных я сделал таким
data Histogram x a = Histogram (HistoEngine x -> a) (HistoEngine x) deriving Functor
Не всякий тип подходит для создания комонады. Не обязательно такой, как приведён выше: значение и функция от этого значения в произвольный тип. Но тип должен позволять выполнять с ним некоторую рекурсию. В данном случае, можно рекурсивно вызывать функцию HistoEngine x → a. В других случаях используют рекурсивные типы данных — списки, деревья.
И так, делаем тип Histogram комонадой
instance Comonad (Histogram x) where
extract (Histogram f x) = f x
duplicate (Histogram f x) = Histogram (Histogram f) x
Это всё.
Функция extract: w a → a (где w — комонада, буква w, принятое обозначение для комонад — m кверх ногами) соответствует в монаде return, но делает обратное действие, возвращает значение из комонады. В некоторых статьях её именовали coreturn (назвать её nruter, кажется, ещё, никто не додумался).
Эта функция далее будет использоваться напрямую. В отличии от функции duplicate: w a → w (w a), которая соответствует для монад join: (Monad m) => m (m a) → m a, только, опять, с противоположным смыслом. Join удаляет один слой монады, а duplicate дублирует слой комонады. Вызов её непосредственно далее не встретится, но duplicate вызывается внутри других функций пакета comonad, в частности, в extend: (w a → b) → w a → w b. Собственно, комонаду можно определить, как через extract, duplicate (и Functor), так и через extract, extend, смотря как удобнее.
И так, сама комонада готова. Переходим к следующему этапу.
В чём хранить
Будем хранить накапливаемые значения (ячейки или карманы гистограммы) в немутабельном векторе. Подключим
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
И запишем
type HistoCounter = VU.Vector Int
type Histo x = Histogram x HistoCounter
Пора написать функцию создающую исходную комонаду-гистограмму с пустыми ячейками.
mkHisto:: (Show x, Ord x, RealFrac x) => x -> x -> Int -> Histo x
mkHisto lo hi sz = Histogram (\e -> VU.replicate (histoEngSize e) 0)
$ mkHistoEngine lo hi sz
Всё просто. Описываем лямбда функцию выделяющую вектор заданного размера заполненный нулями и воспользуемся созданной ранее mkHistoEngine для создания HistoEngine. Параметры mkHisto просто передаются к mkHistoEngine.
Теперь напишем функцию накопления отсчётов в гистограмме.
histoAdd:: x -> Histo x -> HistoCounter
histoAdd x h@(Histogram _ e) = case histoEngPosFn e x of
Just i -> VU.modify (\v -> VUM.modify v (+1) i) (extract h)
Nothing -> extract h
Напомню, что если у монадных функций, монада указывается в типе результата функции, то у комонадных она в аргументе. С помощью histoEngPosFn получаем созданную в mkHistoEngine функцию типа CalcPos. В зависимости от её результата увеличиваем на единицу соотвествующую ячейку вектора или возвращаем вектор неизменным. Сам же вектор получаем выражением extract h.
Для того, что бы не привязывать алгоритм отображения гистограммы к её хранению и накоплению, примем, что для отображения она должна быть представлена списком. Это допустимо, т. к. для отображения список будет обрабатываться меньшее число раз и всегда последовательно. (Способ хранения гистограммы при накоплении можно изменить, например, на более эффективный мутабельный вектор, но это не должно привести к изменениям в функциях отображения гистограммы).
И так, комонадная функция преобразования представления данных гистограммы из вектора в список. Она тоже тривиальна.
histoToList:: Histo x -> [Int]
histoToList = VU.toList . extract
Отображение результата в терминале
Я использовал вывод гистограммы горизонтально, когда её столбики лежат на боку.
Определение функции приведено ниже, в полном коде. Обратите внимание на то, что функция использует и комонаду (в аргументе, естественно), и монаду (естественно, в выходном значении).
histoHorizPrint:: (RealFloat x, Enum x) => Int -> Int -> Histogram x [Int] -> IO ()
Её аргументы: ширина поля вывода, ширина поля для отображения значений шкалы исходной величины и, естественно, комонада. Теперь с данными в виде [Int] вместо VU.Vector Int.
Собираем всё вместе
В качестве тестовых данных просто сформируем последовательность синусоидальных отсчётов
map sin [0,0.01 .. 314.15]
Гистограмму будем накапливать в обычном списковом foldl.
foldl f (mkHisto (-1::Double) 1 20) (map sin [0,0.01 .. 314.16])
(исходные параметры гистограммы — диапазон от -1 до +1, 20 карманов).
Но что из себя будет представлять функция f, которая, для foldl имеет вид (b → a → b), где, в данном случае, b — комонада, а — очередной, накапливаемый отсчёт. Оказывается, ничего сложного. Ведь мы уже написали функцию histoAdd. Так же, как для монад, понадобятся вспомогательные функции похожие на стрелки.
И так, весь тест в функции main.
main :: IO ()
main = histoHorizPrint 65 5 $ histoToList <<=
foldl (\b a -> b =>> histoAdd a) (mkHisto (-1::Double) 1 20)
(map sin [0,0.01 .. 314.16])
{-# LANGUAGE DeriveFunctor, RecordWildCards #-}
import Control.Comonad
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Numeric
type CalcPos x = x -> Maybe Int
data HistoEngine x = HistoEngine { low :: x -- Нижняя граница гистограммы
, step :: x -- Шаг гистограммы
, size :: Int -- кол-во карманов гистограммы
, calcPos :: CalcPos x
}
mkHistoEngine :: (Show x, Ord x, RealFrac x) => x -> x -> Int
-> HistoEngine x
mkHistoEngine lo hi sz
| sz < 2 = error "mkHistoEngine : histogram size must be >1"
| lo>=hi = error $ "mkHistoEngine : illegal diapazone "
++ show lo ++ " - " ++ show hi
| otherwise = let stp = (hi-lo) / fromIntegral sz in
HistoEngine lo stp sz
(\x -> let pos = truncate $ (x - lo) / stp in
if pos<0 || pos >= sz then Nothing
else Just pos)
histoEngPosFn:: HistoEngine x -> CalcPos x
histoEngPosFn = calcPos
histoEngSize:: HistoEngine x -> Int
histoEngSize = size
gistoXList:: (RealFrac x, Enum x) => HistoEngine x -> [x]
gistoXList HistoEngine{..} = take size [low+ step*0.5,(low + step*1.5)..]
------------- Гистограмма как комонада ------------------------
data Histogram x a = Histogram (HistoEngine x -> a) (HistoEngine x)
deriving Functor
instance Comonad (Histogram x) where
extract (Histogram f x) = f x
duplicate (Histogram f x) = Histogram (Histogram f) x
----------- Ф-ии для обработки результата и отображения
histoHorizPrint:: (RealFloat x, Enum x) =>
Int -> Int -> Histogram x [Int] -> IO ()
histoHorizPrint width numWidth h@(Histogram _ e) =
let l = extract h
mx = maximum l
width' = width - numWidth - 1
k = fromIntegral width' / fromIntegral mx ::Double
kPercent = (100 :: Double) / fromIntegral (sum l)
showF w prec v = let s = showFFloat (Just prec) v "" in
replicate (w - length s) ' ' ++ s
in mapM_ (\(x,y)-> do
putStr $ showF numWidth 2 x
putStr " "
let w = truncate $ fromIntegral y * k
putStr $ replicate w 'X'
putStr $ replicate (width'-w+2) ' '
putStrLn $ showFFloat (Just 2)
(fromIntegral y * kPercent) " %")
$ zip (gistoXList e) l
------------- Релизация хранения карманов гистограммы в векторе ----
type HistoCounter = VU.Vector Int
type Histo x = Histogram x HistoCounter
mkHisto:: (Show x, Ord x, RealFrac x) => x -> x -> Int -> Histo x
mkHisto lo hi sz = Histogram (\e -> VU.replicate (histoEngSize e) 0)
$ mkHistoEngine lo hi sz
histoAdd:: x -> Histo x -> HistoCounter
histoAdd x h@(Histogram _ e) = case histoEngPosFn e x of
Just i -> VU.modify (\v -> VUM.modify v (+1) i) (extract h)
Nothing -> extract h
histoToList:: Histo x -> [Int]
histoToList = VU.toList . extract
------------- Тест
main :: IO ()
main = histoHorizPrint 65 5 $ histoToList <<=
foldl (\b a -> b =>> histoAdd a) (mkHisto (-1::Double) 1 20)
(map sin [0,0.01 .. 314.16])
Комонадные трансформеры
Так же, как и для монад, для комонад существуют трансформеры (правда их очень мало, но кто нам мешает писать свои). То есть комонады могут быть вложенными.
Предположим, мы хотим установить ширину поля для вывода чисел в самом начале, когда только создали пустую гистограмму.
Подключим ещё один модуль
import Control.Comonad.Env
который реализует комонаду по смыслу соответствующую монаде Reader.
Пример в функции main теперь будет выглядеть так
(\h-> histoHorizPrint 65 (ask h) (lower h))
$ (histoToList . lower) <<=
foldl (\b a -> b =>> (histoAdd a . lower))
(EnvT 5 (mkHisto (-1::Double) 1 20))
(map sin [0,0.01 .. 314.16])
С помощью (EnvT 5 (…)) мы создаём ещё один комонадный слой и сохраняем в нём значение 5 (желаемую ширину для полей чисел). Поскольку теперь комонадное выражение двухслойное, то, для применения наших функций, использующих комонаду Histogram, требуется вспомогательная функция lower, подобно тому, как в монадных трансформерах для перехода к предыдущему слою используют lift.
Так же обратите внимание на извлечение значения — (ask h). Ну чем не Reader!
Последний пример можно записать и по другому, разобрав в конце два слоя комонад на пару (значение, внутренняя комонада) c помощью функции runEnvT, название которой жирно намекает на runReaderT используемую с ReaderT.
(\(nw,h)-> histoHorizPrint 65 nw h) $ runEnvT
$ (histoToList . lower) <<=
foldl (\b a -> b =>> (histoAdd a . lower))
(EnvT 5 (mkHisto (-1::Double) 1 20))
(map sin [0,0.01 .. 314.16])
Успехов в комонадостроении!
