Какие мотивирующие примеры для Cofree CoMonad в Haskell?

Давайте просто повторим определение типа данных Cofree.

data Cofree f a = a :< f (Cofree f a)

Этого как минимум достаточно, чтобы диагностировать проблему на примере. Когда ты написал

1 :< [2, 3]

вы сделали небольшую ошибку, о которой сообщается скорее более тонко, чем полезно. Здесь f = [] и a что-то числовое, потому что 1 :: a. Соответственно вам нужно

[2, 3] :: [Cofree [] a]

и, следовательно

2 :: Cofree [] a

что может быть в порядке, если Cofree [] a также и экземпляр Num. Таким образом, ваше определение получает ограничение, которое вряд ли будет удовлетворено, и действительно, когда вы используете свое значение, попытка удовлетворить ограничение терпит неудачу.

Попробуйте еще раз с

1 :< [2 :< [], 3 :< []]

и тебе должно повезти.

Теперь давайте посмотрим, что у нас есть. Начните с простого. Что такое Cofree f ()? Что, в частности, такое Cofree [] ()? Последний изоморфен фиксированной точке []: древовидные структуры, в которых каждый узел представляет собой список поддеревьев, также известных как «немаркированные розовые деревья». Например.,

() :< [  () :< [  () :< []
               ,  () :< []
               ]
      ,  () :< []
      ]

Точно так же Cofree Maybe () является более или менее фиксированной точкой Maybe: копией натуральных чисел, потому что Maybe дает нам либо ноль, либо одну позицию, в которую можно вставить поддерево.

zero :: Cofree Maybe ()
zero = () :< Nothing
succ :: Cofree Maybe () -> Cofree Maybe ()
succ n = () :< Just n

Важным тривиальным случаем является Cofree (Const y) (), который является копией y. Функтор Const y не дает нет позиций для поддеревьев.

pack :: y -> Cofree (Const y) ()
pack y = () :< Const y

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

data Cofree nodeOf label = label :< nodeOf (Cofree nodeOf label)

Когда мы маркируем пример (Const y), мы получаем пары

pair :: x -> y -> Cofree (Const y) x
pair x y = x :< Const y

Когда мы присоединяем метки к узлам наших чисел, мы получаем непустые списки

one :: x -> Cofree Maybe x
one = x :< Nothing
cons :: x -> Cofree Maybe x -> Cofree Maybe x
cons x xs = x :< Just xs

А для списков мы получаем помеченные розовые деревья.

0 :< [  1 :< [  3 :< []
             ,  4 :< []
             ]
     ,  2 :< []
     ]

Эти структуры всегда «непусты», потому что существует по крайней мере верхний узел, даже если у него нет дочерних элементов, и этот узел всегда будет иметь метку. Операция extract дает вам метку верхнего узла.

extract :: Cofree f a -> a
extract (a :< _) = a

То есть extract отбрасывает контекст верхней метки.

Теперь операция duplicate украшает каждую метку собственным контекстом.

duplicate :: Cofree f a -> Cofree f (Cofree f a)
duplicate a :< fca = (a :< fca) :< fmap duplicate fca  -- f's fmap

Мы можем получить экземпляр Functor для Cofree f, посетив все дерево.

fmap :: (a -> b) -> Cofree f a -> Cofree f b
fmap g (a :< fca) = g a :< fmap (fmap g) fca
    --                     ^^^^  ^^^^
    --                 f's fmap  ||||
    --                           (Cofree f)'s fmap, used recursively

Нетрудно это увидеть

fmap extract . duplicate = id

поскольку duplicate украшает каждый узел своим контекстом, тогда fmap extract отбрасывает украшение.

Обратите внимание, что fmap получает доступ только к меткам ввода для вычисления меток вывода. Предположим, мы хотим вычислить выходные метки в зависимости от каждой входной метки в ее контексте? Например, для немаркированного дерева мы можем захотеть пометить каждый узел размером всего его поддерева. Благодаря экземпляру Foldable для Cofree f мы должны иметь возможность подсчитывать узлы с помощью.

length :: Foldable f => Cofree f a -> Int

Так что это означает

fmap length . duplicate :: Cofree f a -> Cofree f Int

Ключевая идея комонад заключается в том, что они захватывают «вещи с некоторым контекстом» и позволяют вам везде применять контекстно-зависимые карты.

extend :: Comonad c => (c a -> b) -> c a -> c b
extend f = fmap f       -- context-dependent map everywhere
           .            -- after
           duplicate    -- decorating everything with its context

Более прямое определение extend избавит вас от необходимости дублирования (хотя это означает только совместное использование).

extend :: (Cofree f a -> b) -> Cofree f a -> Cofree f b
extend g ca@(_ :< fca) = g ca :< fmap (extend g) fca

И вы можете вернуть duplicate, взяв

duplicate = extend id -- the output label is the input label in its context

Более того, если вы выберете extract для каждой метки в контексте, вы просто вернете каждую метку туда, откуда она пришла:

extend extract = id

Эти «операции над метками в контексте» называются «совместными стрелками Клейсли».

g :: c a -> b

и работа extend состоит в том, чтобы интерпретировать стрелку со-Клейсли как функцию на целых структурах. Операция extract представляет собой тождественную стрелку Клейсли и интерпретируется extend как функция тождества. Конечно, есть со-композиция Клейсли

(=<=) :: Comonad c => (c s -> t) -> (c r -> s) -> (c r -> t)
(g =<= h) = g . extend h

а законы комонады гарантируют, что =<= является ассоциативным и поглощает extract, давая нам категорию ко-Клейсли. Более того, у нас есть

extend (g =<= h)  =  extend g . extend h

так что extend является функтором (в категориальном смысле) из категории ко-Клейсли в множества-и-функции. Эти законы нетрудно проверить для Cofree, так как они следуют из Functor законов для формы узла.

Теперь, один полезный способ увидеть структуру в cofree comonad - это своего рода "игровой сервер". Структура

a :< fca

представляет состояние игры. Ход в игре состоит либо из «остановки», и в этом случае вы получаете a, либо из «продолжения», выбирая поддерево fca. Например, рассмотрим

Cofree ((->) move) prize

Клиент для этого сервера должен либо остановиться, либо продолжить работу, указав move: это список из moves. Игра проводится следующим образом:

play :: [move] -> Cofree ((->) move) prize -> prize
play []       (prize :< _) = prize
play (m : ms) (_     :< f) = play ms (f m)

Возможно, move — это Char, а prize — результат разбора последовательности символов.

Если вы внимательно посмотрите, то увидите, что [move] — это версия Free ((,) move) (). Бесплатные монады представляют клиентские стратегии. Функтор ((,) move) представляет собой командный интерфейс только с командой «отправить move». Функтор ((->) move) представляет собой соответствующую структуру «ответить на отправку move».

Некоторые функторы можно рассматривать как захват командного интерфейса; свободная монада для такого функтора представляет программы, выполняющие команды; у функтора будет «двойник», который представляет, как реагировать на команды; сосвободная комонада двойного числа — это общее понятие среды, в которой могут выполняться программы, выполняющие команды, с меткой, говорящей, что делать, если программа останавливается и возвращает значение, и подструктурами, говорящими, как продолжить выполнение программы, если он выдает команду.

Например,

data Comms x = Send Char x | Receive (Char -> x)

описывает, что разрешено отправлять или получать символы. Его двойственность

data Responder x = Resp {ifSend :: Char -> x, ifReceive :: (Char, x)}

В качестве упражнения посмотрите, сможете ли вы реализовать взаимодействие

chatter :: Free Comms x -> Cofree Responder y -> (x, y)