Eugene Kirpichov (antilamer) wrote,

Об комонады

Я решил ознакомиться с комонадами и, потратив пока всего несколько часов, пришёл к следующим выводам.

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

Монады абстрагируют эффект, комонады абстрагируют контекст.

Чтобы понять связь между монадами и комонадами, проще смотреть не на "m a" и "c a", а на стрелки Клейсли:
Стрелка a -> m b - "имея чистый аргумент a, производим волшебное b" (имея строку password, функция authenticate волшебно - т.е. асинхронно - производит токен)
Ко-стрелка c a -> b - "имея волшебное a, производим чистое b" (имея область пикселей вокруг текущего, производим значение пикселя с фильтром).
class (Functor c) => Comonad c where
  extract :: c a -> a
  extend  :: c a -> c (c a)
  cobind  :: (c a -> b) -> c a -> c b

Введем метафоры (неочевидно, применимы ли они к любой комонаде, но ничего лучше я пока не придумал; наверное, это типа метафоры "монады-контейнеры"):

  • Значение вида "c a" называется "контекст". Например, окно в двумерном массиве вокруг какого-то пикселя.
  • Результат extract от контекста - это значение, находящееся "в фокусе" контекста. Пиксель, вокруг которого окно.
  • Неявная область всех возможных фокусов, из которой берутся контексты - "вселенная". Сам двумерный массив.
  • Процедура вида "c a -> b" называется "фильтр" или "локальный фильтр". Например, фильтр blur по окну 3x3.
  • Процедура cobind называется "наложение фильтра".

Пример 1. Комонада Store

Двойственная к монаде State, но я их связи сам пока не понимаю – индекс + процедура доступа. Она же называется "Pointed Array".
data Store i a = Store { peek :: i -> a, index :: i } deriving (Functor)

instance Comonad (Store i) where
  extract    (Store peek index) = peek index

  -- просто перефокусируемся вокруг i!
  extend     (Store peek index) = Store (\i -> Store peek i) index

  -- строим контекст вокруг каждой точки i и применяем к нему фильтр f
  cobind f s@(Store peek index) = Store (\i -> f (Store peek i)) index -- (4)

extract возвращает фокус контекста.
extend делает очень интересную вещь. У нас была процедура peek, умевшая возвращать значение по произвольному индексу (peek i) - а мы из нее делаем процедуру peek, возвращающую по индексу контекст - (Store peek i) - как видите, тривиальным образом: просто "перефокусируя" контекст на этот индекс. Помедитируйте над этим и поймите, как соотносятся \i -> peek i и \i -> Store peek i.
Надеюсь, в результате медитации у вас получился один из законов комонад:
fmap extract . extend = id
То есть, исходная вселенная получается взятием значений в фокусах результата extend.
cobind применяет f как "локальный фильтр" - мы кагбэ фокусируемся на каждой возможной точке и применяем в ней f к окружающему ее контексту. Хороший пример - фильтр blur отсюда. Т.е. - 1. формируем контекст вокруг каждой точки i (Store peek i) и 2. применяем к нему f. Шаг 1 - это как раз то, что умеет делать extend!

Отметим следующие соотношения:

  • cobind f = fmap f . extend
    Это очевидным образом следует из предыдущего пояснения к cobind.
  • extend = cobind id
    Это тоже очевидно: extend должен построить нам вселенную контекстов вокруг всех возможных точек; это эквивалентно применению локального фильтра, возвращающего сам контекст.
Кстати, интересно, что так же тривиально выражается join через bind: join = bind id.

Пример 2. Комонада Band

Band (лента) - это простейший zipper над одномерным списком.
data Band a = Band { left :: [a], focus :: a, right :: [a] } 
              deriving (Functor)

goLeft  (Band ls a (r:rs)) = Band (a:ls) r rs
goRight (Band (l:ls) a rs) = Band ls l (a:rs)

instance Comonad Band where
  extract = focus
  extend b = Band (tail $ iterate goLeft b) b (tail $ iterate goRight b)
  cobind f b = fmap f (extend b)
  -- Alternatively:
  -- cobind f b@(Band l a r) = Band (map f $ tail $ iterate goLeft b)
  --                                (f b)
  --                                (map f $ tail $ iterate goRight b)

extract достает значение "в фокусе".
extend строит вселенную всех возможных контекстов - в данном случае "ленту лент", у которой в фокусе текущая лента, влево идут ее возможные сдвиги влево, а вправо - сдвиги вправо (и снова обратите внимание, как это соотносится с исходной лентой - исходная лента состоит из значений в фокусах результатов extend).
cobind гораздо проще реализовать через extend, чем непосредственно. Более того, реализовать его непосредственно у меня не получилось, пока я не понял соотношение между cobind и extend.

Похожий пример, с "лентой" в одну сторону - комонада Stream, описанная в этом посте Конала Эллиотта. Хороший пост, кстати; прочитайте, может, поможет достроить интуицию. Правда, он использует термин extend там где у меня cobind.

Пример 3. Комонада деревьев с атрибутами.

data Tree e a = Leaf { attr :: a, value :: e }
              | Fork { attr :: a, left :: Tree e a, right :: Tree e a }
              deriving (Functor)

Деревья со значениями типа "e" в листьях и с атрибутами типа "a", приписанными к каждому узлу.
Соответственно, Tree e - тип "дерево с e в листьях и произвольными приписанными атрибутами".
instance Comonad (Tree e) where
  extract = attr

  extend t@(Leaf a e)   = Leaf t e
  extend t@(Fork a l r) = Fork t (extend l) (extend r)

  cobind f t@(Leaf a e)   = Leaf (f t) e
  cobind f t@(Fork a l r) = Fork (f t) (cobind f l) (cobind f r)
  -- Alternatively:
  -- cobind f = fmap f . extend

extract достает значение "в фокусе" - т.е. атрибут, приписанный всему дереву.
extend строит "вселенную контекстов" - аннотирует каждое дерево самим собой.
cobind применяет фильтр f к поддереву в каждой точке дерева. Разумеется, это эквивалентно cobind f = fmap f . extend.

Пример 4. Комонада сдвига координат

Это комонада "функций над аддитивным аргументом" или "графиков над двигающейся системой координат". Зачем она нужна, мне пока непонятно, но по крайней мере она сильно отличается от предыдущих и потому полезна для понимания комонад в целом.

data Relative w a = Relative { atCoord :: w -> a } deriving (Functor)

instance (Monoid w) => Comonad (Relative w) where
  extract  (Relative run) = run mempty
  extend   (Relative run) = Relative $ \w1 ->    Relative $ \w2 -> run (mappend w1 w2)
  cobind f (Relative run) = Relative $ \w1 -> f (Relative $ \w2 -> run (mappend w1 w2))


extract применяет функцию к нулю ("фокусом" контекста/графика считается то, что находится у него в нуле)
extend строит вселенную контекстов: в каждой точке w1 этой вселенной находится контекст, чья система координат сдвинута на w1.
cobind применяет локальный фильтр к каждой точке системы координат, как если бы она была нулем.

Наверное, это в каком-то смысле обобщение комонады Band или Pointed array на произвольный (не целочисленный или вообще не числовой) индекс.

Вот пример с дифференцированием, отсюда (отличный туториал про комонады с несколькими примерами, вводящий удобную codo-нотацию, которая еще больше помогает понять комонады и пользоваться ими).
-- на самом деле так не скомпилится, нужен Sum Double, но это фигня
differentiate :: Relative Double Double -> Double
differentiate (Relative f) = (f 0.01 - f 0) / 0.01

f = Relative sin
df = cobind differentiate f

Еще немного ссылок:

http://fmapfixreturn.wordpress.com/2008/07/09/comonads-in-everyday-life/ - треш и угар про рендеринг иерархических меню в html при помощи комонад и зипперов. Не осилил :(
http://www.cl.cam.ac.uk/~tp322/talks/coeffects-talk.pdf комонады и коэффекты (с помощью tagged comonads).


TODO:
1. Понять, существуют ли функции, двойственные liftM*, mapM, sequence и т.п.
2. Разобрать комонаду Cont (@ekmett сказал, что она mother of all comonads тоже)
3. Побольше примеров, что ли
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded  

  • 29 comments